Vybrané kapitoly z datových struktur

V zimním semestru 2021/2022 přednášíme společně s Matejem Lieskovským a Ondrou Mičkou přednášku o pokročilých datových strukturách [NTIN110]. Jejím cílem je podívat se o něco dále, než kam dohlédneme v základním magisterském kursu Datové struktury 1+2. Předmět si můžete zapisovat opakovaně, každý rok děláme něco jiného.

Přednáška se koná v úterý od 12:20 v S322.

datum téma zdroje
5. 10. Streaming algoritmy: model, hledání častých prvků (Misra-Gries). Chakrabati: Data stream algorithms
12. 10. Streaming algoritmy: odhad počtu různých prvků (AMS, BJKST).
2. 11. Konzultace: Streaming grafové algoritmy (kapitoly 13 a 14 z Chakrabatiho).
16. 11. Konzultace: Kukaččí hešování. Valiant, Wootters: Balls in Bins and Power-of-Two-Choices
Pagh, Rodler: Cuckoo Hashing
Slidy ze Stanfordu: dvě tabulky, jedna tabulka
30. 11. Konzultace: Tabelační hešování. Thorup: Fast and Powerful Hashing using Tabulation
Pătrașcu, Thorup: The Power of Simple Tabulation Hashing

Odkazy

Stránku spravuje Martin Mareš