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