Cvičení z Datových struktur I
V zimním semestru 2017/2018 cvičím Datové struktury I [NTIN066] ke své přednášce. Cvičení se koná v lichých týdnech od 10:40 v S8.
Pravidla udělování zápočtů a zadání domácích úkolů najdete na webu přednášky.
| datum | co jsme dělali |
|---|---|
| 5. 10. | Konstrukce dokonale vyvážených BVS ze setřiděného pole či posloupnosti (stačí O(log n) pomocné paměti, ale jde to i s konstantní). Jak zadaný BVS dokonale vyvážit. Očekavaná průměrná hloubka vrcholu v BVS vzniklém Inserty v náhodném pořadí je O(log n); souvislost se složitostí QuickSortu. Trik: reprezentace levého/pravého syna + otce pomocí dvou ukazatelů. Jiný trik: reprezentace AVL stromů, které stačí 1 bit vyvažovací informace na vrchol. |
| 19. 10. | Splay stromy: Experimenty se splayováním na levé cestě – (a) Splay(1), (b) střídavě Splay(1) a Splay(n), (c) Splay(1) … Splay(n). Naivní versus poctivé splayování. Nastavování vah: Static Finger Theorem, Working Set Theorem. Hypotéza: Provedeme-li na libovolném stromu postupně Splay(1) … Splay(n), vznikne cesta. |
| 2. 11. | Diskuse o prvním domácím úkolu. Haldy: párovací varianta binomiální haldy, vznik dlouhé cesty ve Fibonacciho haldě. |
| 16. 11. | Cache-oblivious analýza: Quickselect, rekurzivní Mergesort. Simulátor cache. |
| 30. 11. | Diskuse o druhém domácím úkolu. Cache-oblivious analýza: násobení matic v rekurzivním Z-kovém uspořádání. |
| 14. 12. | Diskuse o třetím domácím úkolu. |
| 4. 1. | Diskuse o čtvrtém domácím úkolu. |