Algorithmen und Datenstrukturen 2

WiSe-2023/24

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

Ü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
E 9.1, 9.2, 9.5, 9.6, 9.8 · Übungsblatt · 📽️ · Folien
23. Oktober – 27. Oktober2 Network Flow I: Ford-Fulkerson, max-flow min-cut, capacity scaling, Edmonds-Karp
E 10 (oder KT 7.1, 7.2, 7.3) · Übungsblatt · 📽️1 · 📽️2 · 📽️3 · 📽️4 · 📽️5 · Folien
30. Oktober – 3. November3 Network Flow II: applications, maximum bipartite matching, disjoint paths
E 11 (oder KT 7.3, 7.5, 7.6) · Übungsblatt · 📽️1 · 📽️2 · Folien
6. November – 10. November4 Amortisierte Analyse von Datenstrukturen: Aggregationsmethode, Buchhaltungsmethode, Potentialmethode, Dynamische Tabellen, Stack mit MultiPop, Splay-Bäume
CLRS 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 cut
KT 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, Quicksort
KT 13.3, 13.5 · Übungsblatt · 📽️ Erwartungswert [23 min] · 📽️ Median und Select [13 min] · 📽️ Quicksort [10 min] · Folien
27. November – 1. Dezember7 NP-Härte I
E 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 II
E 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.