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:

Vortragsthemen

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 V.
2. Simple and Space-Efficient Minimal Perfect Hash Functions Botelho, F. C., Pagh, R. & Ziviani, N. In: WADS 2007 proceedings.
   bearbeitet von Tobias F.
3. Engineering a cache-oblivious sorting algorithm. Brodal, G. S., Fagerberg, R., & Vinther, K. (2008). Journal of Experimental Algorithmics
   bearbeitet von B. 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 S.
5. Lightweight Approximate Selection. Dean, B. C., Jalasutram, R., & Waters, C. (2014). In ESA'14 proceedings.
   bearbeitet von Maximilian C.
6. Public Transit Labelling. Delling, D., Dibbelt, J., Pajor, T. & Werneck, R. F. Extended Abstract in SEA 2015 Proceedings.
   bearbeitet von Arno A.
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.
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 B.
9. Cache Replacement with Memory Allocation. Ghandeharizadeh, S., Irani, S., & Lam, J. (2015). In ALENEX 2015 proceedings.
   bearbeitet von Thomas K.
10. LCP Array Construction in External Memory. Kärkkäinen, J., & Kempa, D. (2014). In SEA 2014 proceedings
    bearbeitet von Sebastian M.
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 H.
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 E.
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 B.

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:
   • Binary und d-ary Heaps - bearbeitet von Niklas G.
   • Fibonacci Heaps - bearbeitet von Alexander N.
   • Pairing Heaps - bearbeitet von Patrick N.
   • Einfache Sequence Heaps ("mittelgroße" Variante aus der Vorlesung) - bearbeitet von Michael A.
   • Binomial Heaps - bearbeitet von Bernardo P.
   • Rank-Pairing Heaps - bearbeitet von Christian K.
   • Weitere Vorschläge willkommen!
   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:
   • Open Addressing mit verschiedenen Probing-Strategien (Linear oder Quadratic Probing, Double Hashing, ...) oder Löschstrategien (z.B. Löschmarkierungen mit Verschieben beim Suchen), etc. - bearbeitet von Matthias S.
   • Hashing mit Chaining. Auch hier gibt es Optionen: Wird das erste Element in der Tabelle gespeichert, oder besteht der Eintrag nur aus einem Listenzeiger? Wie sind die Elemente in der Liste angeordnet (Sortiert? Move-to-Front-Heuristik? Unsortiert in Einfügereihenfolge?), etc. - bearbeitet von Janis H.
   • Cuckoo Hashing - bearbeitet von Sebastian L.
   • Cuckoo Hashing with Pages (Dietzfelbinger, Mitzenmacher, Rink 2011) - bearbeitet von Martin R.
   • Dynamic Perfect Hashing (im Buch von Mehlhorn und Sanders beschrieben) - bearbeitet von Lennart H. und Frederik P.
   • Weitere Vorschläge willkommen!
   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).