Naučit pokročilejší datové struktury a metody jejich návrhu a analýzy.

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ů.

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

A. Koubková, V. Koubek: Datové struktury I. MATFYZPRESS, Praha 2011

Učební text na webové stránce KTIML

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

Statické slovníky:

• perfektní hešování FKS

• deterministické slovníky (Hagerup, Miltersen, Pagh)

• redukce universa

Celočíselné datové struktury:

• van Emde-Boasovy stromy

• x-fast a y-fast stromy

• Fusion trees

Grafové datové struktury:

• dekompozice stromů na lehké a těžké hrany

• aktualizace cest pomocí líného vyhodnocování

• Link-Cut stromy (Sleator, Tarjan)

• inkrementální komponenty souvislosti (Union-Find)

Obecné techniky transformace struktur:

• semidynamizace a dynamizace

• persistence

Cache-oblivious struktury:

• Ordered File Maintenance

• B-stromy

Úsporné datové struktury:

• řetězce nad nebinární abecedou

• úsporná reprezentace stromů

Výpočty v proudovém modelu:

• deterministické hledání častých prvků

• randomizované hledání častých prvků

• odhad počtu různých prvků

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