# 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

## Ordered sets of integers

- Van Emde-Boas trees
- Classical vEB trees
- Implicit initialization of memory
- vEB based on range trees
- Speedup by indirection
- x-fast a y-fast tries

## Heaps

- Binomial
- Lazy binomial
- Fibonacci

## Splay trees

- Weighted analysis
- Static optimality theorem
- Static finger bound
- Working set bound
- Dynamic optimality hypothesis

## Data structures for graphs

- 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))

## Making data structures dynamic

- 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

## Persistent data structures

- 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
^{2}n) amortized time a.k.a. Ordered File Maintenance

- List order in O(1) amortized

- List labelling

## Cache-oblivious data structures

- B-trees (cache-aware)
- Van Emde-Boas layout of binary search trees
- Cache-oblivious B-trees (combining ordered file with vEB layout)