Cvičení z Datových struktur I

pátek od 12:20 v S1, ZS 22/23

K přednášce Datové struktury I vedené Jirkou Finkem vedu cvičení, na kterém se zaměříme na procvičení a hlubší porozumění probírané látky formou řešení příkladů a diskusí o domácích úkolech.

Pokud máte nějaký dotaz, pište na vesely (zavináč) iuuk.mff.cuni.cz, případně se zeptejte při/po cvičení. Také budu rád, když se v průběhu cvičení budete ptát, jakmile vám nebude něco jasné. Chcete-li konzultaci, ozvěte se prosím mi emailem.

Co jsme dělali

30. 9. Úvod k datovým strukturám: opakování vyhledávacích stromů a hald (binárních a d-regulárních), opakování asymptotické notace. Příklady (stihli jsme probrat první tři)
7. 10. Různé varianty dynamického pole a jejich amortizovaná složitost. Binární sčítačka i s odčítáním. Líné vyhodnocování operací na BVS. Příklady (stihli jsme probrat první pět)
14. 10. Líně vyvažované BVS, konstrukce optimálního statického BVS a úvod do splay stromů. Příklady (příklady na splay stromy budou i příště, možná trochu upravené). V recodexu zadán druhý domácí úkol na implementaci splay stromů. Doplnění: je možné použít libovolnou implementaci mazání (operace remove), ale pokud to nebude ta z přednášky nebo z Průvodce labyrintem algoritmů, tak prosím o odkaz, že tato implementace má správnou amortizovanou časovou složitost.
21. 10. Zadán experimentální úkol na splay stromy. Příklady na splay stromy (6. příklad je upravený oproti vytisknuté verzi). Vizualizace Splay stromu.
28. 10. Státní svátek
4. 11. (a,b)-stromy, zaskočil Petr Chmel. Příklady. V recodexu zadán domácí úkol na implementaci (a,b)-stromů.
11. 11. Cache-aware a cache-oblivious algoritmy: analýza počtu přenosů bloků pro QuickSelect a QuickSort s náhodným výběrem pivota, dále pro LinearSelect (deterministický lineární algoritmus na hledání k-tého nejmenšího) a nakonec násobení matic (dle definice při uložení matic po řádcích/sloupcích a rekurzivně při uložení matic po blocích, viz sekce 3.2.3 v článku od Erika Demaine). V recodexu zadán domácí úkol na experimenty s (a,b)-stromy.
18. 11.
  1. Transpozice matic: pokud nejprve rekurzivně transponujeme všechny čtyři podmatice a teprve poté prohazujeme ty dvě mimo hlavní diagonálu, tak dostaneme horší počet přenosů.
  2. Kompetitivnost LRU v problému online stránkování (paging): nejhorší možný poměr počtu výpadků (cache misses) algoritmu LRU oproti optimálnímu algoritmu, mají-li tyto algoritmy k dispozici stejně velkou cache velikosti.
  3. Optimální offline algoritmus pro online paging: Longest Forward Distance (LFD), který vyhodí z cache stránku (blok), která bude potřeba nejpozději v budoucnu.
  4. Perfektní hešování: konstrukce pomocí dvou úrovní tabulek a univerzálních funkcí, výpočet střední hodnoty celkové velikosti tabulek druhé úrovně (viz sekse 5.7 v poznámkách Jeffa Ericksona, původně článek autorů Fredman, Komlos and Szemeredi z roku 1984).
Zádán úkol na implementaci transpozice matic (termín za dva týdny) a rovnou i úkol na experimenty s transpozicí matic (termín za tři týdny)
25. 11. Univerzální, k-nezávislé, kukačkové, tabulační, etc. hešování. Konkrétně vysvětlení tabulačního hešování a důkaz 2-nezávislosti (bude i na přednášce). Kukačkové hešování k řešení kolizí: vysvětlení, přehešování na místě a začátek analýzy (prošli jsme příklad 1 na Tungově cvičení)
2. 12. 3-nezávislost tabulačního (neboli tabulkového) hešování. Rabin-Karpův algoritmus a hešování řetězců pomocí "rolling" hešovacích funkcí zkontruovaných z polynomů vyhodnocených v náhodné bodě a d-univerzalita, kde d je délka hešovaných řetězců; viz str. 10-11 ve skriptech od Martina Mareše. Lemma o kompozici rodin hešovacích funkcí aneb jak vytvořit z c-univerzální rodiny 2-nezávislou rodinu (i pro větší c), viz Lemma G na str. 6 ve skriptech.
9. 12. Cvičení bude nahrazeno konzultacemi ten samý den mezi 9. a 11. hodinou, popř. dle domluvy další týden v pondělí 12.12. dopoledne nebo v úterý 13.12. dopoledne. Příklady na procvičení lineárního přidávání a také univerzality/nezávislosti. Náznak řešení příkladů (popř. odkazy do literatury)
16. 12. Sufixové stromy a sufixová pole a jejich využití na vyhledávání řetězce v textu a na počítání k-gramů. Viz sekse 13.5 a 13.7 v Průvodci labyrintem algoritmů.
6. 1. Geometrické datové struktury: quadtree, k-d stromy (a příklad, proč potřebují polynomiální čas na dotaz) a intervalové stromy (range tree). Technika fractional cascading pro intervalové stromy a pro vyhledávání ve více setříděných polích současně. Opakování bezzámkových datových struktur pro paralelní přístup. Hraní Deadlock Empire. Všichni, kdo dorazili, dostanou na zkoušce jedničku a poté vyřeší slavný problém P vs. NP.

Podmínky zápočtu

Zápočet bude za implementační a experimentální domácí úkoly, které jsou vysvětleny v loňských pravidlech, která prosím dodržujte. Změna oproti loňsku je v počtech bodů: bude vypsáno sedm implementačních úkolů po 10 bodech a tři experimentální po 15 bodech. Na zápočet stačí 75 bodů. Další užitečné odkazy: