CS 61B Spring 2000 Final Exam Solutions


Problem 1:
b.


            3
          /  \
        3      4
       / \    / \
      5   6  4   8
     / \  / \
    5  9 8   7

c.
Omega(log n)

d.
Theta(1)

e. 
y is in x's left subtree.

f.
Theta(n) time, because of roving pointer.

g.
If data you're still using is deallocated, new data may be written over it. 

h. 
False


Problem 2:
a.

          9           OR                     9
         / \                               /  \
        2   10                            2    10
       / \                               / \
      1   6                             1   3
         / \                                 \
        3   7                                 7
             \                               / \
              8                             6   8



b. 

Yes.

          3                                  1               
         / \             	              \		 
        2   4           findElement(1)         2
       /     \          ------------->          \
      1       5					 3
						  \
						   4
						    \
 						     5


c.
    (log n)
k * -------  
    (log k)
or 

k log n 
 
(where log is base k)
   
 
problem 3:
a. 
7 4 2 8 1 0 6 3
4 7 2 8 1 0 6 3
4 7 2 8 0 1 6 3
4 7 2 8 0 1 3 6
2 4 7 8 0 1 3 6
0 1 2 3 4 6 7 8

mergesort

b.
7 4 2 8 1 0 6 3
0 4 2 8 1 7 6 3
0 1 2 8 4 7 6 3
0 1 2 3 4 7 6 8
0 1 2 3 4 6 7 8

selection sort

c.
7 4 2 8 1 0 6 3
4 2 8 0 6 7 1 3
4 8 0 1 2 6 7 3
8 0 1 2 3 4 6 7
0 1 2 3 4 6 7 8

radix sort

d.
7 4 2 8 1 0 6 3
4 7 2 8 1 0 6 3 
2 4 7 8 1 0 6 3
1 2 4 7 8 0 6 3
0 1 2 4 7 8 6 3
0 1 2 4 6 7 8 3
0 1 2 3 4 6 7 8

insertion sort

e.

-Do not rotate the list to find a pivot; or if you do, rotate it back to its
 original state.
-Do not remove pivot from list before partitioning.
-Partition into 3 lists: less than pivot, equal to pivot (including pivot),
 greater than pivot. Sort first & last recursively.


Problem 4:

|                  |
|  ____________    |
| |            |   |
| |	  ___  |<---------------------------------------\
| |value | 7 | |   |					|
| |      |___| |   |					|	
| |       ___  |   |					|
| |next  |_--+-+--------\				|
| |____________|   |    |				|
|                  |    | 				|
|  ____________    |    |				|
| |   	       |<-------/            ______________	|
| |       ___  |   |                |        ____  |	|
| |value | 3 | |   |                | value |_?__| |    |   
| |      |___| |   |		    |        ____  |    |       
| |       ___  |   |                | next  |    | |	|	
| |next  |   | |   |                |       |_---+-+----/
| |      |_--+-|------------------->|______________|
| |____________|   |   
|	    ^  ^   |
|           |  |   |                       HEAP
|-----------|--|---|
| main()    |  |   |
|      __   |  |   |
|   x | -+--/  |   |
|     |__|     |   |	
|      __      |   |
|   y | -+-----/   |
|     |__|         |
|__________________|         

      STACK 



Problem 5:
a. 

        2               5
      / | \            / \
     0  6  7          1   3
    /                    / \
   9                    4   8



b. 

find(4)
union(2, 5)
find(8)


Final: 

             -----2-------
            /   / | \  \   \
           0   6  7  5  3   8
           |        / \ 
           9       1   4
             

c.
Scan through array, find all children of ITEM. If ITEM is not root, make ITEM's
children point to its parent. If ITEM is a root, choose arbitrary child to be
new root; make other children point to it.

d.
One possibility:
Use a general sibling-based tree data structure, but make siblings be
doubly-linked so path compression is fast.

Another possibility:
Each set's root references a linked list of all the items in the set (which
does NOT need to be doubly linked). When sets are unioned, these lists are
concatenated. isolate() walks through the list to find all children of item
(and also removes item from the list).


Problem 6:
a. 
No. 
x is passed by value, cannot be changed.
Strings are immutable.

b.
Yes.
x may be a class variable (static) or object field accessible to foo(), so x
can be changed by foo().

c.
Yes.
x may be passed by reference.


Problem 7:
a.
O(log x + log y + x/y)

b.
f(n) is in O(n sqrt(n)):
  
  n		    n	
 Sum (sqrt(i)) <=  Sum (sqrt(n)) = n sqrt(n) is in O(n sqrt(n)) by choosing
 i=1               i=1

c = 1 and N = any constant.


f(n) is in Omega(n sqrt(n)):

  n                n                n
 Sum (sqrt(i)) >= Sum (sqrt(i)) >= Sum (sqrt(ceil(n/2))) >=
 i=1           i=ceil(n/2)        i=ceil(n/2)

ceil(n/2) sqrt(ceil(n/2)) >= (n/2) sqrt(n/2) = [n sqrt(n)] / [2 sqrt(2)].



[n sqrt(n)] / [2 sqrt(2)] is in Omega(n sqrt(n)) by choosing
d = 1 / [2 sqrt(2)] or smaller and N = any constant.

OR 

by showing n sqrt(n) is in O([n sqrt(n)] / [2 sqrt(2)]) by choosing
c = 2 sqrt(2) or larger and N = any constant.


Problem 8:

int[] counts = new int[range];
for (int i = 0; i < sortMe.length; i++) {
  counts[sortMe[i]]++;
}

int index = 0;
for (int i = 0; i < range; i++) {
  for (int j = 0; j < counts[i]; j++) {
    sorted[index] = i;
    index++;
  }
}