Zobrazenie zdroja stránky Sylabus na skúšku

Na tejto stránke bude postupne vznikať sylabus na skúšku, zatiaľ však nie je kompletný.

Amortizovaná zložitosť a splay stromy
* definícia amortizovanej zložitosti, potenciálová funkcia
* splay stromy (algoritmus, zložitosť a  potenciálová funkcia, netreba celý dôkaz)

RMQ a LCA
* algoritmy s O(n) predspracovaním a O(1) dotazom

Vyhľadávanie kľúčových slov 
* invertovaný index
* lexikografický strom 
* prienik triedených zoznamov (doubling search/galloping search)

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
* hľadanie maximálnych opakovaní
* použitie sufixového stromu a lca na hľadanie približných výskyty vzorky pri Hammingovej vzdialenosti 

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 hľadanie približných výskytov vzorky

Burrowsova–Wheelerova transformácia 
* vytváranie, spätná transformácia, použitie na kompresiu, FM index

Úsporné dátové štruktúry
* štruktúra pre rank a select
* wavelet tree (rank nad väčšou abecedou)
* štruktúra RRR a jej súvis s entropiou 
* úsporné stromy, počet binárnych stromov

Prioritné rady
* Fibonacciho halda a jej amortizovaná analýza
* Tri verzie meldable háld: random, leftist a skew, v každej algoritmus pre zjednotenie a jeho analýza

Hešovanie
* Perfektné hešovanie: algoritmus, odhad očakávanej veľkosti pamäte pri použití univerzálnej triedy hešovacích funkcií

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

Š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

Perzistentné dátové štruktúry
* definícia (čiastočne a úplne) perzistentných a retroaktívnych dátových štruktúr
* všeobecná transformácia dátovej štruktúry na čiastočne perzistentnú (za určitých predpokladov)
* ú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)