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] [P04] video
29. 4. Union-Find (incremental maintenance of connected components): representation based on trees, Union by rank, path compression. Amortized analysis of path compression. Rank trees. [P04] [SE] [TL] video (2022)
6. 5. Online lecture: please watch the video. 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 (2022)
13. 5. Making data structures dynamic: Full and partial rebuilds. Separable search problems and their dynamization using decomposition to exponentially-sized blocks: amortized and worst-case semi-dynamization, amortized full dynamization. Making data structures persistent: ephemeral, semi-persistent, fully persistent, and functional data structures. Techniques: path copying, fat nodes, combination of both. General transformation of pointer-based data structures to semi-persistent. [P05] [M7] [DS] [MS] video
20. 5. Maintaining linear order: list order, list labelling. Cache-oblivious data structures: packed memory array (list labelling with linear range a.k.a. ordered file maintenance), cache-aware B-trees, van Emde-Boas layout of binary trees, cache-oblivious B-trees (combination of vEB layout with PMA). [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, which you made yourself.

Course material

Previous runs of the lecture:

Literature:

This page is maintained by Martin Mareš