| 14.10.2025 |
Organisation und Einführung |
|
CLRS, Kapitel 1 |
| 14.10.2025 |
Inkrementell sortieren (InsertionSort) |
Inkrementeller Algorithmus (24') – Fakultät (11') |
CLRS, Kapitel 2.1 |
| 16.10.2025 |
Teilen und herrschen (MergeSort) |
Pseudocode + Beispiel (18') – Korrektheit (16') |
CLRS, Kapitel 2.3 |
| 21.10.2025 |
Laufzeitanalyse, Groß-Oh-Notation |
Vergleich InsertionSort und MergeSort (18') – Klassifikationsschema für Funktionen (12') |
CLRS, Kapitel 2.2 und 3 |
| 23.10.2025 |
Laufzeitanalyse am Beispiel "Maximales Teilfeld" |
Kubischer Algorithmus für MaxSum (15') – Schnellere Algorithmen für MaxSum (22') |
CLRS, Kapitel 4.1 |
| 28.10.2025 |
Rekursionsgleichungen lösen |
Substitutionsmethode (10') – Rekursionsbaummethode (10') – Meistermethode (10') |
CLRS, Kapitel 4.4 und 4.5 |
| 30.10.2025 |
Prioritätsschlangen, Heaps, HeapSort (30.10.: kleine Änderungen am Pseudocode) |
Prioritätsschlange, MaxHeapify, BuildMaxHeap (23') – HeapSort (12') |
CLRS, Kapitel 6 |
| 04.11.2025 |
Zufallsexperimente |
Gedankenexperiment (17') – Average-Case-Analyse von InsertionSort (11') – Geburtstagsparadoxon & Bonustrack (7') |
CLRS, Kapitel 5 und Anhang C.1–3 |
| 06.11.2025 |
QuickSort und RandomizedQuickSort |
(Deterministisches) QuickSort (16') – Erwartete Laufzeit von Randomized QuickSort (19') |
CLRS, Kapitel 7 |
| 11.11.2025 |
Sortieren in Linearzeit |
Untere Schranke (13') – CountingSort (10') – RadixSort (7') – BucketSort (14') |
CLRS, Kapitel 8 |
| 13.11.2025 |
1. Zwischentest |
|
|
| 18.11.2025 |
Das Auswahlproblem |
Randomisiertes Select (23') – Deterministisches Select (15') |
CLRS, Kapitel 9 |
| 20.11.2025 |
Elementare Datenstrukturen |
Abstrakter Datentyp: Dynamische Menge (8') – Stapel, Schlange, Liste (10') – Von Pseudocode zu Javacode (8') |
CLRS, Kapitel 10 |
| 25.11.2025 |
Hashing |
direkte Adressierung und Hashing mit Verkettung (22') – gute Hashfunktionen und Hashing mit offener Adressierung (23') |
CLRS, Kapitel 11 |
| 27.11.2025 |
Binäre Suchbäume |
Vorarbeiten und Traversierung (21') – Methoden (15') |
CLRS, Kapitel 12 |
| 02.12.2025 |
Rot-Schwarz-Bäume |
Logarithmische Höhe (16') – Einfüge-Operation (16') |
CLRS, Kapitel 13 |
| 04.12.2025 |
fällt aus! |
– |
|
| 09.12.2025 |
Datenstrukturen augmentieren |
Augmentieren – komplett (28') |
CLRS, Kapitel 14 |
| 11.12.2025 |
2. Zwischentest |
| 16.12.2025 |
Amortisierte Analyse |
Aggregationsmethode (9') – Buchhaltermethode (6') – Potentialmethode (9') |
CLRS, Kapitel 17 |
| 18.12.2025 |
Graphen: Repräsentation und Breitensuche |
Beispiele und Repräsentation (16') – Breitensuche (23') |
CLRS, Kapitel 22.1 und 22.2 |
| 23.12.2025 |
Nächstes Paar |
– |
|
| 08.01.2026 |
Kürzeste Wege und Dijkstras Algorithmus |
Dijkstras Algorithmus (22') – Kürzeste Wege und T9 (7') |
CLRS, Kapitel 24.3; Dijkstras Originalartikel (1959);
Das Geheimnis des kürzesten Weges (Gritzmann & Brandenberg, 2005) |
| 13.01.2026 |
Tiefensuche und topologische Sortierung |
Tiefensuche (Beispiel, Pseudocode, Eigenschaften) (22') – Topologische Sortierung (Anwendung, Korrektheit) (12') |
CLRS, Kapitel 22.3 und 22.4 |
| 15.01.2026 |
3. Zwischentest |
Anmelden nicht vergessen! |
|
|
| 20.01.2026 |
Minimale Spannbäume
(20.01.: kleine Änderung am Beweis von Lemma 3)
|
Generischer Algorithmus und Korrektheit (13') – Algorithmen von Jarník–Prim und von Kruskal (18') |
CLRS, Kapitel 23 |
| 22.01.2026 |
Dynamisches Programmieren |
Stabzerlegung (22') – Längste Wege (8') |
CLRS, Kapitel 15 |
| 27.01.2026 |
Greedy-Algorithmen |
Ein einfaches Problem der Ablaufplanung (15') – Ein gewichtetes Problem der Ablaufplanung (14') |
CLRS, Kapitel 16 |
