Česká přednáška zde.

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 Monday from 12:20 in S8
  • Lecture by Michal Koucký
  • The second tutorial by Petr Chmel
  • Summer semester 2024/25

Examination

Students enrolled in winter semester can only be examined by me, and students enrolled in summer semester can only be examined by Michal Koucký. For students enrolled in winter semester, there will be one exam date in June and one in September. The exact dates will be determined later.

Passing conditions

  • Assignments are provided on Git.
  • Solutions should be submitted by ReCodExu.

Overview

  • There are 7 programming assignments per 10 points
  • and 3 experimental assignments per 15 points
  • You need 75 points for class credit
  • Deadline: usually 2 weeks
  • General rules are here.

Programming assignments

  • You are given a partial implementation of a DS
  • Implement the missing bits
  • Automatic checking, tests are public
  • Instructor looks at the source code
  • C++ and (usually) Python available

Experimental assignments

  • Measure properties of a given implementation
  • Write a report (and submit PDF)

Colleagues

More study materials can be found on the following websites.

Past tutorials

1. tutorial on 17.2.
  • Introduction
  • Amortized complexity and dynamic array
2. tutorial on 24.2.
  • Amortized complexity and dynamic array
  • Binary search trees
  • Single rotations
3. tutorial on 3.3.
  • Single and double rotations
  • Splay trees
4. tutorial on 10.3.
  • Properties of Splay trees
  • Static optimal trees and their relation to Splay trees
5. tutorial on 17.3.
  • (a,b)-trees
6. tutorial on 24.3.
  • Cache oblivious vs. aware computation models
  • Matrix transposition
7. tutorial on 31.3.
  • Matrix transposition
  • Heaps
  • Merge-sort, Quick-sort, Heap-sort
8. tutorial on 7.4.
  • Linear probing
  • Cuckoo hashing
  • Separate chaining
9. tutorial on 14.4.
  • Hash functions

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.