(Advanced) Data Structures 2020
, Institut für Informatik, Freie Universität Berlin
- 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.
- 5. March 2020 -- some information added to website (everything can still change)
- Two lectures, one exercise session per week, starting 21th April.
- Lectures: Tuesday and Thursday 10-12.
- 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 replacing 2-3 exercise sheets in second half of course.
- Heaps and amortised analysis
- Soft heaps and selection
- Number systems and de-amortisation
(planned -- very
- Trees and codes
- Splay trees, entropy and static optimality
- Online problems, competitiveness, paging problem
- Tango trees, dynamic optimality
- Geometry of binary search trees
- Link/cut trees and dynamic graph problems
- Succinct data structures
- Pattern avoidance
- Finger trees and Jordan sorting
- External memory
- Dynamic order maintenance
- Bitprobe schemes
- ?? B-Trees, Strings, Hashing, Approximate counting/membership, Integer RAM, Geometric data structures, Lower bounds ???
- Lecture notes (TBA)
- References (TBA)
- Exercise sheets (TBA)
by László Kozma.