Uni-Logo
Algorithms and Complexity
 

Seminar
Algorithm Engineering
Sommersemester 2008
Prof. Dr. Susanne Albers
Tobias Jacobs


Seminar


Zeit und Ort: Mittwochs, 14.15-15.45 Uhr, SR 01-018, Geb. 101.

Die Teilnahme an dieser Veranstaltung kann wahlweise entweder als Proseminar oder als Seminar angerechnet werden.

Die Anmeldung wird über HIS-LSF durchgeführt. Die Anzahl der Teilnehmer ist auf 12 begrenzt. Anmeldeschluss ist der 20. April 2007.

Bei Anregungen und Fragen zum Seminar wenden Sie sich bitte an Tobias Jacobs.

Aktuelles


12. Juni 2008
Die Sitzung am 25. Juni 2008 beginnt bereits um 14.00 Uhr.

23. April 2008
Die Themenvergabe ist abgeschlossen. der erste Vortrag wird am 21. Mai 2008 stattfinden.

22. April 2008
Das Seminar ist vollständig belegt.

Inhalt der Veranstaltung


Effiziente Algorithmen und Datenstrukturen sind Grundvoraussetzung für anspruchsvolle Computeranwendungen. Algorithmik, die systematische Entwicklung effizienter Algorithmen, ist deshalb entscheidend für die Umsetzung technologischer Möglichkeiten in Anwendungen. Die Lösung der anstehenden Probleme wird aber behindert durch eine über Jahrzehnte gewachsene Kluft zwischen dem Wissensstand der Algorithmentheorie und der praktischen Anwendung von Algorithmen.
Zielsetzung des Algorithm Engineering ist es, diese Gräben zu überwinden. Hierzu gehört die Betrachtung von Rechnermodellen jenseits des klassischen Von-Neumann-Rechners, die systematische Evaluation vorhandener algorithmischer Lösungen, sowie die Entwicklung von Algorithmen und Datenstrukturen, die gutes Praxisverhalten mit theoretischen Gütegarantien vereinen.
In diesem Seminar sollen aktuelle Forschungsergebnisse im Bereich des Algorithm Engineering vorgestellt und diskutiert werden.

Voraussetzungen

  • Grundkenntnisse in Algorithmen und Datenstrukturen.

  • Englischkenntnisse zur Aneignung der ausschl. englischsprachigen Literatur.

Anforderungen

  • Anwesenheit und Mitarbeit.

  • Vorbereitung und Durchführung eines 60minütigen Vortrags.

  • Anfertigung einer ca. fünfseitigen schriftlichen Ausarbeitung des Vortrags bis zum 3. August 2008.

Themen



TerminThemaReferentAusarbeitung
21. Mai 2008Schiefe binäre SuchbäumeRabie Hammoudpdf
28. Mai 2008Speichereffiziente SuchmaschinenChristian Ortolfpdf
4. Juni 2008Identifizierung negativer Zyklen in gewichteten GraphenBenjamin Schulzpdf
11. Juni 2008Datenplatzierung auf parallelen PlattenMatthias Keilpdf
18. Juni 2008Externe BreitensucheRobert Jakobpdf
25. Juni 2008
14.00-16.00 Uhr		Routenplanung: Transit Nodes
Routenplanung: Highway Hierarchies 		Marius Heinzmann
Jan Darmochwal		pdf
pdf
2. Juli 2008Fehlertolerante AlgorithmenSebastian Schefczykpdf
9. Juli 2008Hotlink AssignmentBenjamin Udiljakpdf
16. Juli 2008Cache-blinde AlgorithmenIftikhar Ahmadpdf
23. Juli 2008Algorithmen für Stacking-ProblemeTobias Langnerpdf

Literatur

  • G. S. Brodal and G. Moruz. Skewed binary search trees. In Proceedings of the 14th Conference on Annual European Symposium (ESA'06), 2006.

  • Tobias Jacobs. An experimental study of recent hotlink assignment algorithms. In Proceedings of the 9th Workshop on Algorithm Engineering & Experiments (ALENEX'08) , 2008.

  • B. V. Cherkassky, L. Georgiadis, A. V. Goldberg, R. E. Tarjan and R. F. Werneck. Shortest path feasibility algorithms: An experimental evaluation. In Proceedings of the 9th Workshop on Algorithm Engineering & Experiments (ALENEX'08) , 2008.

  • S. Kashyap, Y. Wan and L. Golubchik. Fast reconfiguration of data placement in parallel disks. In Proceedings of the 7th Workshop on Algorithm Engineering & Experiments (ALENEX'06), 2006.

  • D. Ajwani, U. Meyer and V. Osipov. Improved external memory BFS implementations. In Proceedings of the 8th Workshop on Algorithm Engineering & Experiments (ALENEX'07), 2007.

  • H. Bast, S. Funke, D. Matijevic, P. Sanders and D. Schultes. In transit to constant time shortest-path queries in road networks. In Proceedings of the 8th Workshop on Algorithm Engineering & Experiments (ALENEX'07), 2007.

  • P. Sanders, D. Schultes. Engineering highway hierarchies. In Proceedings of the 14th Conference on Annual European Symposium (ESA'06), 2006.

  • R. Bauer and D. Delling. SHARC: Fast and robust unidirectional routing. In Proceedings of the 9th Workshop on Algorithm Engineering & Experiments (ALENEX'08) , 2008.

  • U. Ferraro-Petrillo, I. Finocchi and G. F. Italiano. The price of resiliency: A case study on sorting with memory faults. In Proceedings of the 14th Conference on Annual European Symposium (ESA'06), 2006.

  • F. Transier, P. Sanders. Compressen inverted indexes for in-memory search engines. In Proceedings of the 9th Workshop on Algorithm Engineering & Experiments (ALENEX'08) , 2008.

  • G. S. Brodal, R. Fagerberg, K. Vinther. Engineering a cache-oblivious sorting algorithm. In Journal of Experimental Algorithmics (JEA), Volume 12, August 2007.

  • F. König, M. Lübbecke, R. Möhring, G. Schäfer and I. Spenke. Solutions to real-world instances of PSPACE-complete stacking. In Proceedings of the 15th Conference on Annual European Symposium (ESA'07), 2007.