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.
Last update: doc. RNDr. Pavel Töpfer, CSc. (14.01.2019)
Základní přednáška o konstrukci efektivních datových struktur. Vyhledávací stromy, hešování, struktury pro práci s
řetězci. Analýza nejhoršího, amortizovaného a očekávaného chování datových struktur. Samoupravující se datové
struktury. Chování datových struktur na systémech s paměťovou hierarchií. Přednáška volně navazuje na
přednášky Algoritmizace, Algoritmy a datové struktury 1 a Algoritmy a datové struktury 2 z bakalářského studia.
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.
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.
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.
Last update: Mgr. Martin Mareš, Ph.D. (15.10.2019)
Ke splnění předmětu je nutné získat zápočet a složit zkoušku.
Zápočet se udílí za získání požadovaného počtu bodů za domácí úkoly řešené během semestru. Vzhledem k povaze domácích úkolů nejsou náhradní termíny zápočtu přípustné.
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
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
A. Koubková, V. Koubek: Datové struktury I. MATFYZPRESS, Praha 2011
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.
Last update: Mgr. Martin Mareš, Ph.D. (01.03.2019)
Zkouška je ústní s písemnou přípravou. Zkouší se porozumění teorii prezentované na přednášce.
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.
Last update: doc. RNDr. Pavel Töpfer, CSc. (01.02.2019)