Datové struktury 1

Loňská verze: ZS 2019/20 (Martin Mareš), LS 2019/20 (anglická verze).

Rozvrh: čtvrtek 15:40-17:10, Zoom link.
Přednášející: Petr Gregor (gregor(at)ktiml.mff.cuni.cz)
Informace o přednášce: 2/2 Zk+Z NTIN066 v SISu

Oznámení: Přednáška se bude konat dle rozvrhu na platformě Zoom, viz link výše. Pokud jste nedostali pozvánku s heslem či máte jiné potíže s připojením, napište mi. Záznamy z přednášek budou k dispozici v playlistu na Streamu UK.

(Předběžný) plán přednášek

• 01.10. Přednáška 1: Úvod, modely výpočtu, amortizovaná složitost, příklady. [L01] [P9.1–9.2] [video-úvod] [video01]
• 08.10. Přednáška 2: Potenciálová metoda. Líně vyvažované stromy. Splay stromy (bez Delete a analýzy ceny operace Splay). [L01-2] [P9.3–9.5] [ST] [video02]
• 15.10. Přednáška 3: Splay stromy: alternativní Insert a Delete, amortizovaná (vážená) analýza, statická optimalita. [L02][P9.5][ST] [video03]
• 22.10. Přednáška 4: (a,b)-stromy: definice, operace, výběr parametrů, varianty. Amortizované odhady pro (a,2a-1) a (a,2a)-stromy. [L03][P8.3] [video04]
• 29.10. Přednáška 5: Paměťová hierarchie: hardwarové keše, teoretické modely, cache-aware a cache-oblivious algoritmy. Mergesort. [L05] [CO] [video05]
• 05.11. Přednáška 6: Cache-aware a cache-oblivious algoritmy: transpozice matic. Model versus realita: kompetitivní poměr LRU. [L05] [CO] [video06]
• 12.11. Přednáška 7: Hešování: s řetízky. c-univerzální systémy, očekávaná délka řetězce, konstrukce z lineární kongruence / multiply-shift / skalárního součinu. [L06][P11.3] [P11.5] [video07]
• 19.11. Přednáška 8: Hešování: k-nezávislé systémy, skládání hešovacích systémů, tabulační hešování, kukaččí hešování. [L06] [Tb] [video08]
• 26.11. Přednáška 9: Hešování: hešování s lineárním přidáváním, rolující hešování. [L06] [T] [Tb] [video09]
• 03.12. Přednáška 10: Hešování řetězců, bloomovy filtry: 1-pásmové, více-pásmové, počítací filtry. [L06] [Tb] [video10]
• 10.12. Přednáška 11: Suffixová pole, LCP pole, aplikace. Konstrukce LCP pole (Kasaiův algoritmus) a suffixového pole (zdvojováním). [L08] [video11]
• 17.12. Přednáška 12: Geometrické datové struktury: intervalové dotazy, k-d stromy, intervalové stromy. [L07] [M7] [video12]
• 07.01. Přednáška 13: Paralelní (a,b)-stromy, lock-free struktury (zásobník). [video13]

Doporučená literatura

• [L] M. Mareš, Lecture notes on data structures, 2019.
• [P] Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů, CZ.NIC, 2017.
• [CO] E. D. Demaine, Cache-Oblivious Algorithms and Data Structures, 2002.
• [H] D. P. Mehta, S. Sahni, eds., Handbook of Data Structures and Applications, Chapman & Hall/CRC, Computer and Information Series, 2005.
• [M] K. Mehlhorn, Data Structures and Algorithms, Springer Verlag, 1984.
• [ST] D. D. Sleator, R. E. Tarjan: Self-Adjusting Binary Search Trees, Journal of the ACM, 1985.
• [T] M. Thorup: Linear Probing with 5-Independent Hashing, arXiv:1509.04549, 2017.
• [Tb] M. Thorup: High Speed Hashing for Integers and Strings, arXiv:1504.06804, 2019.

Zkouška
Zkouška je ústní s písemnou přípravou. Detaily o formě a rozsahu zkoušky jsou popsány zde. Zápočet ze cvičení je nutný k absolvování předmětu, ale není podmínkou k přihlášení se ke zkoušce. Zkouškové termíny budou vypsány v SISu. Nové: Pravidla pro distanční zkoušky jsou zde.

Důležité: Pokud se jedná o druhý opravný termín při druhém zápisu předmětu, je nutné se ke zkoušce přihlásit alespoň dva dny předem, tj. 48 hodin před záčátkem zkoušky. To platí jak pro distanční, tak i prezenční zkoušky z DS1.

Konzultace
Po domluvě mailem či po přednášce.