* Monday:     Quiz #1.
* Wednesday:  Binary Search Trees.

* Today:  review of BSTs.
	  hand back quiz 1 (at the end).

* PS 3 has been posted.

---------------------------------

REVIEW OF RANDOM-BST CONSTRUCTION

Consider a random permutation of {1, ..., n}.
Suppose we insert into a BST in that order.
What can we say about the height of the tree?

H_x := r.v. denoting the height of element x in the tree.

PR[H_x > c log n] == ??
     
Note that the root of any subtree is a randomly chosen element from
the keys in that range.  Call this a PARTITION.  

Say that a partition is LUCKY if left and right subtrees both have
size at least 25% of the tree.
So Pr[lucky] = 1/2.

Now, how many lucky partitions can x participate in before it's a leaf?
Well, (# elements in x's subtree) <= n * 0.75^{#lucky partitions}.
So #lucky partitions <= log_4/3 n.

How many (lucky OR unlucky) partitions until we get log_4/3 n lucky
partitions?


   I flip a fair coin T times.

   Pr[ #h <= K ] = Pr[ exists size-(T-K) subset of [1..T] that are all tails]

	       <= (T choose T-K) * 1/2^{T-K}

       	        = (T choose K) * 1/2^{T-K}

	       <= (eT/K)^K / 2^(T-K).


   Pr[ # lucky partitions < log_4/3 n in 10 log_4/3 n tries]

	       <= (10e)^log_4/3 n / 2^(9 log_4/3 n)

	        = (27.1828 / 512) ^ log_4/3 n

	       <= (0.1)^log_4/3 n

	        = 0.1 ^ [(log_10 n) * log_10 (3/4)]

		= (1/n) ^ log_10 (3/4)

	       <= 1/n^2.
   


What does all of this mean?

1) Pr[height of element x >= 10 log_4/3 n ]           <= 1/n^2.
2) Pr[exists x: height of element x >= 10 log_4/3 n ] <= 1/n.
   (why?  union bound.)
3) E[height of tree] = O(log n).
   (why?
	E[height] <=   (10 log_4/3 n)Pr[h < 10 log_4/3 n] 
		     + (n           )Pr[h >= 10 log_4/3 n] 

		  <=   10 log_4/3 n  + n /n 
		   =   10 log_4/3 n  + 1.

   )


--------------------
Let's look at the comparisons that are performed in the BST.  

  * Pick a random root.  Every element will eventually be compared to
    that root.

  * Pick a random second node, say < root.  Every element < root will
    eventually be compared to that node.

  * Etc.

Let's look at the comparisons that are performed by randomized-quicksort.

  * Pick a random pivot.  Every element is compared to that root.

  * In the left subarray, pick a random pivot.  Every element in that
    subarray (i.e., every element < root) is compared to that node.

  * Etc.


What's the relationship between BSTs and randomized-quicksort?
They perform EXACTLY the same set of queries.

So, in essence, we've done the same analysis over again.  But actually
this is stronger!

Suppose that E_{construction of tree}[search depth for x] = O(log n).
Does that imply that E_{construction of tree}[height of tree] = O(log n)?

[Exercise 12.4-2: describe an n-node BST with average node depth
                  Theta(log n) but height omega(log n).]

  build spine of sqrt(n) nodes on a linear spine, and a balanced
  remaining n-sqrt(n).  thus E[h] _could_ be bigger.


----------------------------------

Hand back quiz.

* Quiz:
   <= 35  probably should drop.
   <= 45  in danger; should see us.

   Mean:    58.4
   Std.Dev: 12.4
   Median:  60.5

If there's still time left:
  * go over the priority queue question from the quiz.
  * ask for other questions on the quiz.