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.

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