Zkoušky z Datových struktur I

Ke zkoušce je třeba znát teorii z přednášky: definice datových struktur a operací s nimi, všechna tvrzení a jejich důkazy.

Zkouška je ústní s písemnou přípravou. Dostanete jednu velkou otázku a jednu malou z následujícího seznamu.

Velké otázky

• Definujte Splay strom. Vyslovte a dokažte větu o amortizované složitosti operace Splay.
• Definujte (a,b)-strom. Popište, jak na něm probíhají operace Find, Insert a Delete. Rozeberte jejich slozitost v nejhorším případě.
• Definujte Fibonacciho haldu. Popište její operace a rozeberte jejich amortizovanou časovou složitost.
• Formulujte cache-oblivious algoritmus pro transpozici čtvercové matice. Rozeberte jeho časovou složitost a I/O složitost.
• Srovnejte různé reprezentace statických množin v cache-aware a cache-oblivious modelu: setříděné pole s binárním vyhledáváním, (a,b)-strom, binární vyhledávací strom ve van Emde-Boasově reprezentaci.
• Popište a analyzujte statické perfektní hešování FKS.
• Popište a analyzujte hešování s lineárním přidáváním.
• Popište a analyzujte kukaččí hešování.
• Definujte k-d stromy. Rozeberte časovou a prostorovou složitost konstrukce a obdélníkových dotazů.
• Definujte vícerozměrné intervalové stromy. Rozeberte časovou a prostorovou složitost konstrukce a obdélníkových dotazů (včetně zrychlení kaskádováním). Strukturu rozšiřte o dynamické přidávání bodů.

Malé otázky

• Popište „nafukovací pole“ se zvětšováním a zmenšováním. Analyzujte jeho amortizovanou složitost.
• Popište BB[α]-stromy s líným vyvažováním. Analyzujte jejich amortizovanou složitost.
• Navrhněte operace Find, Insert a Delete na Splay stromu. Analyzujte jejich amortizovanou složitost.
• Vyslovte a dokažte větu o statické optimalitě Splay stromů.
• Vyslovte a dokažte věty o amortizované složitosti operací Insert a Delete na (a,2a-1)-stromech a (a,2a)-stromech.
• Popište a analyzujte algoritmus A-sort.
• Popište d-regulární haldu s operacemi Insert, ExtractMin, Decrease a Build. Analyzujte její složitost v závislosti na počtu prvků a parametru d. Navrhněte optimální volbu parametrů pro Dijkstrův algoritmus.
• Analyzujte k-cestný Mergesort v cache-aware modelu. Jaká je optimální volba k?
• Vyslovte a dokažte Sleatorovu-Tarjanovu větu o kompetitivnosti LRU.
• Definujte c-univerzální a k-nezávislý systém hešovacích funkcí. Vyslovte a dokažte větu o očekávané délce řetězce v hešování s řetězci.
• Popište systém hešovacích funkcí odvozený ze skalárního součinu. Dokažte, že je to 1-univerzální systém ze Z_p^k do Z_p.
• Popište systém lineárních hešovacích funkcí. Dokažte, že je to 2-nezávislý systém ze Z_p do [m].
• Sestrojte k-nezávislý systém hešovacích funkcí ze Z_p do [m].
• Sestrojte 2-nezávislý systém hešovacích funkcí hešující řetězce délky nejvýše L nad abecedou [a] do [m].
• Popište a analyzujte Bloomův filtr.