**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*(*n*^{2}) 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*(*n*^{2}) 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*n*th 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?