Cvičení z Datových struktur I

V zimním semestru 2015/2016 vedu cvičení k přednášce z Datových struktur I Michala Kouckého. Cvičení se koná každý druhý čtvrtek od 17:20 v posluchárně S8.

Zápočet se udílí za vyřešení alespoň 4 z 5 zadaných domácích úkolů. Úkoly najdete na stránce přednášejícího.

datum co jsme dělali
8. 10. „Zoologie“ datových struktur. Vyvažování vyhledávacích stromů, zejména AVL-stromy a amortizovaná rekonstrukce.
22. 10. Počítání s potenciály. Ještě jednou amortizovaná konstrukce vyhledávacích stromů. Dvě verze (a,b)-stromů a zacházení s nimi. Amortizovaná složitost Insertu a Deletu ve (2,3)-stromech a (2,4)-stromech. Kouzelný potenciál 2 1 0 2 4.
5. 11. Rozbor prvního domácího úkolu: interní a externí třídění, jak si pořídit rychlé I/O, triky v implementaci QuickSortu.
19. 11. Rozbor druhého domácího úkolu: chování (a,b)-stromů. Splay stromy: Access Theorem, váhy vrcholů, statická optimalita, co udělají rotace místo dvojrotací.
3. 12. Rozbor třetího domácího úkolu: Splay stromy a srovnání naivní implementace s poctivou. Hrátky s cache-aware a cache-oblivious algoritmy: jiný pohled na vEB reprezentaci stromů, násobení matic a Z-ková reprezentace.
17. 12. Dynamické cache-oblivious struktury: Ordered File Maintenance, jeho kombinace s vEB reprezentací stromu, zrychlení indirekcí.
7. 1. Rozbor čtvrtého domácího úkolu: Transpozice matic a její spletité chování na simulátoru i na reálném hardwaru.
Stránku spravuje Martin Mareš