Algorithmen 2, Vorlesung, WS19/20

By Karlsruher Institut für Technologie (KIT)Education

Algorithmen 2, Vorlesung, WS19/20 episodes

February 05, 2020 28: Algorithmen II, Vorlesung, WS 2019/20, 04.02.2020
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
1 hr 21 min
February 03, 2020 27: Algorithmen II, Vorlesung, WS 2019/20, 03.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
1 hr 8 min
February 03, 2020 26: Algorithmen II, Vorlesung, WS 2019/20, 28.01.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
1 hr 23 min
January 27, 2020 25: Algorithmen II, Vorlesung, WS 2019/20, 27.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
1 hr 13 min
January 23, 2020 24: Algorithmen II, Vorlesung, WS 2019/20, 21.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
1 hr 15 min
January 21, 2020 23: Algorithmen II, Vorlesung, WS 2019/20, 20.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
1 hr 21 min
January 16, 2020 22: Algorithmen II, Vorlesung und Übung, WS 2019/20, 14.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
1 hr 24 min
January 14, 2020 21: Algorithmen II, Vorlesung, WS 2019/20, 13.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
1 hr 23 min
January 13, 2020 20: Algorithmen II, Vorlesung, WS 2019/20, 07.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
1 hr 22 min
December 19, 2019 19: Algorithmen II, Vorlesung und Übung, WS 2019/20, 17.12.2019
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
1 hr 21 min