CSE 326 - Autumn 2000

Homework #5
Due: Friday Nov 10th

1. Weiss 6.8.  (Suggestions: Part (a) - proof by contradiction; (b) - inductive
   proof; (c) - proof by contradiction.)

2. Weiss 6.14.

3. Weiss 6.16.  Follow the pseudocode guidelines.  By "implicit
   position i" we mean "if the array based implementation had been
   used instead, that node would correspond to A[i]".

4. Weiss 6.20, but only keys 1 to 10.

5. Weiss 6.18, part (a).  (This should be *very* easy!)

6.  Weiss 6.18, part (b).  Rather than detailed pseudocode, a more
    relaxed mix of English and code is fine, as used in the skeleton
    solution below.  Copy this partial solution and fill in the
    missing steps in the indicated places.  Please type your solution.
    Note that you can copy this text file from the course web page.

    What is the maximum number of times you might swap a node with
    it's parent when running this algorithm?  Why?

Let H[] be the array containing the heap.

Insert(x){
  Attach x as a new leaf at position P in the fringe of the tree;
  Fixup(P);
}
	
Fixup(P){
	if (P is in an even layer){
		if (P is at the root){
			return; 
		} else if (H[P] < H[grandparent of P]) {
			swap H[P] and H[grandparent of P];
			Fixup(grandparent of P);
		} else if (H[P] > H[parent of P]){
			/* FILL IN HERE */

		}
		else { /* P > grandparent && P < parent */
			/* FILL IN HERE */

		}
	}
	else { /* x is in an odd layer */
			/* FILL IN HERE */


	}
}

QUESTION:  How long did it take you to complete this assignment?

BONUS: Weiss 6.18 part (c).