Fortgeschrittene Datenstrukturen (Advanced Data Structures)

Links

Vorlesungsbeschreibung

Datenstrukturen sind der grundlegende Baustein für effiziente Algorithmen. Aufgrund der stetig anwachsenden Datenmengen (Internet, digitale Bibliotheken, Bioinformatik, etc.) besteht ein grundlegender Bedarf an kleinen, aber leistungsfähigen Datenstrukturen. In dieser Vorlesung wollen wir uns mit modernen Datenstrukturen für fundamentale Objekte wie Bäume, Graphen, Integers und Strings beschäftigen. Ein besonderer Fokus wird hierbei auf die mathematische Analyse dieser Datenstrukturen gelegt; es wird aber auch immer wieder die praktische Seite (Implementierung) angesprochen werden. Die Vorlesung ist so ausgelegt, dass wiederkehrende Techniken anhand von konkreten Problemen gelehrt werden.

Wir behandeln voraussichtlich die folgenden Themen:

- Predecessor data structures: van-Emde-Boas trees, y-fast trees, fusion trees
- Integer sorting
- Dictionaries: cuckoo hashing, FKS dictionary
- Data structures for graphs: distance oracles, spanners, distance labels
- Data structures for trees: lowest common ancestors, level ancestors
- Data structures for arrays: range minima and other kind of range queries
- Succinct data structures: bit vectors, succinct tree navigation
- Data Structures for Strings: Compressed Suffix Arrays

Folien und Skript