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

Vortragsthemen

  1. PHAST: Hardware-Accelerated Shortest Path Trees. A. V. Goldberg, A. Nowatzyk, and R. F. Werneck. IPDPS 2011 proceedings, p. 921-931.
  2. Multilevel local search algorithms for modularity clustering. R. Rotta, A. Noack. Journal of Experimental Algorithimics (JEA) 16, 2011, 2.3 p. 1-27.
  3. Engineering burstsort: Toward fast in-place string sorting. R. Sinha, A. Wirth. WEA 2008 proceedings, p. 14-27.
  4. 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
  5. 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.
  6. Storing a Compressed Function with Constant Time Access. J.B. Hreinsson, M. Krøyer, R. Pagh. ESA 2009 proceedings, p. 730-741.
  7. 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.
  8. 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.
  9. Shortest Path Algorithms: Engineering Aspects. A. V. Goldberg. ISAAC 2001 proceedings, p. 502-513.
  10. 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.
  11. Simple and Space-Efficient Minimal Perfect Hash Functions. F. C. Botelho, R. Pagh, N. Ziviani. WADS 2007 proceedings, p. 139-150.

Programmieraufgaben

  1. Implementieren Sie die Datenstruktur aus Towards Optimal Range Medians. B. Gfeller, P. Sanders. ICALP 2009 proceedings, p. 475-486.
  2. Implementieren Sie den allgemeinen difference cover Algorithmus aus Linear Work Suffix Array Construction. J.Kärkkäinen, P. Sanders, S. Burkhardt. Journal of the ACM, 53 (3), p. 1-19, 2006. Tuningtips gibt es in??? Welche difference cover Größe ist für Ihre Implementierung optimal?
  3. Implementieren and evaluieren Sie effiziente Algorithmen für die Berechnung transitiver Hüllen. Implementierungstips gibts beim Dozenten.
  4. Entwerfen und implementieren Sie eine cache-effiziente Min-Max-Prioritätsliste. Tips gibts beim Dozenten.
  5. 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.
  6. Entwerfen und implementieren Sie einen effizienten Algorithmus für die Multiplikation dünn besetzter Matrizen. Tips gibts beim Dozenten.
  7. Optional Teamprojekt mit dem zuletzt genannten Thema: Entwerfen und implementieren Sie eine Heuristik zur Umordnung einer Matrix so, dass der obige Algorithmus cache-effizienter wird. Dabei geht es darum, die Nichtnulleinträge möglichst nah an die Diagonale zu bringen. Ein Vorschlag: Verwendung unseres Graphpartitionierers KaFFPa (rekurisve Bipartionierung, epsilon=1/3). Wieviel bringt das?
  8. Generieren Sie realistische Eingaben für das skyline Problem, indem Sie den Heise-Neuwagenkatalog crawlen und dann weitere Einträge generieren mit zufällig generiertem Alter [0..3 Jahre] und damit korreliertem Preis.
  9. Vergleichen Sie die Leistung von BFS in einem Gittergraphen mit 3 verschiedenen Implementierungen von FIFO-queues (singly-linked lists, unbounded array, hybrid) und mit einer effizienten Handimplementierung der Variante in Algorithms and Data Structures - The Basic Toolbox. K. Mehlhorn, P. Sanders. Springer, 2008.