Solutions to hw1, written part.


1(a).  Read all N numbers into an array of size N.  Then put them into
max-heap order using the O(N) time procedure from heapsort.  Finally
remove the max item M times, which takes time O(M lg N) = O(N).

1(b).  (TopM from the book.)  Create an empty min-heap, and insert the
first M input items.  For each input after that, insert it, and then
extract (and forget) the min item, so the min-heap again has size M.
When all the input is done, the min-heap contains the M largest items.
Evidently this is O(N) operations on a heap of size M (or M+1), so
it meets the required time and space bounds.



2.  (See 1.5.15 in the textbook)

For trees constructed by weighted quick-union, we claim:

Claim (in book): If the tree has height n, then it has at least 2^n nodes.
Proof by induction:
  Base case (n=0): a tree of height n=0 has exactly 1=2^0 nodes.
  Inductive step (n>0): Any tree T of height n is constructed by linking
  a tree T1 of neight n-1 to the root of another tree T2 of size
  at least that of T1.  By inductive hypothesis, T1 has size at least
  2^(n-1), so T has size at least twice that, i.e. 2^n.

"Bound the number of its nodes at distance k from the root by the
binomial coefficient (n choose k)."  Actually this is not true for all
such trees, for a counterexample see this diagram:
https://docs.google.com/drawings/d/1d5cMWJsWq9IQUgr5f7JmLpnkY8SG8Q7TgUNlKJcsPJ4/edit

But it is true for "binomial trees".  The binomial tree B_0 is a single
node, and the binomial tree B_n is the result of a union on two copies
of the binomial tree B_(n-1).   For an image of such trees, see:
  http://en.wikipedia.org/wiki/File:Binomial_Trees.svg

Let L(n,k) denote the size of level k of B_n.  We see that when k>0,
level k of the height n tree is the union of (copies of) levels k and
k-1 of the height n-1 tree.  So we have this recurrence: L(n,k) =
L(n-1,k) + L(n-1,k-1).  Together with the base cases (L(n,0)=1, and
L(0,k)=0 for k>0), this forces L(n,k) to equal the binomial
coefficient (n choose k).

"Finally, compute the average depth (distance from the root) of a node
in the worst case tree."

I'll take this to mean binomial trees.  For a fixed n, (n choose k) is
symmetric about n/2: (n choose k) = (n choose n-k).  So the average
depth of a node is exactly n/2.


REMARK: in fact it is true, that for any tree of height n constructed
by weighted quick-union, the average depth (distance from root) of a
node is at most n/2.  But since this problem is sort-of busted, I
won't test you on it.