Data Structures I

The essential class about construction of efficient data structures. Search trees, heaps, hashing. Worst-case, average-case and amortized complexity of data structures. Self-adjusting data structures. Behavior and analysis of data structures on systems with memory hierarchy. The lecture builds on the lectures Algorithms and Data Structures I and II and Programming I and II from the bachelor study.

Basic information

  • English tutorials for Data Structures I (NTIN066)
  • Schedule: Every Wednesday from 15:40 at S11
  • Lecture by Petr Gregor
  • The second tutorial by David Mareček
  • Summer semester 2025/26

Passing conditions

  • Assignments are provided on Git.
  • Solutions should be submitted by ReCodExu.
All rules are available here.

Colleagues

More study materials can be found on the following websites.

Past tutorials

1. tutorial on 18.2.
  • Introduction
  • Heap and Dijkstra's algorithm
2. tutorial on 25.2.
  • Binary search trees
  • Single and double rotations
  • Splay trees and operations Find, Insert, Delete
  • Amortized complexity and dynamic array

Study material

  1. Martin Mareš: Lecture notes on data structures and recording of his lectures
  2. Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů. CZ.NIC, 2017. On-line and in our library.
  3. D. P. Mehta, S. Sahni eds.: Handbook of Data Structures and Applications. Chapman & Hall/CRC, Computer and Information Series, 2005, Accessible on-line or through library.
  4. D.D. Sleator, R.E. Tarjan: Self-Adjusting Binary Search Trees. J. ACM 32 (3): 652–686, 1985.
  5. E. Demaine: Cache-Oblivious Algorithms and Data Structures. 2002.
  6. M. Thorup: High Speed Hashing for Integers and Strings. lecture notes, 2014.
  7. M. Thorup: String hashing for linear probing (Sections 5.1-5.4). In Proc. 20th SODA, 655-664, 2009.
  8. D.E. Knuth: The Art of Computer Programming: Volume 3: Sorting and Searching, 2nd edition, Addison-Wesley, 1998
  9. Erik Demaine, and Srinivas Devadas: Introduction to Algorithms (6.006). MIT OpenCourseWare, Fall 2011. Video lectures
  10. Erik Demaine, Srinivas Devadas, and Nancy Lynch: Design and Analysis of Algorithms (6.046J). MIT OpenCourseWare, Spring 2015. Video lectures
  11. Eric Grimson, and John Guttag: Introduction to Computer Science and Programming (6.00). MIT OpenCourseWare, Fall 2008. Video lectures
  12. Donald E. Knuth: The art of computer programming. Volume 3, Sorting and searching. Addison-Wesley, 1973. Available in our library.
Useful links: Catalogue of our library, access to electronic versions of some librarian's books and list of other databazes.