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. |