Advanced Data Structures

Bei Interesse an dieser Veranstaltung bitte einfach zur Vorbesprechung kommen (s.u.). Keine Anmeldung per Email.

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

  • Arne Andersson. Balanced search trees made simple. In Proc. WADS, volume 709 of LNCS, pages 60–71, 1993.
  • Michael Mitzenmacher, Salvatore Pontarelli, and Pedro Reviriego. Adaptive cuckoo filters. In Proc. ALENEX, pages 36–47, 2018.
  • Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, and Ayellet Tal. The Bloomier filter: an efficient data structure for static support lookup tables. In Proc. SODA, pages 30–39, 2004.
  • Michael A. Bender, Martin Farach-Colton, Mayank Goswami, Rob Johnson, Samuel McCauley, Shikha Singh: Bloom Filters, Adaptivity, and the Dictionary Problem. CoRR abs/1711.01616, 2017.

Erweiterte Rechenmodelle

  • Michael A. Bender, Erik D. Demaine, and Martin Farach-Colton. Cache-oblivious B-trees. SIAM J. Comput., 35(2):341–358, 2005.
  • Klaus Brengel, Andreas Crauser, Paolo Ferragina, and Ulrich Meyer. An experimental study of priority queues in external memory. ACM Journal of Experimental Algorithmics, 5:17, 2000.
  • Julian Labeit, Julian Shun, Guy E. Blelloch: Parallel lightweight wavelet tree, suffix array and FM-index construction. J. Discrete Algorithms 43: 2-17, 2017.

Succinct Data Structures

  • Philip Bille, Anders Roy Christiansen, Nicola Prezza, and Frederik Rye Skjoldjensen. Succinct partial sums and Fenwick trees. In Proc. SPIRE, volume 10508 of LNCS, pages 91–96, 2017.
  • Patrick Klitzke and Patrick K. Nicholson. A general framework for dynamic succinct and compressed data structures. In Proc. ALENEX, pages 160– 173, 2016.
  • Stephane Durocher, Meng He, J. Ian Munro, Patrick K. Nicholson, and Matthew Skala. Range majority in constant time and linear space. Inf. Comput., 222:169–179, 2013.
  • Amr Elmasry, Daniel Dahl Juhl, Jyrki Katajainen, and Srinivasa Rao Satti. Selection from read-only memory with limited workspace. Theor. Comput. Sci., 554:64–73, 2014.

Strings

  • Robert W. Irving and Lorna Love. The suffix binary search tree and suffix AVL tree. J. Discrete Algorithms, 1(5-6):387–408, 2003.
  • Yoshimasa Takabatake, Yasuo Tabei, and Hiroshi Sakamoto. Online pattern matching for string edit distance with moves. In Proc. SPIRE, volume 8799 of LNCS, pages 203–214, 2014.
  • Djamal Belazzougui, Patrick Hagge Cording, Simon J. Puglisi, and Yasuo Tabei. Access, rank, and select in grammar-compressed strings. In Proc. ESA, volume 9294 of LNCS, pages 142–154, 2015.
  • Tomohiro I. Longest common extensions with recompression. In Proc. CPM, volume 78 of LIPIcs, pages 18:1–18:15, 2017.
  • Nicola Prezza. In-place sparse suffix sorting. In Proc. SODA, pages 1496–1508, 2018.
  • Pawel Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub Lacki, and Piotr Sankowski. Optimal dynamic strings. In Proc. SODA, pages 1509–1528, 2018.
  • Travis Gagie, Giovanni Manzini, and Jouni Sirén: Wheeler graphs: A framework for BWT-based data structures. Theor. Comput. Sci. 698: 67-78, 2017.

Zuordnung

Autoren Titel Teilnehmer/in Betreuer Termin
1. AnderssonBalanced search trees made simple
2. Mitzenmacher et al.Adaptive cuckoo filters
3. Chazelle et al.The Bloomier filter: an efficient data structure for static support lookup tables
4. Bender et al.Bloom Filters, Adaptivity, and the Dictionary Problem
5. Bender et al.Cache-oblivious B-trees
6. Brengel et al.An experimental study of priority queues in external memory
7. Labeit et al.Parallel lightweight wavelet tree, suffix array and FM-index construction
8. Bille et al.Succinct partial sums and Fenwick trees
9. Klitzke/NicholsonA general framework for dynamic succinct and compressed data structures
10. Durocher et al.Range majority in constant time and linear space
11. Elmasry et al.Selection from read-only memory with limited workspace
12. Irving/LoveThe suffix binary search tree and suffix AVL tree
13. Takabatake et al.Online pattern matching for string edit distance with moves
14. Belazzougui et al.Access, rank, and select in grammar-compressed strings
15. I Longest common extensions with recompression
16. PrezzaIn-place sparse suffix sorting
17. Gawrychowski et al.Optimal dynamic strings
18. Gagie et al.A framework for BWT-based data structures

Zeitlicher Ablauf

  • 23.4.18: Doodle zur Themenvergabe schließt
  • 07.5.18: Einreichung der Kurzzusammenfassungen (“abstracts”)
  • 04.6.18: Einreichung der Ausarbeitungen (“submission deadline”)
  • 25.6.18: Deadline für die Gutachten
  • 09.7.18: Einreichung der finalen Ausarbeitungen
  • 18.7.-20.7.18: Seminarvorträge

Alle Deadlines jeweils abends um 18:00.

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 vom 18.-20.7.2018 jeweils von 9 bis 16 Uhr (c.t) im Raum 3.030 statt.

Es findet eine Vorbesprechung in der OH14, Raum E04 statt, und zwar am 17.4.2018 um 17:15 Uhr statt.

 
Last modified: 2018-04-19 11:08 by Florian Kurpicz
DokuWikiRSS-Feed