Pokročilé datové struktury
V zimním semestru 2019/2020 přednášíme společně s Matejem Lieskovským a Ondrou Mičkou přednášku o pokročilých datových strukturách [NTIN110]. Jejím cílem je podívat se o něco dále, než kam dohlédneme v základním magisterském kursu Datové struktury 1+2.
Přednáška se koná v úterý od 12:20 v S11.
| datum | téma | zdroje |
|---|---|---|
| 8. 10. | Rankově vyvážené binární stromy: různá rankova pravidla, 2,3-stromy, WAVL stromy. | Haeupler, Sen, Tarjan: Rank-Balanced Trees |
| 15. 10. | Pokračování z minula. | |
| 22. 10. | Statická a dynamická optimalita Splay stromů. Wilberův dolní odhad pomocí prokládání v referenčních stromech. Tango stromy: základní princip. | Demaine, Harmon, Iacono, Pătraşcu: Dynamic Optimality—Almost |
| 29. 10. | Důkaz prokládacího odhadu. Tango stromy: detaily konstrukce, důkaz kompetitivnosti. | |
| 5. 11. | Multi-splay stromy. Sbírka horních odhadů: sekvenční průchod, entropie, static finger, dynamic finger, working set, unified, deque. | Wang, Derryberry, Sleator: O(log log n)-Competitive Dynamic Binary Search Trees
Demaine: Lecture 05, Lecture 06 |
| 12. 11. | Přednáška se nekoná: Děkanský sportovní den. | |
| 19. 11. | Cache-oblivious třídění: základy, Funnelsort. | Demaine: Cache-Oblivious Algorithms and Data Structures |
| 26. 11. | Cache-oblivious třídění: konstrukce funnelů. | Demaine: Cache-Oblivious Algorithms and Data Structures |
| 3. 12. | Cache-oblivious třídění: dokončení analýzy Funnelsortu, permutační dolní odhad. | Aggarwal, Vitter: The Input/Output Complexity of Sorting and Related Problems |
| 10. 12. | Cache-oblivious třídění: Distribution sort. | Prokop: Cache-oblivious algorithms |
| 17. 12. | Trable s asymptotikou ve více proměnných. | Howell: On Asymptotic Notation with Multiple Variables |
| 7. 1. | p-fast a q-fast trie. | Willard: New data structures which support very fast search operations |
Zkoušky
Na zkoušce se prosím domluvte e-mailem všem třem přednášejícím.
Ke zkoušce si můžete přinést libovolné tištěné materiály.