====== 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 {{ :fischer:teaching:allgemeine_seminarhinweise.pdf |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 [[https://easychair.org/conferences/?conf=bads2017|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).