Please address all bugs/corrections to Jeff Schoner (cs61b-td).

1-3.

These are available in MS-Word format (update 7/27/00)

2.

  public int hashme(Integer anInt){
    return (1<<30)/anInt.intValue();
  }

Why does this break the Treap? Treaps balance themselves by restoration of the heap property. Since the heap property is never violated given the sequence to insert and the hash function associated with said sequence, there are no rotations performed, and no balancing of the Treap occurs.

3.

NOTE: /* */ comments inside the code are not valid. They are just a convinient way to circumvent problems HTML has with easily representing greater than and less than signs.

  static void levelOfBST(BST someBST, int someLevel){
        Queue myQueue = new Queue();
        BST parentTemp=null;
        BST childTemp=null;
        int numNodesAbove=1/*leftShift*/someLevel;//as if BST is a complete tree
        if(someBST!=null){
           myQueue.insert(someBST);
        }
        for( int i=1; i/*lessthan*/numNodesAbove;i++){
          int bitCount=0;
          for(int j = i;j!=0;*/rightShiftSigned*/1){ //computes lg(i)+1 = depth+1
            bitCount++;
          }
          if(myQueue.empty()){
                break;
          }
          parentTemp=(BST)myQueue.next();
          childTemp=parentTemp.getRight();
          if(childTemp==null){
            i+=numNodesAbove/(1/*leftShift*/bitCount)-1;//number of nodes missing
                                             //from complete tree
          }else{
            myQueue.insert(childTemp);
          }
          childTemp=parentTemp.getLeft();
          if(childTemp==null){
            i+=numNodesAbove/(1/*leftShift*/bitCount)-1;//number of nodes missing
                                            //from complete tree
          } else {
            myQueue.insert(childTemp);
          }
        }
        if(myQueue.empty()){
            System.out.println("Tree contains no nodes at depth "
                                +someLevel);
            return;
        }
        while(!myQueue.empty()){
          System.out.print((BST)myQueue.next().label() +" ");
        }
        System.out.println("");
}

4. There are many possible solutions. Here's one:
rotate 5 left
rotate 15 right
rotate 15 left
rotate 34 left

Note that is possible to convert any BST to any other BST containing the same
keys by performing a series of rotations.

5.

+---+---+---+---+---+---+---+---+---+---+---+                          
| 51| 42| 43| 25| 37| 40| 42| 21| 5 | 28| 33|
+---+---+---+---+---+---+---+---+---+---+---+           

+---+---+---+---+---+---+---+---+---+---+                              
| 43| 42| 42| 25| 37| 40| 33| 21| 5 | 28|
+---+---+---+---+---+---+---+---+---+---+               

a. HDIBEAFJCG
b. ABDHIECFJG
c. HIDEBJFGCA

7.

2163, 49, and 7 are all multiples of 7. Therefore all rational numbers will hash to locations that are divisible by 7, meaning 6/7 of the hashtable is wasted. There will be alot more collisions than necassary. You should make the numbers relatively prime.

8.

a. O(n) Hashtables are not ordered so you have to search the entire table.

b. O(logn) and O(H)

9.

For a fixed sized, well defined, set of data an array is often a better choice. Vectors can grow as is necessary. If this feature is not needed you may want to consider using arrays instead of vectors. Running time should be comparable for vectors and arrays at least in a O() sort of sense. Space could be an issue though. Vectors often allocate more memory than is needed at the moment in the hope that soon more elements will be exapanded. This reduces the number of reallocation and copies, but can waste memory if a vector does not grow much. Vectors are easier to deal with from a programmer's stand point. Going out of bounds is not a concern with vectors. The methods on a vector are also more intuitive (set, hasElement, etc.). However, it's harder to realize that a fence-post error has occured in a vector than in an array. An array will throw an exception if all your indicies are 1 too high. A vector will not.

10.

a. O(n^2). There is a for loop within a for loop. Both can potentially be done n times. Therefore, n^2 time.

b. In this case no. It doesn't matter what the values of the array are, this code will execute the same number of steps. This is not necessarily true of heap sort.

c. O(n * log n). To insert one element is O(log n). To insert n is O(n * log n). To remove is the same. O(2 * n * log n) -> O(n * log n).

d. No. While heap sort has a better overall running time, for small arrays, selection sort may be faster. There is a lot of overhead involved in constructing a heap, copying everything over, and taking it all out. In essence, the m at which n must be larger will be higher for a heap sort. The overhead involved in heap sort will also raise the C in the O definition as well.

11.

a. The more code synchronized, the more time the program will spend in synchronized sections. This could mean unneccesary waiting by another thread. Ben's program would still work. It would just be slower.

b. His program will spend A LOT of it's time checking to see if things are ready. With notify and wait, a program will use its time more efficiently.

c. He could have used the yield() function. This function forces the current thread to bow aside to other threads that may be waiting to execute. Java does not guarantee that multiple threads will run at once (time slicing). All it guarantees is that it can switch between running threads.

12.

a/ Let T2(n) = the number of binary trees with n nodes Let sum(expr, i, low, high) be the summation function (sigma) over the variable i, from i = low to high (inclusive)

T2(n) = 1, if n = 0, 1
sum(T2(i) * T2(n - 1 - i), i, 0, n - 1), if n > 1

Note: for this recurrence relation to work, I set T(0) = 1 although the number of trees of 0 nodes is actually 0 (but this can be easily checked in the java implementation)

b/ Remembering memoization, I can compute T2(n) by first computing T2(0), T2(1), T2(2), ... , T2(n). In this order, each computation of T2 takes O(n). With n computations, I get O(n^2).

c/ Let T3(n) = the number of 3-way trees with n nodes

T3(n) = sum(sum(T3(i) * T3(j) * T(n - 1 - i - j), j, 0, n - 1 - i),
i, 0, n - 1)

d/ Let Tk(n) = the number of k-way trees with n nodes

e/ No way there exists a constant time algorithm for a. The number of such trees is clearly exponential in n. Hence the length of the number of such trees is poly(n). Don't know how you can generate a number the length of which varies as a polynomial of n in constant time. QED. :)
12(e) solution provided by Michael Brudno

13.

// C. Shaw
// CS61B, July 25

/** This is an implementation of a heap priority queue.  Objects of Prioritized
 *  type are added into the queue.  The integer priority is taken and entered 
 *  into a heap.  The Prioritized object itself is added into a hashtable using
 *  the priority as its hashfunction (I use the Integer class to accomplish
this).
 *  Removal is based upon removing the root from the heap, determining the
 *  integer value, and finding the corresponding  prioritized object in the 
 *  hashtable.
 *
 *  Note that the hashtable will handle collisions such that when two objects
of 
 *  the same priority exist, the hashtable will return the more recent of the 
 *  two, which is not be in keeping with the default idea of a FIFO data 
 *  structure.  This could be remedied by not using a hashtable at all.  Also,
 *  the heap class could operate on objects of Prioritized type, so that the
 *  prioritized objects are actually stored in the heap -- not just their 
 *  priorities.
 */

import java.util.*;

/** A Priority Queue represented using a heap. */
public class HeapPriorityQueue { 
  Heap MyHeap = new Heap ();
  Hashtable PriorityItems = new Hashtable ();

  /** True iff this is empty. */
  public boolean empty() {
    return MyHeap.isEmpty ();  
  }

  /** The element of the sequence with the highest priority. Requires 
   * that !empty(). 
   */
  public Prioritized peek() {
    if (empty ()) return null;

    return (Prioritized) PriorityItems.get (new Integer (MyHeap.peek ()));
  }

  /** Return the element of the sequence with the highest priority 
   *  and remove it from the sequence.  Requires that !empty(). 
   */
  public Prioritized remove() { 
    if (empty ()) return null;

    return (Prioritized) PriorityItems.remove (new Integer (MyHeap.remove ()));
  }

  /** Put ITEM into the sequence. */
  public void insert(Prioritized item) {
    // Insert into the heap.
    MyHeap.insert (item.getPriority ());

    // Insert into the hashtable.
    PriorityItems.put (new Integer (item.getPriority ()), item);
  }

  public static void main (String [] args) {
    // Create a new queue.
    HeapPriorityQueue MyQueue = new HeapPriorityQueue ();

    MyQueue.insert (new Prioritized (100));
    MyQueue.insert (new Prioritized (65));
    MyQueue.insert (new Prioritized (23));
    MyQueue.insert (new Prioritized (112));
    MyQueue.insert (new Prioritized (93));
    MyQueue.insert (new Prioritized (-21));
    MyQueue.insert (new Prioritized (0));
    MyQueue.insert (new Prioritized (173));
    MyQueue.insert (new Prioritized (100));

    System.out.println (MyQueue.remove ().getPriority ());
    System.out.println (MyQueue.remove ().getPriority ());
  }    
}


/** An element for our priority queues
 */
class Prioritized {
    private int priority;
   
    public Prioritized(int n) { priority = n; }
    public int getPriority() { return priority; }
}


/** A heap class. */
class Heap {
  int [] A;
  int currentSize;

  public Heap () {
    A = new int [10];
    currentSize = 0;
  }

  public void insert (int a) {
    // Increase the size if we are half full.
    if (currentSize >= A.length / 2) resize (2 * A.length);

    // Add to the array.
    A[++currentSize] = a;

    // Now percolate up.
    percolateUp (currentSize);
  }

  public int remove () {
    if (currentSize < 1) throw new IllegalStateException ();

    // Remove the root element.  Start by swapping it with its
    // last child.
    swap (1, currentSize);

    // Decrement the size counter, effectively removing the element.
    int ReturnValue = A[currentSize];
    A[currentSize--] = 0;

    // Now percolate down.
    percolateDown (1);

    // Return the removed element.
    return ReturnValue;
  }

  public boolean isEmpty () {
    return (currentSize < 1) ? true : false;
  }

  public int peek () {
    return A[1];
  }

  private void resize (int size) {
    // No error checking needed for a private method.
    int [] Temp = new int [size];

    int smallest = (size < A.length) ? size : A.length;

    // Copy over the elements.
    for (int i = 0; i < smallest; i++) {
      Temp[i] = A[i];
    }

    A = Temp;
    currentSize = (currentSize <= size) ? currentSize : size;
  }

  private void swap (int element1, int element2) {
    int temp = A[element1];
    A[element1] = A[element2];
    A[element2] = temp;
  }

  private void percolateUp (int element) {
    // Check to see if we're the root node.
    if (element == 1) return;

    // Check to see if we need to swap.
    if (A[element] > A[element / 2]) {
      int temp = A[element];
      A[element] = A[element / 2];
      A[element / 2] = temp;

      // Now that we've swapped, recursively call the method.
      percolateUp (element / 2);
    }
  }

  private void percolateDown (int element) {
    // Check to see if this exceeds the bounds of the heap.
    if (element > currentSize) return;

    // Check to see if there are any children.
    if (2 * element > currentSize) return;

    // Choose between the children elements.
    int largest;
    if (2 * element + 1 > currentSize) largest = 2 * element;
    else largest = (A[2 * element] >= A[2 * element + 1]) ? 2 * element :
      2 * element + 1;

    // Now determine if a swap is necessary.
    if (A[element] < A[largest]) {
      swap (element, largest);
      percolateDown (largest);
    }
  }
}