Advanced course on Data Structures
This graduate course covers selected works in the area of
Data Structures.
Highlights (topics):
- algorithms that process trees
- precomputed tables and micro-macro algorithms.
- amortized analysis of algorithms
- update-query tradeoffs
Highlights (data structures):
- RMQ, LCA, Level Ancestors (Berkman and Vishkin;
Bender and Farach-Colton)
- UNION-FIND
- Preprocessing for product queries (Alon and Schieber)
- LINK-EVAL-UPDATE (Tarjan)