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. Koucký: Lecture notes on data structures (in Czech + math), Winter 2021/2022.
- 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, 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
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.