| 18.10.2022 |
Organisation und Einführung
|
|
|
|
18.10.2022
|
Sortieren I (InsertionSort)
|
Inkrementeller Algorithmus (24') – Fakultät (11')
|
|
|
20.10.2022
|
Sortieren II (MergeSort)
|
Pseudocode + Beispiel (18') – Korrektheit (16') |
|
| 25.10.2022
|
Laufzeitanalyse, Groß-Oh-Notation
|
Vergleich InsertionSort und MergeSort (18') – Klassifikationsschema für Funktionen (12') |
|
|
27.10.2022
|
Laufzeitanalyse am Beispiel
|
Kubischer Algorithmus für MaxSum (15') – Schnellere Algorithmen für MaxSum (22') |
|
|
03.11.2022
|
Rekursionsgleichungen lösen
|
Substitutionsmethode (10') – Rekursionsbaummethode (10') – Meistermethode (10') |
|
|
08.11.2022
|
Prioritätsschlangen, Heaps, HeapSort
|
Prioritätsschlange, MaxHeapify, BuildMaxHeap (23') – HeapSort (12') |
|
|
10.11.2022
|
Zufallsexperimente
|
Gedankenexperiment (17') – Avagege-Case-Analyse von InsertionSort (11') – Geburtstagsparadoxon & Bonustrack (7') |
|
|
15.11.2022
|
QuickSort und RandomizedQuickSort
|
(Deterministisches) QuickSort (16') – Erwartete Laufzeit von Randomized QuickSort (19') |
|
|
22.11.2022
|
Sortieren in Linearzeit
|
Untere Schranke (13') – CountingSort (10') – RadixSort (7') – BucketSort (14') |
|
|
24.11.2022
|
Das Auswahlproblem
|
Randomisiertes Select (23') – Deterministisches Select (15') |
|
|
29.11.2022
|
Elementare Datenstrukturen
|
Abstrakter Datentyp: Dynamische Menge (8') – Stapel, Schlange, Liste (10') – Von Pseudocode zu Javacode (8') |
|
|
01.12.2022
|
Hashing
|
direkte Adressierung und Hashing mit Verkettung (22') – gute Hashfunktionen und Hashing mit offener Adressierung (23') |
|
|
06.12.2022
|
Binäre Suchbäume
|
Vorarbeiten und Traversierung (21') – Methoden (15') |
|
|
08.12.2022
|
entfällt!
|
– |
|
|
13.12.2022
|
Rot-Schwarz-Bäume [12.01.: Anmerkung zu RBTransplant]
|
Logarithmische Höhe (16') – Einfüge-Operation (16') |
|
|
20.12.2022
|
Datenstrukturen augmentieren
|
Augmentieren – komplett (28')
|
|
|
22.12.2022
|
Nächstes Paar
|
Leider gibt's für diese Vorlesung kein Video :-( |
|
|
10.01.2023
|
Amortisierte Analyse
|
Aggregationsmethode (9') –
Buchhaltermethode (6') –
Potentialmethode (9')
|
|
|
12.01.2023
|
Graphen: Repräsentation und Breitensuche
|
Beispiele und Repräsentation (16') –
Breitensuche (23')
|
|
|
17.01.2023
|
Kürzeste Wege und Dijkstras Algorithmus
|
Dijkstras Algorithmus (22') –
Kürzeste Wege und T9 (7')
|
|
|
24.01.2023
|
Tiefensuche und topologische Sortierung
|
Tiefensuche (Beispiel, Pseudocode, Eigenschaften) (22') –
Topologische Sortierung (Anwendung, Korrektheit) (12')
|
|
|
26.01.2023
|
Minimale Spannbäume
|
Generischer Algorithmus und Korrektheit (13') –
Algorithmen von Jarník–Prim(–Dijkstra) und von Kruskal (18')
|
|
|
31.01.2023
|
Dynamisches Programmieren
|
Stabzerlegung (22') –
Längste Wege (8')
|
|
|
02.02.2023
|
Greedy-Algorithmen
|
Ein einfaches Problem der Ablaufplanung (15') –
Ein gewichtetes Problem der Ablaufplanung (14')
|
|
|
07.02.2023
|
entfällt wegen GADS-Klausur!
|
– |
|
|
09.02.2023
|
Problem des Handlungsreisenden
|
Vorlesungsmitschnitt vom WS 2021, leider ohne die ersten 5' (59')
|
|
