Allgemeines

• Dozent: Prof. Dr. Peter Sanders, Dr. Simon Gog, Dr. Christian Schulz
• Übungsleiter: Michael Axtmann

Aktuelles

• 8. September 2016: Vorlesungsseite angelegt
• 17. Oktober 2016: Skript und Vorlesungsfolien sind online
• 19. Oktober 2016: Update Kapitel 2
• 9. November 2016: Link zu Straßennetzwerken in Übungsblatt 1 korrigiert
• 9. November 2016: Am Mittwoch, dem 16. November, findet ausschließlich Übung statt. Am Anfang werden wir die Übung von heute abschließen.
• 16. Dezember: Korrektur der Folien von der Übung 9. Die Präfixsummeneinträge für "große Elemente" wurden korrigiert.
• 11. Januar: Die Vorlesung am Dienstag, dem 17. Januar, fällt aus. Dafür wird am 18. Januar keine Übung gehalten, sondern 90 Minuten Vorlesung stattfinden.
• 19. Januar: Die Prüfungsanmeldung ist ab sofort freigeschaltet.
• 26. Januar: Die Vorlesung am Mittwoch, dem 1. Februar, fällt aus.
• 2. Fabruar: Als Hilfsmittel ist nur ein DIN-A4 Blatt mit Ihren handschriftlichen Notizen zugelassen.
• 13. Februar: Folien zu den Kapiteln "Fortgeschrittene Datenstrukturen" und "Approximationsalgorithmen" in die Folien mit allen Kapiteln eingefügt. Bisher waren diese beiden Kapitel ausschließlich als separates Kapitel auf der Website verfügbar.
• 13. Februar: Update Kapitel 12. Korrektur im Pseudocode zur Berechnung der kleinsten einschließenden Kugel
• 16. Februar: Korrektur der Musterlösung vom Übungsblatt 6 Aufgabe 3 und der Vorlesungsfolien. In beidem Fällen wurde die Entropie einer Zeichenkette falsch angegeben.
• 20. Februar: Kurrektur der Musterlösung vom Übungsblatt 4 Aufgabe 3c.
• 20. Februar: Kurrektur der Musterlösung vom Übungsblatt 5 Aufgabe 9c.
• 20. Februar: Kurrektur der Musterlösung vom Übungsblatt 7 Aufgabe 7.

Klausur

• Die Ergebnisse der Nachklausur vom 12.09.2017 sind nun online.

Lehrinhalt

Diese Lehrveranstaltung soll Studierenden die grundlegenden theoretischen und praktischen Aspekte der Algorithmentechnik vermitteln. Es werden generelle Methoden zum Entwurf und der Analyse von Algorithmen für grundlegende algorithmische Probleme vermittelt sowie die Grundzüge allgemeiner algorithmischer Methoden wie Approximationsalgorithmen, Lineare Programmierung, Randomisierte Algorithmen, Parallele Algorithmen und parametrisierte Algorithmen behandelt.

Mitschnitt der Vorlesung

Die Aufzeichnung der Vorlesungen und Übungen sind hier zu finden.

Externe Applets

• Fibonacci Heap by Jason Huang and Wei Wang
• String algorithms by Christian Charras und Thierry Lecroq (Knuth-Morris-Pratt, usw.)

Links zu String-Algorithmen

• Top-k Query Completion System by Simon Gog
• Succinct Data Structure Library by Simon Gog

Vorlesungsmaterial

Die Folien der Vorlesung werden nach Kapiteln getrennt online verfügbar sein. Außerdem wird ein Skript angeboten, welches die Themen, die nicht von Algorithms and Data Structures abgedeckt sind, kurz behandelt.

Literaturhinweise

• K. Mehlhorn, P. Sanders: Algorithms and Data Structures - The Basic Toolbox
• K. Mehlhorn, S. Naeher: The LEDA Platform of Combinatorial and Geometric Computing  Topic: Algorithm Engineering, Flows, Geometrie
• R. K. Ahuja, T. L. Magnanti, J.B. Orlin: Network Flows
• M. de Berg, M. van Kreveld, M. Overmars, O. C. Schwarzkopf: Computational Geometry: Algorithms and Applications
• G. Navarro: Compact Data Structures "A Practical Approach", Cambridge University Press
• R. Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.