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

Miniseminar:

Freitag 18.7.2014, 9:45 - ca. 15:30

Vortragsthemen

20 Minuten Präsentation.

1. A Back-to-Basics Empirical Study of Priority Queues. Daniel H. Larkin, Siddhartha Sen and Robert E. Tarjan. Alenex 2014.
   bearbeitet von Richard Molitor

2. Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths. Yano, Yosuke Yano, Takuya Akiba, Yoichi Iwata and Yuichi Yoshida. 22nd ACM Conference on information and Knowledge Management (CIKM).
   bearbeitet von Joachim Priesner

3. Triangle Listing Algorithms: Back from the Diversion. Mark Ortmann and Ulrik Brandes. Alenex 2014.
   bearbeitet von Maximilian Vogel

4. Space-Efficient, High-Performance Rank & Select Structures on Uncompressed Bit Sequences. Dong Zhou, David G. Andersen, Michael Kaminsky. SEA 2013 proceedings.
   bearbeitet von Michael Auracher

5. Branch Mispredictions Don't Affect Mergesort. Amr Elmasry, Jyrki Katajainen and Max Stenmark. SEA 2012 proceedings.
   bearbeitet von Malte Schönbrunn

6. Fast Local Search for the Maximum Independent Set Problem. D. Vieira Andrade, M. G. C. Resende, R. F. Werneck. WEA 2008 proceedings, p. 220-234.
   bearbeitet von Eike Röhrs

7. Finding the Diameter in Large Graphs: Experimentally turning a lower bound into an upper bound. P. Crescenzi, R. Grossi, C. Imbrenda, L. Lanzi and A. Marino. ESA 2010 proceedings.
   bearbeitet von Lea Köckert

8. Storing a Compressed Function with Constant Time Access. J.B. Hreinsson, M. Krøyer, R. Pagh. ESA 2009 proceedings, p. 730-741.
   bearbeitet von Lukas Barth

9. Choosing Probability Distributions for Stochastic Local Search and the Role of Make versus Break. Adrian Balint and Uwe Schöning. SAT 2012: 16-29
   bearbeitet von ?

10. PHAST: Hardware-Accelerated Shortest Path Trees. A. V. Goldberg, A. Nowatzyk, and R. F. Werneck. IPDPS 2011 proceedings, p. 921-931.
    bearbeitet von Alexander Meier

11. Engineering a cache-oblivious sorting algorithm. G. Stølting Brodal, R. Fagerberg, K. Vinther. Journal of Experimental Algorithmics (JEA) 12, 2008, 2.2 p. 1-23
    bearbeitet von ?

12. Shortest-path feasibility algorithms: An experimental evaluation. B. V. Cherkassky, L. Georgiadis, A. V. Goldberg, R. E. Tarjan, R. F. Werneck. ALENEX 2008 proceedings, p. 118-132.
    bearbeitet von ?

13. A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks. I. Abraham, D. Delling, A. V. Goldberg, R. F. Werneck. SEA 2011 proceedings, p. 230-241.
    bearbeitet von ?

14. Maximum Flows by Incremental Breadth-First Search. A. V. Goldberg, S. Hed, H. Kaplan, R. E. Tarjan, R. F. Werneck. ESA 2011 proceedings, p. 457-468.
    bearbeitet von Klara Reichard

15. Shortest Path Algorithms: Engineering Aspects. A. V. Goldberg. ISAAC 2001 proceedings, p. 502-513.
    bearbeitet von Isabel Funke

Programmieraufgaben

5 Minuten Präsentation + Programm + 2 Seiten Ausarbeitung.

1. Implementieren Sie einen effizienten quicksort, der nachweislich branchmispredictions vermeidet. Vergleichen Sie mit std:sort.
   bearbeitet von ?

2. Implementieren Sie eine effiziente und robuste Variante von super-scalar sample sort. Hier sind Ideen zur Verbesserung: Tuning der Anzahl zu bearbeitender Folgen, robuster Umgang mit Eingaben bei denen viele Schlüssel identisch sind, Tuning des base case (Umschaltzeitpunkt, verwendete Algorithmen,...). Single pass variante mit Hilfe einer hybriden Listen-Array Datenstrukture oder Betriebssystemtricks. Multicore Parallelisierung. Bitte mit Christian Ocker und Florian Drews koordinieren. Hinweise. Vergleichen Sie Ihre Implementierung mit STL std:sort.
   bearbeitet von ?

3. Implementieren and evaluieren Sie effiziente Algorithmen für die Berechnung transitiver Hüllen. Implementierungstips gibts beim Dozenten. Diese Aufgabe kann auch von mehreren Personen bearbeitet werden, da es viele algorithmische Ansätze gibt.
   bearbeitet von Tobias Fleck, Max Wagner und Sebastian Ullrich

4. Entwerfen und implementieren Sie einen cache-effizienten Algorithmus zur Run-Formation nach der snow plow Heuristik. Tips gibts beim Dozenten. Schaffen Sie es auch, I/O und Berechnung zu überlappen? Vielleicht können Sie die MCSTL verwenden, um Multicore-Parallelismus zu verwenden? Literatur: The Art of Computer Programming. Volume 3: Sorting and Searching. D.E. Knuth. 2. Auflage. Addison Wesley, 1998.
   bearbeitet von Florian Tobias Schandinat

5. Parallelisiertes Peeling zur Generation von (M)PHFs.
   bearbeitet von ?

Theorieaufgaben

10 Minuten Präsentation + 5 Seiten Ausarbeitung

1. Entwerfen und analysieren Sie einen cache-effizienten Algorithmus zur Run-Formation nach der snow plow Heuristik. Tips gibts beim Dozenten. Schaffen Sie es auch, I/O und Berechnung zu überlappen? Single disk? Parallel disk? Multi-core? Literatur: The Art of Computer Programming. Volume 3: Sorting and Searching. D.E. Knuth. 2. Auflage. Addison Wesley, 1998.

2. Entwerfen und analysieren Sie eine I/O-optimale Prioritätsliste für parallele Platten. Wo ist das Problem? Wie lösen Sie das Problem? Was passiert für mittelgroße Eingaben? Wie wird das verallgemeinert?

Wikipedia

5 Minuten Präsentation + Eine qualitativ hochwertige Wikipedia Seite (vorzugsweise englisch) zu Algorithm Engineering im Allgemeinen oder zu einem Ergebnis aus dieser Vorlesung. Zum Beispiel Filter-Kruskal, Sequence heap, sample sort,...

1. Algorithm Engineering
   bearbeitet von Simon Ochsenreiter