Vybrané kapitoly z datových struktur
V zimním semestru 2023/2024 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á ve středu od 10:40 v S322.
Pokud chcete cokoliv konzultovat, napište mi prosím e-mail na mares@kam.mff.cuni.cz a domluvíme se.
| datum | téma |
|---|---|
| 11. 10. | Opakování modelů s vnitřní a vnější pamětí. Cache-aware třídění k-cestným Mergesortem. Permutační dolní odhad. |
| 18. 10. | Opakování vEB uspořádání binárních stromů v paměti. Funnelsort. |
| 25. 10. | Pokračování Funnelsortu. Distribution sort. |
| 1. 11. | Pokračování Distribution sortu. Cache-oblivious B-stromy. |
| 8. 11. | Pokračování C/O B-stromů. Traversal data structure: uložení v paměti. |
| 15. 11. | Pokračování traversal DS: Scan, Insert, Delete, amortizovaný Scan. |
| 22. 11. | Randomizované Packed Memory Array založené na online list labelingu. |
| 29. 11. | Důkaz věty o Zénonově procházce. Cache-oblivious částečně persistentní pole. |
| 6. 12. | Dokončení analýzy persistentního pole. Zlomkové kaskádování: jednoduchý případ pro posloupnost seznamů; katalogové grafy, stíny a mosty, invarianty. |
| 13. 12. | Zlomkové kaskádování: konstrukce, rozbor, zrychlení. |
| 20. 12. | (Semi)dynamizace zlomkového kaskádování a datová struktura pro Split-Find-Add na pointer machine. |
| 3. 1. | Aplikace kaskádování: intervalové dotazy v R3, průsečíky přímek s lomenou čárou. |
| 10. 1. | Randomizované kaskádování, analýza pomocí Galtonova-Watsonova procesu. |
Zdroje
- Fotky tabule
- Cache-oblivious třídění:
- Aggarwal, Vitter: The input/output complexity of sorting and related problems – dolní odhad
- Brodal, Fagerberg: Cache-oblivious distribution sweeping (rozšířená verze článku) – líný Funnelsort
- Prokop: Cache-Oblivious Algorithms – Distribution sort
- Cache-oblivious datové struktury:
- Bender, Demaine, Farach-Colton: Cache-Oblivious B-Trees
- Bender, Cole, Demaine, Farach-Colton: Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy
- Důkaz velikosti widgetu k Traversal DS
- Bender et al.: Online List Labeling: Breaking the log2 n Barrier
- Davoodi, Fineman, Iacono, Özkan: Cache-Oblivious Persistence
- Zlomkové kaskádování:
- Chazelle, Guibas: Fractional cascading: I. A data structuring technique
- Chazelle, Guibas: Fractional cascading: II. Applications
- Imai, Asano: Dynamic segment intersection with applications (Split-Find-Add)
- Hopcroft, Ullman: Set merging algorithms (Split-Find-Add)
- Sen: Fractional cascading revisited (randomizovaná verze)
Zkoušky
Na zkoušku se zapište v SISu nebo domluvte na jindy e-mailem.
Můžete si přinést tahák. Jedinou podmínkou je, že jste ho vytvořili sami.
Odkazy
- 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