Algorithmen und Datenstrukturen 2

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

Übersicht

Übersicht

• Ab sofort finden die Veranstaltungen Di/Do 8:00-9:45 vollständig online statt:
  • Der Zoom-Link hat die Meeting-ID 966 9678 8856 und den Passcode 004040. Bei schlechter Internetverbindung kann man sich auch telefonisch einwählen unter der Nummer +49 69 3807 9883.
  • Zeiten:
    • 8:00-8:15 auf Zoom. Besprechung, Tipps, Überblick, Einordnung, Beispiele.
    • 8:15-9:15 auf Discord. Die Tutor:innen sind auf Discord verfügbar! Arbeiten Sie dort in Gruppen und rufen Sie die Tutor:innen!
    • 9:15-9:45 auf Zoom. Lösungsspaziergang. (Sie dürfen keine Screenshots oder Mitschnitte machen, weitergeben oder empfangen!)
  • Die Helpdesks finden weiterhin als Mix zwischen Online und Präsenz statt.
• Moodle. Die meisten Lernangebote und Informationen finden sich in Moodle.
• Bei wichtigen Fragen: Sie erreichen den senior staff unter algo221@uni-frankfurt.de (nicht: dell@ oder moodle)

Wochenplan

Die Veranstaltung dauert 15 Wochen:

• 1 Einführung und All-Pairs Shortest Paths
  E 9.1, 9.2, 9.5, 9.6, 9.8 · Organisationsfolien · Übungsblatt
• 2 Network Flow I: Max-flow min-cut theorem, augmenting paths, Ford-Fulkerson
  KT 7.1, 7.2, 7.3 · Übungsblatt
• 3 Network Flow II: scaling, Edmonds-Karp, applications, maximum bipartite matching, disjoint paths
  KT 7.3, 7.5, 7.6 · Übungsblatt
• 4 Amortisierte Analyse: Dynamische Tabellen, MultiPop Stacks, Splay Trees
  CLRS 17.4 · Lecture 9 und Lecture 10.1, 10.5, 10.6 aus den Notizen von Ericksons Director’s Cut · Übungsblatt
• 5 Randomisierte Algorithmen I: Contention resolution, Minimum cut
  KT 13, 13.1, 13.2, 13.12 · Übungsblatt
• 6 Randomisierte Algorithmen II: Selection, Quicksort
  KT 13.3, 13.5 · Übungsblatt
• 7 NP-Vollständigkeit I: Sprachen, Polynomialzeitreduktionen
  E 12, 12.1-12.3, 12.5-12.9 · Übungsblatt
• 8 NP-Vollständigkeit II: P, NP, NP-Vollständigkeit
  E 12.10-12.14 · Übungsblatt
• 9 Recap I
• 10 Berechenbarkeit I: Endliche Automaten, Turing-Maschinen, Nicht-Determinismus, starke Church-Turing Hypothese, Word-RAM
  Kapitel 6 in Ericksons Models of Computation · Übungsblatt
• 11 Berechenbarkeit II: Halteproblem, Satz von Rice
  Kapitel 7 in Ericksons Models of Computation · Übungsblatt
• 12 Lineare Programmierung I: Konvexität, Polytope, Simplex-Algorithmus
  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 · Übungsblatt
• 13 Lineare Programmierung II: Dualität, Integrale Lineare Programmierung
  Notes H von Ericksons Extended Lecture Notes · Linear Programming II von Kevin Wayne · Linear Programming and Polyhedral Combinatorics von Michel Goemans · Übungsblatt
• 14 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
  Notes J von Ericksons Extended Lecture Notes · KT 10.1 · Übungsblatt
• 15 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.

Allgemeines

• Kursformat.
  • Präsenzelemente: Betreute Gruppenarbeit, Lösungsspaziergänge, Besprechungen im Plenum.
  • Online-Elemente: Videos, Folien, Literatur, Übungsblätter, ⭐-Aufgaben, 🌱-Aufgaben, Chat, Helpdesk, individuelles Feedback auf ⭐-Aufgaben.
• 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.
• Anmeldung. Bitte melden Sie sich in Moodle an. Eine Anmeldung per E-Mail ist nicht nötig! Auch die Anmeldung zur Klausur erfolgt nur über QIS oder das Prüfungsamt.
• E-Mail. Nur bei organisatorischen Anliegen (Nachteilsausgleich, Prüfungsvarianten, etc.): E-Mail an algo221@uni-frankfurt.de.

Vorlesungsteam

• Holger Dell (Professor)
• Claudia Gressler (Sekretärin)
• Leo Krull (Dozentin)
• Anselm Haak (Dozent)
• Tutor:innen

Klausur

• Klausur: 22.02.2022 · Klausuraufgaben · Musterlösung
• Nachklausur: 05.04.2022 · Klausuraufgaben · Musterlösung
• Weitere Hinweise zur Klausur finden Sie ganz oben in Moodle.

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