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
RaumUhrzeit (ca.)Vortragende/rThema
-1199:45Simon OchsenreiterWikipedia: Algorithm Engineering.
Fellipe Bernardes-LimaParallelisiertes Peeling zur Generation vom (M)PHFs.
Florian Tobias SchandinatCache-effizienter Algorithmus zur Run-Formation nach der Snow Plow Heuristik.
Tobias Fleck, Max Wagner, Sebastian UllrichEffiziente Algorithmen zur Berechnung transitiver Hüllen.
Maximilian VogelTriangle Listing Algorithms: Back from the Diversion.
Kurze Pause
-11911:00Eike RöhrsFast Local Search for the Maximum Independent Set Problem.
Klara ReichardMaximum Flows by Incremental Breadth-First Search.
Lea KöckertFinding the Diameter in Large Graphs: Experimentally turning a lower bound into an upper bound.
Mittagspause
-11912:40Joachim PriesnerFast and scalable reachability queries on graphs by pruned labeling with landmarks and paths.
Isabel FunkeShortest Path Algorithms: Engineering Aspects.
Alexander MeierPHAST: Hardware-Accelerated Shortest Path Trees.
Kurze Pause
-10914:00Richard MolitorA Back-to-Basics Empirical Study of Priority Queues.
Malte SchönbrunnBranch-Mispredictions Don't Affect Mergesort.
Lukas BarthStoring a Compressed Function with Constant Time Access.

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 Fellipe Bernardes-Lima

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