             Assignment 8 Solutions
             ----------------------


1. It is a simple mathematical fact that

  logb(n) = logb(a)*loga(n) 

where logb is log to base b, and loga is log to base a.

(a) To show that log2(n) = O(log3(n)), we must find a (k,N) pair such
that for all n > N,

log2(n) <= k*log3(n)

We claim that k = 2, N = 1 satisfies this. The reason is 

2*log3(n) = 2*log3(2)*log2(n)
          = log3(4)*log2(n)
          >= log2(n) since log3(4) is greater than 1.


(b) To show that log3(n) = O(log2(n)), we must find a (k,N) pair such
that for all n > N,

log3(n) <= k*log2(n)

We claim that k = 1, N = 2 satisfies this. The reason is 


log2(n) = log3(n)*log2(3)
        >= log3(n) for n > 2.


 Therefore, Scarlett O'Java is right. 


2. Here is the sequence of heaps:

.   4      4      8          8           8              9
          /      / \        / \         / \            / \
         3      3   4      7   4       7   4          7   8
                          /           / \            / \  /
                         3           3   2          3  2 4



     8        7          4       3     2   .
    / \      / \        / \     /
   7   4    3   4      3   2   2
  / \      /
 3   2    2

 Total number of comparisons = 8 to put to the heap + 8 to get from heap
                             = 16

 Total number of comparisons for selection sort = 15 comparisons


 For small input sizes, a simple algorithm like selection sort is
actually much more efficient than fancy algorithms like heapsort. In
this example, not only does selection sort use fewer comparisons, but
it does not need to allocate storage dynamically to create the heap.
Of course, as the input size increases, O(n*log(n)) algorithms will
sooner or later beat selection sort which is O(n^2).


3. It is easy to see that a complete binary tree of height h has 
   between 2^(h) and 2^(h+1) - 1 nodes. 

   From this, we see that if we have n items in a complete binary tree,
   the tree must have a height of ceiling(log2(n+1)) - 1. 

4. 

class HeapAsArray implements SeqStructure {

    protected Comparable[] ar;
    protected int size;
    protected int MAXSIZE;
    protected int nComparisons;

    public HeapAsArray(int max) {
	ar = new Comparable[max];    
	size = 0;
	MAXSIZE = max;
	nComparisons = 0;
    }

    public boolean isEmpty() {
	return size == 0;
    }

    public int size() {
	return this.size;
    }

    public int comparisons() {
	return nComparisons;
    }


    public Object get() {

    //check for empty heap
    if (isEmpty()) {
      System.out.println("Duh: attempt to get from empty heap");
      return null;
    }

    //get kahuna
    Object max = ar[1];

    //get last street-thug and crown him kahuna
    ar[1] = ar[size];
    ar[size] = null;
    size = size - 1;

    //gang war breaks out
    int disturbedIndex = 1; //index of node whose data has been changed
    while (true) { //we'll break out of loop when bubbling is done
        Comparable disturbedGuy = ar[disturbedIndex];
	Comparable leftKid,maxKid;
        int maxKidIndex;
	int leftKidIndex = 2*disturbedIndex;
        int rightKidIndex = 2*disturbedIndex + 1;

 	//if left kid does not exist, bubbling is over
        if (leftKidIndex > size)
	    break;
	else 
	    leftKid = ar[leftKidIndex];

	//now check that right kid exists and compare
	if ((rightKidIndex <= size) && (ar[rightKidIndex].compareTo(leftKid) > 0)){
	    maxKid = ar[rightKidIndex];
	    maxKidIndex = rightKidIndex;
	    nComparisons++;
	}
	else {//right kid does not exist or left kid is bigger
	    maxKid = leftKid;
	    maxKidIndex = leftKidIndex;
            //yuk: nComparisons is not updated consistently. Won't worry about it now.
	}

	//we know which kid is bigger, now compare with disturbed node
	if (disturbedGuy.compareTo(maxKid) < 0) {//swap
	    ar[disturbedIndex] = maxKid;
	    ar[maxKidIndex] = disturbedGuy;
	    disturbedIndex = maxKidIndex;
	    nComparisons++;
	}
	else //no swap, so bubbling is done
	    break;
    }

    return max;
  }

  public void put(Object o) {

    if (size + 1 >= MAXSIZE) {
	System.out.println("Duh:Heap overflow error");
	return;}

    //heap within bounds
    size = size + 1;
    ar[size] = (Comparable)o;

    //new guy is at bottom of heap but may be ambitious, so guns for boss etc.
    int disturbedIndex = size; 
    while (disturbedIndex != 1) {//while we are not at root
	int popIndex = disturbedIndex/2;//index of parent
	nComparisons++;
	if (ar[popIndex].compareTo(ar[disturbedIndex]) < 0) {
	    //swap
	    Comparable temp = ar[popIndex];
	    ar[popIndex] = ar[disturbedIndex];
	    ar[disturbedIndex] = temp;
	    disturbedIndex = popIndex;
	}
	else
	    break;
    }
  }
}


5. 

The following BST is the final result after all insertions.

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

After root is deleted, the following BST is produced by the algorithm
given in class. It is also possible to move 4 into the root position,
hoisting its right subtree up with it. 


             2
            / \
           1   4
                \
                 6
                / \
               5   9
                  /
                 7




6.

O(n), where n is the number of elements in the tree.
Code: see LoHi.java


7.

See Blockwart.java (using Map), BlockwartEnum.java (using Hashtable) and
Office.java (for both versions).  Needs other class files as well.
