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. Plan: 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]

Course material

Previous runs of the lecture:

Literature:

This page is maintained by Martin Mareš