This is an old revision of the document!


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

  • 1. Michael Mitzenmacher, Salvatore Pontarelli, and Pedro Reviriego. Adaptive cuckoo filters [ALENEX'18]
  • Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, and Ayellet Tal. The Bloomier filter: an efficient data structure for static support lookup tables [SODA'04]
  • Michael A. Bender, Martin Farach-Colton, Mayank Goswami, Rob Johnson, Samuel McCauley, Shikha Singh: Bloom Filters, Adaptivity, and the Dictionary Problem [FOCS'18]

Erweiterte Rechenmodelle

  • 4. Jiang/Larsen: A Faster External Memory Priority Queue with DecreaseKey [SODA'19]
  • Bender et al.: Cache-oblivious B-trees [SIAM J. Comput., 35(2):341–358, 2005.]
  • Bender et al.: A locality-preserving cache-oblivious dynamic dictionary. [Journal of Algorithms 53(2), 115-136, 2004]
  • Lee et al.: Partitioned Parallel Radix Sort [Journal of Parallel and Distributed Computing 62(4), 656–668, 2002]
  • Brodal et al.: Engineering a Cache-Oblivious Sorting Algorithm [ACM Journal of Experimental Algorithmics, Vol. 12, Article No. 2.2, 2008]

Texte

  • 9. Kempa: Optimal Construction of Compressed Indexes for Highly Repetitive Texts [SODA'19]
  • Dudek/Gawrychowski: Slowing Down Top Trees for Better Worst-Case Compression [CPM'18]
  • Kaneta: Fast Wavelet Tree Construction in Practice [SPIRE'18]
  • Gog et al.: Fixed Block Compression Boosting in FM-Indexes: Theory and Practice [Algorithmica 2018]
  • Jo et al.: Compressed Range Minimum Queries [SPIRE'18]
  • Enno Ohlebusch et al.: Trickier XBWT Tricks [SPIRE'18]

Succinct Data Structures

  • 15. 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.
  • 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.

Zeitlicher Ablauf

  • 25.1.2019, 14:00 Vorbesprechung in OH12 3.030
  • 01.02.2019: Doodle zur Themenvergabe schließt
  • 29.4.2019: Einreichung der Kurzzusammenfassungen (“abstracts”)
  • 20.5.2019: Einreichung der Ausarbeitungen (“submission deadline”)
  • 11.6.2019: Deadline für die Gutachten
  • 24.6.2019: Einreichung der finalen Ausarbeitungen
  • 10.-12.7.2019: Seminarvorträge

Alle Deadlines jeweils abends um 18:00.

Einreichung der Artikel

Bitte reichen Sie Ihren Beitrag auf den Seiten von https://easychair.org/my/conference?conf=bads19 ein (Account nötig). Benutzen Sie bitte diesen Latex-Style. Bitte tragen Sie bereits bei der Einreichung der Kurzzusammenfassung Ihre Matrikelnummer im Feld Web page ein.

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 statt. Termine, auch zur obligatorischen Vorbesprechung, s. unter “zeitlicher Ablauf”.

 
Last modified: 2019-06-14 22:16 (external edit)
DokuWikiRSS-Feed