61B Final Exam Solutions
			Fall 97
Problem 1.
---------
a) Your name

b) false, true, false, true, true

c) Squeezer1/String

Squeezer1 uses the immutable String class, and therefore
creates a new string with each removal of whitespace.  Think 
of this as copying an array of characters with each change.
Squeezer2 change the mutable StringBuffer object in place.

d) Replace the first "1" by a "3"

e) O(log n - k)

f) reference counting

g) fragmentation

h) fragmentation


Problem 2.
---------

a) Depth-first: ABFCHGDE
   Breadth-first: ABCDEFGH

b) Depth-first: ABFCHDGE
   Breadth-first: ABCDEFGH

d) 
	i	A	B	C	D	E	F	G
	-	inf	inf	0	inf	inf	inf	inf
	C	inf	inf	0	inf	2	inf	4
	E	inf	3	0	8	2	inf	4
	B	9	3	0	8	2	12	4
	G	9	3	0	8	2	7	4
	F	9	3	0	8	2	7	4
	D	9	3	0	8	2	7	4
	A	9	3	0	8	2	7	4

Problem 3
---------

a)           10
          4     17
        1  5  16  21

b)            21
            17
          16
        10
       5
     4 
   1

c)         2B
      1B         5R
    nb  nb    4B    6B
            nb nb  nb nb

d)         a   b   c   d  
         -----------------
         |   |   |   |   |
         --------------\--
               -----------------
               |   |   |   |   |
               --/--------------
         -----------------
         |   |   |   |   |
         ------|-------|--
              dab     dad

e) O(L)

Problem 4
---------

The expected solution uses a queue of elements, where each element
contains a reference to TreeNode and an integer, which is the level
of that TreeNode in the tree.  There were many other solutions that
used data structures other than a queue.  (A small advantage to a 
queue over a stack is that one can stop as soon as you reach a level
that is greater than the desired level, because elements are stored
in breadth-first order.)  Some people also uses a queue with
markers, such as an Integer object, between each level, saying
at what level the next set of TreeNodes lived.  

The common incorrect solutions assumed the tree was complete.
Another less common problem was only traversing a single chaing
in the tree (by following only the left pointers).

Problem 5
---------

a) threw A
b) threw C
c) error
d) threw B

Problem 6
---------

a) 

fit    fan    fan   bat
fan    fin    bat   bit
bat    fit    rat   fan
rat    bat    fat   fat
fin    rat    fin   fin
fat    fat    fit   fit
bit    bit    bit   rat


b) a = 2 1 1 5

        0  1  2  3  4  5
   c =  0  2  1  0  0  1

   c =  0  2  3  3  3  4

   c =  0  2  3  3  3  3
   b =  -  -  -  5

   c =  0  1  3  3  3  3
   b =  -  1  -  5

   c =  0  0  3  3  3  3
   b =  1  1  -  5

   c =  0  0  2  3  3  3
   b =  1  1  2  5
  
Problem 7
---------

    stack                      program store
                                     -----------   -----------
a)  ln1 --------------------------->|  3 |  ---|-->|  4 |  / |
                                    -----------    -----------
                                                    ^
                               -----------         /
    ln2 ---------------------->|  2 |  --|---------
                               -----------

        -----------
b)  ln3 |  3 |  / |
        -----------
        ^ 
         \____
              \
        -------\---
    ln4 |  1 |  \ |
        -----------

                            
c)  Same as part a), but with the ListNode containing
	a 4 crossed out.


Problem 8
---------

a) For a given column a, it traverses the matrix of size N, always performing
only constant amount of work by looking up one entry in the row assciated 
with b.  Hence, the complexity is O(N).

b) The MysteryCompute method determines whether there is a flight with only 
one stop (i.e., a minimal path of length two) from city A to city B, which 
consumes minimal fuel (has minimal path weight).  It will print out the cost 
of the minimal flight route and its intermediate stop city.


c) In the worst case, the complexity would now be O(N^2) since for every 
entry E in the adjacency list of A (there are N such entries), we would have 
to look through the complete list associated with the respective E (again up 
to N entries in each such list).  This is worse than the adjacency matrix 
implementation.

e) In this case, every adjacency list is of constant size 1, namely, has one 
entry to its immediate neighbor.  Consequently, the complexity would now be 
O(1).  This is better than the adjacency matrix implementation.


Problem 9
---------

a)  ( 0 <= front <= rear < capacity ) && ( rear - front == count )
  ||
    ( 0 <= rear < front < capacity ) && (rear + (capacity - front) == count)

b) This problem was corrected to give the complexity as: O(k* N * log k)

    There are at least a couple of strategies that work.  First, 
    assume the lists are sorted smallest to largest (to simplify 
    the explanation).  Put the lists into a heap, where the keys 
    in the heap ordering are the values of the first element of 
    each list.  

    The algorithm removes the smallest heap element, removes the 
    first item in that list, appends it to the end of the resulting
    list (initially empty), and reinserts the remaining list back
    into the heap.  

    The two heap operations at each step take O(log K) time.  There
    are N*k elements in all of the lists, and therefore N*k steps.