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 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
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.
Stránku spravuje Martin Mareš