Catalog of requirements for exam in DS2

Static dictionaries

FKS perfect hashing (Fredman, Komlós, Szemerédi)
Deterministic static dictionaries (Hagerup, Miltersen, Pagh) for polynomial universe
- Randomized version
- Derandomization using conditional expectation

Static trees
- Paths by range trees
- Heavy-light decomposition of trees
Dynamic trees (Link-Cut trees, Sleator and Tarjan)
- Dynamic tree decomposition
- Representation by interconnected Splay trees
- Application: Making Dinitz's max-flow algorithm faster
Incremental connected components (Union-Find)
- Representation by rooted trees
- Optimization: Union by rank and path compression
- Analysis of doubly recursive structures
  - Example with interval queries using an associative operation
  - Path compression only: O(log n)
  - Path compression with Union by rank: O(α(n))

Simulating Delete by tombstones and occasional rebuilds
Dynamization of 2D range trees by partial rebuilds
General transforms
- Separable search problems
- Amortized semi-dynamization
- Worst-case semi-dynamization
- Amortized full dynamization

Classification: ephemeral, semi-persistent, fully persistent, functional
Functional stacks using confluent linked lists
Functional binary search trees using path copying
General model of pointer-based data structures
- Semi-persistence using fat nodes
- Semi-persistence by combining fat nodes with node copying
- Full persistence based on linearized history (sketch)
Maintaining linear order
- List labelling
  - Exponential range in O(1) worst-case time
  - Polynomial range in O(log n) amortized time
  - Linear range in O(log² n) amortized time a.k.a. Ordered File Maintenance
- List order in O(1) amortized