Algorithmen und Datenstrukturen 2

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

Ü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)

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
  Übungsblatt · E 9.1, 9.2, 9.5, 9.6, 9.8 · 📽️ · Folien
• 23. Oktober – 27. Oktober2 Network Flow I: Ford-Fulkerson, max-flow min-cut, capacity scaling, Edmonds-Karp
  Übungsblatt · E 10 (oder KT 7.1, 7.2, 7.3) · 📽️1 · 📽️2 · 📽️3 · 📽️4 · 📽️5 · Folien
• 30. Oktober – 3. November3 Network Flow II: applications, maximum bipartite matching, disjoint paths
  Übungsblatt · E 11 (oder KT 7.3, 7.5, 7.6) · 📽️1 · 📽️2 · Folien
• 6. November – 10. November4 Amortisierte Analyse von Datenstrukturen: Aggregationsmethode, Buchhaltungsmethode, Potentialmethode, Dynamische Tabellen, Stack mit MultiPop, Splay-Bäume
  Übungsblatt · CLRS 17.4 · Ericksons Director’s Cut, Kapitel 9 und Kapitel 10.1, 10.5, 10.6 · 📽️1 · 📽️2 · 📽️3 · 📽️4 · 📽️5 · Folien
• 13. November – 17. November5 Randomisierte Algorithmen I: Contention resolution, Minimum cut
  Übungsblatt · KT 13, 13.1, 13.2, 13.12 · 📽️ Grundlagen [13 min] · 📽️ Contention Resolution [19 min] · 📽️ Minimum Cut [24 min] · Folien
• 20. November – 24. November6 Randomisierte Algorithmen II: Selection, Quicksort
  Übungsblatt · KT 13.3, 13.5 · 📽️ Erwartungswert [23 min] · 📽️ Median und Select [13 min] · 📽️ Quicksort [10 min] · Folien
• 27. November – 1. Dezember7 NP-Vollständigkeit I
  Übungsblatt · E 12.1–12.9 · 📽️ 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-Vollständigkeit II
  Übungsblatt · E 12.10–12.14 · 📽️ Graphfärbung [13 min] · 📽️ Hamiltonische Kreise [20 min] · 📽️ Teilmengensumme [19 min] · Gekritzel
• 11. Dezember – 15. Dezember9 Berechenbarkeit I
  Übungsblatt · Kapitel 6 in Ericksons Models of Computation · 📽️ Turing-Maschine [24 min] · 📽️ Entscheidbarkeit [23 min] · 📽️ Berechenbarkeit [5 min] · 📽️ Semi-Entscheidbarkeit [10 min] · 📽️ Variationen der Turing-Maschine [18 min] · 📽️ Komplexität [9 min] · Gekritzel
• 18. Dezember – 22. Dezember0 Recap I
• 8. Januar – 12. Januar10 Berechenbarkeit II: Halteproblem, Satz von Rice
  Übungsblatt · Kapitel 7 in Ericksons Models of Computation · 📽️ Entscheidbarkeit und Semientscheidbarkeit [10 min] · 📽️ Eine universelle Turingmaschine [19 min] · 📽️ Eine unentscheidbare Sprache [5 min] · 📽️ Unentscheidbarkeit mittels Reduktion [12 min] · 📽️ Der Satz von Rice [17 min] · Gekritzel
• 15. Januar – 19. Januar11 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
  Übungsblatt · Notes J von Ericksons Extended Lecture Notes · KT 10.1 · (ergänzend: V 12, 13.1, 1, 2; KT 11.4, 11.6; CFKLMPPS 3.1) · 📽️ Approximationsalgorithmen für Vertex-Cover [4 min] · 📽️ LP-Rundung, E J.6, J.2 [15 min] · 📽️ Randomisierte LP-Rundung, E J.7 [8 min] · 📽️ Gierige Algorithmen, E J.3, J.5 [13 min] · 📽️ Übersicht [2 min] · 📽️ Approximationsalgorithmen für Load Balancing, E J.1 [24 min] · 📽️ Exakter Bounded Search Tree Algorithmus für Vertex-Cover, KT 10.1 [14 min] · Gekritzel
• 22. Januar – 26. Januar12 Lineare Programmierung I
  Übungsblatt · Notes I von Ericksons Extended Lecture Notes · Linear Programming I von Kevin Wayne · Linear Programming III von Kevin Wayne · Linear Programming and Polyhedral Combinatorics von Michel Goemans · 📽️ LP Definition [12 min] · 📽️ Zulässige und optimale Lösungen [22 min] · 📽️ LP Algorithmen [17 min] · Folien
• 29. Januar – 2. Februar13 Lineare Programmierung II
  Übungsblatt · Notes H von Ericksons Extended Lecture Notes · Linear Programming II von Kevin Wayne · Linear Programming and Polyhedral Combinatorics von Michel Goemans · 📽️ Primal und Dual LP [10 min] · 📽️ Dualität [20 min] ⛴ · 📽️ (M)(I)LP Komplexität [20 min] · Folien
• 5. Februar – 9. Februar0 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
• Einsicht zur Zweitklausur: Reklamationen zu den Freitext-Aufgaben können Sie am 04.04.2024 zwischen 13:30 und 15:00 in folgendem Zoom-Meeting anbringen: Link
• 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”.

Ä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.