CS 61B Fall 1998 Final Exam Solutions

Problem 1:
b. 

          7                          9                              
        /   \                      /   \                           
       3     12                  3     12      OR         
      / \    / \     =>         / \    / \
     1   6  9   15             1   6  11  15
        / \    /                  /       /
       5  11  14                 5       14         
                               


          6
        /   \
       3     12
      / \    / \
     1   5  9   15                     
            \   /
            11 14


c.
Theta(n), Omega(n), or 0(n)

d. 
Wf Xg

e. 
insert() may cause the array to run out of space.

f.
Any sequence of operations that 
1) Ends with the right keys in the tree and
2) Ends with insert(2) or find(2) is correct

g.
Worse:  19 bytes
Only in the latter case can the memory formerly occupied by W objects be reused
for X objects.


Problem 2:
a. 
X 3 4 5 5 12 8 9 7

b.

       7
      / \
     5   9
    / \   \
   2   6   10
  / \
 1   3

c.
a b d c f g


E      --->A<--------D<---------
      |              ^          |
      |		     |          G	
      |		     |  	
     / 	             |  
    / 		     |
   /	             |
  B<--------C        F


Problem 3:
a. 
5 8 1 0 7 3 9 5
3 8 1 0 7 5 9 5 
3 0 1 8 7 5 9 5
3 0 1 5 7 5 9 8
0 3 1 5 7 5 9 8
0 1 3 5 7 5 9 8
0 1 3 5 7 5 8 9
0 1 3 5 5 7 8 9

b.
One portion might get all the keys, the other portion none.

c.
(i) Insertion sort: 2
(ii) Selection sort: k
(iii) Quicksort (array-based): k
(iv) Radix sort: p


Problem 5:
a.
Walk through both lists in same order as merge step in mergesort.
Write common elements to output list.
O(s + t) = O(max{s, t})

b.
For each item in T, check if it's in S (by binary search).
Write common items to output array.
O(t log s)

c.
For each item in SMALLER set, check if it's in larger set using hash
table. Write common item to output list & output hash table.
O(min{s, t})


Problem 6:
a. 
The nodes are stored on the stack.

b.
Two possible answers:
1. Put all red nodes (or green nodes, but not both) in the queue with a depth
   of zero. Mark them visited. Then continue running BFS as usual.
2. Augment the graph with an extra vertex u, which has edges to every red
   vertex (or every green vertex, but not both). Run BFS starting from u.


Problem 7:
a.
Possible answers:
1. Tree has extra field for minimum item. The end of every insert() or delete()
   calls the log-n version of findMin and stores the minimum item in the field.
2. Tree has extra field for minimum item. Update on insert() is
   obvious. delete() takes us to the lower left leaf if we delete the minimum,
   so we can just look up the new minimum.
3. Maintain pointer to leftmost leaf.

b.
- Lists are doubly-linked
- Objects have references to their locations in lists

c.
Lazy deletion list can grow very long, so find() is not O(log n).


Problem 8:

 public DSElement find() { 
   if (parent == null) {
     return this;
   }
   parent = parent.find();
   return parent;	
 }


 public void union(DSElement other) {
   DSElement thisRoot = this.find();
   DSElement otherRoot = other.find();
   if (thisRoot != otherRoot) {
     if (thisRoot.rank > otherRoot.rank) {
       otherRoot.parent = thisRoot;
     } else {
       thisRoot.parent = otherRoot;
       if (thisRoot.rank == otherRoot.rank) {
         otherRoot.rank++;
       }
     }
   }
 }