Syllabus
Static dictionaries:
• FKS perfect hashing
• deterministic dictionaries (Hagerup, Miltersen, Pagh)
• reduction of universe
Integer data structures:
• van Emde-Boas trees
• x-fast a y-fast trees
• Fusion trees
Graph data structures:
• heavy-light decomposition of trees
• path updates based on lazy evaluation
• Link-Cut trees (Sleator, Tarjan)
• incremental connectivity (Union-Find)
General transforms of data structures:
• semidynamization and dynamization
• persistence
Cache-oblivious structures:
• Ordered File Maintenance
• B-trees
Succinct data structures:
• strings over non-binary alphabets
• succinct representation of trees
Computation in stream model:
• determinisitic search for frequent elements
• randomized search for frequent elements
• estimating the number of distinct elements
Annotation
This course extends NTIN066 Data Structures I. It covers more advanced techniques of design and analysis of data structures: deterministic representation of static sets, data structures for integers, basic data structures for graphs, dynamic cache-oblivious search trees, dynamization, persistence, succinct data structures, computation in stream model.