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.
The dates of the exams are listed in SIS, where you can also register for the exams. If you sign up for a date, use it or excuse yourself or cancel in time. A missed date will forfeit your attempt, plus the missed date may have been used by one of your classmates. You should already have credit from the exercises before the exam.
You will be tested on the material we have covered during the lectures. Sample exam questions can be found here. The exam is oral. You will have time to prepare after getting the questions. Study materials (notes, textbooks and lecture notes) or laptops, calculators, PDAs, etc. are not allowed on the exam. Formal attire is not required, but appropriate dress is recommended.