Algorithm Engineering: Materialien zur Vorlesung

  1. Skript zusammengestellt von Felix Putze.
  2. Vorlesung
  3. Vortrag FilterKruskal
  4. External Memory Folien von Roman Dementiev. Wir haben daraus gemacht: STXXL, cache oblivious Algorithmen und suffix sorting.
  5. Suffix Sorting
  6. Auswirkungen von Branch Misprediction auf die Laufzeit von Quicksort

Themenwünsche für die Übung bitte an Lorenz Hübschle-Schneider (huebschleBky4∂kit edu). Das vormals verlinkte Email-Formular hat nicht funktioniert, die Emails kamen nicht an. Bitte nochmal direkt schreiben!

Miniseminar:

Dienstag 14.7.2015, 13:00-19:00, Raum: 301 (13:00–15:30) / 236 (15:45–19:00)

Vortragsthemen

20 Minuten Präsentation.
  1. Experimental Comparison of Semantic Word Clouds. Barth, L., Kobourov, S., & Pupyrev, S. (2014). In SEA 2014 proceedings.
    und On Semantic Word Cloud Representation. Barth, L., Kobourov, S., Pupyrev, S., & Ueckerdt, T. (2013). CoRR abs/1304.8016, Data Structures and Algorithms; Computation and Language.
    bearbeitet von Laura Vonessen
  2. Simple and Space-Efficient Minimal Perfect Hash Functions Botelho, F. C., Pagh, R. & Ziviani, N. In: WADS 2007 proceedings.
    bearbeitet von Tobias Fabritz
  3. Engineering a cache-oblivious sorting algorithm. Brodal, G. S., Fagerberg, R., & Vinther, K. (2008). Journal of Experimental Algorithmics
    bearbeitet von Beskorovajnov Wasilij
  4. 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 Alina Saalfeld
  5. Lightweight Approximate Selection. Dean, B. C., Jalasutram, R., & Waters, C. (2014). In ESA'14 proceedings.
    bearbeitet von Maximilian Czerny
  6. Public Transit Labelling. Delling, D., Dibbelt, J., Pajor, T. & Werneck, R. F. Extended Abstract in SEA 2015 Proceedings.
    bearbeitet von Arno Appenzeller
  7. 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 Tobias Müller
  8. 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 Sebastian Bayer
  9. Cache Replacement with Memory Allocation. Ghandeharizadeh, S., Irani, S., & Lam, J. (2015). In ALENEX 2015 proceedings.
    bearbeitet von Thomas Keh
  10. LCP Array Construction in External Memory. Kärkkäinen, J., & Kempa, D. (2014). In SEA 2014 proceedings
    bearbeitet von Sebastian Meßmer
  11. 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 Robert Hangu
  12. Multilevel Local Search Algorithms for Modularity Clustering. Rotta, R. & Noack, A. In: ACM Journal of Experimental Algorithms 16(2), 2.3 (2011)
    bearbeitet von Andreas Eberle
  13. Robust Distance Queries on Massive Networks. Werneck, R. F., Delling, D., Goldberg, A. V, & Pajor, T. (2014). In ESA’14 proceedings
    bearbeitet von Jan Broß

Vorläufige Reihenfolge

Nach Themennummern: 1 7 4 12 13 6 2 8 9 3 10 11 5. Je nach Constraints der Reder kann sich die Reihenfolge noch ändern. Prinzipiell herrscht für die gesamte Dauer des Miniseminars Anwesenheitspflicht.

Programmieraufgaben

Abgabe bis 16.10.2015, 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 in C++11/14. Ein Framework für die Evaluation ist vorgegeben. Die Implementierungen sollen allgemein nutzbar sein, daher sollte beispielsweise der Datentyp ein Template-Parameter sein, etc. Da es eine Vielzahl verschiedener Möglichkeiten gibt, können (und sollen) beide Aufgaben von mehreren Personen bearbeitet werden. Diese sollen miteinander verglichen werden, wozu das Framework diverse Benchmarks enthält.

Framework: https://github.com/lorenzhs/algen-framework — auch gehostet im KIT-Gitlab unter https://git.scc.kit.edu/lorenz/algen-framework/

Hinweis: Die aufgelisteten und aktuell implementierten Benchmarks sind nicht final. Sie sollen Ihre Datenstrukturen nicht darauf optimieren, in diesen speziellen synthetischen Benchmarks performant zu sein, sondern unter allgemeinen Workloads. Da die Performance einiger Varianten grundsätzlich limitiert ist, sind die Benchmarks auch nur ein Teil der Note. Wenn Sie möchten, können Sie auch zusätzliche Operationen implementieren (beispielsweise decreaseKey bei adressierbaren Priority Queues).

  1. Priority Queues. Mögliche Varianten: Neben Microbenchmarks, die die Performance der einzelnen Operationen und Abfolgen von Operationen messen, wird auch die Performance in Anwendungen wie Heapsort gemessen.
  2. Hashtabellen. Mögliche Varianten: Hier gibt es wieder Microbenchmarks und synthetische Benchmarks, die die Performance der Operationen alleine bzw. in bestimmten Kombinationen messen. Zusätzlich wird es auch hier Anwendungsbenchmarks geben (z.B. word count).