Algorithmen und Datenstrukturen 2
WiSe-2023/24- Modulkürzel: B-ALGO-2→ALGO2
- Externe Links:
Ü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.
Ähnliche Kurse
- Algorithms and Data Structures II von Inge Li Gørtz (DTU Copenhagen).
- Algorithm Design von Kevin Wayne (Princeton University).
- Algorithms and Models of Computation von Jeff Erickson (University of Illinois)
- Algorithms von Jeff Erickson (University of Illinois)
- Eine vorherige Iteration von ALGO2 wurde im WiSe-2020 (Prof. Meyer) angeboten, wofür Videos aus Präcoronazeiten zusammengeschnitten wurden.