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...

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...

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...

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:...

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...

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...

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...

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...

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...