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 |