Cvičení z Datových struktur I
pondělí od 9:00 v S7, ZS 23/24
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. |
|
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:
- Úkoly se odevzdávají v recodexu
- Zadání úkolů a šablony zdrojových kódů jsou v repozitáři na GitLabu
- Vzorové řešení experimentálního úkolu (pro nafukovací pole)