Data Structures I

Previous year: 2020/21 EN (by Martin Mareš), 2019/20 EN

Schedule: Monday 12:20-13:50, room S5 and over Zoom. You should have received a link for Zoom by email. If not, please let me know.
Lecturer: Petr Gregor (gregor(at)ktiml.mff.cuni.cz)
Information on the lecture: 2/1 Zk+Z NTIN066 in SIS

Plan of lectures

• 14.02. Lecture 1: Introduction, model of computation, amortized complexity, examples. [L01]
• 21.02. Lecture 2: Amortized complexity: potentials. Lazily balanced trees. Splay trees (introduction). [L01-2] [ST]
• 28.03. Lecture 3: Splay trees: operations, amortized (weighted) analysis, static optimality. [L02] [ST]
• 07.03. Lecture 4: (a,b)-trees: definition, operations, choice of parameters, variants. Modification costs in (a,2a-1)-trees. [L03]
• 14.03. Lecture 5: Amortized bound for (a,2a)-trees. Memory hierarchy: hardware caches, theoretical models, cache-aware and cache-oblivious algorithms. Mergesort. [L05] [CO]
• 21.03. Lecture 6: Multiway mergesort. Cache-aware and cache-oblivious algorithms: matrix transposition. Model versus reality: LRU strategy. [L05] [CO]
• 28.03. Lecture 7: LRU competitivity. Hashing: with chaining. c-universal families, expected length of chains, constructions from scalar product / linear congruence. [L06]
• 04.04. Lecture 8: Hashing: k-independent families, compositions mod m. Tabulation hashing, cuckoo hashing. [L06] [Tb]
• 11.04. Lecture 9: Hashing: with linear probing and its analysis. [L06] [T] [Tb]
• 18.04. no lecture
• 25.04. Lecture 10: Hashing of strings, rolling hashing. Bloom filters: simple, multi-band, single-band, counting filters. [L06] [Tb]
• 02.05. Lecture 11: Suffix array, LCP array, applications. Constructions of LCP array (Kasai's algorithm) and suffix array (doubling). [L08]
• 09.05. Lecture 12: Geometric data structures: range queries, k-d search trees, range trees. [L07] [M7]
• 16.05. Lecture 13: 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, 2021.
• [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 Wednesdays at 9:00-10:30 in S8 or at 12:20-13:50 in S1, both taught by David Mareček.

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. New: Rules for distance exams.

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