Algorithmen und Datenstrukturen 2

WiSe-2021/22

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

Die Veranstaltung dauert 15 Wochen, die Pläne sind vorläufig:

Einführung und All-Pairs Shortest Paths
Network Flow I: Max-flow min-cut theorem, augmenting paths, Ford-Fulkerson
Network Flow II: scaling, Edmonds-Karp, applications, maximum bipartite matching, disjoint paths
Amortisierte Analyse: Dynamische Tabellen, MultiPop Stacks, Splay Trees
Randomisierte Algorithmen I: Contention resolution, Minimum cut
Randomisierte Algorithmen II: Selection, Quicksort
Hartnäckigkeit I: Sprachen, Polynomialzeitreduktionen
Hartnäckigkeit II: P, NP, NP-Vollständigkeit
Recap I
Berechnungsmodelle: Endliche Automaten, Turing-Maschinen, Nicht-Determinismus, starke Church-Turing Hypothese, Word-RAM
Berechenbarkeit: Halteproblem, Satz von Rice
Lineare Programmierung I: Konvexität, Polytope, Simplex-Algorithmus
Lineare Programmierung II: Dualität, Integrale Lineare Programmierung
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
Recap II

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

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.

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.

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.