Algorithmen 2, Vorlesung, WS19/20

28| 0:00:00 Start 0:00:11 Externes binäres Mischen 0:13:06 8 Approximationsalgorithmen 0:26:45 9 Fixed-Parameter-Algorithmen 0:38:52 10 Parallele Algorithmen 0:52:22 11 Stringology 0:56:36 12 Geometrische Algorithmen 1:14:40 13 Onlinealgorithmen

27| 0:00:00 Start 0:03:24 Fortgeschrittene Datenstrukturen 0:06:37 Pairing Heaps 0:15:49 Laufzeit im Durchschnitt 0:21:31 Bucket-Queue 0:37:07 Starke Zusammenhangskomponenten 0:44:05 Zusammenfassung: SCC Berechnung 0:53:28 Residual Graph 1:02:41 Randomisierte Algorithmen

26| 0:00:00 Start 0:02:19 The Document Retrieval Problem 0:03:30 Top-k Document Retrieval 0:04:39 Important Query Types 0:05:51 Inverted Indexes 0:09:13 Suffix Arrays 0:11:10 Warmup: Document Listing 0:14:24 Top-k Retrieval 0:15:21 Example 0:21:58 Example Space Usage from [LG17] 0:24:29 Range Minimum Query 0:25:12 2D-Weighted Range Queries 0:34:43 Range Minimum Query Problem 0:49:25 Comparison with other Implementations 0:50:41 (Hyper)Graph Partitioning 0:51:25 Graphs and Hypergraphs 0:54:48 Applications 0:57:08 Successful Heuristic: Multilevel Paradigm 1:09:41 Fiduccia-Mattheyses Algorithm 1:12:28 Adaptive Flow Iterations 1:13:57 Hypergraph Flow Network 1:16:56 Optimized Flow Problem Modeling Approach 1:19:22 Most Balanced Minimum Cut 1:21:10 Experiments: Connectivity Optimization

25| 0:00:00 Start 0:00:54 Datenkompression 0:01:52 Verlustfreie Textkompression 0:03:14 Wörterbuchbasierte Textkompression 0:05:11 Lempel-Ziv Kompression 0:06:22 Beispiel 0:21:16 Burrows Wheeler Transformation 0:47:23 Backward Search 0:57:44 Wavelet Tree Example: Calculate Rank

23| 0:00:00 Start 0:00:09 Suffixtabellenkonstruktion: Zusammenfassung 0:01:49 Suche in Suffix Arrays 0:07:08 LCP-Array 0:27:51 Suffix-Baum aus SA und LCP 0:34:16 Datenkompression 0:36:49 Verlustfreie Textkompression 0:46:48 10.Übung 0:47:28 Themenübersicht 0:47:57 in-place Multikey Quicksort 0:58:11 Suche mit Suffix-Arrays 1:03:55 LCP-Array

23 | 0:00:00 Start 0:00:05 Suffix Array Konstruktionsalgorithmen 0:00:51 SA mit Präfix Verdopplung 0:11:39 Linear Work Suffix Array Construction 0:13:50 SA berechnen 0:17:21 Asymmetrisches Divide-and-Conquer 0:18:38 Rekursion Beispiel 0:34:17 Least Significant Digit First Radix Sort 0:40:22 Implementierung 0:41:42 Verallgemeinerung: Differenzenüberdeckungen 0:46:09 COBS: A Compact Bit-Sliced Signature Index 0:47:28 Motivation / Applications 1:14:27 COBS: Disk Access Pattern

22 | 0:00:00 Start 0:01:50 Volltextsuche von langsam bis schnell 0:03:43 Invertierter Index 0:09:34 Etwas ""Stringology""-Notation 0:11:16 Suffixe Sortieren 0:13:18 Volltextsuche 0:15:22 Suffix-Baum 0:25:08 Alphabet-Modell 0:28:50 Suffix Array Konstruktionsalgorithmen 0:32:47 SA mit Präfix Verdopplung 0:52:33 Beginn Übung 9 0:53:25 Online Algorithmen - Grundlagen 0:59:18 Online Algorithmen - Gütemaß 1:01:12 Beispiel: Ski Rental Problem 1:10:42 Online Algorithmen - Online Bidding

21 | 0:00:00 Start 0:01:49 Strings sortieren 0:22:18 Evaluation 0:27:18 Strings sortieren: Multikey Quicksort 0:39:16 Strings sortieren: Algorithmen-Übersicht 0:43:15 Vergleich sequentielle Algorithmen 0:44:51 Naives Pattern Matching 0:51:58 Knuth-Morris-Pratt 1:14:18 Berechnung des Border-Arrays 1:16:48 Volltextsuche von langsam bis superschnell 1:18:35 Invertierter Index

20 | 0:00:00 Start 0:01:25 Onlinealgorithmen 0:05:59 Competitive analysis 0:07:29 A typical online problem: ski rental 0:08:55 Upper bound for ski rental 0:10:55 Lower bound for ski rental 0:16:04 Paging 0:19:44 Definitions 0:20:23 Paging algorithms 0:24:41 Longest Forward Distance 0:27:48 Using the claim 0:29:48 Comparison of algorithms 0:35:28 A general lower bound 0:41:28 Resource augmentation 0:42:53 Conservative algorithms 0:44:42 Competitive ratio 0:47:01 Counting the faults of OPT 0:48:57 Conclusion 0:50:17 Notes 0:53:07 New results 0:54:51 Randomized algorithms 0:56:49 Three types of adversaries 0:59:04 Marking Algorithms 1:02:31 Competitive ratio of RMARK 1:03:33 Analysis of RMARK 1:08:00 Lower bound for OPT 1:09:59 Upper bound for RMARK 1:10:51 Discussion 1:15:54 Disadvantages of competitive analysis 1:16:55 Stringology

18 | 0:00:00 Start 0:00:05 Wiederholung 0:15:41 Wavelet Tree Dominance Reporting Query 0:20:49 Laufzeit Analyse 0:21:59 Allgemeine Reporting Query 0:26:51 Bitvektoren 0:31:43 Mehr zu Bitvektoren 0:34:08 Übung 8 0:34:14 Themenübersicht 0:35:11 Geometrische Algorithmen 0:38:01 Geometrische Methoden 0:42:44 Intervall Tree: Konstruktion 0:44:57 Intervall Tree: Schnitt mit Punkt 0:48:25 Bitvektoren: Rank und Select 0:50:27 Bitvektoren: Implementierung von Rank 0:56:09 2D Range Queries: Wavelet Tree 0:59:03 2D Range Queries: Wavelet Tree - Count Operation 1:01:33 Sweep-Line: Allgemein 1:02:50 Sweep-Line: Beispiel 1:05:56 Linienschnitt: überlappende Liniensegmente 1:08:00 Linienschnitt: Illustration Sweepline-Algorithmus 1:14:21 Punktorientierung 1:17:23 Konvexe Hülle

18 | 0:00:00 Start 0:00:05 12.1 Streckenschnitt 0:09:33 12.2 2D Konvexe Hülle 0:19:37 3D Konvexe Hülle 0:24:19 12.3 Kleinste einschließende Kugel 0:44:00 Ähnliche Randomisierte Linearzeitalgorithmen 0:48:41 12.4 2D Bereichssuche 1:02:45 Wavelet Tree

17 | 0:00:00 Start 0:00:05 12 Geometrische Algorithmen 0:37:19 Übung 7 0:38:00 Approximationsalgorithmen 0:38:05 Grundlagen 0:38:56 Gütemaß 0:39:32 Klassen 0:41:33 Minimum Metric TSP 0:52:13 Zusammenfassung 0:52:51 Parametrisierte Algorithmen: fixed parameter tractable (FPT) 0:54:57 Parametrisierte Algorithmen: Definition 0:55:56 Techniken 0:57:50 Schiebepuzzle 0:59:59 Parallelverarbeitung: Modelle 1:04:43 PRAM Speicherkonflikte 1:08:38 Verbindungsnetzwerke Struktur 1:11:45 Anwendungen: Präfixsumme - Hypercube 1:16:04 Anwendungen: Paralleler Quicksort 1:20:20 Parallele Programmierung: Ein Einstieg

16 | 0:00:00 Start 0:00:05 Vorlesungswiederholung 0:02:23 Sortieren 0:02:45 Paralleles Quicksort 0:04:09 Anfänger-Parallelisierung 0:05:26 Theoretiker-Parallelisierung 0:08:43 Beispiel 0:16:30 Analyse 0:20:27 Verallgemeinerung für n >> p nach Schema F? 0:30:40 Paralleles Sortieren durch Mehrwegmischen 0:34:12 Mehr zu parallelem Sortieren 0:36:22 Messergebnisse 0:42:28 Übung 0:44:07 Applications 0:46:30 Large real-world networks 0:52:31 Branch and Reduce 0:54:39 Reduction rules 0:58:27 And more reductions 1:00:59 Praxisanwendung 1:02:44 The power of simple reductions 1:04:19 Combining reductions and inexact algorithms 1:06:03 Evolutionary algorithm 1:08:47 ReduMIS 1:12:12 Iterated Local Search 1:13:49 Accelerating Local Search 1:16:28 Linear-time reductions 1:18:46 Scalable Reductions 1:22:51 PACE 2019 Competition 1:25:12 Conclusion

15 | 0:00:00 Start 0:00:05 9 Fixed-Parameter-Algorithmen 0:01:15 Naive tiefenbeschränkte Suche 0:07:03 Reduktionsregeln 0:10:20 Verbesserte tiefenbeschränkte Suche 0:21:00 Zusammenfassung 0:23:23 10 Parallele Algorithmen 0:24:02 Warum Parallelverarbeitung 0:32:43 10.1 Modell 0:36:17 Kostenmodell für Nachrichtenaustausch 0:39:52 Warum kein Multicore-Modell 0:43:55 Formulierung paralleler Algorithmen 0:46:33 Analyse paralleler Algorithmen 0:53:45 10.2 Beispiel: Assoziative Operationen 1:06:39 Analyse 1:11:36 Diskussion Reduktionsoperation 1:12:12 Hyperwürfel 1:15:57 Präfixsummen 1:18:02 Hyperwürfelalgorithmus 1:24:40 Analyse

13 | 0:00:00 Start 0:00:05 Rucksackproblem 0:01:00 Fully Polynomial Time Approximations Scheme 0:02:57 Lemma 6 0:10:57 Lemma 7 0:13:31 Das beste bekannte FPTAS 0:16:27 Optimale Algorithmen für das Rucksackproblem 0:20:44 Fixed-Parameter-Algorithmen 0:22:41 Beispiel: VERTEX COVER 0:25:56 Fixed parameter tractable 0:30:23 Naive tiefenbeschränkte Suche 0:34:04 Kernbildung für Vertex Cover 0:42:25 Übung 6 0:43:04 Randomisierte Algorithmen 0:44:06 Monte Carlo Simulation 0:44:47 Las Vegas zu Monte Carlo 0:48:06 Matrix-Matrix Multiplikation 0:53:39 Coupon Collector 0:56:29 Harmonische Zahlen 0:57:24 Speichermodell 1:00:49 Blockgrößen 1:01:52 I/O-effizientes Design 1:05:17 Externe Priority Queue 1:09:30 Externes Sortieren

13 | 0:00:00 Start 0:00:50 Approximationsalgorithmen 0:06:54 Scheduling unabhängiger gewichteter Jobs auf parallelen Maschinen 0:10:22 List Scheduling 0:19:27 Der Approximationsfaktor 0:34:27 Nichtapproximierbarkeit des Handlungsreisendenproblems (TSP) 0:37:04 Beweis 0:45:57 Euler-Touren/-Kreise 0:48:36 2-Approximation durch minimalen Spannbaum 0:51:56 Beispiel 0:54:47 Beweis 0:55:39 Zusatz: Mehr TSP 1:07:03 Pseudopolynomielle Algorithmen 1:09:07 Beispiel: Rucksackproblem 1:10:50 Dynamische Programmierung nach Profit 1:14:45 Fully Polynomial Time Approximation Scheme 1:16:27 Beispielschranken 1:18:17 FPTAS für Knapsack

12 | 0:00:00 Start 0:00:05 Externe Algorithmen 0:04:35 Externe Prioritätslisten 0:23:46 Experiments 0:29:19 Offenes Problem 0:44:50 Approximationsalgorithmen 0:45:37 Übung 0:46:51 Potentialmethode 0:50:01 preflow-push Algorithmus 0:56:31 FIFO preflow-push Algorithmus 1:10:36 Matching

11 | 0:00:00 Start 0:00:59 Randomisierte Algorithmen 0:01:39 Wichtigste Unterscheidung 0:02:43 Beispiel: Monte Carlo-Algorithmus 0:10:57 Sort Checking II 0:15:22 Hashing II 0:23:57 Cuckoo Hashing 0:35:49 Random Graph Theory 0:39:51 Space Efficient Cuckoo Hashing 0:45:22 Zusammenfassung: Randomisierte Algorithmen 0:47:33 Externe Algorithmen 0:47:37 Das Sekundärspeichermodell 0:51:08 Externe Stapel 0:54:29 Externes Sortieren 1:02:52 Zahlenbeispiel 1:04:17 Mehrwegmischen

10 | 0:00:00 Start 0:00:05 Zusammenfassung letzter Vorlesung 0:02:20 Highest Level Preflow Push 0:04:14 Proof of Lemma 12 0:07:03 Claims 0:20:04 MFIFO: Modified FIFO Selection Rule 0:21:04 Heuristic Improvements 0:28:20 Experimental Results 0:29:51 Timings: Random Graphs 0:33:04 Timings: CG1 0:34:10 Timings: CG2 0:35:07 Timings: AMO 0:36:36 Asymptotics 0:37:54 Recent AE Results on Max-Flow 0:40:04 Zusammenfassung Flows und Matchings

09 | 0:00:00 Start 0:00:05 Ford Fulkerson Algorithm 0:03:24 Matching 0:08:18 Maximum Cardinality Bipartite Matching 0:14:11 Similar Performance for Weighted Graphs 0:19:48 Disadvantage of augmenting paths algorithms 0:28:09 Level Function 0:48:19 Partial Correctness 1:09:34 Searching for Eligible Edges 1:14:36 FIFO Preflow push

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 f(v)

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 Algorithmus für zufällige Kantengewichte 0:32:19 Analyse

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 Dijkstra's Algorithmus: Pseudocode 0:35:35 Beispiel 0:37:04 Laufzeit 0:41:31 Laufzeit im Durchschnitt 0:49:55 Lineare Laufzeit für dichte Graphen 0:59:50 Präfixminima einer Zufallsfolge 1:02:15 Monotone ganzzahlige Prioritätslisten 1:08:41 Bucket-Queue 1:10:47 Operationen 1:13:53 Laufzeit Dijkstra mit Bucket-Queues

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 Example: Sorting Benchmark 1:11:57 JouleSort 1:13:11 Applications that ""Change the World"" 1:18:45 Conclusion

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