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

Algorithmen 2, Vorlesung, WS19/20

28: Algorithmen II, Vorlesung, WS 2019/20, 04.02.2020

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

27: Algorithmen II, Vorlesung, WS 2019/20, 03.02.2020

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

26: Algorithmen II, Vorlesung, WS 2019/20, 28.01.2020

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

25: Algorithmen II, Vorlesung, WS 2019/20, 27.01.2020

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

24: Algorithmen II, Vorlesung, WS 2019/20, 21.01.2020

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

23: Algorithmen II, Vorlesung, WS 2019/20, 20.01.2020

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

22: Algorithmen II, Vorlesung und Übung, WS 2019/20, 14.01.2020

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

21: Algorithmen II, Vorlesung, WS 2019/20, 13.01.2020

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

20: Algorithmen II, Vorlesung, WS 2019/20, 07.01.2020

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

19: Algorithmen II, Vorlesung und Übung, WS 2019/20, 17.12.2019

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

18: Algorithmen II, Vorlesung, WS 2019/20, 16.12.2019

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

17: Algorithmen II, Vorlesung und Übung, WS 2019/20, 10.12.2019

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

16: Algorithmen II, Vorlesung und Übung, WS 2019/20, 03.12.2019

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

15: Algorithmen II, Vorlesung, WS 2019/20, 02.12.2019

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

hubhopper

Algorithmen 2, Vorlesung, WS19/20

hubhopper