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. Geometrické datové struktury postavené nad množinou bodů. Konkrétně quadtree (rozebrali jsme hloubku, počet vrcholů, chování ve více dimenzích a zlepšení kompresí cest) a kd stromy (rozebrali jsme hledání minima v jedné souřadnici, tedy např. nejlevějšího prvku, a heuristiku na hledání nejbližšího souseda, čili Nearest Neighbor query). Technika fractional cascading pro vyhledávání ve více setříděných polí najednou (lze použít na range trees, což snad bude vysvětleno na přednášce).
18. 12. Sufixové a LCP pole, použití na počítání k-gramů (různých podřetězců délky k). Vyhledávání jehly pomocí binárního vyhledávání nad sufixovým polem a jeho zlepšení pomocí předvýpočtů LCP hodnot pro intervaly v binárním vyhledávání. Sufixové stromy: definice, uložení v lineárním prostoru a použití na vyhledávání jehly bez binárního vyhledávání.
25. 12. Plán: Boží hod vánoční. Pokud již budete přesyceni dobrotami a/nebo vám budou chybět datové struktury, můžete se podívat na videokurz Bena Langmeada, kde popisuje ještě efektivnější datové struktury pro řetězce než jsou sufixová pole a stromy.
1. 12. Plán: Nový rok, do něhož přeji vše nejlepší. Jinak platí to, co na Boží hod vánoční.
8. 1. Problémy s paralelním přístupem k datovým strukturám a způsoby jejich řešení: zámky a atomické operace. Jednoduchý zámek pomocí atomické instrukce CompareAndSwap (CAS) nebo LoadLinked/StoreConditional (LL/SC). DeadlockEmpire aneb přehlídka problémů v paralelních programech (a také přehlídka synchronizačních primitiv v jazyce C#).

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: