(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]
    Jordan sorting. [jordan-notes]
  7. Order maintenance. [notes-order]
  8. Online problems, competitive ratio, paging. [paging-notes]
    List update. [list-notes]
  9. Splay (self-adjusting) trees. [splay-notes]
  10. Geometry of binary search trees. [geom-notes]
    Tango trees. [tango-notes]


[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.
  7. Bender, Cole, Demaine, Farach-Colton, Zito: Two simplified algorithms for maintaining order in a list.
  8. Albers: Competitive online algorithms
  9. Sleator, Tarjan: Self-adjusting binary search trees.
    [Tar, Section 4.3]
  10. Demaine et al.: Geometry of BST.
    Demaine et al.: Tango trees.
 
[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.