R-4.8:
Describe the output of the following sequence of stack operations:
push(5), push(3), pop(), push(2), push(8), pop(), pop(), push(9),
push(1), pop(), push(7), push(6), pop(), pop(), push(4), pop(), pop().
5 5 3 5 5 2 5 2 8 5 2 5 5 9 5 9 1 5 9 5 9 7 5 9 7 6 5 9 7 5 9 5 9 4 5 9 5
R-4.11:
Describe the output of the following sequence of queue operations:
queue(5), enqueue(3), dequeue(), enqueue(2), enqueue(8), dequeue(),
dequeue(), enqueue(9), enqueue(1), dequeue(), enqueue(7), enqueue(6),
dequeue(), dequeue(), enqueue(4), dequeue(), dequeue().
5 5 3 3 3 2 3 2 8 2 8 8 8 9 8 9 1 9 1 9 1 7 9 1 7 6 1 7 6 7 6 7 6 4 6 4 4
C-3.16: Suppose each row of an n x n array A consists of 1's and 0's such that, in any row of A, all the 1's come before any of the 0's in that row. Assuming A is already in memory, describe a method running in O(n) time (not O(n2) time) for finding the row of A that contians the most 1's.
Start in the lower left corner of the array and follow this rule:
If there is a 1 to your right, store the row number and move right;
otherwise, move up.
Keep going until you reach the top of the array. The answer will be the last row number stored.
C-3.18: Suppose each row of an n x n array A consists of 1's and 0's such that, in any row i of A, all the 1's come before any of the 0's in that row. Suppose further that the number of 1's in row i is at least the number in row i+1, for i=0,1,...,n-2. Assuming A is already in memory, describe a method running in O(n) time (not O(n2) time) for counting the number of 1's in the array A.
Same as for the previous question, except that every time you move up you add the column index to an accumulator variable. The final value of this variable is the required sum.
C-4.7 (if time permits): In the Towers of Hanoi puzzle, we are given a platform with three pegs, a, b and c. One peg, a, has a stack of n disks, each larger than the next, so that the smallest is on the top and the largest is on the bottom. The puzzle is to move all the disks from peg a to peg c, moving one disk at a time, so that we never place a larger disk on top of a smaller one.
Describe a recursive algorithm for solving the
Towers of Hanoi problem for arbitrary n.
(Hint: Consider first the subproblem of moving all but the
nth disk from peg a to another peg,
using a third peg as "temporary storage").
First, use a recursive call to move the n-1 smaller disks
from the source peg to the auxiliary peg.
Then move the large disk from the source to the destination peg.
Finally, use another recursive call to move the smaller disks
from the auxiliary peg to the destination peg.
The complete program can be found in Hanoi.java
How many steps would it take to successfully move all n disks?
Let Tn denote the number of steps required to
move n disks.
Then T1=1, and
Tn=1+2 Tn-1, for n > 1.
From this we can deduce that T2=3, T3=7
and, in general, Tn=2n-1.
There are many Tower of Hanoi resources on the Web, including:
http://mathworld.wolfram.com/TowerofHanoi.html
http://www.cut-the-knot.org/recurrence/hanoi.shtml
http://hanoitower.mkolar.org/HTonWebE.html