Logo ČVUT
Loading...
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2025/2026
Faculties | School elective courses | ECTS courses catalogue | Settings | Česká verze
Welcome page > Faculty of Information Technology > Department of Theoretical Computer Science > Data Structures

Data Structures

Display time-table
Code Completion Credits Range Language
BI-DAS Z,ZK 5 2P+1C Czech
Course guarantor:
Michal Opler
Lecturer:
Radek Hušek, Michal Opler
Tutor:
Radek Hušek, Michal Opler
Supervisor:
Department of Theoretical Computer Science
Synopsis:

The course introduces more advanced data structures, including analysis of their complexity.

Requirements:

We assume that the student has a basic knowledge of algorithm design (which could have been acquired in the courses BI-PA1 and BI-PA2) and graph theory (BI-AG1: Algorithms and Graphs 1). It is an advantage if the student has completed or is concurrently taking the course Algorithms and Graphs 2 (BI-AG2), but it is not a requirement.

Syllabus of lectures:

1. (a,b)-trees and red-black trees

2. Persistent variants of trees and their motivation

3. List labelling

4. Introduction to randomized structures: treaps

5. Hashing I: function systems

6. Hashing II: linear addition analysis

7. Hashing III: Bloom filters

8. Binomial heaps

9. Fibonacci heaps

10. Counting points in a plane (2D range trees)

11. Heavy-light decomposition

12. String matching

13. Reserve (dynamization of data structures)

Syllabus of tutorials:

The tutorials consist of solving assigned tasks on topics covered in lectures.

Study Objective:
Study materials:

- Martin Mareš, Tomáš 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

- K. Mehlhorn: Data Structures and Algorithms I: Sorting and Searching. Springer-Verlag, Berlin, 1984

- T. H. Cormen, C.E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. Third edition, MIT Press, 2009.

- Martin Mareš: Lecture notes on data structures. Available online at https://mj.ucw.cz/vyuka/dsnotes/

- Mikkel Thorup: Lecture Notes on Linear Probing with 5-Independent Hashing, 2015. Available online at https://arxiv.org/abs/1509.04549

- Mikkel Thorup: High Speed Hashing for Integers and Strings, 2015. Available online at https://arxiv.org/abs/1504.06804

Note:

Information and materials are to be foudn at https://courses.fit.cvut.cz/BI-DAS/. The course is presented in Czech.

Further information:
https://courses.fit.cvut.cz/BI-DAS/
Time-table for winter semester 2025/2026:
Time-table is not available yet
Time-table for summer semester 2025/2026:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2025-11-29
Copyright © Jiří Kosek, 2010–2022 | Copyright © ČVUT, 2010–2022
Hosted by Výpočetní a informační centrum ČVUT
Send your questions and comments to ServiceDesk ČVUT or to spravcekos@cvut.cz
For updated information see http://bilakniha.cvut.cz/en/predmet8483006.html