Beschreibung

In datenintensiven Bereichen wie etwa Bioinformatik, sozialen Netzwerken oder Suchmaschinen sind effiziente Algorithmen abhängig von Datenstrukturen, welche die Grundoperationen der Algorithmen effizient unterstützen. Darüber hinaus sollen die Strukturen möglichst platzeffizient sein und schnell konstruiert oder aktualisiert werden. In dieser Vorlesungen werden wir Datenstrukturen für verschiedene fundamentale Objekte wie Bäume, Graphen und Strings vorstellen. Wir werden uns dabei auf die Highlights der verschiedener Forschungsbereiche konzentrieren. Neben der theoretischen Analyse der Strukturen werden wir uns auch mit der praktischen Performance der Strukturen beschäftigen und Einsatzgebiete erläutern.

Die voraussichtlichen Themen sind:

 - Dictionary data structures: Hashing (universal, perfect, minimum monoton, cuckoo)
 - Predecessor data structures: van-Emde-Boas trees, y-fast trees, fusion trees
 - Orthogonal range search structures
 - Range minimum queries
 - Index structures for arrays
 - Top-k document retrieval

Folien

• Vorlesung 0
• Vorlesung 1
• Vorlesung 2
• Vorlesung 3
• Vorlesung 4
• Vorlesung 5
• Vorlesung 6
• Vorlesung 7 
• Vorlesung 8

Miniseminar  (am 16.07.2015)

• Themenliste
• Raum: 236 (9:45 - 13:00 Uhr)
• Folienvorlage