Data Structures 2

I am teaching Data Structures II [NTIN067] in the summer semester of 2025/2026.

The lectures will be on Tuesdays from 15:40 in S6.

If you want to consult anything, please write an e-mail to mares+ds@kam.mff.cuni.cz and we will discuss possibilities.

Course material

Previous runs of the lecture:

Literature:

[D] Martin Mareš: Lecture notes on data structures
[E] Erik Demaine: přednáška Advanced Data Structures z MIT
[EC] Erik Demaine: Cache-Oblivious Algorithms and Data Structures (lecture notes)
[G] Martin Mareš: Krajinou grafových algoritmů (Czech)
[H] Handbook of Data Structures and Applications (accessible online from university network)
[P] Martin Mareš: My notes (scanned, Czech)
[S] Martin Mareš: The Saga of Minimum Spanning Trees, PhD Thesis at MFF UK, 2008
[DS] Driscoll, Sarnak, Sleator, Tarjan: Making Data Structures Persistent, Proceedings of STOC, 1986
[FKS] Fredman, Komlós, Szemerédi: Storing a Sparse Table with O(1) Worst Case Access Time, Journal of ACM, 1984
[HMP] Hagerup, Miltersen, Pagh: Deterministic Dictionaries, Journal of Algorithms, 2001
[M] Kurt Mehlhorn: Data Structures and Algorithms (digital version of the book)
[MP] Michal Pokorný: Practical Data Structures, bachelor thesis at MFF UK, 2015
[MS] Milan Straka: Functional Data Structures and Algorithms, PhD thesis at MFF UK, 2013
[SE] Seidel: Union Find (lecture slides)
[STa] Sleator, Tarjan: A Data Structure for Dynamic Trees, Journal of Computer and System Sciences, 1983
[STb] Sleator, Tarjan: Self-Adjusting Binary Search Trees, Journal of the ACM, 1985
[TL] Tarjan, van Leeuwen: Worst-Case Analysis of Set Union Algorithms, Journal of the ACM, 1984 (original analysis, not used at our lecture)