Algorithmen 2, Vorlesung, WS19/20

08 | 0:00:00 Start 0:00:05 Maximum Flows and Matchings 0:06:49 Computer Blocking Flows 0:21:08 Dinitz Analysis 0:30:00 Übung 3 0:31:22 Kürzeste-Wege-Suche 0:37:28 Dijkstras Algorithmus 0:40:20 Bidirektionale Suche 0:46:21 A*-Suche 1:01:34 Starke Zusammenhangskomponenten 1:10:16 Floys Warshall: SCC als Speedup Technik

07 | 0:00:00 Start 0:02:01 Maximum Flows and Matchings 0:05:38 Network 0:07:41 Flows 0:12:54 s-t Cuts 0:14:33 Anwendung 0:31:49 Lösungsmöglichkeiten 0:45:39 Beispiel 0:49:42 Residual Graph 0:51:51 Augmenting Paths 0:53:19 Ford Fulkerson Algorithm 0:54:44 Ford Fulkerson - Correctness 1:04:19 Max-Flow-Min-Cut theorem 1:13:34 Blocking Flows 1:16:04 Dinitz Algorithm 1:18:45 Dinitz - Correctness 1:19:32 Beispiel

06 | 0:00:00 Start 0:00:05 Rückblick 0:07:15 Invarianten von Gc 0:12:59 Repräsentation offener Komponenten 0:27:34 Beispiel 0:37:43 2-zusammenhängende Komponenten 0:40:35 Übung 0:41:17 Spezielle Priority Queues 0:52:56 Radix Heaps

Wegen technischer Probleme konnten die letzten 45 Minuten der Vorlesung nicht aufgezeichnet werden. 05| 0:00:00 Start 0:00:05 Definition msd(a,b) 0:00:07 Lineare Laufzeit für zufällige Kantengewichte 0:00:39 All-Pairs Shortest Paths 0:05:32 Knotenpotentiale 0:09:18 Hilfsknoten 0:10:58 Definition der Potentiale 0:13:29 Algorithmus 0:14:47 Laufzeit 0:16:45 Distanz zu einem Zielknoten 0:21:11 Ideen für Routenplanung 0:27:24 Bidirektionale Suche 0:30:21 A*-Suche 0:35:29 Benötigte Eigenschaften von

04 | 0:00:00 Start 0:01:28 Binomialbäume 0:02:14 Kaskadierende Schnitte 0:02:39 Kürzeste Wege 0:04:43 Monotone 0:06:51 Bucket-Queue 0:07:18 Operationen 0:11:06 Radix-Heaps 0:13:56 Definition msd(a,b) 0:16:13 Radix-Heap-Invariante 0:18:44 Vergleich: Buckets-Queues und Radix-Heaps 0:19:33 Radix Heap: deleteMin 0:22:56 Buckets bei Änderung von d* 0:26:15 Kosten der deleteMin-Operationen 0:26:42 Laufzeit Dijkstra mit Radix-Heaps 0:27:23 Lineare Laufzeit für zufällige Kantengewichte 0:29:04 Änderung im

03 | 0:00:00 Start 0:00:05 2 Fortgeschrittene Datenstrukturen 0:00:27 2.1 Adressierbare Prioritätslisten 0:01:45 Wälder Bearbeiten 0:02:10 Pairing Heaps 0:03:06 Fibonacci Heaps 0:05:01 Amortisierte Analyse von deleteMin 0:08:48 Warum ist maxRank logarithmisch? – Binomialbäume 0:11:41 Kaskadierende Schnitte 0:17:29 Auftritt Herr Fibonacci 0:18:57 Beweis: 0:23:56 Addressable Priority Queues: Mehr 0:27:47 Fortgeschrittene Graphenalgorithmen; 3 Kürzeste Wege 0:29:56 Allgemeine Definitionen 0:33:14

01 |0:00:00 Start 0:00:10 Materialen 0:06:14 Inhaltsübersicht 0:11:21 Zusammenfassung – Rolle der Algorithmik 0:12:21 ""Machine Learning macht das von selbst?"" 0:15:19 1 Algorithm Engineering 0:23:46 Gaps between Theory & Practice 0:28:21 Algorithmics as Algorithm Engineering 0:34:02 Bits of History 0:40:56 Realistic Models 0:45:06 Design 0:47:53 Analysis 0:50:01 Implementation 0:53:38 Experiments 0:57:04 Algorithm Libraries – Challenges 1:03:03 Problem Instances 1:06:58

02 | 0:00:00 Start 0:00:55 Experimental Methodology 0:07:03 Quality Criteria 0:16:12 Not Here but Important 0:22:41 The Starting Point 0:24:01 The Process 0:29:36 Of Risks and Opportunities 0:34:03 Fortgeschrittene Datenstrukturen 0:36:16 Adressierbare Prioritätenlisten 0:44:00 Grundlegende Datenstruktur 0:48:01 Pairing Heaps 1:06:25 Fibonacci Heaps