KIT Lehre und Wissen
Algorithmen 2 — twenty-eight lectures from KIT, 2019.Algorithmen 2. Twenty-eight lectures in German from KIT.
2019 · 28 lectures · 35.2 h2020 · 17 lectures · 18.0 h2018 · 30 lectures · 40.9 h2017 · 26 lectures · 33.7 h2016 · 26 lectures · 34.5 h
Algorithmen 2 · 28 lectures
01: Rolle der Algorithmik, Algorithm Engineering
02: Experimental Methodology, Adressierbare Prioritätenlisten
03: Fortgeschrittene Datenstrukturen, Binomialbäume
04: Binomialbäume, Radix-Heaps, deleteMin-Operationen
05: All-Pairs Shortest Paths, Knotenpotentiale, Routenplanung
06: Repräsentation offener Komponenten, Übung
07: Maximum Flows and Matchings, s-t Cuts
08: Computer Blocking Flows, Übung
09: Ford Fulkerson Algorithm, Level Function
10: Flows and Matchings, MFIFO Modified FIFO Selection Rule
11: Randomisierte Algorithmen
12: Externe Algorithmen: Externe Prioritätslisten, Übung
13: Approximationsalgorithmen
14: Fixed-Parameter-Algorithmen, Naive tiefenbeschränkte Suche
15: Fixed-Parameter-Algorithmen, Parallele Algorithmen
16: Paralleles Sortieren: Anfänger- und
17: Geometrische Algorithmen, Übung
18: Streckenschnitt, 2D Konvexe Hülle
19: Bitvektoren, Übung: Geometrische Algorithmen, Bitvektoren
20: Onlinealgorithmen, Paging algorithms
21: Stringology (Zeichenkettenalgorithmen)
22: Stringology: Notation, Suffixe sortieren, Suffixbaum
23: SA mit Präfix Verdopplung, Rekursion, COBS
24: LCP-Array, Verlustfreie Textkompression, Übung
25: Datenkompression, Lempel-Ziv Kompression
26: Efficient Document Retrieval on General Sequences
27: Pairing Heaps, Bucket Queue, Residual Graph
28: Approximationsalgorithmen, Fixed-Parameter-AlgorithmenAlgorithmen 2 · 17 lectures
A2_01: Overview and Algorithm Engineering Methodology
A2_02: Advanced Data Structures
A2_03: Advanced Graph Algorithms, Shortest Paths
A2_04: All-Pairs Shortest Paths
A2_05: Depth-First Search
A2_06: Flows I
A2_07: Flows II
A2_08: 6 Randomised Algorithms
A2_09: 7 External Algorithms
A2_10: 8 Approximation Algorithms
A2_11:Fixed Paramter Algorithms
A2_12: Parallel Algorithms
A2_13: Computational Geometry I
A2_14: Computational Geometry_II
A2_15: 13 Online Algorithms
A2_16: String Algorithms I
A2_17: String Algorithms IIAlgorithmen 2 · 30 lectures
01: Algorithm Theory
02: Datenstrukturen, Pairung Heaps, Fibonacci Heaps
03: Gray-/JouleSort, Pairing Heaps, Dijkstra’s Algorithmmus
04: Dijkstra’s Algorithmus, Radix-Heaps, Bucket-Queue
05: Monotone ganzzahlige Prioritätslisten, Radix-Heaps
06: DFS, Bucket Queues, Analyse für MST
07: Schrumpfgraph, SCC Berechnung, Linear programming
08: Ford Fulkerson Algorithm, Blocking Flows
09: Ford Fulkerson, Dinitz Algorithm,blocking flows
10: Preflow-Push Algorithms, Pratial Correctness
11:Ford Fulkerson Algorithm, Blocking Flows, Random Graphs
12: Randomisierte Algorithmen, Cuckoo Hashing
13: Cuckoo Hashing, Das Sekundärspeichermodell
14: Spannbäume, Matching, Monte Carlo Simulation
15: Der Approximationsfaktor, Pseudopolynomielle Algorithmen
16: Naive tiefenbeschränkte Suche
17: Analyse paralleler Algorithmen, Hyperwürfelalgorithmus
18: Paralleles Sortieren, Parallele Algorithmen
19: Geometrische Algorithmen, Streckenschnitt, Überlappungen
20: Streckenschnitt, Konvexe Hülle, Geometrische Methoden, Übung
21: Kleinste einschließende Kugel, Wavelet Tree
22: Wavelet Tree, Onlinealgorithmen, Paging
23: Strings sortieren, Suffixe sortieren, Knuth-Morris-Pratt
24: Suffix-Baum, Alphabet-Modell, Übung
25: Suffixtabellen, Differenzenüberdeckungen, LCP-Array
26: LCP-Array, Lempel-Ziv Kompression
27: SAT Solving, Union-find merging, Graph Contraction
28: Übung: In-place Multikey Quicksort, Partitionierung
29: Algorithm Engineering, Fortgeschrittene Datenstrukturen
30: Approximationsalgorithmen, Pseudopolynomielle AlgorithmenAlgorithmen 2 · 26 lectures
01: Randomisierte Algorithmen, W-Theorie, Polynome
02: Randomisierter Quicksort, Einfache Schranken
03: Randomisierte Algorithmen: Erdos-Renyi-Zufallsgraphen
04: Approximationsalgorithmen
05: Pseudopolynomielle Laufzeit, KNAPSACK, PTAS versus FPTAS
06: Stringology (Zeichenkettenalgorithmen)
07: Alphabet-Modell, Teile-und-Herrsche-Ansatz, Rekursion
08: Datenkompression: Verlustfreie Textkompression
09: Range minimum queries, Burrows-Wheeler-Transformation
10: Huffman-Shaped Wavelet Tree, Succinct Data Structures, Übung
11: Naiver Algorithmus, Plane-Sweep-Algorithmus, Graham’s Scan
12: Orthogonal range searching, Übung
13: Online-Algorithmus, Wettbewerbsfaktor & strikte
14: LRU, Randomisierte Onlinealgorithmen, Übung
15: Deterministischer Weighted Majority Algorithm (WMA)
16: Parallele Reduktion, Parallele Präfixsummen, Übung
17: Adressierbare Prioritätslisten, Pairing Heaps
18: Fortgeschrittene Graphenalgorithmen, Dijkstra’s Agorithmus
19: Radix-Heaps, deleteMin-Operationen
20: Anwendungen von DFS, SCCs generischer Algorithmus
21: Maximum Flows and Matchings, Residual Graph
22: Dinitz Algorithm, Dinitz Analysis, Übung
23: Flüsse und Ford Fulkerson, Übung
24: Sekundärspeichermodell, Externe Stapel, Externes Mischen
25: Claims, Übung
26: Seminar: Proofs from the bookAlgorithmen 2 · 26 lectures
01: Fortgeschrittene Datenstrukturen
02: Adressierbare Prioritätslisten, Pairing Heaps, deleteMin
03: Kürzeste Wege, Pseudocode, Laufzeit Dijkstra, Radix Heap
04: Fortgeschrittene Graphenalgorithmen, Kürzeste Wege
05: Starke Zusammenhangskomponenten, Suche in Graphen
06: Tiefensuchschema, Nomenklatur, DFS Nummerierung
07: Algorithmenforschung, Bindestrichalgorithmen, Sortiersysteme
08: Flußprobleme, Flüsse und Schnitte
09: Starke Zusammenhangskomponenten, Max. Flüsse
10: Dinics Algorithmus, Finden von Matchings
11: Preflow Push Algorithmus, Heuristische Improvements
12: Randomisierter Algorithmus
13: Externe Stapel, Sortieren durch Externes Binäres Mischen
14: Approximationsalgorithmen, Job Scheduling
15: Pseudopolynomelle Algorithmen, Fixparameteralgorithmen
16: Fixed-Parameter-Algorithmen
17: Parallelverarbeitung, Approximationsalgorithmen
18: Stringology, Pattern Matching, KMP-Algorithmus
19: Stringology, Alphabetmodell, Teile- und Herrsche Ansatz
20: Differenzüberdeckungen, LCP-Array
21: Burrows-Wheeler-Transformation, Daten-/Textkompression
22: Onlinealgorithmen, Paging Algorithmen
23: Online Algorithmen, Geometrische Algorithmen
24: Konvexe Hüllen, Bereichssuche, Kleinste einschließende Kugel
25: Wavelet Tree, Sweepline, Linienschnitt
26: Kürzeste Wege, verschiedene Algorithmen, Sortieren











