Syllabus
- Introduction:
- Heaps
- Trees
- Splay Trees,
(Tarjan)
- Dynamic Trees,
(Tarjan)
- Average height of a Random Search Tree
- Treaps (Postscript)
- Deletions from a Random Search Tree
- Fringe analysis -- space utilization of a Random B-Tree
(Eisenbarth et al.)
- Persistent Data Structures,
(Sarnak and Tarjan)
- Hashing:
- Pattern Matching
- Knuth, Morris and Pratt (KMP)
- Suffix Trees
- Algorithmic Techniques
- Dynamic Programming
- Optimum Alphabetic Search Trees
- Parsing Context Free Languages
- Dynamization
- Sparsification
( Eppstein et al.)
- log log N Priority Queue