CSC 311: Data Structures (Fall 2007)

Sample solution to Assignment 2: Chapters 5 and 6

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

Solution:

Algorithm: cleanStack(Stack s)

Input: a stack s

Output: Empty stack s

Procedure:

        If s.isEmpty() return s;

        s.pop();

        cleanStack(s);

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?

Solution:

Use two queues Q1 and Q2, where Q1 stores elements and Q2 is used for auxiliary

boolean isEmpty() { Q1.isEmpty()};

int size() { Q1.size()};

void push(Object o) { Q1.enqueue(o) };

Object pop() {

            While (!Q1.isEmpty())

                    Q2.enqueue( Q1.dequeue()) ;

Object o = Q2.dequeue();

While (!Q2.isEmpty())

        Q1.enqueue( Q2.dequeue() );

            Return o;

}

Object top(): similar to pop()

isEmpty, size, push: O(1)

pop, top: O(n)

To implement the Stack ADT using two queues, Q1 and Q2, we can simply enqueue elements into Q1 whenever a push call is made. This takes O(1) time to complete. For pop calls, we can dequeue all elements of Q1 and enqueue them into Q2 except for the last element which we set aside in a temp variable. We then return the elements to Q1 by dequeuing from Q2 and enqueuing into Q1. The last element that we set aside earlier is then returned as the result of the pop. Thus, performing a pop takes O(n) time.

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?

Solution: Alice should put on an even integer in S and all the other 99 integers in T.

The chance that Bob picks S is 0.5, where Alice must win.

The chance that Bob pocks T is also 0.5, where Alice wins at the chance of 49/99 (49 even integers out of 99 overall integers).

This gives her 0.5*(1+49/99) = 74/99 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).

Solution: Assume that header and trailer point to the first and the last node.

Algorithm: reverseDLL(DoublyLinkedList dll)

Input: A doubly linked list dll

Output: reversed dll

Procedure:

            DoublyLinkedNode pre=dll.header, cur=pre.next; nxt=cur.next;

            While (cur!=trailer) {

                    cur.previous=nxt;

                    cur.next=pre;

                    pre=cur;

                    cur=nxt;

                    nxt=nxt.next;

            }

            swap(dll.header, dll.trailer);

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.

Solution:

(i)                 For the first n push operations,

a.      total number of pushes is n

b.      at the 2¹, 2², 2^lognth pushes, need array copies, total copies: 2⁰+ 2¹+ 2²+ ...+ 2^logn =2^logn+1 -1 = 2n + 1

(ii)               For the second n pop operations,

a.      Total number of pops is n

b.      The array copies

• When the size is n/4, need copies of n/4, and the size is changed to n/2 --> n/2²

• When the size is n/2/4, need copies of n/2/4, and the size is changed to n/4 --> n/2³

• When the size is n/4/4, need copies of n/4/4, and the size is changed to n/4/2 --> n/2⁴

• ^...

• this will repeat at most logn times, so the total copies is n/2²+n/2³+…+n/2^long<n

Total number of operations is at most n+2n+1+n+n=5n+1, that is O(n).

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.

Solution:

Implement an iterator for a circularly linked list

o       Keep a current pointer

o       hasNext(): return true if current.next!=null

o       next(): ret = current; current=current.next; return ret

Implement an iterator for a circularly linked list

o       Keep a pointer (say first) point to the current node (whichever) when the iterator is constructed

o       Initialize a pointer (say current) point to the node pointed to by first

o       hasNext(): return true if current.next!=first, false otherwise

o       next(): ret = current; current=current.next; return ret