--------
Question 1
Amortized complexity. Lazy balanced trees.
Question 2
Perfect hashing.
--------
Question 1
Splay trees, amortized analysis.
Question 2
Model Bins and Balls.
--------
Question 1
(a,b)-trees: definitions, operations, parameter selection, variations.
Question 2
2-independent hash systems.
--------
Question 1
Memory hierarchy: hardware caches, external memory model, cache-aware and cache-oblivious algorithms.
Question 2
Tabulation hashing.
--------
Question 1
Hashing: linear probing, cuckoo hashing
Question 2
Model Bins and Balls.
--------
Question 1
Hashing: selection of hash function: k-independent systems, tabulation hashing.
Question 2
Bloom filters: 1-band, multi-band, counting filters.
--------
Question 1
Hash systems.
Question 2
Parallel data structures: locks, lock-free data structures.
--------
Question 1
Suffix arrays.
Question 2
2-independent hash systems.
--------
Question 1
Geometric data structures: range queries, range trees.
Question 2
Hashing strings.