Algorithmen und Datenstrukturen 2

ALGO2 · WiSe-2021/22

Overview

Ort und Zeit

(Diese Pläne sind vorläufig.)

Wochenplan

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

  1. Einführung und All-Pairs Shortest Paths

  2. Network Flow I: Max-flow min-cut theorem, augmenting paths, Ford-Fulkerson

  3. Network Flow II: scaling, Edmonds-Karp, applications, maximum bipartite matching, disjoint paths

  4. Randomisierte Algorithmen I: Contention resolution, Minimum cut

  5. Randomisierte Algorithmen II: Selection, Quicksort

  6. Hartnäckigkeit I: Sprachen, Polynomialzeitreduktionen

  7. Hartnäckigkeit II: P, NP, NP-Vollständigkeit

  8. Berechenbarkeit: Turing-Maschinen, Halteproblem, Satz von Rice

  9. Lineare Programmierung I: Simplex-Algorithmus

  10. Lineare Programmierung II: Dualität

  11. Parametrisierte Algorithmen

  12. Approximationsalgorithmen

  13. IO-Model: Cache hierarchy

  14. Parallele Algorithmen

Literatur

Allgemeines

Vorlesungsteam

Ähnliche Kurse

Klausur