Analýza datových struktur

V zimním semestru 2018/2019 povedu rozšiřující cvičení [NTIN105] k Datovým strukturám I [NTIN066]. Rád bych se na něm trochu hlouběji věnovat návrhu a analýze datových struktur, které zazněly na přednášce, ale na jejich zkoumání není na klasickém cvičení čas.

Cvičení se koná každý lichý čtvrtek semestru od 9:00 v pracovně S322 nebo na chodbě před ní. Začínáme 18. října.

Zápočet se uděluje za aktivní účast na cvičení.

Pokud se mnou chcete cokoliv probrat, jste vítáni v mé pracovně S322 na Malé Straně. Případně napište e-mail na adresu mares+ds@kam.mff.cuni.cz.

datum téma
18. 10. Splay stromy: vážená analýza, váhy 1/n, invariance vzhledem k měřítku, statická optimalita, static finger bound, working set bound.
1. 11. Splay stromy: důkaz working set bound, zmínka o traversal bound, různé implementace Insertu. Reprezentace trie pomocí propojených Splay stromů. Modelování posloupností, move-to-front kodér.
15. 11. Cache-aware a cache-oblivious techniky. Mergesort, (a,b)-stromy, van Emde-Boasovo uložení binárních stromů.
29. 11. Cvičení pro nemoc odpadá.
Stránku spravuje Martin Mareš