Subjects

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

Data Structures I - NTIN066

Title:	Datové struktury I
Guaranteed by:	Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2016 to 2016
Semester:	winter
E-Credits:	5
Hours per week, examination:	winter s.: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, English
Teaching methods:	full-time
Teaching methods:	full-time

Guarantor:	RNDr. Jiří Fink, Ph.D. prof. Mgr. Michal Koucký, 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
Is co-requisite for:	NTIN067

Opinion survey results Examination dates 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, 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: T_KTI (25.04.2016)

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

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

Syllabus -

Last update: RNDr. Jan Hric (27.04.2018)

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

Entry requirements -

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

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