Skip to content
Algorithmen 2, Vorlesung, WS17/18 podcast artwork

Algorithmen 2, Vorlesung, WS17/18

by Karlsruher Institut für Technologie (KIT)

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.Literaturhinweise:- K. Mehlhorn, P. Sanders: Algorithms and Data Structures - The Basic Toolbox- K. Mehlhorn, S. Naeher: The LEDA Platform of Combinatorial and Geometric Computing Topic: Algorithm Engineering, Flows, Geometrie- R. K. Ahuja, T. L. Magnanti, J.B. Orlin: Network Flows- M. de Berg, M. van Kreveld, M. Overmars, O. C. Schwarzkopf: Computational Geometry: Algorithms and Applications- G. Navarro: Compact Data Structures "A Practical Approach", Cambridge University Press- R. Niedermeier: Invitation to Fixed-Parameter

From the show's RSS feed, refreshed Feb 1, 2025. Source feed.

Subscribe Bookmark

Episodes

  1. 26: Algorithmen 2, Vorlesung, WS 2017/18, 06.02.2018

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

  2. 24: Algorithmen 2, Vorlesung, WS 2017/18, 30.01.2018

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

  3. 25: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 05.02.2018

    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…

    more
  4. 23: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 29.01.2018

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

  5. 22: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 23.01.2018

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

  6. 21: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 16.01.2018

    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…

    more
  7. 20: Algorithmen 2, Vorlesung, WS 2017/18, 15.01.2018

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

  8. 19: Algorithmen 2, Vorlesung, WS 2017/18, 08.01.2018

    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

  9. 18: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 19.12.2017

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

  10. 17: Algorithmen 2, Vorlesung, WS 2017/18, 18.12.2017

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

  11. 16: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 12.12.2017

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

  12. 15: Algorithmen 2, Vorlesung, WS 2017/18, 11.12.2017

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

  13. 14: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 05.12.2017

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

  14. 13: Algorithmen 2, Vorlesung, WS 2017/18, 04.12.2017

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

  15. 12: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 28.11.2017

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

  16. 11: Algorithmen 2, Vorlesung, WS 2017/18, 27.11.2017

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

  17. 10: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 21.11.2017

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

  18. 09: Algorithmen 2, Vorlesung, WS 2017/18, 20.11.2017

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

  19. 08: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 14.11.2017

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

  20. 07: Algorithmen 2, Vorlesung, WS 2017/18, 13.11.2017

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

  21. 06: Algorithmen 2, Vorlesung, WS 2017/18, 07.11.2017

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

  22. 05: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 06.11.2017

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

  23. 04: Algorithmen 2, Vorlesung, WS 2017/18, 30.10.2017

    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…

    more
  24. 03: Algorithmen 2, Vorlesung, WS 2017/18, 24.10.2017

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

  25. 02: Algorithmen 2, Vorlesung, WS 2017/18, 23.10.2017

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

  26. 01: Algorithmen 2, Vorlesung, WS 2017/18, 17.10.2017

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

About this show

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.Literaturhinweise:- K. Mehlhorn, P. Sanders: Algorithms and Data Structures - The Basic Toolbox- K. Mehlhorn, S. Naeher: The LEDA Platform of Combinatorial and Geometric Computing Topic: Algorithm Engineering, Flows, Geometrie- R. K. Ahuja, T. L. Magnanti, J.B. Orlin: Network Flows- M. de Berg, M. van Kreveld, M. Overmars, O. C. Schwarzkopf: Computational Geometry: Algorithms and Applications- G. Navarro: Compact Data Structures "A Practical Approach", Cambridge University Press- R. Niedermeier: Invitation to Fixed-Parameter

Hosted by

Karlsruher Institut für Technologie (KIT)

Categories

Frequently asked questions

How many episodes does Algorithmen 2, Vorlesung, WS17/18 have?

Algorithmen 2, Vorlesung, WS17/18 has 26 episodes on PodParley. The most recent episode was published on February 8, 2018.

What is Algorithmen 2, Vorlesung, WS17/18 about?

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

How often does Algorithmen 2, Vorlesung, WS17/18 release new episodes?

Algorithmen 2, Vorlesung, WS17/18 publishes a few times a week, based on its 26 episodes since October 2017.

Who hosts Algorithmen 2, Vorlesung, WS17/18?

Algorithmen 2, Vorlesung, WS17/18 is created and hosted by Karlsruher Institut für Technologie (KIT).
Link copied