(Advanced) Data Structures 2020 :: László Kozma :: Freie Universität Berlin
(Advanced) Data Structures 2020
László Kozma, Institut für Informatik, Freie Universität Berlin


News

  • 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.

Organisation

  • Lectures: 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.

Lectures

  1. Organization.
    Basic data structures and models. Heaps. [draft notes]
  2. Amortized analysis recap. [notes-amortized]
    Skew (self-adjusting) heaps. [notes-skew]
  3. Soft heaps and selection. [notes-soft] [structured-selection]
  4. Number systems and de-amortization. [nr-systems]
    Augmented trees and applications. [augmented]
  5. Range minimum queries. [rmq-notes] [cart-tree]
  6. 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 tentative

- Pattern avoidance, Persistence, External memory, Strings, Hashing, Approximate counting/membership, Integer RAM, Lower bounds

[Videos via KVV page]

Exercises


References/Further reading

  1. [CLRS, Sections 3, 6, 10, 12, 13]
    [Tar, Sections 1, 3.1, 3.2]
  2. [CLRS, Section 17]
    Sleator, Tarjan: Self-adjusting heaps.
  3. 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.
  4. Clancy, Knuth, pg. 52-55.
    [CLRS, Section 14]
    [Tar, Sections 4.1, 4.2]
  5. Bender et al.: LCA in trees and DAGs.
    Fischer, Heun: Improvements on the RMQ.
  6. 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


---
Contact:
laszlo.kozma@fu-berlin.de

Last updated by László Kozma.