(Advanced) Data Structures 2020
, Institut für Informatik, Freie Universität Berlin
- 19. April 2020 -- first lecture/exercise uploaded
- 31. March 2020 -- Lectures to start 21th April, probably mostly online/remote. More information soon.
- 12. March 2020 -- NOTE: The COVID-19 situation will likely cause some delay/disruption, stay safe and informed.
Tuesday and Thursday 10-12 online (recorded) with weekly Q&A Tuesday 10:15.
- Exercise sessions: Wednesday 14-16. Instructor: Katharina Klost.
- Some organisational info on course KVV page.
- Exercise sheets: one per week (except last 1-2), one mini-project in second half of course.
Basic data structures and models. Heaps.
- Amortized analysis recap. [notes-amortized]
Skew (self-adjusting) heaps. [notes-skew]
- Soft heaps and selection. [notes-soft] [structured-selection]
- Number systems and de-amortization. [nr-systems]
Augmented trees and applications. [augmented]
- Range minimum queries. [rmq-notes] [cart-tree]
- Finger trees and applications. [finger-notes]
Next planned -- tentative:
- Dynamic order maintenance
- Online problems, competitiveness, paging problem
- Splay trees, entropy and static optimality
- Tango trees, dynamic optimality
- Geometry of binary search trees
- Succinct data structures
- Link/cut trees and dynamic graph problems
- Bitprobe schemes
Further possible topics -- very
- Pattern avoidance, Persistence, External memory, Strings, Hashing, Approximate counting/membership, Integer RAM, Lower bounds
[Videos via KVV page
- [CLRS, Sections 3, 6, 10, 12, 13]
[Tar, Sections 1, 3.1, 3.2]
- [CLRS, Section 17]
Sleator, Tarjan: Self-adjusting heaps.
- Kaplan, Zwick: A simpler implementation and analysis of Chazelle's soft heaps.
Kaplan, Kozma, Zamir, Zwick: Selection from heaps, row-sorted matrices, and X+Y using soft heaps.
- Clancy, Knuth, pg. 52-55.
[CLRS, Section 14]
[Tar, Sections 4.1, 4.2]
- Bender et al.: LCA in trees and DAGs.
Fischer, Heun: Improvements on the RMQ.
- Hoffmann, Mehlhorn, Rosenstiehl, Tarjan: Sorting Jordan sequences.
[CLRS] Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, 3rd Ed. The MIT Press 2009
[Tar] Tarjan: Data Structures and Network Algorithms, SIAM 1987
by László Kozma.