Sylabus na skúšku

Na tejto stránke je sylabus na skúšku v školskom roku 2016/17 (neobsahuje úplný obsah všetkých prednášok)

Úsporné dátové štruktúry

• štruktúra pre rank a select
• wavelet tree
• štruktúra RRR a jej súvis s entropiou
• úsporné stromy, počet binárnych stromov

Amortizovaná zložitosť

• definícia amortizovanej zložitosti, potenciálová funkcia

Prioritné rady

• Fibonacciho halda a jej amortizovaná analýza

RMQ a LCA

• jednoduché algoritmy
• algoritmy s O(n) predspracovaním a O(1) dotazom
• segmentové/intervalové stromy

Scapegoat stromy, splay stromy a link-cut stromy

• scapegoat stromy, vrátane analýzy
• splay stromy (algoritmus, zložitosť a potenciálová funkcia, netreba celý dôkaz)
• použitie splay stromov na join a split
• link-cut stromy (štruktúra, expose, netreba analýzu zložitosti)

Vyhľadávanie kľúčových slov

• invertovaný index
• lexikografický strom

Sufixové stromy a polia

• sufixový strom
• sufixové pole
• vyhľadávanie vzorky v sufixovom strome a poli
• lineárny algoritmus na konštrukciu sufixového poľa
• konverzia zo sufixového poľa na sufixový strom a naopak
• použitie sufixového stromu a lca na hľadanie približných výskytov vzorky pri Hammingovej vzdialenosti

Burrowsova–Wheelerova transformácia

• vytváranie, spätná transformácia, použitie na kompresiu, FM index

Vyhľadávanie vzorky v texte

• triviálny algoritmus na presné výskyty
• použitie konečných algoritmov, Morrisov-Prattov a Knuthov-Morrisov-Prattov algoritmus
• dynamické programovanie na výpočet editačnej vzdialenosti a na hľadanie približných výskytov vzorky

Hešovanie

• Perfektné hešovanie: algoritmus, odhad očakávanej veľkosti pamäte pri použití univerzálnej triedy hešovacích funkcií
• Bloomov filter - algoritmus, približný odhad pravdepodobnosti chyby

Štruktúry pre externú pamäť

• výpočtový model externej pamäti, cache oblivious model
• B-stromy
• statické cache-oblivious stromy s vEB rozložením

Štruktúry pre celočíselné kľúče

• van Emde Boas stromy, x-fast trie, y-fast trie

Streaming model

• count-min sketch vrátane odhadu chyby

Perzistentné dátové štruktúry

• definícia (čiastočne a úplne) perzistentných a retroaktívnych dátových štruktúr
• všeobecné transformácie dátovej štruktúry na čiastočne perzistentnú (fat nodes, node copying)
• úplná retroaktivita pre problém nasledovníka (successor) a podobné rozložiteľné vyhľadávacie problémy

Geometrické dátové štruktúry

• lokalizácia bodu v rovine (planar point location) pomocou perzistentných a retroaktívnych štruktúr
• rozsahové stromy (range trees) a ich zrýchlenie (layered range trees)
• využitie wavelet trees namiesto statických rozsahových stromov