Algorithmen 2, Vorlesung, WS18/19

30 | 0:00:00 Start 0:00:20 Schrumpfgraph 0:02:39 Approximationsalgorithmen 0:03:29 Scheduling unabhängiger gewichteter Jobs auf parallelen Maschinen 0:03:57 Viele kleine Jobs 0:04:52 Untere Schranken 0:05:10 Der Approximationsfaktor 0:07:17 Diese Schranke ist bestmöglich 0:07:49 Mehr zu Scheduling 0:07:58 Nichtapproximierbarkeit des Handlungsreisendenproblems 0:08:33 Hamilton Cycle 0:10:07 TSP mit Dreiecksungleichung 0:10:38 2-Approximstion durch minimalen Spannbaum 0:11:16 Pseudopolynomielle Algorithmen 0:12:26 Fully Polynomial Time Approximation Scheme 0:13:31 Fixed Parameter Algorithmen 0:14:49 VERTEX Cover 0:15:05 Fixed parameter tractable 0:16:32 Naive tiefenbeschränkte Suche 0:19:19 Kernbildung für Vertex Cover 0:21:45 Warum Parallelverarbeitung 0:22:58 Modell Nachrichtengekoppelte Parallelrechner 0:23:30 Kostenmodell für Nachrichtenaustausch 0:24:56 Warum kein Multicore-Modell? 0:26:18 Analyse paralleler Algorithmen 0:26:49 Pseudocode 0:27:41 Weniger ist mehr 0:28:10 Hyperwürfel 0:28:56 Hyperwürfelaulgorithmus 0:31:31 Paralleles Quicksort 0:32:00 Theoretiker-Parallelisierung 0:34:01 Onlinealgorithmen 0:34:29 Competitive analysis 0:35:19 A typical online problem: Ski rental 0:36:32 Paging 0:37:48 Comparison of algorithms 0:39:57 Discussion 0:42:00 Stringology 0:43:29 Strings Sortieren 0:47:55 Naives Pattern Matching 0:48:29 Knuth-Morris-Pratt 0:50:27 Volltextsuche von Langsam bis Superschnell 0:51:18 Invertierter Index 0:52:13 Etwas ""Stringology""-Notation 0:53:14 Suffixe Sortieren 0:53:56 Volltextsuche 0:54:45 Suffix-Baum 0:56:22 SA mit Präfix Verdopplung 0:58:05 Ein erster Teile-und-Herrsche-Ansatz 0:58:52 SA berechnen 1:00:42 Rekursion 1:03:52 LCP-Array 1:07:13 Datenkompression 1:08:51 Wörterbasierte Textkompression 1:09:59 Lempel-Ziv Kompression 1:11:29 Burrows Wheeler Transformation 1:14:47 Geometrische Algorithmen 1:15:37 Plane-Sweep-Algorithmen 1:18:08 Verallgemeinerung 1:21:33 Mehr Linienschnitt 1:22:51 Kleine einschließende Kugel

29 | 0:00:00 Starten 0:00:10 Inhaltsübersicht 0:03:02 Rolle der Algorithmik 0:03:43 Machine Learning macht das von selbst 0:17:02 Algorithm Theory 0:21:47 Graphenalgorithmen 0:22:20 Laufzeit 0:26:50 Satz 1 0:29:13 Monotone ganzzahlige Prioritätslisten 0:30:15 Bucket Queue 0:33:27 Analyse 0:34:30 All-Pair Shortest Paths 0:35:09 Knotenpotentiale 0:36:07 Algorithmus 0:37:46 Landmarks 0:38:33 Zusammenfassung Kürzeste Wege 0:39:47 Fortgeschrittene Datenstrukturen 0:40:21 Adressierbare Prioritätslisten 0:41:04 Grundlegende Datenstruktur 0:42:44 Pairing Heaps 0:47:06 Union by Rank 0:49:25 Zusammenfassung Datenstrukturen 0:50:45 Anwendung von DFS 0:51:16 Starke Zusammenhangskomponenten 0:54:00 Repräsentation offener Komponenten 0:57:08 Zusammenfassung SCC Berechnung 0:57:34 2 zusammenhängende Komponenten 0:57:47 Mehr DFS basierte Linearzeitalgorithmen 0:58:25 Maximum Flows and Matchings 0:58:31 Definitions: Network 0:59:24 Duality between Flows and Cuts 1:00:01 Applications 1:00:27 Algorithms 1956-now 1:04:27 Residual Graph 1:06:27 Ford Fulkerson Algorithm 1:07:34 Max Flow Min Gut theorem 1:07:41 Bad Example for Ford Fulkerson 1:08:35 Blocking Flows 1:08:58 Dinitz Algorithm 1:09:52 Blocking Flow Analysis 1:11:20 Maximum Cardinality Bipartite Matching 1:13:09 Preflow Push Algorithms 1:14:45 Level Function 1:16:04 FIFO Preflow push 1:17:17 Timings 1:17:24 Zusammenfassung Flows and Matchings 1:17:57 Randomisierte Algorithmen 1:18:11 Here Fast SOace Efficient Hashing 1:18:50 Externe Algorithmen

28 | 0:00:00 Start 0:00:08 Übung 11 0:02:04 Themenübersicht 0:02:49 in-place Multikey Quicksort 0:08:18 Partitionierung 0:20:32 Suche mit Suffix-Arrays 0:34:34 Ablauf 0:40:40 Zusammenfassung 0:43:06 LCP-Array 0:52:10 Schnelle Suche mit Suffix-Arrays 0:55:58 Redundante Vergleiche

28 | 0:00:00 Start 0:00:05 Einleitung 0:00:28 Dominik Schreiber - SAT Solving and Automated Planning 0:00:41 Overview 0:01:51 The SAT Problem 0:03:39 SAT Solving 0:05:06 Parallel SAT Solving 0:09:30 Automated Planning 0:13:20 SAT-based Planning 0:17:44 Outlook: Future Research and Teaching 0:23:16 Sebastian Lamm - Distributed Connected Components 0:23:45 Connected Components and Applications 0:25:23 Sequential Algorithms 0:26:16 General Framework 0:29:04 All-Reduce (AR) - Algorithm 0:31:14 Union-find merging (UFM) 0:35:26 Graph Contraction (GC) - Algorithm 0:38:21 Label Propagation (LP) 0:40:44 Comparison 0:43:14 Conclusion 0:44:40 Sebastion Schlag - High Quality Hypergraph Partitioning 0:47:24 Applications 0:48:57 Parallel Sparse-Matrix Vector Product (SpM x V) 0:52:09 From SpM x V to Hypergraph Partitioning 0:56:33 How does Hypergraph Partitioning work? 0:59:27 Taxonomy of Hypergraph Partitioning Tools 1:01:07 Why Yet Another Multilevel Algorithm? 1:05:30 Latest Experimental Results 1:08:45 KaHyPar - Karlsruhe Hypergraph Partitioning 1:10:20 Tobias Maier - Parallele Algorithmen - Einschub Shared Memory Datenstrukturen 1:12:12 Concurrent Hash Table 1:17:19 Migration als Lösung 1:20:33 Vergrößern der Hash Tabelle 1:24:09 Deallocation Problem

26 | 0:00:00 Start 0:00:05 LCP-Array 0:11:29 Textkompression 0:12:39 Lempel-Ziv Kompression (LZ) 0:30:17 Burrows-Wheeler-Transformation 0:35:48 Burrows-Wheeler-Transformation-- Rücktransformation 0:48:41 Was bringt die BWT? 0:50:52 BWT--Kompression 0:58:13 Suche in BWT 0:59:10 Backward Search 1:12:41 Wavelet Tree Example: Calculate Rank

25 | 0:00:00 Start 0:00:05 Suffix Array Konstruktionsalgorithmen 0:01:30 SA mit Präfix Verdopplung 0:04:27 Suffixtabellen 0:05:56 Ein erster Teile-und-Herrsche-Ansatz 0:07:22 Asymmetrisches Divide-and-Conquer 0:14:36 Rekursion 0:27:05 Least Significant Digit First Radix Sort 0:28:40 Stabiles Ganzzahliges Sortieren 0:30:16 Sortieren: Most Significant Digit Radix Sort 0:33:16 Suffix-Baum 0:36:08 Implementierung: Vergleichs-Operatoren 0:37:40 Verallgemeinerung: Differenzenüberdeckungen 0:46:22 Suche in Suffix Arrays 0:48:49 LCP-Array 1:10:20 Suffix-Baum aus SA und LCP 1:10:40 Datenkompression 1:12:20 THeorie Verlustfreier Textkompression 1:22:46 Wörterbuchbasierte Textkompression

24 | 0:00:00 Start 0:00:07 Stringology 0:02:36 Fragen zur letzten Vorlesung/ Wiederholung 0:08:51 Suffix-Baum 0:13:39 Alphabet-Modell 0:17:31 Suffix Array Konstruktionsalgorithmen 0:19:50 SA mit Präfix Verdopplung 0:36:14 Ein erster Teile-und-Herrsche-Ansatz 0:37:32 SA1 berechnen 0:39:42 Berechne SA0 aus SA1 0:41:12 Asymmetrisches Divide-and-Conquer 0:43:50 Übung 0:43:53 Online Algorithmen 0:46:32 kompetitiver Faktor 0:48:15 Ski Rental Problem 1:00:15 Doubling Strategie 1:01:09 Online Bidding

23 | 0:00:00 Start 0:00:05 Competitive analysis 0:01:19 Atypical online problem: ski rental 0:01:50 Paging 0:02:33 Longest Forward Distance is optimal 0:02:50 Comparison of algorithms 0:03:28 Resource augmentation 0:03:41 Competitive ratio 0:03:53 Counting the faults of OPT 0:03:55 Randomized algorithms 0:04:04 Marking Algorithms 0:04:58 Why competitive analysis 0:06:30 Disadvantages of competitive analysis 0:08:35 Stringology 0:10:08 Strings Sortieren 0:19:15 Multikey Quicksort 0:23:21 Ohne Endzeichen 0:31:58 Algorithmen-Übersicht 0:33:11 Vergleich Sequentielle Algorithmen 0:37:40 Naives Pattern Matching 0:43:03 Knuth-Morris-Pratt 0:58:59 Berechnung des Border-Arrays 1:06:06 Volltextsuche von Langsam bis Superschnell 1:11:48 Invertierter Index 1:14:24 Suffixtabellen 1:14:56 Etwas ""Stringology""-Notation 1:16:22 Suffixe Sortieren 1:18:00 Anwendungen 1:19:04 Suffixe Sortieren 1:19:09 Suffix-Baum

22 | 0:00:00 Start 0:00:33 2D Bereichssuche 0:01:30 Wavelet Tree 0:10:21 Bitvektoren 0:12:16 Onlinealgorithmen 0:17:10 Competitive analysis 0:22:46 online problem: ski rental 0:31:16 Paging 0:42:50 Comparison of algorithms 0:48:43 A general lower bound 0:55:01 Resource augmentation 0:57:08 Conservative algorithms 1:05:36 New results 1:07:48 Radomized algorithms 1:09:04 Three types of adversaries 1:11:34 Marking Algorithm 1:13:52 Competetive ratio of RMARK

21 | 0:00:00 Start 0:00:05 12.3 Kleinste einschließende Kugel 0:13:24 Ähnliche Randomisierte Linearzeitalgorithmen 0:18:20 12.4 2D Bereichssuche 0:23:00 1D Bereichssuche 0:34:42 Wavelet Tree 0:43:30 Wavelet Tree Counting Query 0:47:19 Wavelet Tree Dominance Counting Query 1:09:08 Allgemeine Reporting Query 1:16:12 Mehr zu Bitvektoren 1:19:06 13 Onlinealgorithmen

19 | 0:00:00 Start 0:00:05 Geometrische Algorithmen 0:02:41 Elementare geometrische Objekte 0:08:38 Typische Fragestellungen 0:13:23 Datenstrukturen für Punktmengen 0:19:51 Streckenschnitt (line segment intersection) 0:22:44 Streckenschnitt: Untere Schranke 0:26:40 Plane-Sweep für orth. Streckenschnitt 0:35:29 Verallgemeinerung – aber erstmal ""nicht ganz"" 0:38:46 Verallgemeinerung – Grundidee 0:45:00 Verallgemeinerung – Korrektheit 0:46:41 Verallgemeinerung – Implementierung 0:56:15 Verallgemeinerung – Beispiel 0:59:30 Verallgemeinerung – jetzt fast wirklich 1:11:54 Überlappungen finden 1:17:02 Mehr Linienschnitt 1:20:01 2D Konvexe Hülle

20 | 0:00:00 Start 0:00:16 Streckenschnitt 0:08:45 2D Konvexe Hülle 0:11:12 Graham's Scan 0:19:43 3D Konvexe Hülle 0:25:50 Kleinste einschließende Kugel 0:50:26 Übung 9 0:51:44 Geometrische Algorithmen 0:54:56 Geometrische Methoden 0:59:46 Sweep-Line Beispiel: Skyline 1:22:03 Punktorientierung

18 | 0:00:00 Start 0:00:16 Sortieren 0:00:33 Theoretiker-Parallelisierung 0:00:47 Analyse 0:01:06 Verallgemeinerung 0:02:49 Paralleles Sortieren durch Mehwegemischen 0:07:54 Messungen Spare T1 - 8 Kerne, 128 bit Elemente 0:10:53 Mehr zu parallelem sortieren 0:14:24 Experiments 0:25:29 Messungen 0:35:18 Mehr zu parallelem Algorithmen - Parallelisierung der Basic Toolbox 0:49:10 Übung 0:49:15 Themenübersicht 0:50:09 Parametrisierte Algorithmen 1:00:03 Parallelverarbeitung 1:04:16 PRAM 1:07:13 Verbindungsnetzwerke 1:13:07 Anwendungen 1:26:54 Parallele Programmierung

17 | 0:00:00 Starten 0:00:05 Nachrichtengekoppelte Parallelrechner 0:02:02 Analyse paraller Algorithmen 0:12:22 Beispiel: Assoziative Operationen (= Reduktion) 0:27:26 Diskussion Reduktionsoperation 0:28:36 Hyperwürfel 0:34:09 Hyperwürfelalgorithmus 0:46:14 Sortieren 0:47:12 Paralleles Quicksort 0:52:53 Beispiel 1:13:00 Analyse 1:21:01 Paralleles Sortieren durch Mehrwegemischen

16 | 0:00:00 Start 0:00:57 Naive tiefenbeschränkte Suche 0:01:20 Naive tiefenbeschränkte Suche - Laufzeit 0:02:29 Kernbildung für Vertex Cover 0:03:01 Kernbildung für Vertex Cover - Korrektheit 0:03:47 Kernbildung für Vertex Cover - Laufzeit 0:05:05 Kernbildung für Vertex Cover - Beispiel 0:07:02 Reduktionsregeln 0:09:36 Verbesserte tiefenbeschränkte Suche 0:14:06 Weitere Verbesserungen 0:15:52 Zusammenfassung 0:19:41 Parallele Algorithmen 0:20:21 Warum Parallelverarbeitung 0:28:49 Modell - Nachrichtengekoppelte Parallelrechner 0:30:07 Kostenmodell für Nachrichtenaustausch 0:34:05 Warum kein Multicore Modell 0:36:37 Formulierung paralleler Algorithmen 0:39:53 Analyse paralleler Algorithmen 0:40:16 Dynamic Space Efficient Hashing 0:41:01 Basics - Hash Tables 0:42:18 Classic Space Efficient Hashing 0:43:20 Final Size Not Known A Priori 0:45:18 Resizing 0:47:07 Secondary Contribution - Efficient Growing 0:50:47 Multi Table Approach 0:52:08 Cuckoo Displacement 0:53:14 Cintribution - Dynamic Space Efficient Cuckoo Table 0:55:51 Result - Insertion into Growing Table 0:56:28 Result - Word Count Benchmark 0:57:03 Result - Load Bound 0:57:40 Conclusion 0:59:30 Übung 0:59:59 Approximtionsalgorithmen

15 | 0:00:00 Starten 0:00:05 8 Approximationsalgorithmen 0:00:23 Scheduling unabhängiger gewichteter Jobs auf parallelen Machinen 0:01:03 List Scheduling 0:01:27 Viele Kleine Jobs 0:04:13 Der Approximationsfaktor 0:08:23 Diese Schranke is bestmöglich 0:10:04 Mehr zu Scheduling 0:24:05 Nichtapproximierbarkeit des Handlungsreisendenproblems (TSP) 0:29:53 TSP mit Dreiecksungleichung 0:31:12 2-Approximation durch minimalen Spannbaum 0:35:57 Beispiel 0:40:12 Mehr TSP 0:51:39 Pseudopolynomielle Algorithmen 0:53:41 Beispiel Rucksackproblem 0:55:38 Dynamische Programmierung nach Profit 0:56:59 Fully Polynomial Time Approximation Scheme 1:00:23 FPTAS für Knapsack 1:02:42 Das beste bekannte FPTAS 1:04:31 Fully Polynomial Time Approximation Scheme 1:05:16 Optimale Algorithmen für das Rucksackproblem 1:09:58 9 Fixed-Parameter-Algorithmen 1:11:51 Beispiel: VERTEX COVER (Knotenüberdeckung) 1:13:32 VERTEX COVER Grundlegendes 1:16:02 FIxed parameter tractable 1:19:06 Naive tiefenbeschränkte Suche 1:23:27 Kernbildung für Vertex Cover

14 | 0:00:00 Starten 0:05:55 Frage 0:07:29 Große Queues 0:08:34 Minimale Spannbäume 0:10:49 Mehr zu externen Algorithmen-Basic Toolbox 0:16:58 Approximationsalgorithmen 0:23:15 Scheduling unabhängiger gewichteter Jobs auf parallelen Maschienen 0:28:52 List Scheduling 0:36:37 Untere Schranken 0:38:16 Übung 0:38:35 Matching 0:41:14 Bipartite-Matching 0:43:07 Matching Anwendungen 0:46:08 Randomisierte Algorithmen 0:48:48 Monte Carlo Simulation 0:51:33 Las Vegas --> Monte Carlo 0:55:38 Beispiel 1 Matrix-Matrix Multiplikation 1:05:51 Beispiel 2 Coupon Collector 1:11:35 Speichermodell 1:14:33 I/O-effizientes Design 1:16:15 Blockgrößen

13 | 0:00:00 Starten 0:00:05 Here: Fast Space Efficient Hashing 0:01:06 Cuckoo Hashing 0:01:57 Space Efficient Cuckoo Hashing 0:03:41 Random Graph Theory 0:05:52 Das Sekundärspeichermodell 0:09:50 Externe Stapel 0:15:00 Externes Sortieren 0:18:31 Externes binäres Mischen - I/O - Analyse 0:23:02 Run Formation 0:24:57 Sortieren durch Externes Binäres Mischen 0:27:07 Zahlenbeispiel: PC 2018 0:31:56 Mehrwegmischen 0:36:43 Sortieren durch Mehrweg-Mischen 0:50:13 Externe Prioritätslisten 0:54:17 Mittelgroße PQs 0:58:26 Analyse - I/Os 1:01:25 Analyse - Vergleiche (Maß für interne Arbeit) 1:02:33 Große Queues 1:07:45 Experiments 1:09:42 Alpha-21164, 533 MHz, 1997 1:14:13 AMD Ryzen 1800X 1:16:03 Minimale Spannbäume 1:22:01 Externe MST-Berechnung 1:27:18 Approximationsalgorithmen

12 | 0:00:00 Start 0:00:05 Randomisierte Algorithmen 0:00:23 Sortieren - Ergebnisüberprüfung (cheking) 0:03:23 Sort Cheking 0:10:42 Hashing 0:13:55 Here: Fast Space Efficient Hashing 0:15:44 Related Work 0:21:27 Cuckoo Hashing 0:25:55 Cuckoo Hashing - Rebuilds 0:35:29 Cuckoo Hashing - How many Rebuilds? 0:37:45 Random Graph Theory 0:41:12 Space Efficient Cuckoo Hashing 0:45:21 Zusammenfassung: Randomisierte Algorithmen 0:46:00 Ausblick: Randomisierte Algorithmen 0:46:47 Übung 5 0:46:56 Themenübersicht 0:48:36 Potentialmethode 0:53:52 Preflow-push Algorithmus 1:01:56 FIFO preflow-push Algorithmus

11 | 0:00:00 Start 0:00:05 Ford Fulkerson Algorithm 0:01:12 Blocking Flows 0:01:26 Dinitz Algorithm 0:02:02 Dinitz Analysis 0:03:10 Preflow-Push Algorithms 0:03:59 Level Function 0:09:26 FIFO Preflow push 0:10:00 Highest Level Preflow Push 0:11:13 Proof of Lemma 12 0:16:11 Claims 0:35:57 Heuristic Improvements 0:42:24 Experimental results 0:47:29 Trainings: Random Graphs 0:53:01 Training: CG1 0:56:33 Training: CG2 0:58:11 Training: AMO 1:03:46 Zusammenfassung Flows und Matchings 1:10:08 6. Randomisierte Algorithmen 1:14:20 6.1 Sortieren - Ergenisüberprüfung