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().
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().
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.
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.
C-4.7 (if time permits): In the Towers of Hanoi puzzle, we are given a platform with three pegs, a, b and c. On peg a there is 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 puzzle 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").
How many steps would it take to successfully move all n disks?