CSC 311: Data Structures (Fall 2007)

Assignment 2: Chapters 5 and 6

Due October 11, 2007

All questions are equally scored.

1. R-5.4 Give a recursive method for removing all the elements in a stack.

2. C-5.4 Describe how to implement the stack ADT using two queues. What is the running time of the push() and pop() methods in this case?

3. C-5.11 Alice has two queues, S and T, which can store integers. Bob gives Alice 50 odd integers and 50 even integers and insists that she stores all 100 integers in S and T. They then play a game where Bob picks S or T at random and then applies the round-robin scheduler, to the chosen queue a random number of times. If the number left out of the queue at the end of this game is odd, Bob wins. Otherwise, Alice wins. How can Alice allocate integers to queues to optimize her chances of winning? What is her chance of winning?

4. R-6.9 Describe a nonrecursive method for reversing a node list represented with a doubly linked list using a single pass through the list (you may use the internal node pointers).

5. C-6.3 Show that, using an extendable array that grows and shrinks as described in the previous exercise (grows by doubling the array size when array is full, while shrinks by half the array size when the number of elements is below the quarter of the array size), the following series of 2n operations takes O(n) time: (i) n push operations on an array list with initial capacity N =1; (ii) n pop (removal of the last element) operations.

6. C-6.14 Describe how to implement an iterator for a circularly linked list. Since hasNext() will always return true in this case, describe how to perform hasNewNext(), which returns true if and only if the next node in the list has not previously had its element returned by its iterator.