Differences
This shows you the differences between two versions of the page.
|
fischer:teaching:ads-ss2020 [2020-01-15 15:15] |
fischer:teaching:ads-ss2020 [2020-03-27 20:43] |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Advanced Data Structures (and Algorithms) ====== | ====== Advanced Data Structures (and Algorithms) ====== | ||
| + | **20.3.2020: Das Seminar wird zunächst wie geplant (online) weiterlaufen. Je nach Lage bei Semesterende wird das Format der Vorträge evtl. auf Videovorträge umgestellt.** | ||
| ===== Inhalt ===== | ===== 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. | + | 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. |
| ===== Allgemeine Hinweise ===== | ===== Allgemeine Hinweise ===== | ||
| Line 9: | Line 10: | ||
| ===== Themenliste ===== | ===== Themenliste ===== | ||
| - | ==== Allgemein ==== | + | ==== Parallele Algorithmen ==== |
| - | * Mihai Patrascu, Liam Roditty: Distance Oracles beyond the Thorup-Zwick Bound. SIAM J. Comput. 43(1): 300-311 (2014) | + | * **(1)** Omar Obeya, Endrias Kahssay, Edward Fan, Julian Shun: Theoretically-Efficient and Practical Parallel In-Place Radix Sorting. SPAA 2019: 213-224 |
| - | * Timothy M. Chan, Mihai Patrascu: Counting Inversions, Offline Orthogonal Range Counting, and Related Problems. SODA 2010: 161-173 | + | * **(2)** Yan Gu, Julian Shun, Yihan Sun, Guy E. Blelloch: A Top-Down Parallel Semisort. SPAA 2015: 24-34 |
| - | * Naila Rahman, Richard Cole, Rajeev Raman: Optimised Predecessor Data Structures for Internal Memory. Algorithm Engineering 2001: 67-78 | + | * **(3)** Uwe Baier, Timo Beller, Enno Ohlebusch: Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies. ACM Journal of Experimental Algorithmics 22 (2017) |
| - | * Mihai Patrascu, Mikkel Thorup: Time-space trade-offs for predecessor search. STOC 2006: 232-240 | + | * **(4)** Timo Bingmann, Peter Sanders, Matthias Schimek: Communication-Efficient String Sorting. CoRR abs/2001.08516 (2020) |
| - | * Emmanuel Esposito, Thomas Mueller Graf, Sebastiano Vigna: RecSplit: Minimal Perfect Hashing via Recursive Splitting. arXiv:1910.06416v2. To appear in: ALENEX 2020 | + | |
| - | + | ||
| - | ==== Parallel Algorithms ==== | + | |
| - | * Omar Obeya, Endrias Kahssay, Edward Fan, Julian Shun: Theoretically-Efficient and Practical Parallel In-Place Radix Sorting. SPAA 2019: 213-224 | + | |
| - | * | + | |
| ==== Texte ==== | ==== Texte ==== | ||
| - | * Johannes Bader, Simon Gog, Matthias Petri: Practical Variable Length Gap Pattern Matching. SEA 2016: 1-16 | + | * **(5)** 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 | + | * **(6)** Vincent Cohen-Addad, Laurent Feuilloley, Tatiana Starikovskaya: Lower bounds for text indexing with mismatches and differences. SODA 2019: 1146-1164 (Thomas Buse) |
| - | * Dominik Kempa, Tomasz Kociumaka: String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure. STOC 2019: 756-767 | + | * **(7)** 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 | + | * **(8)** Travis Gagie, Gonzalo Navarro, Nicola Prezza: Optimal-Time Text Indexing in BWT-runs Bounded Space. SODA 2018: 1459-1477 |
| + | * **(9)** Giulia Bernardini, Huiping Chen, Gabriele Fici, Grigorios Loukides and Solon P. Pissis: Reverse-Safe Data Structures for Text Indexing. ALENEX 2020: 199-213 (Mustafa Yalciner) | ||
| + | * **(10)** Philip Bille, Inge Li Gørtz, Teresa Anna Steiner: String Indexing with Compressed Patterns. CoRR abs/1909.11930 (2019) | ||
| + | |||
| + | |||
| + | ==== Space Efficient Data Structures ==== | ||
| + | * **(11)** Pooya Davoodi, Rajeev Raman, Srinivasa Rao Satti: On Succinct Representations of Binary Trees. Mathematics in Computer Science 11(2): 177-189 (2017) (Christoph Stockhoff) | ||
| + | * **(12)** Andreas Poyias, Simon J. Puglisi, Rajeev Raman: Compact Dynamic Rewritable (CDRW) Arrays. ALENEX 2017: 109-119 (Jan Meinhövel) | ||
| + | * **(13)** José Fuentes Sepúlveda, Gonzalo Navarro, Diego Seco: Implementing the Topological Model Succinctly. SPIRE 2019: 499-512 | ||
| + | * **(14)** Michal Ganczorz: Using statistical encoding to achieve tree succinctness never seen before. CoRR abs/1807.06359 (2018) | ||
| + | * **(15)** Tim Baumann, Torben Hagerup: Rank-Select Indices Without Tears. WADS 2019: 85-98 (Jan-Philipp Tarnowski) | ||
| + | * **(16)** Emmanuel Esposito, Thomas Mueller Graf, Sebastiano Vigna: RecSplit: Minimal Perfect Hashing via Recursive Splitting. arXiv:1910.06416v2. To appear in: ALENEX 2020 (Alexander Herlez) | ||
| + | * **(17)** J. Ian Munro, Bryce Sandlund, Corwin Sinnamon: Space-Efficient Data Structures for Lattices. arXiv:1902.05166 (Benedict Schubert) | ||
| - | ==== Succinct Data Structures ==== | + | ==== Graphen und Sonstiges ==== |
| - | * Pooya Davoodi, Rajeev Raman, Srinivasa Rao Satti: On Succinct Representations of Binary Trees. Mathematics in Computer Science 11(2): 177-189 (2017) | + | * **(18)** Mihai Patrascu, Liam Roditty: Distance Oracles beyond the Thorup-Zwick Bound. SIAM J. Comput. 43(1): 300-311 (2014) |
| - | * Andreas Poyias, Simon J. Puglisi, Rajeev Raman: Compact Dynamic Rewritable (CDRW) Arrays. ALENEX 2017: 109-119 | + | * **(19)** Timothy M. Chan, Mihai Patrascu: Counting Inversions, Offline Orthogonal Range Counting, and Related Problems. SODA 2010: 161-173 |
| - | * José Fuentes Sepúlveda, Gonzalo Navarro, Diego Seco: Implementing the Topological Model Succinctly. SPIRE 2019: 499-512 | + | * **(20)** Naila Rahman, Richard Cole, Rajeev Raman: Optimised Predecessor Data Structures for Internal Memory. Algorithm Engineering 2001: 67-78 (Timm Grote) |
| + | * **(21)** Mihai Patrascu, Mikkel Thorup: Time-space trade-offs for predecessor search. STOC 2006: 232-240 | ||
| + | * **(22)** Gerth Stølting Brodal, Pooya Davoodi, Moshe Lewenstein, Rajeev Raman, Srinivasa Rao Satti: Two dimensional range minimum queries and Fibonacci lattices. Theor. Comput. Sci. 638: 33-43 (2016) (Maximilian Freese) | ||
| ===== Zeitlicher Ablauf ===== | ===== Zeitlicher Ablauf ===== | ||
| - | * **31.1.2020, 14:00 Vorbesprechung in OH12 3.031** | + | * Die Vorbesprechung fand am 31.1.2020 um 14:00 statt |
| * 07.02.2020: Doodle zur Themenvergabe schließt | * 07.02.2020: Doodle zur Themenvergabe schließt | ||
| - | * 20.4.2020: Einreichung der Kurzzusammenfassungen ("abstracts") | + | * **20.4.2020: Einreichung der Kurzzusammenfassungen ("abstracts")** |
| - | * 25.5.2020: Einreichung der Ausarbeitungen ("submission deadline") | + | * 25.5.2020: Einreichung der Ausarbeitungen ("submission deadline"). Bitte beachten Sie auch unsere [[https://ls11-www.cs.tu-dortmund.de/fischer/abschlussarbeiten/regeln#haeufig_wiederkehrende_fehler_im_deutschen|Hinweise zur Rechtschreibung etc.]] |
| * 22.6.2020: Deadline für die Gutachten | * 22.6.2020: Deadline für die Gutachten | ||
| * 29.6.2020: Deadline für die Einreichung der finalen Ausarbeitungen | * 29.6.2020: Deadline für die Einreichung der finalen Ausarbeitungen | ||