Efficient data structures are important components of all nontrivial algorithms, and are basic building blocks of the modern computing infrastructure. Besides their practical importance, the design and analysis of data structures has revealed a rich mathematical theory. The ultimate theoretical limits of data structures are the subject of deep open questions.

The topic of this course is the design and analysis of data structures (including both classical and recent results), with emphasis on data structures that are adaptive, exploiting regularities in their input.

As prerequisite, algorithmic and relevant mathematical background knowledge is assumed (e.g., the course "Advanced algorithms" or similar).

Lectures: Wednesdays 2-4 in T9/049

Exercises (tutorials): Thursdays 10-12 in A3/019

First meeting: April 16th.

Similar course in 2020:

http://page.mi.fu-berlin.de/lkozma/ds2020

Lecture material:

link (mostly notes and recordings from last time)

Die Schwerpunkte dieser Vorlesung sind Design, Analyse, und Anwendungen von Datenstrukturen. Die Vorlesung wird in der englischen Sprache gehalten.

Literature

• Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, 3rd Ed. The MIT Press 2009
• Mehlhorn: Data Structures and Algorithms (3 volumes), Springer 1984
• Tarjan: Data Structures and Network Algorithms, SIAM 1987
• recent articles

Links to similar courses at other universities:

• Pat Morin, Carleton,  http://cglab.ca/~morin/teaching/5408/
• Erik Demaine, MIT, http://courses.csail.mit.edu/6.851/
• Jeff Erickson, UIUC, http://jeffe.cs.illinois.edu/teaching/datastructures/
• Venkatesh Raman, IMSc, https://www.imsc.res.in/~vraman/adsjan2012/index.html