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

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.

Course website

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

Lecture videos

see Resources -> video link

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

Zielgruppe

Informatiker und interessierte Mathematiker im Masterstudium.

Empfohlene Vorkennntnisse

"Höhere Algorithmik" oder eine andere Vorlesung ähnlichen Inhalts.