Data Structures I

Previous year: 2022/23 EN (by Martin Mareš), 2021/22 EN

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

Plan of lectures

• 19.02. Lecture 1: Introduction, model of computation, amortized complexity, examples. [L01]
• 26.02. Lecture 2: Amortized complexity: potentials. Lazily balanced trees. Splay trees (introduction). [L01-2] [ST]
• 04.03. no lecture
• 11.03. Lecture 3: Splay trees: operations, amortized (weighted) analysis, static optimality. [L02] [ST]
• 18.03. Lecture 4: (a,b)-trees: definition, operations, choice of parameters, variants. Modification costs in (a,2a-1)-trees. [L03]
• 25.03. Lecture 5: Amortized bound for (a,2a)-trees. Memory hierarchy: hardware caches, theoretical models, cache-aware and cache-oblivious algorithms. Mergesort. [L05] [CO]
• 01.04. no lecture
• 08.04. Lecture 6: Multiway mergesort. Cache-aware and cache-oblivious algorithms: matrix transposition. Model versus reality: LRU strategy. [L05] [CO]
• 15.03. Lecture 7: Hashing: with chaining. c-universal families, expected length of chains, constructions from scalar product / linear congruence. [L06]
• 22.04. Lecture 8: Hashing: k-independent families, compositions mod m. Tabulation hashing, cuckoo hashing, hashing with linear probing. [L06] [Tb]
• 29.04. Lecture 9: Hashing of strings, rolling hashing. Bloom filters: simple, multi-band, single-band, counting filters. [L06] [Tb]
• 06.05. Lecture 10: Suffix array, LCP array, applications. Constructions of LCP array (Kasai's algorithm) and suffix array (doubling). [L08]
• 13.05. Lecture 11: Geometric data structures: range queries, k-d search trees, range trees. [L07] [M7]
• 20.05. Lecture 12: Parallel data structures: (a,b)-trees, lock-free and wait-free data structures, lock-free stack. [L09]

Recommended literature

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

Video recordings from the previous year are available here (by Martin Mareš).

Tutorials
The lecture is accompanied by tutorials on Tuesday at 10:40-12:10 in S10 (by David Mareček) or on Friday at 12:20-13:50 in S8 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.