SubjectsSubjects(version: 877)
Course, academic year 2020/2021
  
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 [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
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
K//Is co-requisite for: NTIN105, NTIN067
Annotation -
Last update: doc. RNDr. Pavel Töpfer, CSc. (14.01.2019)
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.
Aim of the course -
Last update: doc. RNDr. Pavel Töpfer, CSc. (14.01.2019)

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

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

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.

Literature -
Last update: T_KTI (26.04.2016)

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

Requirements to the exam -
Last update: doc. RNDr. Pavel Töpfer, CSc. (14.01.2019)

Knowledge and understanding of the material covered during the class.

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

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.

Entry requirements -
Last update: T_KTI (28.04.2015)

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

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html