Algorithm Engineering: Materialien zur Vorlesung

  1. Skript zusammengestellt von Felix Putze.
  2. Vorlesung
  3. Präsentation FilterKruskal

Themenwünsche für die Übung bitte an Sascha Witt (sascha.witt∂kit edu).

Miniseminar:

  1. Engineering a cache-oblivious sorting algorithm. — Benedict Toussaint
  2. LCP Array Construction in External Memory. — Tobias Ribizel
  3. On Succinct Representations of Binary Trees. — Yordan Boev
  4. Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search. — Steffen Ehrle
  5. Robust Distance Queries on Massive Networks. — Julian Labeit
  6. Public Transit Labelling. — Anne Cathérine Jäger
  7. Multilevel Local Search Algorithms for Modularity Clustering. — Oliver Plate

Vortragsthemen

20 Minuten Präsentation.
  1. Simple and Space-Efficient Minimal Perfect Hash Functions Botelho, F. C., Pagh, R. & Ziviani, N. In: WADS 2007 proceedings.
    bearbeitet von N.N.
  2. Engineering a cache-oblivious sorting algorithm. Brodal, G. S., Fagerberg, R., & Vinther, K. (2008). Journal of Experimental Algorithmics
    bearbeitet von Benedict Toussaint
  3. Shortest-path feasibility algorithms. Cherkassky, B. V., Georgiadis, L., Goldberg, A. V., Tarjan, R. E., & Werneck, R. F. (2009). Journal of Experimental Algorithmics, 14, 2.7.
    bearbeitet von N.N.
  4. Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search. Goldberg et al. ESA 2015 proceedings.
    bearbeitet von Steffen Ehrle
  5. An improved data stream summary: the count-min sketch and its applications. Cormode, G., & Muthukrishnan, S. (2005). Journal of Algorithms, 55(1), 58–75.
    bearbeitet von N.N.
  6. On Succinct Representations of Binary Trees. Davoodi, P., Raman, R., & Satti, S. R. (2014). arXiv preprint.
    bearbeitet von Yordan Boev
  7. Lightweight Approximate Selection. Dean, B. C., Jalasutram, R., & Waters, C. (2014). In ESA'14 proceedings.
    bearbeitet von N.N.
  8. Public Transit Labelling. Delling, D., Dibbelt, J., Pajor, T. & Werneck, R. F. Extended Abstract in SEA 2015 Proceedings.
    bearbeitet von Anne Cathérine Jäger
  9. 2-Connectivity in Directed Graphs: An Experimental Study. Di Luigi, W., Georgiadis, L., Italiano, G. F., Laura, L., & Parotsidis, N. (2015). In ALENEX 2015 proceedings
    bearbeitet von N.N.
  10. Balanced allocation and dictionaries with tightly packed constant size bins. Dietzfelbinger, M., & Weidling, C. (2007). Journal of Theoretical Computer Science, 380(1-2), 47–68.
    bearbeitet von N.N.
  11. Cache Replacement with Memory Allocation. Ghandeharizadeh, S., Irani, S., & Lam, J. (2015). In ALENEX 2015 proceedings.
    bearbeitet von N.N.
  12. LCP Array Construction in External Memory. Kärkkäinen, J., & Kempa, D. (2014). In SEA 2014 proceedings
    bearbeitet von Tobias Ribizel
  13. A Back-to-Basics Empirical Study of Priority Queues Larkin, D., Sen, S., & Tarjan, R. E. In: ALENEX 2014 proceedings. Technical report available here
    bearbeitet von N.N.
  14. Multilevel Local Search Algorithms for Modularity Clustering. Rotta, R. & Noack, A. In: ACM Journal of Experimental Algorithms 16(2), 2.3 (2011)
    bearbeitet von Oliver Plate
  15. Robust Distance Queries on Massive Networks. Werneck, R. F., Delling, D., Goldberg, A. V, & Pajor, T. (2014). In ESA’14 proceedings
    bearbeitet von Julian Labeit
  16. An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees. Hagerup, T. (2010). In LNCS vol. 5911, pp. 178-189
    bearbeitet von N.N.
  17. A new algorithm for the minimum spanning tree verification problem. Williamson, M., Subramani, K. (2014). In Comput Optim Appl vol. 61, pp. 189-204
    bearbeitet von N.N.

Programmieraufgaben

Abgabe bis 16.10.2016, 23:59 AoE (Anywhere on Earth, UTC-12). Programm + 2 Seiten Ausarbeitung mit Beschreibung und Experimenten (darf auch etwas länger sein).

Implementieren und evaluieren Sie effiziente Datenstrukturen für 2D orthogonal range search in C++11/14. Ein Framework für die Evaluation ist vorgegeben. Da es eine Vielzahl verschiedener Möglichkeiten gibt, kann (und soll) die Aufgabe von mehreren Personen bearbeitet werden. Diese sollen miteinander verglichen werden, wozu das Framework diverse Benchmarks enthält.

Mögliche Datenstrukturen beinhalten:

  1. Quad trees — bearbeitet von Joel Speitelsbach und Inna Belyantseva
  2. k-d trees — bearbeitet von Alexandru Lesi
  3. Range trees — bearbeitet von Chao Wang und Zhijia Song
  4. Range trees w/ Fractional Cascading — bearbeitet von Thomas Zenkel
  5. R trees — bearbeitet von Ole Berger
  6. R* trees — bearbeitet von Sidney Bender
  7. R+ trees — bearbeitet von Samuel Groß und Katharina Männle
  8. Priority R trees — bearbeitet von Iris Mehrbrodt
  9. Hilbert R trees — bearbeitet von Matthias Gräser und Peter Eisenmann
  10. Wavelet trees — bearbeitet von Nil Busra Bedir

Bis zu 2 Leute können ein Thema gemeinsam in einer Gruppe bearbeiten. Weitere Datenstrukturen sind nach Absprache möglich.