Cvičení z Datových struktur I

středa od 9:00 v S6, ZS 24/25

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

K přednášce Datové struktury I Jirky Finka 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. Zakočil Petr Chmel: Úvod, opakování z bakalářského studia: Dijkstra a haldy, asymptotika a binární vyhledávací stromy. Úlohy na cvičení (a řešení k nim)
9. 10. Amortizace pomocí penízků (účetní metoda), potenciálů a agregací (spočtením celkové časové složitosti). Úlohy na cvičení. Prošli jsme si řešení první tři a půl.
16. 10. BVS vyvažavané líně (tedy BB[alpha] stromy) nebo pomocí splayování. V recodexu zadán úkol na implementaci splay stromů. Příklady, ze kterých jsme stihli první čtyři. Vizualizace splay stromů. Tahák na splay stromy od Ondry Mičky.
23. 10. Vysvětlení experimentálního úkolu se Splay stromy. Rovněž zadán úkol na implementaci (a,b)-stromů. Dále (a,b)-stromy ve variantě z úkolu (a taky Průvodce), tedy data jsou ve vnitřních uzlech a listy jsou prázdné (None / null). Příklady, ze kterých jsme probrali první dva a trochu pátý (čtvrtý a šestý příklad budou příště).
30. 10. Zakočil Petr Chmel: Vysvětlení experimentálního úkolu na experimenty s (a,b)-stromy. Dokončení (a,b)-stromů a začátek I/O složitosti: Příklady, ze kterých Petr probral první čtyří.
6. 11. I/O složitosti: násobení matic a QuickSelect. Příklady, ze kterých jsme pořádně prošli první dva. Čtvrtý a pátý budou příště.
13. 11. Komentáře k experimentálnímu úkolu na splay stromy a představení experimentálního úkolu na transpozici matic. Dokončení I/O složitosti (naivní rekurzivní transpozice a kompetitivní poměr LRU). Krátké opakování pravděpodobnosti. Příklady, ze kterých jsme pořádně prošli prvních pět.
20. 11. hešování!!! Konkrétně hešovací funkce univerzální, k-nezávislé a tabulační (které jsme si vyzkoušeli sami na sobě – díky Petrovi za vytvoření tabulek). Příklady, ze kterých jsme prošli první tři, čtvrtý bude příště. Perfektní hešování v posledním příkladu jsme nestihli, ale ho 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. Opět hešování!!! Hlavně 3-nezávislost tabulkového hešování (a taky proč není 4-nezávislé, pokud použijeme alespoň 4 tabulky). Příklady, ze kterých jsme prošli první tři, tedy vše bez bonusu.
4. 12. Hešovací tabulky a řešení kolizí: lineární přidávání a kukačkové hešování. Příklady, ze kterých jsme prošli všechny, včetně bonusu na tabuli (jak počítat modulo Mersennovo prvočíslo pomocí rychlých operací). Část řešení z loňska.
11. 12. Bloomovy filtry: vícepásmové (tedy s více tabulkami) a jak pomocí nich řešit úkol "find duplicates". Analýza počítacího Bloom filtru dle lecture notes M. Mareše (viz poslední dvě stránky). "Rolling hash" ř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ů). Příklady, které jsme všechny prošli.
18. 12. Sufixové stromy a pole, LCP: definice, příklady na BAROKOAROKOKO$ včetně konstrukce sufixového pole zdvojováním. Použití: index pro vyhledávání řetězců, počítání k-gramů (různých podřetězců délky k), nejdelší opakující se podslovo a nejdelší společné podslovo dvou řetězců.
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. Geometrické datové struktury postavené nad množinou bodů. Konkrétně quadtree (hloubka, počet vrcholů, chování ve více dimenzích a zlepšení kompresí cest), k-d stromy (rozebrali jsme hledání minima v jedné souřadnici, tedy např. nejlevějšího bodu, dynamizaci přes BB[alfa] stromy a heuristiku na hledání nejbližšího souseda, čili Nearest Neighbor query) a range trees, u kterých jsme zrychlili counting query (počítání bodů v obdélníku) o logaritmus pomocí techniky fractional cascading, kterou lze použít pro vyhledávání ve více setříděných polí najednou.
... Pokud vám bude chybět další cviko nebo si budete chtít procvičit paralelní programování, zahrajte si DeadlockEmpire, což je přehlídka problémů v paralelních programech a také 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í je též všeobecná část starších pravidel Ondry Mičky. V krátkosti: bude vypsáno alespoň 7 implementačních úkolů po 10 bodech a 3 experimentální po 15 bodech. Na zápočet stačí 75 bodů. Užitečné odkazy: