Data Structures 2
V letním semestru 2025/2026 přednáším Datové struktury II [NTIN067].
Přednáška se koná v úterky od 15:40 v S8.
If you want to consult anything, please write an e-mail to mares+ds@kam.mff.cuni.cz and we will discuss possibilities.
| datum | téma | zdroje | záznam |
|---|---|---|---|
| 19. 2. | Výpočetní model Word-RAM. Různé způsoby statické reprezentace slovníků. Perfektní hešování FKS v univerzálních systémů funkcí. Poznámka o třídění reálných čísel. Deterministické statické slovníky: redukce obecného univerza na polynomiální (toliko náčrt) a polynomiálního na kvadratické (n-ární trie), princip permutování bodů v matici, použití ke konstrukci perfektního hešování. | [P01] [FKS] [HMP] [S2.1] | |
| 4. 3. | Plan: Dokončení statických slovníků: důkaz lemmatu, randomizovaná konstrukce řádkových permutací, derandomizace pomocí podmíněných středních hodnot. Uspořádané celočíselné struktury: van Emde-Boasovy stromy pomocí rekurzivního dělení na přihrádky. | [P01] [HMP] [P02] [G] |
Materiály
Předchozí běhy přednášky
- 2024 (anglicky, s videozáznamy)
- 2022 (anglicky, s videozáznamy)
- 2020 (česky, s videozáznamy)
- 2018 (česky)
- 2016 (česky, s videozáznamy)
Literatura:
- [D] Martin Mareš: Lecture notes on data structures
- [E] Erik Demaine: přednáška Advanced Data Structures z MIT
- [EC] Erik Demaine: Cache-Oblivious Algorithms and Data Structures (lecture notes)
- [G] Martin Mareš: Krajinou grafových algoritmů
- [H] Handbook of Data Structures and Applications (dostupné online z univerzitní sítě)
- [P] Martin Mareš: Poznámky k DS2 (sken)
- [S] Martin Mareš: The Saga of Minimum Spanning Trees, dizertační práce na MFF UK, 2008
- [DS] Driscoll, Sarnak, Sleator, Tarjan: Making Data Structures Persistent, Proceedings of STOC, 1986
- [FKS] Fredman, Komlós, Szemerédi: Storing a Sparse Table with O(1) Worst Case Access Time, Journal of ACM, 1984
- [HMP] Hagerup, Miltersen, Pagh: Deterministic Dictionaries, Journal of Algorithms, 2001
- [M] Kurt Mehlhorn: Data Structures and Algorithms (digitální verze knihy)
- [MP] Michal Pokorný: Practical Data Structures, bachelor thesis at MFF UK, 2015
- [MS] Milan Straka: Functional Data Structures and Algorithms, dizertační práce na MFF UK, 2013
- [SE] Seidel: Union Find (prezentace k přednášce)
- [STa] Sleator, Tarjan: A Data Structure for Dynamic Trees, Journal of Computer and System Sciences, 1983
- [STb] Sleator, Tarjan: Self-Adjusting Binary Search Trees, Journal of the ACM, 1985
- [TL] Tarjan, van Leeuwen: Worst-Case Analysis of Set Union Algorithms, Journal of the ACM, 1984 (původní analýza, na přednášce nepoužito)