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.

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: