Data Structures 1
LS 2024/2025
NTIN066 - 2/2 Zk/Z
Michal Koucký
<koucky@iuuk.mff.cuni.cz>
Lecture time: Tue 9:00-10:30.
Lecture room: S3, Malá Strana.
The basic course about construction of efficient data structures, mandatory for Master's students. Search trees, hashing, structures for working with strings. Worst-case, average-case and amortized complexity of data structures. Self-adjusting data structures. Behavior of data structures on systems with memory hierarchy. The lecture builds on the lectures Algorithmization, Algorithms and Data Structures 1 and Algorithms and Data Structures 2 from the bachelor study.
Sylabus
- Amortized and worst-case complexity
- Trees, BB-α trees, (a,b)-trees, splay trees
- Techniques for memory hierarchy
- Hashing, choice of hash functions: universal hash functions, k-indepenence
- Linear probing, cuckoo hashing, bloom filter
- Text data structures, suffix tree, suffix array
- Parallel data structures
- Multidimensional data structures
- K-d trees
- Range trees
Study materials
- P. Gregor: Previous year English lectures, Summer 2023/2024.
- J. Fink: Previous semester Czech lectures, Winter 2024/2025.
- M. Mareš: Lecture notes on data structures, 2019-2024, and recording of his lectures.
- M. Mareš, T. Valla: Průvodce labyrintem algoritmů, CZ.NIC, 2017.
- D. P. Mehta, S. Sahni eds.: Handbook of Data Structures and Applications. Chapman & Hall/CRC, Computer and Information Series, 2005.
- D.D. Sleator, R.E. Tarjan: Self-Adjusting Binary Search Trees. J. ACM 32 (3): 652–686, 1985.
- E. Demaine: Cache-Oblivious Algorithms and Data Structures. 2002.
- M. Thorup: High Speed Hashing for Integers and Strings. lecture notes, 2014.
- M. Thorup: String hashing for linear probing (Sections 5.1-5.4). In Proc. 20th SODA, 655-664, 2009.
- D.E. Knuth: The Art of Computer Programming: Volume 3: Sorting and Searching, 2nd edition, Addison-Wesley, 1998
- Erik Demaine, and Srinivas Devadas: Introduction to Algorithms (6.006). MIT OpenCourseWare, Fall 2011. Video lectures
- Erik Demaine, Srinivas Devadas, and Nancy Lynch: Design and Analysis of Algorithms (6.046J). MIT OpenCourseWare, Spring 2015. Video lectures
- Eric Grimson, and John Guttag: Introduction to Computer Science and Programming (6.00). MIT OpenCourseWare, Fall 2008. Video lectures
- Donald E. Knuth: The art of computer programming. Volume 3, Sorting and searching. Addison-Wesley, 1973. Available in our library.
Tutorials
Tutorials are 90 minutes. Credits are given based on the homeworks, details will be provided by the tutorial teachers.
Tutorial dates:
Exam
To pass the course, you need to pass an exam and get a credit from the tutorials.
The exam is oral and covers material that was covered during the lectures.