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:

Donnerstag 7.2.2013, 14:00-19:00

Vortragsthemen

20 Minuten Präsentation.
  1. Fast, Small, Simple Rank/Select on Bitmaps. Gonzalo Navarro and Eliana Providel. SEA 2012 proceedings.
    bearbeitet von Elias Bordolo
  2. Branch Mispredictions Don't Affect Mergesort. Amr Elmasry, Jyrki Katajainen and Max Stenmark. SEA 2012 proceedings.
    bearbeitet von Jan-Martin Knorr
  3. 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 Valentin Buchhold
  4. 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 Marcel Radermacher
  5. Storing a Compressed Function with Constant Time Access. J.B. Hreinsson, M. Krøyer, R. Pagh. ESA 2009 proceedings, p. 730-741.
    bearbeitet von Metodi Manolov
  6. 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 Luben Alexandrov
  7. PHAST: Hardware-Accelerated Shortest Path Trees. A. V. Goldberg, A. Nowatzyk, and R. F. Werneck. IPDPS 2011 proceedings, p. 921-931.
    bearbeitet von Tobias Zirr
  8. Engineering burstsort: Toward fast in-place string sorting. R. Sinha, A. Wirth. WEA 2008 proceedings, p. 14-27.
    bearbeitet von Dominik Messinger
  9. 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 Emanuel Schrade
  10. 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 Tobias Zündorf
  11. 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 Fabian Klute
  12. 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 Michael Axtmann
  13. Shortest Path Algorithms: Engineering Aspects. A. V. Goldberg. ISAAC 2001 proceedings, p. 502-513.
    bearbeitet von David Merkel
  14. Simple and Space-Efficient Minimal Perfect Hash Functions. F. C. Botelho, R. Pagh, N. Ziviani. WADS 2007 proceedings, p. 139-150.
    bearbeitet von Lorenz Diener

Programmieraufgaben

5 Minuten Präsentation + Programm + 2 Seiten Ausarbeitung.
  1. Implementieren Sie einen near-inplace radix-sort. Hinweise. Vergleichen Sie Ihre Implementierung mit STL std:sort.
    bearbeitet von Christian Ocker
  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 Misch Sadler, Sebastian Lehmann, Eric Braun
  3. Implementieren Sie einen effizienten sequentiellen Radix-Sort für 8-bit Schlüssel unter Verwendung der Ideen diesem Papier. Hier wird durch geschickte Kombination von Hardware- und Betriebssystemeigenschaften eine deutliche Beschleunigung gegenüber dem naiven Ansatz erreicht. Gedacht ist an eine stark vereinfachte Linux-Implementierung. Grob gesagt nutzt man aus, dass der virtuelle Adressraum viel größer ist als der physikalische. Weitere Informationen gibts beim Dozenten.
    bearbeitet von Florian Drews
  4. 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 N.N.
  5. Entwerfen und implementieren Sie eine cache-effiziente Min-Max-Prioritätsliste. Tips gibts beim Dozenten.
    bearbeitet von Markus Jung
  6. 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 N.N.
  7. Entwerfen und implementieren Sie einen effizienten Algorithmus für die Multiplikation dünn besetzter Matrizen. Tips gibts beim Dozenten.
    bearbeitet von Yvonne Braun
  8. Implementieren Sie einen effizienten Mischalgorithmus der mit predicated instructions arbeitet. Können Sie das 4-Wege-Mischen und 8-Wege-Mischen verallgemeinern? Vergleichen Sie sich mit den Funktionen der STL.
    bearbeitet von Florian Richter

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?