Analýza datových struktur

V zimním semestru 2019/2020 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 bude konat každou druhou středu od 9:00 v pracovně S322.

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
16. 10.	Splay stromy: vážená analýza, váhy 1/n, invariance vzhledem k měřítku, statická optimalita, static finger bound, working set bound, zmínka o traversal bound.
30. 10.	Reprezentace trie pomocí propojených Splay stromů. (a,b)-stromy: amortizace počtu změn, hledání relativně k prstu pomocí propojení v rámci hladiny.
13. 11.	Binomiální haldy: kešování minima, různé varianty konsolidace (například párováním). Fibonacciho haldy: souvislost s binomiálními stromy (není to inkluze!), jak se staví cestička.
27. 11.	Fibonacciho haldy: proč je potřeba značit vrcholy. Cache-aware a cache-oblivious techniky: binární vyhledávání, (a,b)-stromy, van Emde-Boasovské uložení binárních stromů.
11. 12.	Systémy hešovacích funkcí: (k,c)-nezávislost implikuje (k-1,c)-nezávislost. (2,c)-nezávislost implikuje c-universalitu. Nezávislost tabelačního hešování. 2-nezávislá verze skalárních součinů.
8. 1.	Cvičení pro nemoc odpadlo. O zápočet mi prosím napište.