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 algo2-2023@uni-frankfurt.de (nicht: dell@ oder moodle)
While videos, lectures, and exercise sheets are in German, it is possible to follow this course and ask questions in English. The textbooks are available in English, and the written exams are bilingual.
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): Individuelles Feedback, betreute Präsenzübungen und schriftliche Projekte. Diese Präsenzzeit findet ausschließlich im Seminarraum statt und wird nicht hybrid übertragen.
- Lernzentrum: Das Ingo Wegner-Lernzentrum hat flexible Öffnungszeiten und bietet fachliche Beratung zu den Lerninhalten von ALGO-2 an. Einfach ohne Anmeldung hineinschauen!
Wochenplan
Die Veranstaltung dauert 15 Wochen:
- 16. Oktober – 20. Oktober1 Einführung und All-Pairs Shortest Paths
- 23. Oktober – 27. Oktober2 Network Flow I: Ford-Fulkerson, max-flow min-cut, capacity scaling, Edmonds-Karp
- 30. Oktober – 3. November3 Network Flow II: applications, maximum bipartite matching, disjoint paths
- 6.
November
– 10.
November4
Amortisierte Analyse von Datenstrukturen:
Aggregationsmethode, Buchhaltungsmethode, Potentialmethode, Dynamische Tabellen, Stack mit MultiPop, Splay-BäumeCLRS 17.4 · Ericksons Director’s Cut, Kapitel 9 und Kapitel 10.1, 10.5, 10.6 · Übungsblatt · 📽️1 · 📽️2 · 📽️3 · 📽️4 · 📽️5 · Folien
- 13.
November
– 17.
November5
Randomisierte Algorithmen I:
Contention resolution, Minimum cutKT 13, 13.1, 13.2, 13.12 · Übungsblatt · 📽️ Grundlagen [13 min] · 📽️ Contention Resolution [19 min] · 📽️ Minimum Cut [24 min] · Folien
- 20.
November
– 24.
November6
Randomisierte Algorithmen II:
Selection, QuicksortKT 13.3, 13.5 · Übungsblatt · 📽️ Erwartungswert [23 min] · 📽️ Median und Select [13 min] · 📽️ Quicksort [10 min] · Folien
- 27.
November
– 1.
Dezember7
NP-Härte IE 12.1–12.9 · Übungsblatt · 📽️ Motivation [8 min] · 📽️ CircuitSAT [7 min] · 📽️ P versus NP [10 min] · 📽️ NP-hardness and NP-completeness [7 min] · 📽️ SAT [8 min] · 📽️ 3SAT [8 min] · 📽️ Maximum Independent Set [9 min] · 📽️ Maximum Clique, Minimum Vertex-Cover [9 min] · Folien
- 4.
Dezember
– 8.
Dezember8
NP-Härte IIE 12.10–12.14 · Übungsblatt · 📽️ Graphfärbung [13 min] · 📽️ Hamiltonische Kreise [20 min] · 📽️ Teilmengensumme [19 min] · Gekritzel
- 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. [Volltext als E-Book (deutsch) · Full text as E-Book (english)]. (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
Die Kursleitung ist nur über algo2-2023@uni-frankfurt.de erreichbar.
Klausur
- Anmeldung: Die Anmeldung zu den Klausuren erfolgt ausschließlich über QIS.
- 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.
- Bonuspunkte: Es gibt keine “Bonuspunkte”.
If and only if you want to take the exam as an Erasmus student or a PhD student, you need to register two weeks before the exam at algo2-2023@uni-frankfurt.de.
Ä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.