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 chcete cokoliv konzultovat, napište mi prosím e-mail na mares+ds@kam.mff.cuni.cz a domluvíme se.

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á.
13. 12.	Binomiální haldy: konsolidace párováním, různé varianty amortizovaných cen operací, kešování minima, Decrease a Increase. Fibonacciho haldy: souvislost s binomiálními stromy (není to inkluze!), cesta ranku 1, proč je potřeba značit vrcholy.
3. 1.	Stavebnice hešovacích funkcí.