Data Structures I

Previous year: 2018/19 EN (by Martin Mareš)

Schedule: Monday 17:20-18:50, room S5.
Lecturer: Petr Gregor (gregor(at)ktiml.mff.cuni.cz)
Information on the lecture: 2/1 Zk+Z NTIN066 in SIS

List of lectures
Here will be a list of topics covered by each lecture with a reference to study materials. For a plan of lectures see the previous year.

• 17.02. Lecture 1: Introduction, model of computation, amortized complexity, examples. [L01]
• 24.02. Lecture 2: Amortized complexity: potentials. Lazily balanced trees. Splay trees (without analysis of splaying cost). [L01-2] [ST]
• 02.03. Lecture 3: Splay trees: alternative Insert and Delete, amortized (weighted) analysis, static optimality, working set bound (without proof). [L02] [ST]
• 09.03. Lecture 4: (a,b)-trees: definition, operations, choice of parameters. Amortized bounds for (a,2a-1) and (a,2a)-trees. Top-down splitting and joining. [L03]
• 16.03. Lecture 5: Heaps: binary and d-regular heaps, strict and lazy binomial heaps, Fibonacci heaps. Use in Dijkstra's algorithm. [L04] Limnu board.
• 23.03. Lecture 6: Memory hierarchy: hardware caches, theoretical models, cache-aware and cache-oblivious algorithms. Mergesort, matrix transposition. [L05] [CO] Limnu board.
• 30.03. Lecture 7: Cache-oblivious algorithms: matrix transposition. Model versus reality: competitivity of LRU. [L05] [CO] Limnu board.
• 06.04. Lecture 8: Hashing: with chaining. c-universal families, expected length of chains, constructions from linear congruence / multiply-shift / scalar product. [L06] Limnu board.
• 13.04. no lecture
• 20.04. Lecture 9: Hashing: k-independent families, compositions of hashing families. Rolling hashes, hashing strings. [L06] [Tb] Limnu board.
• 27.04. Lecture 10: Hashing: Tabulation hashing, cuckoo hashing, linear probing. [L06] [T] [Tb] Limnu board.
• 04.05. Lecture 11: Bloom filters: single-band, multi-band, counting filters. [L06] Limnu board.
• 11.05. Lecture 12: Geometric data structures: range queries, k-d trees, range trees. [L07] [M7] Limnu board.
• 18.05. Lecture 13: Suffix array, LCP array, applications. Constructions of LCP array (Kasai's algorithm) and suffix array (doubling). [L08] Limnu board.

Recommended literature

• [L] M. Mareš, Lecture notes on data structures, 2019.
• [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.

Additional recommended course
There is an (optional) extension course called Implementation of Data Structures taught this term by Jiří Fink.

Exam
The exam will be oral with written preparation. Details on the form and extent of the exam are specified here. The credit from the practicals is required to pass the course, but not necessary to sign up for the exam. Exam dates will be available in SIS.

Consultation hours
After the lecture or by an (email) appointment.