Cvičení z Datových struktur I

středa od 9:00 v S1, ZS 26/27

„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ů. Běžně budeme procvičovat látku z poslední přednášky a někdy též diskutovat domácí úkoly.

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

30. 9. Úvod, krátké opakování modelu RAM a asymptotické O notace. Nafukovací pole zdvojováním kapacity: tři důkazy konstantní amortizované složitosti (agregační, účetní a potenciálem). Úlohy na cvičení, z nichž jsme prošli řešení prvních dvou úloh.
7. 10. Opakování amortizované složitosti a potenciálové metody, ukázka na dynamickém poli. BB[alfa]-stromy. Úlohy na cvičení, z nichž jsme prošli řešení prvních tří úloh.
14. 10. Splay stromy (opakování dle slajdů). Úlohy na cvičení, z nichž jsme prošli řešení prvních tří úloh a 4.a-c)
Další: Vizualizace splay stromů a tahák na splay stromy od Ondry Mičky.
21. 10. Vysvětlení experimentálního úkolu na Splay stromy. Rovněž zadán úkol na implementaci Insertu pro (a,b)-stromy. 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), dle slajdů. Probrali jsme amortizovanou analýzu počtu změn v (a,b)-stromech a jak odvodit potenciál (tedy co od něho chceme). Příklady, ze kterých jsme probrali hlavně druhý a třetí. (Navíc: Vizualizace B-stromů.)
4. 11. I/O složitosti: rekurzivní versus nerekurzivní MergeSort, transpozice matice. Příklady, z nichž jsme probrali první dva.
11. 11. Komentáře k experimentálnímu úkolu na splay stromy a představení experimentálního úkolu na transpozici matic. I/O složitosti: pravděpodobnostní analýza QuickSelectu, online algoritmy pro správu cache, hlavně LRU. Příklady, ze kterých jsme probrali první dva.
18. 11. Plán: 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ů.

Podmínky zápočtu

Zápočet bude za implementační a experimentální domácí úkoly, které jsou vysvětleny v pravidlech (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: