Otázky ke zkoušce z Datových struktur I (NTIN066)

Poznámka: proběhly menší změny po prvním předtermínu (pouze přeuspořádání, množina se nezměnila). 23. ledna proběhlo menší upřesnění dvou otázek (věta o délce řetězce v hešování s řetězci a doplnění otázky na použití Range trees).

„Velké“ otázky

• Definujte Splay strom. Popište, jak na něm probíhají operace Splay, Find, Insert a Delete. Popište výhody a nevýhody oproti jiným datovým strukturám, zejména vyváženým vyhledávacím stromům. 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. Vyslovte a dokažte větu o amortizovaném počtu změn uzlů pro operace Insert a Delete a (a,2a)-stromech. Jak se to liší pro (a,2a-1)-stromy? Popište výhody a nevýhody oproti jiným datovým strukturám, zejména vyváženým binárním vyhledávacím stromům.
• Definujte I/O model pro správu cache a srovnejte cache-aware a cache-oblivious algoritmy. Vyslovte a dokažte Sleatorovu-Tarjanovu větu o kompetitivnosti LRU. Popište přínos této věty pro analýzu cache-oblivious algoritmů.
• Definujte c-univerzální a k-nezávislé rodiny hešovacích funkcí. Uveďte příklady, kde nestačí c-universální rodina hešovacích funkcí, ale musíme použít k-nezávislou rodinu. Analýza hešování se separovanými řetězci: Formulujte a dokažte větu o střední hodnotě počtu kolizí nového prvku y s reprezentovanou množinu v hešování s řetězci, tj. o střední délce řetězce, do kterého bychom přidali y (jde o větu na str. 1 v [L kap. 6]). Ukažte příklady c-univerzálních a k-nezávislých rodin pro hešování přirozených čísel. Pro jeden příklad dokažte c-universalitu nebo k-nezávislost, pro k ≥ 2.
• Popište a analyzujte hešování s lineárním přidáváním s plně náhodnou hešovací funkcí a např. třetinovým zaplněním. Popište výhody a nevýhody oproti jiným datovým strukturám, zejména založeným na hešování.
• Definujte vícerozměrné intervalové stromy (range trees) a popište, jaké dotazy umí zpracovat. Rozeberte prostorovou složitost datové struktury a časovou složitost konstrukce a obdélníkových dotazů (bonus: včetně zrychlení zlomkovým kaskádováním).
• Definujte sufixové pole a LCP pole. Popište a analyzujte algoritmy na jejich konstrukci (pro sufixové pole stačí ve skoro lineárním čase). Popište příklad úlohy, kterou umí tato pole efektivně řešit.
• Popište zámky a atomické operace CAS a LL/SC. Navrhněte a analyzujte bezzámkovou implementaci zásobníku. Vysvětlete problém ABA a navrhněte jeho řešení. Porovnejte paralelizaci datových struktur za použití zámků a za použití atomikých operací (tzv. bezzámkové datové struktury), přičemž v obou případech vysvětlete, jaké mohou nastat problémy.

„Malé“ otázky

• Popište dynamické pole, tedy „nafukovací pole" se zvětšováním a zmenšováním. Analyzujte jeho amortizovanou složitost.
• Popište vyhledávací stromy s líným vyvažováním (BB[α]-stromy). Analyzujte jejich amortizovanou složitost. Uveďte příklad jejich použití.
• Navrhněte operace Find, Insert a Delete na Splay stromu. Analyzujte jejich amortizovanou složitost. Větu o složitosti operace Splay stačí vyslovit, nemusíte ji dokazovat.
• Analyzujte hloubku (a,b)-stromů.
• Analyzujte k-cestný Mergesort v cache-aware modelu. Jaká je optimální volba k?
• Formulujte cache-oblivious algoritmus pro transpozici čtvercové matice. Rozeberte časovou složitost a I/O složitost.
• 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 ℤ_p^k do ℤ_p.
• Popište systém hešovacích funkcí založených na lineární kongruenci. Dokažte, že je to 2-nezávislý systém ze ℤ_p do [m] (můžete využít lemma o modulení, které zformulujte, ale nemusíte dokazovat).
• Sestrojte k-nezávislý systém hešovacích funkcí ze ℤ_p do [m]. Zdůvodněte k-nezávislost (můžete využít lemma o modulení, které zformulujte, ale nemusíte dokazovat).
• Sestrojte 2-nezávislý systém hešující řetězce délky nejvýše L nad abecedou [a] do [m] založený na polynomech, tedy "rolling hash". Popište výhodu použití tohoto systému oproti jiným hešovacím funkcím.
• Popište a analyzujte Bloomův filtr. Uveďte příklad jeho praktického použití.
• Definujte k-d stromy a ukažte, že 2-d intervalové dotazy trvají Ω(√n).
• Ukažte, jak dynamizovat dvou dimenzionální intervalové stromy (tedy Range trees), stačí Insert.
• Ukažte, jak použít sufixové pole a LCP pole na nalezení nejdelšího společného podřetězce dvou řetězců.
• Ukažte, jak paralelizovat (a,b)-strom pomocí zámků.