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. Plán: Cache-oblivious třídění.
Stránku spravuje Martin Mareš