Algorithmen 2, Vorlesung, WS17/18

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

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

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

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)

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

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

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

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

18 | 0:00:00 Starten 0:00:09 Fortgeschrittene Graphenalgorithmen 0:04:34 Allgemeine Definition 0:06:17 Kante relaxieren 0:07:11 Dijkstra's Agorithmus 0:08:40 Beispiel 0:09:00 Laufzeit 0:14:55 Lineare Laufzeit für dichte Graphen 0:26:30 Präfixminima einer Zufallsfolge 0:27:32 Monotone ganzzahlige Prioritätslisten 0:31:28 Bucket-Queue 0:34:22 Operation 0:35:17 Laufzeit Dijkstra mit Bucket-Queues 0:36:35 Übung8 0:36:41 Amortisierte Analyse 0:39:57 Legende 0:41:59 Fibonacci Heaps - Insert 0:44:09 Fibonacci Heaps - Delete Min 0:56:33 Fibonacci Heaps - Decrease Key 1:02:11 Fibonacci Heaps

17 | 0:00:00 Starten 0:00:46 Aufgabenvarianten 0:01:16 Verteilte Eigenschaften 0:01:30 Theoretiker-Quicksort 0:06:08 Fortgeschrittene Datenstrukturen 0:10:27 Adressierbare Prioritätslisten 0:34:55 Adressierbare Prioritätslisten: Anwendungen 0:38:27 Grundlegende Datenstruktur 0:39:29 Wälder bearbeiten 0:40:59 Pairing Heaps (Paarungs-Haufen??) 0:46:39 Pairing Heaps - Repräsentationen 0:48:35 Pairing Heaps - Analyse 0:49:51 Fibonacci Heaps 0:53:27 Repräsentation 0:54:09 deleteMin mit Union-by-Rank 0:55:46 Schnelles Union-by-Rank 0:59:15 Amortisierte Analyse von deleteMin 1:03:06 Warum ist maxRank logarithmisch? - Binomialbäume 1:07:19 Kaskadierende Schnitte 1:13:30 Auftritt Herr Fibonacci 1:18:39 Beweis 1:23:23 Addressable Priority Queues: Mehr 1:25:24 Zusammenfassung: Datenstrukturen

16 | 0:00:00 Starten 0:00:09 Parallele Reduktion: Algorithmus 0:05:38 Analyse paralleler Programme 0:14:10 Parallele Präfixsummen 0:44:36 Übung 7 0:45:28 Expertenauswahl 0:49:41 Parallelverarbeitung 0:52:09 PRAM 0:54:56 Verbindungsnetzwerke 1:01:33 Nachrichtenaustausch: Pipelining 1:06:31 Anwendungen 1:20:13 Parallele Programmierung

15 | 0:00:00 Starten 0:00:33 Überblick 0:01:07 Problemstellung 0:04:06 Auswahl von Experten 0:05:07 Auswahl von Experten: der deterministische Weighted Majority Algorithm (wma) 0:07:49 Qualität von WMA 0:09:31 Beweis 0:16:48 Verallgemeinerte Problemstellung 0:18:17 Randomisiert: randWMA 0:21:13 Qualität von randWMA 0:23:06 Beweis 0:31:57 Warum Parallelverarbeitung? 0:42:17 Verschiede Modelle für Parallelverarbeitung 0:43:44 Nachrichtengekoppelter Parallelrechner 0:45:29 Parallelrechner mit globalem Speicher 0:46:50 Nachrichtenkopplung versus Speicherkopplung 0:52:19 Parallele Beispielalgorithmen 0:52:59 Überblick 0:54:08 Modell für Nachrichtenaustausch 0:58:14 Kostenmodell für Nachrichtenaustausch 1:01:24 Programmiermodell 1:05:54 Reduktion 1:09:50 Parallele Reduktion: Algorithmusidee 1:13:57 Parallele Reduktion: Algorithmus 1:20:10 Parallele Reduktion: Analyse 1:21:45 Parallele Reduktion mit p<n 1:24:04 Anmerkungen

14 | 0:00:00 Starten 0:01:57 LRU - Beispiel 0:05:27 LRU ist K- Kompetitiv 0:06:22 LRU ist K-Kompetitive – Beweisskizze 0:15:44 Resource Augmentation: (h,k)-Seitenwechsel 0:24:12 Randomisiert 0:25:14 Randomisierte Onlinealgorithmen 0:26:09 Widersacher: verschieden miese Typen 0:30:04 Wettbewerbsfaktor 0:31:52 RANDMARK Algorithmus 0:35:50 Beweis 0:55:17 Übung 6 0:55:45 Online Algorithmen

13 | 0:00:00 Starten 0:02:50 Eine Reihe von Beispiele 0:05:39 Beispiel Job-Scheduling 0:07:07 Beispiel Skiausleihe 0:09:30 Speicherverwaltung 0:12:04 Auswahl von Experten 0:14:23 Beispiel Selbstorganisierende Datenstrukturen 0:15:12 Online-Algorithmus 0:19:55 Competitive Analysis 0:24:45 Wettbewerbsfaktor 0:27:53 Strikte c-Kompetitivität 0:30:07 Wettbewerbsfaktor und strikte Kompetitivität 0:37:13 Nicht-strikte c-Kompetitivität 0:43:36 ListScheduling ist (fast) ein Onlinealgorithmus 0:46:48 Skiausleihe 0:47:19 Optimale Kosten 0:49:27 Deterministische Entscheidung für Skilauf 0:52:03 Speicherverwaltung 0:54:28 Plan für diesen Abschnitt 0:56:17 Longest Forward Distance (LFD) 0:59:14 Optimalität von LFD 0:59:41 Optimalität von LFD-Beweisskizze 1:05:38 Deterministische Onlinealgorithmen 1:15:10 Untere Schranke für den Wettbewerbsfaktor 1:15:39 Untere Schranke für den Wettbewerbsfaktor-Beweisskizze

12 | 0:00:00 Starten 0:00:09 Orthogonal range searching 0:01:01 Orthogonal range searching - 1D 0:07:03 Orthogonal range searching - 2D 0:17:40 Wavelet Tree Dominance Reporting Query 0:17:54 Reduktion auf 1..n x 1..n 0:18:18 Beispiel 0:19:54 Wavelet Tree 0:22:18 Beispiel 0:24:30 Wavelet Tree Counting Query 0:27:01 Wavelet Tree Dominance Counting Query 0:32:57 Beispiel 0:34:15 Analyse 0:34:57 Wavelet Tree Dominance Reporting Query 0:40:43 Analyse 0:42:29 Allgemeine Reporting Query 0:44:54 Übung 5 0:45:58 Lempel-Ziv 78 decompression 1:00:07 Geometrische Algorithmen 1:01:36 Geometrische Methoden 1:03:18 Sweep-Line 1:06:59 One-Dimensional Problem 1:07:24 Skyline 1:08:31 Interval Search Trees 1:18:06 Rectangle Intersection Problem 1:21:39 Punktorientierung

11 | 0:00:00 Starten 0:06:23 Typische Fragestellungen 0:15:56 Streckenschnitt: Naiver Algorithmus 0:19:04 Idee: Plane-Sweep-Algorithmus 0:24:57 Plane-Sweep für orth. Streckenschnitt 0:29:03 Verallgemeinerung - Grundidee 0:40:56 Verallgemeinerung - Beispiel 0:49:50 Überlappungen finden 0:52:30 2D Konvexe Hülle 0:56:53 Graham's Scan 1:02:07 Kleinste einschließende Kugel 1:19:40 2D Bereichssuche (range research) 1:25:45 Reduktion auf 1..n x 1..n

10 | 0:00:00 Starten 0:00:21 Wavelet Tree Example: Calculate Rank 0:09:48 Huffman-shaped Wavelet Tree 0:12:42 Practical Performance of FM-Index 0:14:54 Succinct Data Structures 0:17:09 Succinct representation of trees 0:19:34 Child operation in detail 0:22:09 Succinct representation of trees (2) 0:29:34 LOUDS-level order unary degree sequence 0:44:15 Anfang der Übung 0:44:30 Today topics 0:44:59 Select in constant time: Step 1 0:47:49 Select in constant time: Step 2 0:49:33 Select in constant time: Step 3 0:56:54 Select in constant time: Query 1:01:17 Lempel-Ziv: Overview 1:02:06 Sliding Window Lempel-Ziv 77 1:08:01 Lempel-Ziv 78 1:16:08 Sliding Window Lempel-Ziv 77

09 | 0:00:00 Starten 0:00:18 Range minimum queries (RMQs) 0:00:43 Overview 0:01:05 O(n), Olog(n)-solution 1 0:01:18 O(nlogn), O solution 2 0:01:38 O(nlog(logn)), O(1) solution 0:02:17 O(n),O(1) solution 0:02:33 LCA & +1RMQ 0:02:51 O(n),O(1) solution 0:08:08 LCA& +1RQM 0:16:49 (O(n),O(1)) solution (4n+o(n) bits) 0:34:19 (O(n),O(1)) solution (2n+0(n) bits ) 0:47:12 Burrows-Wheeler-Transformation: Einführung 0:48:52 Wiederholung: Suffix-Array 0:49:24 Transformation 0:52:22 Burrows-Wheeler-Transformation: Eigenschaften 0:53:52 Rücktrnasformation 1:05:34 Berechnung von LF 1:08:02 Ablauf der Berechnung von LF 1:10:34 Was bringt die BWT? 1:11:41 Kompression 1:12:03 Kompression: Move-To-Front (MTF) Kodierung 1:13:38 Kompression: Huffmann Kodierung 1:14:37 Suche in der Burrowa-Wheeler Transformation 1:15:35 Backward Search 1:21:55 Backward Search: Summary 1:22:37 Wavelet Tree Example: Calculate Rank

08 | 0:00:00 Starten 0:00:34 Verlustfreie Textkompression 0:01:25 Theorie verlustfreier Textkompression 0:10:57 Wörterbuchbasierte Textkompression 0:12:58 Lempel-Ziv Kompresssion (LZ) 0:17:44 Naive LZ Dekompression 0:20:15 LZ- Verfeinerungen 0:21:39 LCP zwischen beliebigen Suffixen 0:23:44 Range minimum queries (RMQs) 0:25:17 Overview 0:26:08 O(n), Olog(n)- solution 0:30:13 O(nlog(n)), O(1) solution 2 0:40:07 Themenübersicht 0:40:31 In-place Multikey Quicksort 0:50:59 Suche mit Border-Array 1:02:52 Suche mit Suffix-Array 1:10:06 LCP-Array 1:11:24 Schnelle Suche mit Suffix-Array

07 | 0:00:00 Starten 0:00:22 Suffix-Baum 0:01:20 Alphabet-Modell 0:02:41 Geordnetes ganzzahliges Alphabet 0:04:39 Verallgemeinerung: Lexikographische Namen 0:05:31 Ein erster Teile-und-Herrsche-Ansatz 0:13:30 Asymmetrisches Divide-and-Conquer 0:18:09 Rekursion, Beispiel 0:25:39 Least Significant Digit First Radix Sort 0:28:03 Stabiles Ganzzahliges Sortieren 0:32:09 Rekursions-Beispiel: Einfacher Fall 0:33:53 Sortieren der mod 0 Suffixe 0:39:37 Analyse 0:41:58 Implementierung: Vergleichs-Operatoren 0:42:35 Implementierung: Radix-Sortieren 0:42:50 Implementierung: Tripel Sortieren 0:43:24 Implementierung: Lexikographisches Benennen 0:43:47 Verallgemeinerung: Differenzüberdeckungen 0:48:00 Verbesserungen/ Verallgemeinerungen 0:48:54 Suffixtabellenkonstruktion: Zusammenfassung 0:49:29 Suche in Suffix Arrays 0:53:50 LCP-Array 1:08:43 LCP-Array: Berechnung 1:13:28 Suffix-Baum aus SA und LCP 1:21:07 Suche in Suffix-Bäumen 1:22:01 Datenkompression

06 | 0:00:00 Starten 0:00:32 4 Stringology (Zeichenkettenalgorithmen) 0:04:16 Strings Sortieren 0:15:40 Strings Sortieren - Laufzeitanalyse 0:18:27 Naives Pattern Matching 0:55:49 Volltextsuche von langsam bis Superschnell 1:04:37 Suffixtabellen 1:05:37 Etwas ""Stringology""-Notation 1:07:03 Suffixe Sortieren 1:14:18 Volltextsuche 1:14:38 Suffix-Baum

05 | 0:00:00 Starten 0:00:34 Turing-Reduzierbarkeit 0:02:47 Pseudopolynomielle Laufzeit 0:05:58 Zwei kleine Warnungen 0:07:55 KNAPSACK Suchproblem 0:10:22 KNAPSACK: Codierungen der Eingabe 0:11:47 Schwere des KNAPSACK Suchproblems 0:12:41 KNAPSACK: pseudopolynomielle Laufzeit 0:22:08 Polynomielle Approximationsschema 0:25:56 PTAS versus FPTAS 0:26:34 Von pseudopolynomieller zu polynomieller Laufzeit 0:28:12 FPTAS für KNAPSACK 0:32:14 epsApproxKnapsack ist FPTAS 0:32:46 epsApproxKnapsack ist FPTAS: Approximation 0:36:12 epsApproxKnapsack ist FPTAS: Polynomialzeit 0:37:06 Varianten von Approximation: zwei Beispiele 0:37:56 Anfang der Übung 0:38:33 Approximationsalgorithmen: Grundlagen 0:40:40 Approximationsalgorithmen: Gütemaß 0:43:43 Approximationsalgorithmen: Klassen 0:47:55 Scheduling unabhängiger gewichteter Jobs auf parallelen Maschinen 0:49:52 2-Approximation für Jobs Scheduling 0:51:27 4/3- Approximation für Jobs Scheduling 0:52:00 Fall 1: kleiner Job 0:56:49 Nur große Jobs 1:03:52 Minimum Metric TSP 1:13:46 Kleine Änderung in der Definition 1:14:21 Perfekt balancierte Graphpartitionierung 1:15:58 3-Partion 1:17:08 Reduktion

04 | 0:00:00 Starten 0:01:07 Suchprobleme 0:04:15 Approximation bei Suchprobleme 0:07:10 Approximation bei Zählprobleme 0:08:51 Job Scheduling: Aufgabenstellung 0:13:14 Naheliegender Algorithmus: listScheduling 0:20:19 Eigenschaften des Algorithmus 0:26:55 Approxiamtionsfaktor 0:28:43 Eigenschaften des Algorithmus (2) 0:34:43 Erinnerung: TSP-Suchproblem 0:37:41 TSP-alpha-Approximations-Suchproblem 0:40:06 Erinnerung: Hamiltonkreis (Entscheidungdproblem) 0:41:02 Schwere Approximierbarkeit des TSP 0:42:09 Schwere Approximierbarkeit des TST: Konstruktion 0:52:57 MetricTSP

03 | 0:00:00 Starten 0:00:10 Kapitel: Randomisierte Algorithmen 0:00:45 Überblick 0:02:44 Erdos-Renyi-Zufallsgraphen 0:04:59 ER-Graphen: einfache Beobachtungen 0:11:05 Manchmal interessieren sehr große n und asymptotische Eigenschaften 0:15:21 ER-Graphen:Durschmesser <=2 0:21:51 Zusammenhangskomponenten 0:23:15 Erwartet konstanter Knotengrad 0:24:21 Andere Anforderungen? 0:24:58 Barabasi-Albert Modell

02 | 0:00:00 Starten 0:01:08 Erinnerung an W-Theorie 0:02:22 Randomisierter Quicksort 0:04:34 randQS: Anzahl Vergleiche 0:11:40 randQS: Anzahl Vergleiche mit hoher Wkt. 0:28:25 Chernoff-Schranken 0:29:04 Einfache Schranken 0:32:19 Chernoff-Schranken 0:38:03 Chernoff-Schranken: Beweis von Teil 1 0:44:26 Chernoff-Schranken: Verienfachungen 0:45:47 Chernoff-Schranken: Korollare 0:47:14 Auswertung von Und-Oder-Bäume 0:51:13 Satz 0:53:50 Beweis 1:00:35 Zwischenüberlegung 1:04:58 Algorithmus: randomisierte UOB-Auswertung 1:07:20 Satz 1:09:19 Beweis 1:18:58 Satz

01 | 0:00:00 Starten 0:00:10 Kapitel: Randomisierte Algorithmen 0:01:10 Überblick 0:01:38 Sichtweisen für randomisierte Algorithmen 0:03:33 Fundamentale Änderung 0:04:03 Beispiel: Randomisierter Quicksort 0:05:32 Zufallsvariablen überall 0:05:49 Errinerung an W-Theorie 0:09:32 Standardbeispiel: Würfeln 0:15:26 Algorithmen mit unbekannter Laufzeit 0:16:25 Algorithmen, die ""variierende Ausgaben"" liefern 0:21:05 Vorteile randomisierter Algorithmen 0:23:28 Motivation 0:25:14 Polynome 0:32:21 Ausblick: polynomial identity testing 0:35:27 Randomisierter Quicksort 0:37:27 randQS: Anzahl Vergleiche