Advanced Data Structures

Inhalt

Wir wollen uns mit fortgeschrittenen Datenstrukturen für grundlegende Probleme beschäftigen, z.B. Suchen, Hashing, Datenstrukturen für Arrays, Bäume und Graphen, Succinct Data Structures, External Memory Data Structures.

Allgemeine Hinweise

Bitte beachten Sie neben den in der Vorbesprechung bekanntgegebenen Informationen auch dieses Informationsblatt.

Themenliste

Allgemein

Brodnik et al.: Resizable Arrays in Optimal Time and Space
Katajainen: Worst-Case-Efficient Dynamic Arrays in Practice
Dementiev et al.: Engineering a Sorted List Data Structure for 32 Bit Keys
Andersson: Balanced Search Trees Made Simple
Putze et al.: Cache- Hash-, and Space-Efficient Bloom Filters

Heaps

Hansen et al.: Hollow Heaps
Chan: Quake Heaps: A Simple Alternative to Fibonacci Heaps
Edelkamp et al.: An In-Place Priority Queue with O(1) Time for Push and lg n+O(1) Comparisons for Pop

Erweiterte Rechenmodelle

Brengel et al: An Experimental Study of Priority Queues in External Memory
Arge: The Buffer Tree: A Technique for Designing Batched External Data Structures
Brodal/Fagerberg: Funnel Heap - A Cache Oblivious Priority Queue
Shun/Blelloch: A Simple Parallel Cartesian Tree Algorithm and its Application to Parallel Suffix Tree Construction

Succinct Data Structures

Zhou et al.: Space-Efficient, High-Performance Rank and Select Structures on Uncompressed Sequences
Okanohara/Sadakane: Practical Entropy-Compressed Rank/Select Dictionary
Navarro/Sadakane: Fully Functional Static and Dynamic Succinct Trees
Klitzke/Nicholson: A General Framework for Dynamic Succinct and Compressed Data Structures
Durocher et al: Range Majority in Constant Time and Linear Space
Elmasry et al: Selection from read-only memory with limited workspace

Strings

Grossi/Ottaviano: Fast Compressed Tries through Path Decomposition
Gog et al.: CSA++: Fast Pattern Search for Large Alphabets
Prezza: A Framework of Dynamic Data Structures for String Processing

Zuordnung

	Autoren	Titel	Teilnehmer/in	Betreuer	Termin
1.	Brodnik et al.	Resizable Arrays in Optimal Time and Space	Tim Tannert	Fischer	Mo 9
2.	Katajainen	Worst-Case-Efficient Dynamic Arrays in Practice	Jakob Knorr	Kurpicz	Mo 10
3.	Dementiev et al.	Engineering a Sorted List Data Structure for 32 Bit Keys	Jangin Yuen	Fischer	Mo 11
5.	Putze et al.	Cache- Hash-, and Space-Efficient Bloom Filters	Jens Zentgraf	Köppl	Mo 13
6.	Hansen et al.	Hollow Heaps	Jens Knippers	Fischer	Mo 14
7.	Chan	Quake Heaps: A Simple Alternative to Fibonacci Heaps	Nils Brinkmann	Fischer	Mo 15
12.	Shun/Blelloch	A Simple Parallel Cartesian Tree Algorithm and its Application to Parallel Suffix Tree Construction	Dominik Görtz	Fischer	Mo 16
9.	Brengel et al	An Experimental Study of Priority Queues in External Memory	Fabian Pawlowski	Kurpicz	Di 9
10.	Arge	The Buffer Tree: A Technique for Designing Batched External Data Structures	Roland Wyzgol	Kurpicz	Di 10
11.	Brodal/Fagerberg	Funnel Heap - A Cache Oblivious Priority Queue	U.-E. Wiebelitz	Köppl	Di 11
13.	Zhou et al.	Space-Efficient, High-Performance Rank and Select Structures on Uncompressed Sequences	Ole Bergenholtz	Köppl	Di 13
14.	Okanohara/Sadakane	Practical Entropy-Compressed Rank/Select Dictionary	Dennis Rohde	Köppl	Di 14
15.	Navarro/Sadakane	Fully Functional Static and Dynamic Succinct Trees	Patrick Dinklage	Köppl	Di 15
19.	Grossi/Ottaviano	Fast Compressed Tries through Path Decomposition	Nils Bergmann	Kurpicz	Mi 9
20.	Gog et al.	CSA++: Fast Pattern Search for Large Alphabets	Lena Rolf	Kurpicz	Mi 10
21.	Prezza	A Framework of Dynamic Data Structures for String Processing	Daniel Korner	Fischer	Mi 11

Zeitlicher Ablauf

21.5. Einreichung der Kurzzusammenfassungen (“abstracts”)
25.6. Einreichung der Ausarbeitungen (“submission deadline”)
9.7. Deadline für die Gutachten
23.7. Einreichung der finalen Ausarbeitungen
31.7.-2.8. Seminarvorträge

Einreichung der Artikel

Bitte reichen Sie Ihren Beitrag auf den Seiten von easychair ein (Account nötig).

Voraussetzungen

Sie sollten Spaß an algorithmischen Problem und der Analyse von Algorithmen haben. Die Vorlesung DAP2 sollte 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, Text-Indexierung 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) in der Arbeitsgruppe von Johannes Fischer.

Ort und Zeit

Das Seminar findet als Blockveranstaltung am 31.7.17, 1.8.17 und 2.8.17 jeweils von 9 bis 16 Uhr (c.t) im Raum 3.030 (OH12) statt.

Es fand eine Vorbesprechung in der 2. VL-Woche statt, und zwar am 25.04.2017 um 17:00 (OH14, E04).

Table of Contents