COMP2011 Tutorial Exercises 4, Week 5

Stacks, Queues, Algorithms, Recursion

  1. 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().

  2. 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().

  3. 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.

  4. 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.

  5. 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?