Differences

This shows you the differences between two versions of the page.

Link to this comparison view

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"​)
 
Last modified: 2020-03-27 20:43 (external edit)
DokuWikiRSS-Feed