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.
• Popište a analyzujte hešování s lineárním přidáváním.
• 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ů.
• Definujte suffixové pole a LCP pole. Popište a analyzujte algoritmy na jejich konstrukci.

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ěty o amortizované složitosti operací Insert a Delete na (a,2a-1)-stromech a (a,2a)-stromech.
• 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 kukaččí hešování a vyslovte větu o jeho složitosti (bez důkazu).
• Popište a analyzujte Bloomův filtr.
• Ukažte, jak provádět 1-rozměrné intervalové dotazy na binárním vyhledávacím stromu.
• Definujte k-d stromy a ukažte, že 2-d intervalové dotazy trvají Ω(sqrt(n)).
• Ukažte, jak použít suffixové pole a LCP pole na nalezení nejdelšího společného podřetězce dvou řetězců.