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
  • Doubly recursive analysis of 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
• 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
• 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 or Packed Memory Array
  • List order in O(1) amortized

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)
  • Speedup using indirection