Algorithmen und Datenstrukturen 2

WiSe-2023/24

Modulkürzel: B-ALGO-2→ALGO2
Externe Links:
QIS

Übersicht

Organisatorisches

Termine. Dienstag und Donnerstag, 08:15-09:30, H VI (Hörsaaltrakt Bockenheim).
Erste Veranstaltung: Dienstag, 17.10.2023, 8-10 Uhr, H VI (Hörsaaltrakt Bockenheim).
Voraussetzungen. Der Kurs baut auf Algorithmen und Datenstrukturen 1 (ALGO1) auf. Sie müssen die Kompetenzen aus ALGO1 bereits meistern, um an ALGO2 teilnehmen zu können.
Organisatorische und inhaltliche Fragen: Die meisten Fragen sind vielleicht weiter unten bereits beantwortet? Ansonsten gerne eine E-Mail an algo1-2023@uni-frankfurt.de (nicht: dell@ oder moodle)

Note: While the videos, lectures, and exercise sheets are in German, it is possible to follow this course in English. The textbooks are available in English, and the written exams will be available bilingually.

Vorlesungskonzept

Der Kurs findet als Flipped Classroom statt, das heißt:

Eigenständige Vorbereitung: Video der Woche, Buchkapitel und erste Übungen durcharbeiten.
„Plenum“ (Dienstag und Donnerstag, 8:15–9:30 in Hörsaal VI, mit allen Studierenden und Professor oder Dozent:in): Fragen & Antworten, Quizze, Kurzpräsentationen, Präsenzübungen und Lösungsspaziergänge. Diese Präsenzzeit findet ausschließlich im Hörsaal statt und wird nicht hybrid übertragen.
„Tutorium“ (in kleinen Gruppen mit Tutor:in): Betreute Präsenzübungen und individuelles Feedback. Diese Präsenzzeit findet ausschließlich im Seminarraum statt und wird nicht hybrid übertragen.

Wochenplan

Die Veranstaltung dauert 15 Wochen:

16. Oktober – 20. Oktober1 Einführung und All-Pairs Shortest Paths
23. Oktober – 27. Oktober2 Network Flow I: Max-flow min-cut theorem, augmenting paths, Ford-Fulkerson
30. Oktober – 3. November3 Network Flow II: scaling, Edmonds-Karp, applications, maximum bipartite matching, disjoint paths
6. November – 10. November4 Amortisierte Analyse: Dynamische Tabellen, MultiPop Stacks, Splay Trees
13. November – 17. November5 Randomisierte Algorithmen I: Contention resolution, Minimum cut
20. November – 24. November6 Randomisierte Algorithmen II: Selection, Quicksort
27. November – 1. Dezember7 Hartnäckigkeit I: Sprachen, Polynomialzeitreduktionen
4. Dezember – 8. Dezember8 Hartnäckigkeit II: P, NP, NP-Vollständigkeit
11. Dezember – 15. Dezember9 Berechnungsmodelle: Endliche Automaten, Turing-Maschinen, Nicht-Determinismus, starke Church-Turing Hypothese, Word-RAM
18. Dezember – 22. Dezember10 Recap I
8. Januar – 12. Januar11 Berechenbarkeit: Halteproblem, Satz von Rice
15. Januar – 19. Januar12 Lineare Programmierung I: Konvexität, Polytope, Simplex-Algorithmus
22. Januar – 26. Januar13 Lineare Programmierung II: Dualität, Integrale Lineare Programmierung
29. Januar – 2. Februar14 Algorithmen für NP-schwere Probleme: Approximationsalgorithmen für Vertex-Cover durch LP-Relaxierung, Randomisiertes Runden, Greedy; FPT-Algorithmus für Vertex-Cover durch Bounded Search Trees
5. Februar – 9. Februar15 Recap II

Literatur

E: Algorithms von Jeff Erickson. [pdf · web]. (Ein wunderschönes Buch.)
KT: Algorithm Design von Jon Kleinberg und Éva Tardos. [pdf · e-UB · UB]. (Ein modernes Buch, das die verschiedenen Entwurfsmethoden in den Mittelpunkt stellt, anstatt einzelner Probleme.)
CLRS: Algorithmen – Eine Einführung (4. Auflage) von Cormen, Leiserson, Rivest, Stein. [e-UB]. (Das Standardwerk.)
C: Linear Programming von Vašek Chvátal. [UB] (Für eine Einführung in die Lineare Programmierung.)
V: Approximation Algorithms von Vijay V. Vazirani [e-UB · UB] (Für eine Einführung in Approximationsalgorithmen.)
CFKLMPPS: Parameterized Algorithms von Cygan, Fomin, Kowalik, et al. [pdf · e-UB · UB] (Für eine Einführung in parametrisierte Algorithmen.)

Lernziele

Nach der Veranstaltung können die Studierenden:

Algorithmen und Datenstrukturen aus dem erweiterten Grundkanon und den Vertiefungsgebieten beschreiben, anwenden, und implementieren,
sie an neue Problemstellungen anpassen,
Eigenschaften (wie etwa die Komplexität und Korrektheit) dieser und ähnlicher Algorithmen untersuchen und begründen,
neue Algorithmen für verwandte Problemstellungen entwickeln.

Außerdem können die Studierenden:

Wichtige Ergebnisse und Konzepte in den Bereichen der NP-Vollständigkeit und Entscheidbarkeit wiedergeben, anwenden, und erläutern,
einschätzen, welche praktischen und theoretischen Konsequenzen die Hartnäckigkeit eines Problems hat,
untersuchen und begründen, ob und warum ein gegebenes Problem hartnäckig ist.

Inhalt

Erweiterter Grundkanon von Algorithmen und Datenstrukturen: All Pairs Shortest Paths, Network Flow, Amortisierte Analyse, Randomisierte Algorithmen, Lineare Programmierung
Hartnäckigkeit: Reduktionen, P und NP, NP-Vollständigkeit, Berechenbarkeit
Vertiefungsgebiete, die in der Frankfurter Theorie vertreten sind: Approximationsalgorithmen, Parametrisierte Algorithmen, und weitere.

Vorlesungsteam

Holger Dell (Professor) | Sprechstunde: Dienstag 10-11 Uhr, Raum 302, RMS 11-15
Claudia Gressler (Sekretärin)
Anselm Haak (Dozent)
Tutor:innen

Klausur

Erstklausur: 13.02.2024
Zweitklausur: 26.03.2024
Altklausuren. Dieses Verzeichnis enthält alle ALGO2-Klausuren samt Lösungsvorschlägen seitdem das Modul B-ALGO-2 in der aktuellen Form existiert.