Differences
This shows you the differences between two versions of the page.
fischer:teaching:ads-ss2020 [2020-01-17 10:46] |
fischer:teaching:ads-ss2020 [2020-01-22 14:33] |
||
---|---|---|---|
Line 2: | Line 2: | ||
===== 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 9: | ||
===== Themenliste ===== | ===== Themenliste ===== | ||
- | ==== Allgemein ==== | + | ==== Graphen und Sonstiges ==== |
* Mihai Patrascu, Liam Roditty: Distance Oracles beyond the Thorup-Zwick Bound. SIAM J. Comput. 43(1): 300-311 (2014) | * 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 | * 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 | * 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 | * Mihai Patrascu, Mikkel Thorup: Time-space trade-offs for predecessor search. STOC 2006: 232-240 | ||
- | * Emmanuel Esposito, Thomas Mueller Graf, Sebastiano Vigna: RecSplit: Minimal Perfect Hashing via Recursive Splitting. arXiv:1910.06416v2. To appear in: ALENEX 2020 | ||
- | ==== Parallel Algorithms ==== | + | ==== Parallele Algorithmen ==== |
* Omar Obeya, Endrias Kahssay, Edward Fan, Julian Shun: Theoretically-Efficient and Practical Parallel In-Place Radix Sorting. SPAA 2019: 213-224 | * Omar Obeya, Endrias Kahssay, Edward Fan, Julian Shun: Theoretically-Efficient and Practical Parallel In-Place Radix Sorting. SPAA 2019: 213-224 | ||
- | * | + | * Yan Gu, Julian Shun, Yihan Sun, Guy E. Blelloch: A Top-Down Parallel Semisort. SPAA 2015: 24-34 |
==== Texte ==== | ==== Texte ==== | ||
Line 26: | Line 25: | ||
* Travis Gagie, Gonzalo Navarro, Nicola Prezza: Optimal-Time Text Indexing in BWT-runs Bounded Space. SODA 2018: 1459-1477 | * Travis Gagie, Gonzalo Navarro, Nicola Prezza: Optimal-Time Text Indexing in BWT-runs Bounded Space. SODA 2018: 1459-1477 | ||
- | ==== Succinct Data Structures ==== | + | ==== Space Efficient Data Structures ==== |
* Pooya Davoodi, Rajeev Raman, Srinivasa Rao Satti: On Succinct Representations of Binary Trees. Mathematics in Computer Science 11(2): 177-189 (2017) | * 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 | * 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 | * José Fuentes Sepúlveda, Gonzalo Navarro, Diego Seco: Implementing the Topological Model Succinctly. SPIRE 2019: 499-512 | ||
* Michal Ganczorz: Using statistical encoding to achieve tree succinctness never seen before. CoRR abs/1807.06359 (2018) | * Michal Ganczorz: Using statistical encoding to achieve tree succinctness never seen before. CoRR abs/1807.06359 (2018) | ||
+ | * Tim Baumann, Torben Hagerup: Rank-Select Indices Without Tears. WADS 2019: 85-98 | ||
+ | * Emmanuel Esposito, Thomas Mueller Graf, Sebastiano Vigna: RecSplit: Minimal Perfect Hashing via Recursive Splitting. arXiv:1910.06416v2. To appear in: ALENEX 2020 | ||
+ | * J. Ian Munro, Bryce Sandlund, Corwin Sinnamon: Space-Efficient Data Structures for Lattices. arXiv:1902.05166 | ||
+ | |||
===== Zeitlicher Ablauf ===== | ===== Zeitlicher Ablauf ===== | ||
- | * **31.1.2020, 14:00 Vorbesprechung in OH12 3.031** | + | * **31.1.2020, 14:00 Vorbesprechung in OH12 3.031. Interessierte Teil*nehmer müssen hier ohne vorherige Anmeldungung erscheinen.** |
* 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") |