Differences
This shows you the differences between two versions of the page.
|
fischer:teaching:ads-ss2020 [2020-02-12 10:01] |
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. Auch fortgeschrittene Algorithmen wie die parallele Konstruktion von Datenstrukturen und parallels Sortieren werden behandelt. | 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. | ||
| Line 20: | Line 21: | ||
| * **(7)** 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 | ||
| * **(8)** 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 | + | * **(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) | * **(10)** Philip Bille, Inge Li Gørtz, Teresa Anna Steiner: String Indexing with Compressed Patterns. CoRR abs/1909.11930 (2019) | ||
| Line 36: | Line 37: | ||
| * **(18)** Mihai Patrascu, Liam Roditty: Distance Oracles beyond the Thorup-Zwick Bound. SIAM J. Comput. 43(1): 300-311 (2014) | * **(18)** Mihai Patrascu, Liam Roditty: Distance Oracles beyond the Thorup-Zwick Bound. SIAM J. Comput. 43(1): 300-311 (2014) | ||
| * **(19)** Timothy M. Chan, Mihai Patrascu: Counting Inversions, Offline Orthogonal Range Counting, and Related Problems. SODA 2010: 161-173 | * **(19)** Timothy M. Chan, Mihai Patrascu: Counting Inversions, Offline Orthogonal Range Counting, and Related Problems. SODA 2010: 161-173 | ||
| - | * **(20)** Naila Rahman, Richard Cole, Rajeev Raman: Optimised Predecessor Data Structures for Internal Memory. Algorithm Engineering 2001: 67-78 | + | * **(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 | * **(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) | * **(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) | ||