RECITATION NOTES	   15-451 Algorithms		      09/29/04
Plan:
* Go over quiz
* Material related to recent lectures.
=======================================================================

Quiz:
1. recurrences. (go through them or ask students to explain)
2. asymptotic analysis.   ditto.
3. quicksort.             ditto

B-trees
=======

Have the class work out the result of inserting A,B,C,D,E,F,G,H,I into
an initally empty B-tree with t=2 (i.e., a 2-3-4 tree).  For instance,
after the first 3 letters you just have one node. Then, the next
insert brings the B up, and the D goes in to the leaf with the C. E goes
into the leaf, and then F brings up the D.  At the very end, the "I"
should cause the root to get split.  


Treaps and tree rotations
=========================
Might be good to do an example.  You can have students make up (key,
priority) pairs and then insert them in and do the rotations.


Auxiliary information in search trees:
=====================================

By adding extra information to the nodes of a binary search tree, it's
often possible to perform other operations you might be interested
in.  However, the data you add has to have two properties:

   (1) it's sufficient to solve the problem you want to solve
   (2) the values of the data in a node can be maintained efficiently.

E.g., what if we want to do the following operations:

   - output the kth smallest element (let's assume all keys
     are distinct) 

   - do a version of lookup(x) that tells us the rank of x (how many
     keys are smaller than x).

If we had fixed set of data, this would be easy.  We just make a
sorted array. To output the kth smallest element, we just output A[k].
To get the rank of x, we just do binary search to find it, and then
output which location it's in. 

How could we do this with search trees, if we want to do inserts too?

Here would be a *bad* way of solving the problem: have each node
store the rank of its key.  Why is this bad?  Because if you insert a
new key (that, say, is smaller than everything else) you may have to
update *everyone's* rank.  So we don't have property (2).

What's a better way?  One thing we can do is store the size of the
subtree rooted at each node in that node.

  - how do we use this to solve the problems?

  - how do we maintain these when we do an insertion or tree rotation?