|
|
|
||
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.
Last update: T_KTI (25.04.2016)
|
|
||
Naučit pokročilejší datové struktury a metody jejich návrhu a analýzy. Last update: T_KTI (25.04.2016)
|
|
||
Předmět je zakončen zkouškou, u níž se ověřuje porozumění látce z přednášky a schopnost aplikovat ji na řešení obdobných problémů. Last update: Mareš Martin, Mgr., Ph.D. (02.03.2018)
|
|
||
D. P. Mehta, S. Sahni eds.: Handbook of Data Structures and Applications. Chapman & Hall/CRC, Computer and Information Series, 2005
K. Mehlhorn: Data Structures and Algorithms I -- Sorting and Searching, Springer-Verlag, 1984 Last update: T_KTI (26.04.2016)
|
|
||
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 Last update: T_KTI (25.04.2016)
|