Cvičení z Datových struktur I

pondělí od 9:00 v S7, ZS 23/24

„Ranní ptáče dál doskáče.“

K přednášce Datové struktury I Martina Mareše 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. Běžně budeme procvičovat látku z poslední přednášky.

Pokud máte nějaký dotaz, pište na vesely (obmotané a) 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é. Po domluvě mohu poskytnout konzultace.

Co jsme dělali

2. 10. Zaskočil Jirka Fink: Úvod a pravidla. Dijkstrův algoritmus a haldy. BVS a jejich vyvažování v lineárním čase.
9. 10. Óčková notace, amortizace a BVS. Příklady, ze kterých jsme stihli první čtyři (řešení posledních dvou na požádání vysvětlím).
16. 10. Zaskočil Jirka Fink: Splay stromy: dvojrotace, splay prvků v rostoucím pořadí, naivní implementace splayování pomocí jednoduchých rotací a proč nefunguje, volání splay v Insert a Delete, intervalový dotaz, použití splay stromů, nerovnoměrné vyhledávání prvků, staticky optimální strom, diskuze o statické a dynamické optimalitě.
23. 10. Zadán první experimentální úkol na splay stromy. BB[alpha] stromy (líně vyvažované) a splay stromy: rozebírání potenciálů pro amortizovanou analýzu. Příklady, ze kterých jsme stihli první dva (k dalším mohu říct řešení, ale nejspíš se k nim vracet nebudeme) PS: můžete se podívat na vizualizaci Splay stromu.
30. 10. (a,b)-stromy: Příklady, ze kterých jsme stihli první tři (včetně příkladu 2,5 o vytváření (a,b)-stromů v lineárním čase ze setřízené posloupnosti). Vizualizace B-stromů, což jsou (a,b)-stromy pro zadané b, kde a je horní celá část z b/2. Vzorové řešení experimentálního úkolu (pro nafukovací pole)
6. 11. Operace join pro (a,b)-stromy. Cache-aware a cache-oblivious algoritmy: binární vyhledávání, QuickSelect a LinearSelect a násobení matic dle definice s ideální uložením násobených matic. Příklady (nestihli jsme 2c QuickSort, 3b blokové násobení matic a 4 rychlejší binární vyhledávání)
13. 11.
  1. Cache-oblivious transpozice matic: pokud TransposeAndSwap upravíme tak, že nejprve transponujeme obě zadané matice (rekurzivně) a teprve poté je prohazujeme (průchodem po řádcích), tak dostaneme horší časovou složitost i počet přenosů.
  2. Kompetitivnost LRU v problému online správy cache: 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 velikost cache a srovnání se Sleator-Tarjanovou větou.
  3. Optimální offline algoritmus pro online správu cache: Longest Forward Distance (LFD), který vyhodí z cache blok, který bude potřeba nejpozději v budoucnu.
  4. Hešování: opakování definice c-univerzality a (k,c)-nezávislosti. Rozebrání toho, co znamená (1,c)-nezávislost.
20. 11. Hešování univerzální, k-nezávislé, tabulační: Příklady, ze kterých jsme prošli první, druhý a 3.a) (k tabulačnímu hešování se pokusím najít zdroj, kde by byl celý důkaz). Perfektní hešování v posledním příkladu jsme nestihli, ale ji načíst ze sekce 5.7 v poznámkách Jeffa Ericksona (původní článek je od autorů Fredman, Komlos and Szemeredi z roku 1984).
27. 11. Opakování tabelace (díky Petrovi za vytvoření tabulek). Hešování a řešení kolizí: pár příkladů na lineární přidávání (stručná řešení). Vysvětlení kukačkového hešování včetně přehešování na místě (ale bez analýzy).
4. 12. Hešování řetězců (dle lecture notes M. Mareše) a použití na Rabin-Karpův algoritmus (algoritmus je popsán v sekci 13.4 v Průvodci labyrintem algoritmů). Bloomovy filtry (vícepásmové a analýza počítacího dle lecture notes M. Mareše).
11. 12. Plán: Vícerozměrné datové struktury (dle přednášky)

Podmínky zápočtu

Zápočet bude za implementační a experimentální domácí úkoly, které jsou vysvětleny v pravidlech přednášejícího (relevantní jsou též starší pravidla Ondry Mičky. V krátkosti: bude vypsáno alespoň osm implementačních úkolů po 10 bodech a čtyři experimentální po 15 bodech. Na zápočet stačí 90 bodů. Úkoly budeme opravovat napůl s Petrem Chmelem. Další užitečné odkazy: