Administrative:
    Recall that hw1 written is due by 5pm tomorrow,
    Late penalty is 10pts/day (counted fractionally).
    The hw1 program is due 9pm Tuesday (turnin not enabled yet).

I'll spend 15-20 minutes on hw1 written problem 2, since (I've heard!)
you need some idea of how to "prove", or at least convincingly argue,
about a property of a data structure or algorithm.

Let me consider the first part of problem 2, about the size of trees
in weighted-union UF.  (This is essentially in your book already.)  It
is possible to get partial credit just with examples and diagrams, but
let me sketch out the "invariant proof" approach:

    Consider the following claim about the trees that occur in the
    weighted-union UF data structure:

      (INV) Each tree has size at least 2^n, where n is its height.

    We claim INV is an "invariant": it is true after any number of UF
    operations.  We see it is true initially, when all trees are
    single nodes: each has height 0 and size 1=2^0.

    The only operation which modifies the trees is a union, joining
    together two trees T1 and T2 to produce a new tree T.   Supposing
    INV is true before the union, we need to check it is true after.
    That is, we need to check that tree T has the property.

    Suppose T1 has height n1 and size s1, T2 has height n2 and size s2.
    Suppose we linked the root of T1 to the root of T2, so s1 <= s2.
    The new tree T has size s=s1+s2 and height n = max(n1+1,n2).
    Since INV was true before, we know s1 >= 2^n1 and s2 >= 2^n2.

    Now I'll leave it to you to finish showing: s >= 2^n.

REMARK: In terms of mathematical proofs seen in CS224, this is a
    "proof by induction"; the induction is on the number of operations
    of the data structure.  (That number of operations is not an
    explicit variable, above.)  We make such arguments in terms of an
    "invariant" property, remaining true after each operation.

The second part (involving k), is only true for "worst case" trees,
i.e. trees which are as trees created are as small as possible for
their height.   (See if you can find a counterexample to the way I
stated the problem, the book gets it right in problem 1.5.15.)
You may need this fact about binomial coefficients:
   C(n,k) = C(n-1,k) + C(n-1,k-1), at least for n>k>0.


OK, with the remaining time, we'll get into 2-3 trees (preliminary to
left-leaning red-black trees) of Section 3.3.  We follow the slides:

   33BalancedSearchTrees.pdf   (pages 1-16?)

REMARK: we may get away from slides soon, to reduce the pace, and also
  to see some working code.