1. Write and simulate a recursive program to reverse a list.
2. You might enjoy finding an algorithm for the following generalization of the Towers of Hanoi problem. The disks are each labelled with a positive integer. A configuration of disks on a peg is "legal" if each disk's integer is no larger than the sum of the integers on all disks below it, or there are no disks below it. How can the disks be moved so that any legal original configuration of n disks on peg 1 ends up on peg 3, with all intermediate configurations being legal?
3. Write the permutation program so it treats the permutation as a data abstraction.
4. In order to use storage efficiently when n stacks are needed during the execution of a program, it may be desirable to implement all the stacks in one array as shown here for n= 4.
The Bi's and Ti's point to the bottoms and tops of the stacks, which grow to the right as indicated. Think of the total storage currently allocated to stack i as being from B(i) to B(i + 1). Stack i is actually using T(i) - B(i + 1) + 1 positions of the array. If B1 = 1, B2 = 10, B3 = 15, B4 = 25, B5 = size of the array = 35, T1 = 3, T2 = 12, T3 = 20, and T4 = 33, then the stacks are using 3, 3, 6, and 9 entries, respectively, while they are allocated 9, 5, 10, and 10 entries.
When an entry is to be inserted into a stack that is currently using all its allocated storage, the stack is said to have overflowed. Stack i overflows if Ti = B(i + 1) - 1. Write a function to manage the storage provided by the array. Whenever a stack overflows, the function is to be invoked. If there is any unused space in the array, then the stack with an unused but allocated position which is "closest" to the overflow stack is to give up one of its unused positions. This position is then used by the overflow stack to accommodate its entry. This function must be written to shift stacks around. If no unused space exists in the array, then the procedure should print an "out of stack storage" message.