Vybrané kapitoly z datových struktur

V zimním semestru 2020/2021 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.

Navazujeme na naši loňskou přednášku Pokročilé datové struktury.

Přednášky se budou konat online, odkaz na Zoom vám přišel e-mailem.

datum téma zdroje záznam
8. 10. Stručné (succinct) datové struktury: reprezentace binárních stromů, rank a select na řetězcích bitů, operace se závorkami. Demaine: Lecture 17 video
15. 10. Celočíselné datové struktury: Word-RAM a jeho varianty (Céčkové instrukce vs. AC0). Vektorové výpočty pomocí aritmetiky. Opakovaní fusion trees a fusion nodes, problémy s počítáním sketchů. Q-haldy: předvýpočet funkcí, aplikace na minimální kostry (Fredmanův-Willardův algoritmus). Poznámky z Datových struktur 2
Mareš: The Saga of Minimum Spanning Trees (kapitoly 2.1, 2.3, 2.4)
video tabule
22. 10. Q-haldy: stav struktury, implementace operací, velmi-pseudo-sketche a dekodér. Fredman, Willard: Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths
Mareš: The Saga of Minimum Spanning Trees (kapitola 2.5)
video tabule
29. 10. Q-haldy: zbylé části dekodéru. Skip listy. Pugh: Skip Lists: A Probabilistic Alternative to Balanced Trees video tabule
5. 11. Randomizované vyhledávací stromy: BST vzniklé inserty z náhodné posloupnosti; randomized binary search tree; treap. Aragon: Treaps
Martínez & Roura: Randomized Binary Search Trees
video tabule
12. 11. Úvod do fractional cascadingu: prohledávání K setříděných polí délky L v čase O(K + log L). Cache-oblivious lookahead array. Bender et al.: Cache-Oblivious Streaming B-Trees video tabule
19. 11. Fractional cascading: katalogové grafy, mosty a díry, část budovacího algoritmu. Chazelle, Guibas: Fractional cascading: I. a data structuring technique video tabule
26. 11. Fractional cascading: zbytek budovacího algoritmu, amortizovaná analýza, zrychlená verze, náhrada binárního vyhledávání. Aplikace: DS pro průsečíky lomené čáry s přímkami. Chazelle, Guibas: Fractional cascading: II. applications video tabule
3. 12. Plán: Paralelní datové struktury.
Stránku spravuje Martin Mareš