Das Vorlesungsverzeichnis enthält die Belegnummer und offizielle Kommentare zur Vorlesung.

Wir wollen uns mit fortgeschrittenen Datenstrukturen für grundlegende Probleme beschäftigen, z.B. Suchen, Hashing, Datenstrukturen für Arrays, Bäume und Graphen. Das 'unplugged' im Titel der Veranstaltung deutet darauf hin, dass wir insbesondere an Problemen interessiert sind, für die es mittlerweile 'relativ' einfache Lösungen gibt, die in der Vergangenheit aber als sehr kompliziert angesehen wurden.

Im Sinne des 'unplugged' wird von jede(r/m) Vortragenden erwartet, dass der 45- bis 60-minütige Folien- und/oder Tafelvortrag so gestaltet ist, dass alle anderen Stud. das Thema danach verstanden haben und den Lösungsweg nachvollziehen und wiedergeben können (etwa wie bei einer guten Vorlesung). Falls dies für ein bestimmtes Thema nicht möglich ist (etwa weil die Originalliteratur zu umfangreich ist), ist der Stoff entsprechend zu kürzen.

Im Allgemeinen sind Bilder das geeignetste Mittel, um komplexe Sachverhalte möglichst einfach zu vermitteln (sofern letztere vom Vortragenden verstanden wurden). Weitere Hinweise zur Foliengestaltung und zum Vortrag werden an dieser Stelle rechtzeitig veröffentlicht.

Die angegebene Literatur zu einem Thema ist nur als Vorschlag anzusehen. Allerdings hat der Dozent im Sinne des 'unplugged' versucht, möglichst einfache und in sich abgeschlossene Beschreibungen anzugeben.

• Linear Probing and Perfect Hashing This analysis of linear probing and [T. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms. MIT Press, 3rd Edition, 2009. Chapter 11.5]
• Treaps [J. Erickson: Algorithms. Lecture Notes, 2011. Chapter 10.1. Available online.]
• Splay Trees [D. Mehta, S. Sahni (Eds.): Handbook of Data Structures and Applications. Chapman & Hall/CRC, 2005. Chapters 12.1-12.4] (Thema vergeben.)
• Scapegoat Trees [P. Morin: Open Data Structures. Athabasca University Press, Edmonton, 2013. Chapter 8. Also available online.] (Thema vergeben.)
• Quake Heaps [T. Chan: Quake Heaps: A Simple Alternative to Fibonacci Heaps. LNCS 8066, 27-32. Springer, 2013.]
• Level Ancestor Queries [M. A. Bender, M. Farach-Colton: The Level Ancestor Problem simplified. Theor. Comput. Sci. 321(1): 5-12, 2004.]
• van Emde Boas Trees [T. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms. MIT Press, 3rd Edition, 2009. Chapter 20]
• Succinct Data Structures: Rank and Select [G. Navarro and V. Mäkinen: Compressed Full-Text Indices. ACM Computing Surveys 39(1): Article No. 2, 2007. Section 6.1]
• Succinct Data Structures: Wavelet Trees [F. Claude, G. Navarro: The Wavelet Matrix. LNCS 7608, 167-179. Springer, 2012.]
• Succinct Trees [R. Geary, N. Rahman, R. Raman, V. Raman: A Simple Optimal Representation for Balanced Parentheses. Theor. Comput. Sci. 368(3): 231-246, 2006.]

Spätestens 2 Wochen vor dem Vortrag sollen Sie in einem halbstündigen Treffen mit dem Seminarleiter oder -betreuer die bis auf Feinkosmetik fertigen Folien zeigen und erklären können. Bitte vereinbaren Sie dieses Treffen rechtzeitig, also mindestens 4 Wochen vor dem Vortrag.

Spätestens 1 Woche nach dem Vortrag müssen Sie die schriftliche Ausarbeitung abgeben (per Email als pdf).

Beide Deadlines sind hart.

Sie sollten Spaß an algorithmischen Problem und der Analyse von Algorithmen haben. Die Vorlesungen DAP1 und DAP2 sollten nicht zu Ihren schlechtesten Fächern gehört haben. Im Idealfall haben Sie bereits andere Veranstaltungen aus diesem Bereich gehört (Algorithmen und Datenstrukturen, Effiziente Algorithmen, Algorithm Engineering, Algorithmische Bioinformatik, etc.) bzw. haben vor, dies noch zu tun.

Das Seminar ist geeignet für Informatiker im Master- oder Diplomstudiengang (Hauptstudium). Sie eignet sich gut als Vorbereitung zur Erstellung von Studien- oder Abschlussarbeiten (Master/Diplom) im Bereich Text-Indexierung.

Das Seminar findet als Blockveranstaltung am 20.3. von 15 bis 18 Uhr (c.t) im Raum 202 (OH14) statt.

Es fand eine Vorbesprechung in der 2. VL-Woche statt, und zwar am 23.10.2013 um 11:00.