Data Structures 2

I am teaching Data Structures II [NTIN067] in the summer semester of 2023/2024.

The lectures will be on Mondays from 15:40 in S8.

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 recording
19. 2. Static dictionary problem. FKS perfect hashing built from universal systems of hash functions. HMP hashing: reduction of universe to polynomial (just sketch) and then to quadratic (n-ary trie). [P01] [FKS] [S2.1]
26. 2. No lecture today.
4. 3. 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
[partial sound]
11. 3. A remark on sorting of reals. 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
[bad sound]
18. 3. Generalized vEB trees: storing just ones (x-fast tries), speedup by indirection (y-fast tries). Heaps: binary, d-regular. Binomial trees and a sketch of binomial heaps. [P02] [E11] [D4] video
25. 3. Heaps: Binomial, lazy binomial, Fibonacci. [D4] video
1. 4. No lecture today: Ēostre, Paasfees, Великден, Ülestõusmispühad, Πάσχα, Páskar, 復活祭, Pace. —
8. 4. Splay trees: weighted analysis, static optimality, static finger bound, working set bound, hypothesis on dynamic optimality. [D2.3] [STb] video
15. 4. 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
22. 4. Link-cut trees: dynamic decomposition based on interconnected Splay trees. Application to Dinitz's maximum flow algorithm. Intermezzo: Static structure for interval evaluation of an associative operation. [P03] [STa] [STb] video
29. 4. Plan: Union-Find (incremental maintenance of connected components): representation based on trees, Union by rank, path compression. Amortized analysis of path compression. [P04] [SE] [TL]
6. 5. There will be no lecture.
13. 5. Plan: 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]
3. 5. Plan: 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]
17. 5. Plan: 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]

Course material

Previous runs of the lecture:

Literature:

This page is maintained by Martin Mareš