26 | 0:00:00 Starten 0:00:09 Seminar: Proofs from the book 0:04:48 Theses 2018: External, Parallel, and Distributed Sorting 0:11:12 Graph Generators 0:17:23 High Quality Hypergraph Partitioning 0:23:59 Kernbildung in der Praxis 0:38:53 Start Vorlesung 0:40:33 Randomisierte Algorithmen 0:43:44 Approximationsalgorithmen 0:49:41 Online Algorithmen

Algorithmen 2, Vorlesung, WS17/18

26: Algorithmen 2, Vorlesung, WS 2017/18, 06.02.2018

24 | 0:00:00 Starten 0:00:09 highest level preflow push 0:06:51 Example 0:13:50 Proof of Lemma 12 0:17:30 Claims 0:28:47 Heuristic Improvements 0:33:32 Experimental results 0:33:39 Timings: Random Graphs 0:36:16 Timings 0:36:40 Asymptotics 0:36:43 Zusammenfassung Flows und Matchings 0:49:53 Sortieren durch Mehrwege-Mischen 0:50:00 Das Sekundärspeichermodell 0:51:59 Externe Stapel 1:08:30 Externes (binäres) Mischen 1:08:56 Run Formation 1:10:11 Sortieren durch Externes Binäres Mischen 1:12:01 Zahlenbeispiel 1:14:11 Mehrwegmischen 1:20:53 Mehr zu externem Sortieren 1:21:31 Externe Prioritätslisten 1:21:57 Minimale Spannbäume 1:23:36 Externe MST-Berechnung 1:24:14 Beispiel, Sibeyn's algorithm 1:24:19 Mehr zu externen Algorithmen - Basic Toolbox

24: Algorithmen 2, Vorlesung, WS 2017/18, 30.01.2018

25 | 0:00:00 Starten 0:00:15 Highest Level Preflow Push 0:00:55 Claims 0:01:07 Proof of Lemma 12 0:02:32 Claims 0:12:13 Anfang der Übung 0:12:27 Themenübersicht 0:13:08 Preflow-push Algorithmus 0:20:44 FIFO preflow-push Algorithmus 0:42:37 Matching 0:44:31 Bipartite-Matching 0:46:40 Speichermodell 0:48:26 Latenzen 0:49:47 I/O-efffizientes Design 0:51:12 Blockgrößen 0:55:33 Externes Sortieren 1:02:00 Strings Sortieren 1:02:56 Stringology (Zeichenkettenalgorithmen) 1:05:15 Suche in Suffix Arrays 1:05:21 LCP-Array: Berechnung 1:06:18 Datenkompression 1:06:23 Verlustfreie Textkompression 1:06:34 Lempel-Ziv Kompression (LZ) 1:07:33 Range minimum queries (RMQs) 1:07:44 Overview 1:09:43 Burrows-Wheeler-Transformation 1:10:36 Wavelet Tree Example: Calculate Rank 1:12:39 O(n) space /constant query time 1:13:19 Typische Fragenstellungen 1:14:28 Datenstrukturen für Punktmengen 1:14:40 Plane-Sweep-Algorithmen 1:15:57 Konvexe Hülle 1:16:04 Kleinste einschließende Kugel 1:16:37 2D Bereichssuche 1:16:48 Reduktion 1:17:10 Wavelet Tree Dominance Counting Query 1:18:08 Orthogonal range searching 1:18:44 Adressierbare Prioritätslisten 1:18:56 Grundlegende Datenstrukturen 1:19:27 Pairing Heaps 1:19:52 Binomialbäume 1:20:13 Kaskadierende Schnitte 1:20:27 Fortgeschrittene Graphenalgorithmen 1:20:42 Allgemeine Definition 1:21:25 Monotone ganzzahlige Prioritätslisten 1:21:59 Bucket-Queue 1:22:20 Operationen 1:23:25 All-Pairs Shortest Paths 1:23:49 Knotenpotentiale 1:24:23 Ideen für Routenplanung 1:24:42 Distanz zu einem Zielknoten t 1:25:15 Starke Zusammenhangskomponenten 1:26:52 Maximum Flows and Matchings

25: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 05.02.2018

23 | 0:00:00 Starten 0:07:03 Flüsse und Ford Fulkerson 0:08:39 Max Flow - Min Cut 0:12:42 Dinitz: Distanz Label 0:14:37 Dinitz: Schichtgraph 0:15:45 Dinitz: Blockierender Fluss 0:17:21 Dinitz: Blockierender Fluss Operationen 0:20:36 Dinitz: Kosten pro Blockierender Fluss 0:24:14 Dinitz: Laufzeit 0:25:37 Dinitz: Kosten pro Phase, Unit Capacity Network 0:30:24 Maximum Cardinality Bipartite Matching 0:31:35 Preflow-Push Algorithms 0:34:00 Level Function 0:36:49 Procedure genericPreflowPush 1:21:53 Searching for Eligible Edges 1:23:50 Satz 11. Arbitrary Preflow Push finds a maximum flow in time O (n²m)

23: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 29.01.2018

22 | 0:00:00 Starten 0:00:09 Algorithms 1956-now 0:00:47 Residual Graph 0:02:25 A Bad Example for Ford Fulkerson 0:03:19 Blocking Flows 0:04:57 Dinitz Algorithm 0:06:11 Blocking Flows Analysis 0:07:39 Dinitz Analysis 0:17:14 Matching 0:20:28 Maximum Cardinality Bipartite Matching 0:23:44 Disadvantage of augmenting paths algorithms 0:45:52 Übung 11 0:46:25 Kürzeste-Wege-Suche 0:48:11 Suche in Graphen 0:51:22 Dijikstras Algorithmus 0:53:19 Bidirectionale Suche 1:00:03 A*-Suche

22: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 23.01.2018

21 | 0:00:00 Starten 0:00:18 Maximum Flows and Matchings 0:00:37 Definitions: Network 0:02:23 Flows 0:06:45 Applications 0:07:19 Applications in our Group 0:14:39 Option 1: linear programming 0:16:09 Algorithms 1956-now 0:19:49 Example 0:24:55 Residual Graph 0:31:33 Ford Fulkerson Algorithm 0:43:36 Übung 0:44:35 SCC 0:55:06 Floyd Warshall: SCC als Speedup Technik

21: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 16.01.2018

0 | 0:00:00 Starten 0:00:18 Anwendungen von DFS 0:05:13 Tiefensuchschema für G= (V,E) 0:09:29 Starke Zusammenhangskomponenten 0:12:53 SCCs generischer Algorithmus 0:20:12 Ziel: Effizienter Algorithmus 0:27:20 Invarianten 0:39:53 Invarianten von Gc 0:53:47 traverseNonTreeEdge(v,w) 0:56:47 Backtrack(u, v) 1:01:52 Beispiel 1:11:28 Zusammenfassung: SCC Berechnung 1:14:09 Mehr DFS-basierte Linearzeitalgorithmen

20: Algorithmen 2, Vorlesung, WS 2017/18, 15.01.2018

19 | 0:00:00 Starten 0:00:09 Erinnerung 0:21:19 Radix-Heaps 0:35:25 Radix-Heap-Invariante 0:40:45 Radix Heap: deleteMin 0:45:28 Kosten der deleteMin-Operationen 1:07:04 all-pair-shortest-path (APSP) 1:23:03 Definition der Potentiale

hubhopper

Algorithmen 2, Vorlesung, WS17/18

hubhopper