Subjects

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

Data Structures I - NTIX066

Title:	Datové struktury I
Guaranteed by:	Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2022
Semester:	both
E-Credits:	5
Hours per week, examination:	2/1, C+Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	Czech
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:	RNDr. Jiří Fink, Ph.D. Mgr. Martin Mareš, Ph.D. doc. Mgr. Petr Gregor, 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 :	NTIN066
Interchangeability :	NTIN066
Is incompatible with:	NTIN066
Is interchangeable with:	NTIN066

Opinion survey results Examination dates WS schedule SS schedule Noticeboard

Annotation -

Last update: Mgr. Petr Jedelský (01.03.2021)

The basic course about construction of efficient data structures, mandatory for Master's students. Search trees, heaps, hashing. Worst-case, average-case and amortized complexity of data structures. Self-adjusting data structures. Behavior and analysis of data structures on systems with memory hierarchy. The lecture builds on the lectures Algorithms and Data Structures I and II and Programming I and II from the bachelor study.

Aim of the course - Czech

Last update: Mgr. Petr Jedelský (01.03.2021)

Naučit pokročilejší datové struktury včetně teoretické analýzy a experimentů s chováním na reálných počítačích.

Course completion requirements -

Last update: Mgr. Petr Jedelský (01.03.2021)

It is necessary to obtain class credit and pass the exam.

Class credit is given for reaching the required number of points for assignments solved during the semester.

The character of the assignments does not allow repeated attempts to obtain credit.

Literature -

Last update: Mgr. Petr Jedelský (01.03.2021)

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: Mgr. Petr Jedelský (01.03.2021)

The exam is oral with written preparation. To pass the exam, understanding of material presented at the lecture is required.

Syllabus -

Last update: Mgr. Petr Jedelský (01.03.2021)

Trees

• (a,b)-trees and their variants

• Move-to-Front strategy for lists, Splay trees

• other solutions: AVL trees, red-black trees, BB-alpha trees

Heaps

• regular heaps

• binomial heaps

• Fibonacci heaps

Techniques for memory hierarchy

• I/O model, cache-oblivious analysis, LRU strategy for on-line paging

• examples: matrix transposition and multiplication, van Emde-Boas tree layout

• cache-aware techniques

Hashing

• collisions and their resolution, analysis for uniformly distributed data

• selecting a hash function: universal hashing, good hash functions

• cuckoo hashing

Multidimensional data structures

• KD trees

• range trees

Warning: The course will be given since 2018/19 in English only in the summer term (instead of the winter term in previous years) and in Czech only in the winter term.

Entry requirements -

Last update: Mgr. Petr Jedelský (01.03.2021)

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