Algorithm Engineering: Materialien zur Vorlesung
- Skript zusammengestellt von Felix Putze
- Vorlesung
- Vortrag FilterKruskal
- External Memory Folien von Roman Dementiev. Wir haben daraus gemacht: STXXL, cache oblivious Algorithmen und suffix sorting.
- Suffix Sorting
Vortragsthemen
-
PHAST: Hardware-Accelerated Shortest Path Trees. A. V. Goldberg, A. Nowatzyk, and R. F. Werneck. IPDPS 2011 proceedings, p. 921-931.
-
Multilevel local search algorithms for modularity clustering. R. Rotta, A. Noack. Journal of Experimental Algorithimics (JEA) 16, 2011, 2.3 p. 1-27.
-
Engineering burstsort: Toward fast in-place string sorting. R. Sinha, A. Wirth. WEA 2008 proceedings, p. 14-27.
-
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
-
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.
-
Storing a Compressed Function with Constant Time Access. J.B. Hreinsson, M. Krøyer, R. Pagh. ESA 2009 proceedings, p. 730-741.
-
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.
-
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.
-
Shortest Path Algorithms: Engineering Aspects. A. V. Goldberg. ISAAC 2001 proceedings, p. 502-513.
-
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.
-
Simple and Space-Efficient Minimal Perfect Hash Functions. F. C. Botelho, R. Pagh, N. Ziviani. WADS 2007 proceedings, p. 139-150.
Programmieraufgaben
-
Implementieren Sie die Datenstruktur aus
Towards Optimal Range Medians. B. Gfeller, P. Sanders. ICALP 2009 proceedings, p. 475-486.
-
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?
-
Implementieren and evaluieren Sie effiziente Algorithmen für die Berechnung transitiver Hüllen. Implementierungstips gibts beim Dozenten.
-
Entwerfen und implementieren Sie eine cache-effiziente Min-Max-Prioritätsliste. Tips gibts beim Dozenten.
-
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.
-
Entwerfen und implementieren Sie einen effizienten Algorithmus für die Multiplikation dünn besetzter Matrizen. Tips gibts beim Dozenten.
-
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?
-
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.
-
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.