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