# 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 Friday from 12:20 in S8
- Lecture by Petr Gregor
- Summer semester 2023/24

## Passing conditions

### 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

### 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)

### General rules

- Feel free to talk about assignments with other people, but do not share code nor reports (except with the instructor).
- Deadlines are strict.
- Before deadline, you can re-submit.
- The code must pass all tests.
- Quality of your code and reports contributes to grading.
- Do not use non-trivial code you didn't write yourself. This includes other peoples' implementations and non-obvious library functions. Trivial cases of growing arrays (appending to std::vector in C++ or list.append() in Python) are permitted, anything more complicated isn't. When in doubt, ask your instructor.
- All theorems used in your reports must be stated in full and their source must be properly cited. If the theorem was stated at the lecture, citing the lecture is considered sufficient.

### Colleagues

More study materials can be found on the following websites.### Past tutorials

- 1. tutorial on 23.2.
- Introduction
- Amortized complexity
- Variants of growing arrays

- 2. tutorial on 1.3.
- Binary search trees
- Single and double rotations
- Splay trees

- 3. tutorial on 15.3.
- Properties of Splay trees
- Static optimal trees and their relation to Splay trees

- 4. tutorial on 22.3.
- (a,b)-trees

- 5. tutorial on 12.4.
- Cache oblivious vs. aware computation models
- Matrix transposition

- 6. tutorial on 19.4.
- Introduction to hashing

- 7. tutorial on 26.4.
- Linear probing, Cuckoo hashing
- k-independent hashing

- 8. tutorial on 3.5.
- Bloom filter
- Counting filter
- Tabular hashing

## Study material

- Martin Mareš: Lecture notes on data structures and recording of his lectures
- Martin Mareš, Tomáš Valla:
*Průvodce labyrintem algoritmů*. CZ.NIC, 2017. On-line and in our library. - 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. - 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 - Erik Demaine, and Srinivas Devadas:
*Introduction to Algorithms (6.006)*. MIT OpenCourseWare, Fall 2011. Video lectures - Erik Demaine, Srinivas Devadas, and Nancy Lynch:
*Design and Analysis of Algorithms (6.046J)*. MIT OpenCourseWare, Spring 2015. Video lectures - Eric Grimson, and John Guttag:
*Introduction to Computer Science and Programming (6.00)*. MIT OpenCourseWare, Fall 2008. Video lectures - Donald E. Knuth:
*The art of computer programming. Volume 3, Sorting and searching*. Addison-Wesley, 1973. Available in our library.