Advanced Data Structures (and Algorithms)

Bei Interesse an diesem Seminar melden Sie sich bitte bis zum Beginn der Vorlesungszeit (12.4.2021) per Email an Johannes Fischer an. Es gibt maximal 18 Plätze.

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. Auch fortgeschrittene Algorithmen wie die parallele Konstruktion von Datenstrukturen und parallels Sortieren werden behandelt.

Bitte beachten Sie dieses Informationsblatt.

• Bryce Sandlund, Sebastian Wild: Lazy Search Trees. CoRR abs/2010.08840 (2020)
• Gerth S. Brodal: Soft Sequence Heaps. SOSA'21.

• Fabrizio Grandoni, Giuseppe F. Italiano, Aleksander Lukasiewicz, Nikos Parotsidis, Przemyslaw Uznanski: All-Pairs LCA in DAGs: Breaking through the O(n2.5) barrier. CoRR abs/2007.08914 (2020) (Motzet; Betreuer Johannes Fischer)
• Nicola Prezza: On Locating Paths in Compressed Cardinal Trees. CoRR abs/2004.01120 (2020)

• Dekel Tsur: Succinct data structure for dynamic trees with faster queries. Theor. Comput. Sci. 780: 12-19 (2019)
• Mingmou Liu, Yitong Yin, Huacheng Yu: Succinct Filters for Sets of Unknown Sizes. CoRR abs/2004.12465 (2020)
• Giulio Ermanno Pibiri, Rossano Venturini: Succinct Dynamic Ordered Sets with Random Access. CoRR abs/2003.11835 (2020) (Voß; Betreuer Jonas Ellert)

• Jarno N. Alanko, Travis Gagie, Gonzalo Navarro, Louisa Seelbach Benkner: Tunneling on Wheeler Graphs. DCC 2019: 122-131 (Diederich; Betreuer Patrick Dinklage)
• Dmitry Kosolobov, Daniel Valenzuela, Gonzalo Navarro, Simon J. Puglisi: Lempel-Ziv-Like Parsing in Small Space. Algorithmica 82(11): 3195-3215 (2020) (Wolff; Betreuer Patrick Dinklage)
• Golnaz Badkobeh, Maxime Crochemore: Left Lyndon tree construction. CoRR abs/2011.12742 (2020) (Buse; Betreuer Jonas Ellert)
• Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda: The Parameterized Suffix Tray. CoRR abs/2012.10092 (2020) (Wegener; Betreuer Nico Bertram)
• J. Ian Munro, Gonzalo Navarro, Yakov Nekrich: Text Indexing and Searching in Sublinear Time. CPM 2020: 24:1-24:15
• Djamal Belazzougui, Manuel Cáceres, Travis Gagie, Pawel Gawrychowski, Juha Kärkkäinen, Gonzalo Navarro, Alberto Ordóñez Pereira, Simon J. Puglisi, Yasuo Tabei: Block trees. J. Comput. Syst. Sci. 117: 1-22 (2021)

• 14.4.2021: Doodle zur Themenvergabe schließt
• 26.4.2021: Einreichung der Kurzzusammenfassungen (“abstracts”)
• 7.6.2021: Einreichung der Ausarbeitungen (“submission deadline”). Bitte beachten Sie auch unsere Hinweise zur Rechtschreibung etc.
• 28.6.2021: Deadline für die Gutachten
• 5.7.2021: Deadline für die Einreichung der finalen Ausarbeitungen
• 20.-22.7.2021, jeweils 9:00-16:00: Seminarvorträge

Alle Deadlines jeweils abends um 18:00.

Bitte reichen Sie Ihren Beitrag auf den Seiten von https://easychair.org/my/conference?conf=bads21 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.

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.

Das Seminar findet als Blockveranstaltung statt. Termine, auch zur obligatorischen Vorbesprechung, s. unter “zeitlicher Ablauf”.