Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

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 -

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: RNDr. Jiří Fink, Ph.D. (20.09.2022)

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