|
|
|
||
Last update: Mgr. Petr Jedelský (01.03.2021)
|
|
||
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. |
|
||
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. |
|
||
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
|
|
||
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. |
|
||
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. |
|
||
Last update: Mgr. Petr Jedelský (01.03.2021)
Knowledge on the level of the undergraduate Algorithms and data structures. |