|
|
||
Last update: T_KTI (25.04.2016)
|
|
||
Last update: T_KTI (25.04.2016)
Naučit pokročilejší datové struktury a metody jejich návrhu a analýzy. |
|
||
Last update: Mgr. Martin Mareš, Ph.D. (02.03.2018)
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: T_KTI (26.04.2016)
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 (25.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 |