Data Structures 1 - NTIN066
Title: Datové struktury 1
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2020
Semester: both
E-Credits: 6
Hours per week, examination: 2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Teaching methods: full-time
Additional information: https://ktiml.mff.cuni.cz/~fink/teaching/data_structures_I/
Note: you can enroll for the course in winter and in summer semester
Guarantor: prof. Mgr. Michal Koucký, Ph.D.
RNDr. Jiří Fink, Ph.D.
Mgr. Martin Mareš, Ph.D.
Class: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Softwarové systémy
Informatika Mgr. - Matematická lingvistika
Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Theoretical Computer Science
Incompatibility : NTIX066
Interchangeability : NTIX066
Is co-requisite for: NTIN067, NTIN105
Is incompatible with: NTIX066
Is interchangeable with: NTIX066
Opinion survey results   Examination dates   WS schedule   SS schedule   Noticeboard   
Annotation -
The basic course about construction of efficient data structures, mandatory for Master's students. Search trees, hashing, structures for working with strings. Worst-case, average-case and amortized complexity of data structures. Self-adjusting data structures. Behavior of data structures on systems with memory hierarchy. The lecture builds on the lectures Algorithmization, Algorithms and Data Structures 1 and Algorithms and Data Structures 2 from the bachelor study.
Last update: Töpfer Pavel, doc. RNDr., CSc. (14.01.2019)
Aim of the course -

The course should provide a student with a deeper understanding of data structures and their behaviour on real computers.

Last update: Töpfer Pavel, doc. RNDr., CSc. (14.01.2019)
Course completion requirements -

One has to get a passing grade from the tutorials before comming for an exam. To get a passing grade from the tutorials one has to earn sufficient

amount of points from the homeworks. Due to the specifics of the homeworks no make-ups are possible.

Last update: Töpfer Pavel, doc. RNDr., CSc. (14.01.2019)
Literature -

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

Last update: T_KTI (26.04.2016)
Requirements to the exam -

Knowledge and understanding of the material covered during the class.

Last update: Töpfer Pavel, doc. RNDr., CSc. (14.01.2019)
Syllabus -

Trees

(a,b)-trees

Splay trees

BB-α trees

Hashing

Choice of hash functions: universal hash functions, k-indepenence

Linear probing

Cuckoo hashing

Bloom filter

Text data structures

Suffix tree

Suffix array

Techniques for memory hierarchy

Parallel data structures

Multidimensional data structures

K-d trees

Range trees

Warning: The course is offered in English only in the summer term and in Czech only in the winter term.

Last update: Töpfer Pavel, doc. RNDr., CSc. (01.02.2019)
Entry requirements -

Knowledge on the level of the undergraduate Algorithms and data structures.

Notice that Czech lectures and tutorials are in winter semesters while English lectures and tutorials are in summer semesters only.

Last update: Fink Jiří, RNDr., Ph.D. (20.09.2022)