(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
- Organization.
Basic data structures and models. Heaps.
[draft notes]
- 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]
Jordan sorting. [jordan-notes]
- Order maintenance. [notes-order]
- Online problems, competitive ratio, paging. [paging-notes]
List update. [list-notes]
- Splay (self-adjusting) trees. [splay-notes]
- Geometry of binary search trees. [geom-notes]
Tango trees. [tango-notes]
[Videos via
KVV page]
Exercises
References/Further reading
- [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.
- Bender, Cole, Demaine, Farach-Colton, Zito: Two simplified algorithms for maintaining order in a list.
- Albers: Competitive online algorithms
- Sleator, Tarjan: Self-adjusting binary search trees.
[Tar, Section 4.3]
- 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.