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. Plán: Opět hešování!!! 3-nezávislost tabelace a řešení kolizí

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: