Data Structures 2
I am teaching Data Structures II [NTIN067] in the summer semester of 2021/2022. We meet on Tuesdays from 15:40 in S3.
If you want to consult anything, please write an e-mail to firstname.lastname@example.org and we will discuss possibilities.
|15. 2.||Our model of computation: the Word-RAM. Static dictionary problem. FKS perfect hashing built from universal systems of hash functions. A remark on sorting of reals. HMP hashing: reduction of universe to polynomial (just sketch) and then to quadratic (n-ary trie).||[P01] [FKS] [S2.1]||video|
|22. 2.||Deterministic static dictionaries: principle of permuting points in a grid, application to construction of HMP perfect hashing. Randomized construction of row permutations, derandomization using conditional expectation.||[P01] [HMP]||video|
|1. 3.||Structures for ordered sets of integers: van Emde-Boas trees based on recursive subdivision to buckets. A trick for implicit initialization of memory. vEB interpreted as a binary range tree: easier, but with slower updates.||[P02] [G] [E11]||video|
|8. 3.||Generalized vEB trees: storing just ones (x-fast tries), speedup by indirection (y-fast tries). Heaps: binary, d-regular. Binomial trees.||[P02] [D4]||video|
|15. 3.||Heaps: Binomial, lazy binomial, Fibonacci.||[D4]||video|
|22. 3.||Splay trees: weighted analysis, static optimality, static finger bound, working set bound, hypothesis on dynamic optimality.||[D2.3] [STb]||video|
|29. 3.||Introduction to data structures for graphs. Representation of static paths based on range trees with lazy propagation of updates. Heavy-light decomposition of trees. Link-Cut trees: interface, idea of thick-thin decomposition.||[P03]||video|
|5. 4.||Link-cut trees: dynamic decomposition based on interconnected Splay trees. Application on Dinitz's maximum flow algorithm. Intermezzo: Static structure for interval evaluation of an associative operation.||[P03] [STa] [STb]||video|
|12. 4.||Union-Find (incremental maintenance of connected components): representation based on trees, Union by rank, path compression. Amortized analysis of path compression.||[P04] [SE] [TL]||video|
|19. 4.||Union-Find continued: Amortized analysis of path compression: O(log n) for path compression only, O(α(n)) when combined with Union by rank.||[P04] [SE] [TL]||video|
|26. 4.||Making data structures dynamic: Full and partial rebuilds, semi-dynamization of 2D range trees using partial rebuilds. Separable search problems and their dynamization using decomposition to exponentially-sized blocks: amortized and worst-case semi-dynamization, amortized full dynamization.||[P05] [M7]||video|
|3. 5.||Making data structures persistent: ephemeral, semi-persistent, fully persistent, and functional data structures. Techniques: path copying, fat nodes, combination of both. General transform of pointer-based data structures to semi-persistent, a sketch of full persistence. Application: planar point location. Maintaining linear order: list order, list labelling.||[P05] [DS] [MS]||video|
|10. 5.||No lecture today.|
|17. 5.||Cache-oblivious data structures: packed memory array (list labelling with linear range), cache-aware B-trees, van Emde-Boas layout of binary trees, cache-oblivious B-trees.||[P06] [EC] [MP]||video|
There are exam dates listed in SIS. Please sign up there or send me an e-mail if no date suits you.
You are expected to know the material from the lectures (data structures and theorems on their properties; see the catalog of requirements), to understand it, and to be able to modify the data structures to solve similar problems.
You are allowed to bring a cheat sheet on a single A4 page.
Previous runs of the lecture:
- [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ů (Czech)
- [H] Handbook of Data Structures and Applications (accessible online from university network)
- [P] Martin Mareš: My notes (scanned, Czech)
- [S] Martin Mareš: The Saga of Minimum Spanning Trees, PhD Thesis at 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 (digital version of the book)
- [MP] Michal Pokorný: Practical Data Structures, bachelor thesis at MFF UK, 2015
- [MS] Milan Straka: Functional Data Structures and Algorithms, PhD thesis at MFF UK, 2013
- [SE] Seidel: Union Find (lecture slides)
- [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 (original analysis, not used at our lecture)