Požadavky ke zkoušce z DS2

Statické slovníky

Perfektní hešování FKS (Fredman, Komlós, Szemerédi)
Deterministické statické slovníky (Hagerup, Miltersen, Pagh) pro polynomiální universum
- Randomizovaná verze
- Derandomizace pomocí podmíněných středních hodnot

Van Emde-Boasovy stromy
- Klasické vEB stromy
- Implicitní inicializace paměti
- vEB pomocí intervalových stromů
- Zrychlení použitím indirekce
- x-fast a y-fast stromy
Fusion trees
- Fusion nodes a konstrukce stromu z nich
- Komprese trie pomocí sketchů a pseudo-sketchů
- Simulace vektorového počítače na RAMu
- Výpočet dvojkového logaritmu v konstantním čase

Statická reprezentace stromů
- Reprezentace cest intervalovými stromy
- Heavy-light dekompozice stromů
Dynamické stromy (Link-Cut trees, Sleator a Tarjan)
- Dynamický rozklad na cesty
- Reprezentace propojenýmy Splay-stromy
Inkrementální komponenty souvislosti (Union-Find)
- Reprezentace zakořeněnými stromy
- Optimalizace: Union dle ranku a komprese cest
- Technika dvojitě rekurzivní analýzy struktur
  - Příklad s asociativní operací a intervalovými dotazy
  - Samotná komprese cest stojí O(log n)
  - Kombinace komprese s ranky zlepšuje na O(α(n))

Obecná dynamizace
- Rozložitelné vyhledávací problémy
- Amortizovaná semi-dynamizace
- Worst-case semi-dynamizace
- Amortizovaná plná dynamizace
Exponenciální stromy a dynamizace Fusion nodes

Klasifikace: efemérní, semipersistentní, plně persistentní, funkcionální DS
Srůstající spojové seznamy
Funkcionální vyhledávací stromy s kopírováním cest
Obecný model ukazatelových datových struktur
- Semi-persistence pomocí tlustých vrcholů
- Semi-persistence kombinací tlustých vrcholů s kopírováním
- Plná persistence linearizací historie
Udržování linéarního uspořádání
- List labelling
  - Exponenciální rozsah v O(1) worst-case na operaci
  - Polynomiální rozsah v O(log n) amortizovaně na operaci
- List order v O(1) amortizovaně na operaci