Data Structures I

Previous years: 2024/25 EN (by Michal Koucký), 2023/24 EN, 2022/23 EN (by Martin Mareš)

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

Plan of lectures

• 18.02. Lecture 1: Introduction, model of computation, amortized complexity, examples. [L01]
• 25.02. Lecture 2: Amortized complexity: potentials. Lazily balanced trees. Splay trees (introduction). [L01-2] [ST]
• 04.03. Lecture 3: Splay trees: operations, amortized (weighted) analysis, static optimality. [L02] [ST]
• 11.03. Lecture 4: (a,b)-trees: definition, operations, choice of parameters, variants. Modification costs in (a,2a-1)-trees. [L03]
• 18.03. Lecture 5: Amortized bound for (a,2a)-trees. Memory hierarchy: hardware caches, theoretical models, cache-aware and cache-oblivious algorithms. Mergesort. [L05] [CO]
• 25.03. Lecture 6: Multiway mergesort. Cache-aware and cache-oblivious algorithms: matrix transposition. Model versus reality: LRU strategy. [L05] [CO]
• 01.04. Lecture 7: LRU competitivity. Hashing: with chaining. c-universal families, expected length of chains, constructions from scalar product / linear congruence. [L06]
• 08.04. Lecture 8: Hashing: k-independent families, compositions mod m. Tabulation hashing, cuckoo hashing. [L06] [Tb]
• 15.04. Lecture 9: Hashing: with linear probing and its analysis. [L06] [T] [Tb]
• 22.04. Lecture 10: Hashing of strings, rolling hashing. Bloom filters: simple, multi-band, single-band, counting filters. [L06] [Tb]
• 29.04. Lecture 11: Suffix array, LCP array, applications. Constructions of LCP array (Kasai's algorithm) and suffix array (doubling). [L08]
• 06.05. Lecture 12: Geometric data structures: range queries, k-d search trees, range trees. [L07] [M7]
• 13.04. no lecture
• 20.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, 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.
• D.E. Knuth: The Art of Computer Programming: Volume 3: Sorting and Searching, 2nd edition, Addison-Wesley, 1998, available in our library.
• E. Demaine, and S. Devadas: Introduction to Algorithms (6.006). MIT OpenCourseWare, Fall 2011. Video lectures
• E. Demaine, S. Devadas, and N. Lynch: Design and Analysis of Algorithms (6.046J). MIT OpenCourseWare, Spring 2015. Video lectures
• E. Grimson, and J. Guttag: Introduction to Computer Science and Programming (6.00). MIT OpenCourseWare, Fall 2008. Video lectures

Video recordings from the year 2022/23 are available here (by Martin Mareš).

Tutorials
The lecture is accompanied by tutorials on Mondays at 9:00-10:30 in S6 (by David Mareček) or on Wednesday at 15:40-17:10 in S11 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.