CS410, Summer 1998
Homework 5 Sample Solution
Dan Grossman / Parag Tole

1. Reverse-sorted order.  As each smaller heap is built, the new
element will fall of the way to the bottom of the heap because
everything below it will have smaller keys.  Hence the maximum number
of calls to heapify will be made.

2. Put the lists into a heap using the head node of the list as the
key.  While the heap is not empty, delete-min.  Take the head of this
deleted list and make it the next element in the final result.  Remove
the head from the list.  If the list is not empty, insert it into the
heap.

3. We could use a balanced tree for each bucket instead of a list.  We
do not care because the worst-case never actually happens.  If it
could, then we should invest our resources in a better hash function,
not better worst-case behavior.

4. Hash (er, transform) the String you are looking up.  At each node,
compare the keys.  Only if they match do you compare the strings.

5.

h'(k) = k mod m
Linear probing:
	Bucket  0   1   2   3   4   5   6   7   8   9    10
	Key	22  88		4   15  28  17	59  31	 10

Quadratic Probing: c_1=1, c_2=3
	Bucket  0   1   2   3   4   5   6   7   8   9    10
	Key	22      88  17	4   	28  59	15  31	 10


Double Hashing: h_2(k) = 1 + (k mod (m-1))
	Bucket  0   1   2   3   4   5   6   7   8   9    10
	Key	22	59  17	4   15	28  88      31	 10

6. Put one chip on every red node.  When we insert a node, it is red,
so we pay an extra O(1) chip at the beginning of the insert.  Then if
we have any case but 1, we do only O(1) work.  We pay no extra because
the number of red nodes stays the same.  Every color flip reduces the
number of red nodes in the tree, so this accounts for using a saved up
chip.  Case 1 cannot occur without red nodes in the tree.

7. This is just connectivity, so we should use union-find.  Actors are
not small integers, we should assign each Actor an integer the first
time we hear of him/her, and keep the Actor->integer mapping in a hash
table.  On Together, we union the sets containing the two actors.  On
Kevin Bacon, we see if Kevin Bacon and the input Actor are in the same
set.