Vybrané kapitoly z datových struktur
V zimním semestru 2024/2025 přednáším o pokročilých datových strukturách [NTIN110]. 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 úterky od 15:40 v pracovně S322. Začínáme 8. 10.
Pokud chcete cokoliv konzultovat, napište mi prosím e-mail na mares@kam.mff.cuni.cz a domluvíme se.
| datum | téma |
|---|---|
| 8. 10. | Persistentní deque a c-steque. |
| 15. 10. | Konfluentně persistentní trie. |
| 22. 10. | Úvod do úsporných datových struktur. Reprezentace binárních stromů à la halda. Indexy pro Rank a Select v sublineárním prostoru. Reprezentace pěstovaných a binárních stromů pomocí závorek. |
| 29. 10. | Match a Enclose na posloupnosti závorek. |
| 5. 11. | Přednáška se nekoná: děkanský sportovní den |
| 12. 11. | TODO |
| 19. 11. | Ještě k závorkám: Rank a Select na uniformně řídkých množinách. Choice dictionaries a párovací struktura pro neinicializovanou paměť. |
Zdroje
- Persistentní struktury:
- Kaplan, Tarjan: Persistent Lists with Catenation via Recursive Slow-Down (deque, c-steque)
- Demaine, Langerman, Price: Confluently Persistent Tries for Efficient Version Control
- Úsporné struktury:
- Demaine: Advanced Data Structures, přednáška 17 (Rank a Select, reprezentace stromů)
- Geary et al.: A simple optimal representation for balanced parentheses (Match a Enclose)
Odkazy
- VKDS 2023: cache-oblivious třídění + datové struktury, zlomkové kaskádování
- VKDS 2022: Q-haldy, Fusion trees, exponenciální stromy, redukce univerza na polynomiální, Marked ancestor a dolní odhad na něj
- VKDS 2021: streaming algoritmy, analýza kukaččího hešování
- VKDS 2020: celočíselné struktury, randomizované stromy, zlomkové kaskádování, lock/wait-free struktury
- PDS 2019: rankové vyvážené stromy, kompetitivní dynamické stromy, cache-oblivious struktury, p/q-fast trie