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

10 | 0:00:00 Start 0:00:39 Preflow-Push Algorithms 0:02:02 Level Funktion 0:05:36 Example 0:06:50 Pratial Correctness 0:13:09 Lemma 4. 0:16:18 Lemma 5. 0:21:08 Lemma 6. 0:23:11 Lemma 7. 0:23:34 Lemma 8. 0:26:09 Lemma 9. 0:32:41 Searching for Eligable Edges 0:37:49 Satz 11. 0:40:06 FIFO Preflow push 0:41:52 Highest Level Preflow Push 0:45:18 Example 0:51:22 Übung 4 0:51:56 Flüsse und Ford Fulkerson 0:55:48 Residualgraph 1:02:15 Max Flow - Min Cut 1:04:59 Dinitz Algorithmus

09 | 0:00:00 Start 0:00:09 Ford Fulkerson - Correctness 0:00:46 Ford Fulkerson Algorithm 0:08:49 Max-Flow-Min-Cut theorem 0:11:18 A bad example for Ford Fulkerson 0:13:25 Dinitz Algorithm 0:18:35 Dinitz-Correctness 0:21:22 Computing blocking flows 0:27:46 Blocking flows analysis 0:33:40 Dinitz analysis 0:40:55 Matching 0:43:54 Maximum cardinality bipartite matching 0:46:31 Similar performance for weight graphs? 0:50:06 Disadvantage of augmenting paths algorithms 0:52:10 Pre-flow-push algorithms 0:57:23 Level function 1:19:34 Partial correctness

08 | 0:00:00 Start 0:00:05 Augmenting Paths 0:01:56 Ford Fulkerson Algorithm 0:07:57 Some Basic Observations 0:14:57 Blocking Flows 0:16:44 Suche in Graphen 0:20:19 Dijkstras Algorithmus 0:28:30 A*-Suche 0:31:31 A*-Suche – Potentialfunktionen 0:37:23 A*-Suche – Landmarken 0:47:01 Starke Zusammenhangskomponenten 1:00:07 Floyd Warshall: SCC als Speedup Technik

07 | 0:00:00 Start 0:00:37 Tiefensuchschema 0:01:14 Starke Zusammenhangskomponenten 0:02:21 Schrumpfgraph 0:02:55 Konkreter: SCCs mittels DFS 0:04:04 Invarianten von G 0:05:58 Lemma: Abgeschlossene SCCs von G sind SCCs von G 0:06:14 Repräsentation offener Komponenten 0:13:24 Beispiel 0:24:48 Zusammenfassung: SCC Berechnung 0:26:22 2-zusammenhängende Komponenten 0:29:06 Mehr DFS-basierte Linearzeitalgorithmen 0:31:56 Maximum Flows and Matching 0:33:06 Definitions: Network 0:34:38 Definition: Flows 0:36:14 Definition: Minimum s-t Cuts 0:37:22 Duality between flows and cuts 0:40:17 Applications 0:47:18 Applications in our group 0:54:42 Option 1: Linear programming 0:57:56 Algorithms 1956 - now 1:06:42 Augmenting paths 1:09:13 Example 1:13:33 Residual Graph 1:19:05 Ford Fulkerson Algorithm 1:21:39 A bad example for Ford Fulkerson 1:22:56 An even worse example 1:20:25 Average case Analyse für MST

06 | 0:00:00 Start 0:02:23 Anwendungen von DFS 0:06:45 DFS Nummerierung 0:09:51 Starke Zusammenhangskomponenten 0:17:07 Abstrakter Algorithmus 0:21:45 Auswirkungen einer neuen Kante e auf Gc, (Gc)s 0:28:56 Invarianten von Gc 0:34:11 Repräsentation offener Komponenten 0:46:37 Spezielle Priority Queues 0:51:13 Bucket Queues 0:57:25 Radix Heaps 1:20:25 Average case Analyse für MST

05 | 0:00:00 Start 0:00:08 Kürzeste Wege 0:02:50 Allgemeine Definition 0:03:01 Monotone ganzzahlige Prioritätslisten 0:04:23 Laufzeit Dijkstra mit Bucket-Queues 0:05:13 Radix-Heaps 0:07:25 Radix Heap: deleteMin 0:09:39 Beispiel 0:14:16 Laufzeit Dijkstra mit Radix-Heaps 0:16:21 Lineare Laufzeit für zufällige Kantengewichte 0:18:53 Änderung im Algorithmus für zufällige Kantengewichte 0:22:24 Analyse 0:28:29 All-Pairs Shortest Paths 0:33:59 Knotenpotenziale 0:40:25 Hilfsknoten 0:42:04 Definition der Potenziale 0:47:44 Algorithmus 0:49:03 Laufzeit 0:49:15 Distanz zu einem Zielknoten 0:52:43 Ideen für Routenplanung 1:10:21 Biderktionale Suche 1:14:42 A*-Suche 1:18:53 Benötigte Eigenschaften von f(v) 1:20:46 Wie finden wir f(v)? 1:24:06 Landmarks 1:29:03 Zusammenfassung: Kürzeste Wege

04 | 0:00:00 Start 0:00:04 Dijkstra's Algorithmus: Pseudocode 0:00:39 Laufzeit 0:01:30 Laufzeit im Durchschnitt 0:02:05 Lineare Laufzeit für dichte Graphen 0:02:21 Satz 1 0:11:50 Präfixminima einer Zufallsfolge 0:14:11 Monotone ganzzahlige Prioritätslisten 0:17:38 Bucket-Queue 0:20:18 Operationen 0:24:46 Laufzeit Dijkstra mit Bucket-Queues 0:26:07 Radix-Heaps 0:29:28 Definition 0:32:05 Radix-Heap_invariante 0:36:38 Radix Heap: deleteMin 0:39:34 Buckets 0:41:40 Lufzwit Dijkstra mit Radix-Heaps 0:42:31 Übung 0:42:36 Amortisierte Analyse 0:52:53 Legende 0:54:44 Fibonacci Heaps - Insert 0:56:45 Fibonacci Heaps - Delete Min 1:08:31 Fibonacci Heaps - Decrease Key

03 | 0:00:00 Start 0:00:10 Algorithmics as Algorithm Engineering 0:01:26 Problem Instances 0:02:50 Example: Sorting Benchmark (Indy) 0:09:34 GraySort: 0:11:27 JouleSort 0:13:39 Applications that ""Change the world"" 0:22:09 Conclusion 0:24:17 More on experimental Methodology 0:29:48 Quality Criteria 0:36:53 Not here but important 0:37:57 The starting point 0:40:08 The Process 0:45:06 Of Risks and Opportunities 0:47:19 Fortgeschrittene Datenstrukturen 0:47:35 Adressierbare Prioritätslisten 0:47:54 Grundlegende Datenstrukturen 0:48:19 Wälder bearbeiten 0:48:46 Pairing Heaps 0:50:27 Fibonacci Heaps 0:50:46 Repräsentation 0:51:09 deleteMin mit Union-by-Rank 0:52:22 Kaskadierende Schnitte 0:53:56 Addressable Priority Queues: Mehr 0:55:09 Zusammenfassung: Datenstrukturen 0:55:51 Kürzeste Wege 0:57:46 Allgemeine Definitionen 0:59:39 Kante 1:00:43 Dijkstra's Algorithmmus 1:05:03 Laufzeit

Diese Lehrveranstaltung soll Studierenden die grundlegenden theoretischen und praktischen Aspekte der Algorithmentechnik vermitteln. Es werden generelle Methoden zum Entwurf und der Analyse von Algorithmen für grundlegende algorithmische Probleme vermittelt sowie die Grundzüge allgemeiner algorithmischer Methoden wie Approximationsalgorithmen, Lineare Programmierung, Randomisierte Algorithmen, Parallele Algorithmen und parametrisierte Algorithmen behandelt.

02 | 0:00:00 Start 0:01:39 Fortgeschrittene Datenstrukturen 0:03:10 Adressierbare Prioritätslisten 0:07:41 Grundlegende Datenstruktur 0:11:23 Pairung Heaps 0:23:14 Fibonacci Heaps 0:25:26 Repräsentation 0:26:22 deleteMin mit Union-by-Rank 0:27:23 Schnelles Union-by-Rank 0:30:49 Amortisierte Analyse von deleteMin 0:36:19 Schnelles Union-by-Rank 0:38:10 Warum ist maxRank logarithmisch? 0:40:10 Kaskadierende Schnitte 0:45:36 Auftritt Herr Fibonacci 0:51:52 Addressable Priority Queues: Mehr 0:52:57 Zusammenfassung: Datenstrukturen