Data Structures 2

I am teaching Data Structures II [NTIN067] in the summer semester of 2021/2022. We meet on Tuesdays from 15:40 in S3.

If you want to consult anything, please write an e-mail to mares+ds@kam.mff.cuni.cz and we will discuss possibilities.

datum topics sources video
15. 2. Our model of computation: the Word-RAM. Static dictionary problem. FKS perfect hashing built from universal systems of hash functions. A remark on sorting of reals. HMP hashing: reduction of universe to polynomial (just sketch) and then to quadratic (n-ary trie). [P01] [FKS] [S2.1] video
22. 2. Deterministic static dictionaries: principle of permuting points in a grid, application to construction of HMP perfect hashing. Randomized construction of row permutations, derandomization using conditional expectation. [P01] [HMP] video
1. 3. Structures for ordered sets of integers: van Emde-Boas trees based on recursive subdivision to buckets. A trick for implicit initialization of memory. vEB interpreted as a binary range tree: easier, but with slower updates. [P02] [G] [E11] video
8. 3. Generalized vEB trees: storing just ones (x-fast tries), speedup by indirection (y-fast tries). Heaps: binary, d-regular. Binomial trees. [P02] [D4] video
15. 3. Heaps: Binomial, lazy binomial, Fibonacci. [D4] video
22. 3. Splay trees: weighted analysis, static optimality, static finger bound, working set bound, hypothesis on dynamic optimality. [D2.3] [STb] video
29. 3. Introduction to data structures for graphs. Representation of static paths based on range trees with lazy propagation of updates. Heavy-light decomposition of trees. Link-Cut trees: interface, idea of thick-thin decomposition. [P03] video
5. 4. Link-cut trees: dynamic decomposition based on interconnected Splay trees. Application on Dinitz's maximum flow algorithm. Intermezzo: Static structure for interval evaluation of an associative operation. [P03] [STa] [STb] video
12. 4. Union-Find (incremental maintenance of connected components): representation based on trees, Union by rank, path compression. Amortized analysis of path compression. [P04] [SE] [TL] video
19. 4. Union-Find continued: Amortized analysis of path compression: O(log n) for path compression only, O(α(n)) when combined with Union by rank. [P04] [SE] [TL] video
26. 4. Making data structures dynamic: Full and partial rebuilds, semi-dynamization of 2D range trees using partial rebuilds. Separable search problems and their dynamization using decomposition to exponentially-sized blocks: amortized and worst-case semi-dynamization, amortized full dynamization. [P05] [M7] video
3. 5. Making data structures persistent: ephemeral, semi-persistent, fully persistent, and functional data structures. Techniques: path copying, fat nodes, combination of both. General transform of pointer-based data structures to semi-persistent, a sketch of full persistence. Application: planar point location. Maintaining linear order: list order, list labelling. [P05] [DS] [MS] video
10. 5. No lecture today.
17. 5. Cache-oblivious data structures: packed memory array (list labelling with linear range), cache-aware B-trees, van Emde-Boas layout of binary trees, cache-oblivious B-trees. [P06] [EC] [MP] video

Exams

There are exam dates listed in SIS. Please sign up there or send me an e-mail if no date suits you.

You are expected to know the material from the lectures (data structures and theorems on their properties; see the catalog of requirements), to understand it, and to be able to modify the data structures to solve similar problems.

You are allowed to bring a cheat sheet on a single A4 page.

Course material

Previous runs of the lecture:

Literature:

This page is maintained by Martin Mareš