Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | |||
|
fischer:teaching:ads-ss2019 [2020-01-14 15:23] Johannes Fischer [Advanced Data Structures] |
fischer:teaching:ads-ss2019 [2020-01-14 15:55] (current) Johannes Fischer |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Advanced Data Structures (and Algorithms) ====== | ====== Advanced Data Structures (and Algorithms) ====== | ||
| - | ===== Inhalt ===== | + | Das Seminar ist vorbei. |
| - | 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_ads.pdf |Informationsblatt}}. | + | |
| - | + | ||
| - | ===== Themenliste ===== | + | |
| - | + | ||
| - | ==== Allgemein ==== | + | |
| - | * Mihai Patrascu, Liam Roditty: Distance Oracles beyond the Thorup-Zwick Bound. SIAM J. Comput. 43(1): 300-311 (2014) | + | |
| - | * Timothy M. Chan, Mihai Patrascu: Counting Inversions, Offline Orthogonal Range Counting, and Related Problems. SODA 2010: 161-173 | + | |
| - | * Naila Rahman, Richard Cole, Rajeev Raman: Optimised Predecessor Data Structures for Internal Memory. Algorithm Engineering 2001: 67-78 | + | |
| - | * Mihai Patrascu, Mikkel Thorup: Time-space trade-offs for predecessor search. STOC 2006: 232-240 | + | |
| - | + | ||
| - | ==== Parallel Algorithms ==== | + | |
| - | * Omar Obeya, Endrias Kahssay, Edward Fan, Julian Shun: Theoretically-Efficient and Practical Parallel In-Place Radix Sorting. SPAA 2019: 213-224 | + | |
| - | * | + | |
| - | + | ||
| - | ==== Texte ==== | + | |
| - | * Johannes Bader, Simon Gog, Matthias Petri: Practical Variable Length Gap Pattern Matching. SEA 2016: 1-16 | + | |
| - | * Vincent Cohen-Addad, Laurent Feuilloley, Tatiana Starikovskaya: Lower bounds for text indexing with mismatches and differences. SODA 2019: 1146-1164 | + | |
| - | * Dominik Kempa, Tomasz Kociumaka: String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure. STOC 2019: 756-767 | + | |
| - | * Travis Gagie, Gonzalo Navarro, Nicola Prezza: Optimal-Time Text Indexing in BWT-runs Bounded Space. SODA 2018: 1459-1477 | + | |
| - | + | ||
| - | ==== Succinct Data Structures ==== | + | |
| - | * Pooya Davoodi, Rajeev Raman, Srinivasa Rao Satti: On Succinct Representations of Binary Trees. Mathematics in Computer Science 11(2): 177-189 (2017) | + | |
| - | * Andreas Poyias, Simon J. Puglisi, Rajeev Raman: Compact Dynamic Rewritable (CDRW) Arrays. ALENEX 2017: 109-119 | + | |
| - | * José Fuentes Sepúlveda, Gonzalo Navarro, Diego Seco: Implementing the Topological Model Succinctly. SPIRE 2019: 499-512 | + | |
| - | + | ||
| - | ===== Zeitlicher Ablauf ===== | + | |
| - | + | ||
| - | * 31.1.2020, 14:00 Vorbesprechung in TBA | + | |
| - | * 07.02.2020: Doodle zur Themenvergabe schließt | + | |
| - | * 20.4.2020: Einreichung der Kurzzusammenfassungen ("abstracts") | + | |
| - | * 25.5.2020: Einreichung der Ausarbeitungen ("submission deadline") | + | |
| - | * 22.6.2020: Deadline für die Gutachten | + | |
| - | * 29.6.2020: Deadline für die Einreichung der finalen Ausarbeitungen | + | |
| - | * 14.-16.7.2020, jeweils 9:15-16:00: 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=bads20]] ein (Account nötig). Benutzen Sie bitte [[http://drops.dagstuhl.de/styles/lipics-v2018/lipics-v2018-authors.zip|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". | + | |
| - | + | ||
| - | + | ||