Syllabus
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.
Annotation
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.