Algorithmen 2, WS2016/17, Vorlesung

Algorithmen 2, WS2016/17, Vorlesung episodes:

• February 16, 2017Algorithmen II, Vorlesung, WS 2016/17, 07.02.2017, 26

  26 |

  0:00:00 Starten

  0:01:13 Fortgeschrittene Graphenalgorithmen: 2 Kürzeste Wege

  0:02:31 Monotone ganzzahlige Prioritätslisten

  0:03:05 Radix-Heaps

  0:04:38 All-Pairs Shortest Paths

  0:06:18 3 Anwendungen von DFS

  0:08:27 Algorithms 1956-now

  0:11:39 Preflow-Push Algorithms

  0:13:38 5 Externe Algorithmen

  0:15:04 6 Fixed-Parameter-Algorithmen

  0:16:16 Fixed parameter tractable

  0:16:49 Beispiel: VERTEX COVER

  0:17:46 Naive tiefenbeschränkte Suche

  0:18:38 7 Parallele Algorithmen

  0:18:41 Warum Parallelverarbeitung

  0:19:30 Kostenmodell für Nachrichtenaustausch

  0:20:12 7.2 Beispiel: Assoziative Operationen (=Reduktion)

  0:21:17 7.3 Sortieren

  0:21:59 8 Stringology (Zeichenkettenalgorithmen)

  0:22:25 Knuth-Morris-Pratt (1977)

  0:27:42 9 Geometrische Algorithmen

  0:27:54 9.1 Streckenschnitt (line segment intersection)

  0:28:42 Verallgemeinerung

  0:29:38 9.3 Kleinste einschließende Kugel

  0:30:08 9.4 2D Bereichssuche (range search)

  0:32:55 10 Onlinealgorithmen

  0:33:33 Competitive analysis

  ...more

  ---

• February 03, 2017Algorithmen II, Vorlesung und Übung, WS 2016/17, 31.01.2017, 25

  25 |

  0:00:00 Starten

  0:00:24 Wavlet Tree

  0:08:46 Allgemeine Reporting Query

  0:09:02 Bitvektoren

  0:15:34 Suffix Array

  0:15:45 Backward Search

  0:20:37 Wavelet Tree Example: Calculate Rank

  0:24:21 Index size comparison

  0:26:55 Beginn Übung 13

  0:27:01 Themenübersicht

  0:28:27 Geometrische Algorithmen

  0:32:55 Geometrische Methoden

  0:35:13 Sweep-Line

  0:39:04 One-Dimensional Problem

  0:39:26 Skyline

  0:56:58 Linienschnitt

  1:02:03 Punktorientierung

  ...more

  ---

• February 02, 2017Algorithmen II, Vorlesung, WS 2016/17, 25.01.2017, 24

  24 |

  0:00:00 Starten

  0:00:14 Verallgemeinerung

  0:10:21 Überlappungen finden

  0:11:52 Platzverbrauch

  0:12:45 Mehr Linienschnitt

  0:13:34 9.2 2D Konvexe Hülle

  0:17:35 Graham's Scan

  0:23:22 3D Konvexe Hülle

  0:25:05 9.3 Kleinste einschließende Kugel

  0:31:29 Kleinste einschließende Kugel - Korrektheitm

  0:35:57 Kleinste einschließende Kugel - Analyse

  0:49:17 9.4 2D Bereichssuche

  0:52:14 1D Bereichssuche

  0:58:43 Reduktion auf 1...n x 1...n

  1:01:19 Beispiel

  1:02:05 Walvelet Tree

  ...more

  ---

• February 02, 2017Algorithmen II, Übung und Vorlesung, WS 2016/17, 24.01.2017, 23

  23 |

  0:00:00 Starten

  0:00:07 Übung 12 - Online Algorithmen

  0:02:44 Grundlagen

  0:04:19 Gütemaß

  0:05:21 Ski Rental Problem

  0:06:46 Randomisierte Ski Rental Strategie

  0:18:02 Doubling Strategie

  0:18:52 Online Bidding

  0:40:30 Zusammenfassung

  0:41:39 Vorlesung: Kapitel 9 - Geometrische Algorithmen

  0:45:17 Elementare Geometrische Objekte

  0:49:22 Typische Fragestellungen

  0:53:29 Verweissensitive Grafik (Wikipedia)

  0:54:30 Datenstrukturen für Punktemengen

  0:54:42 Mehr Fragestellungen

  0:59:47 9.1 Streckenschnitt (line segment intersection)

  1:01:02 Streckenschnitt: Anwendungen

  1:01:44 Streckenschnitt: Naiver Algorithmus

  1:02:18 Streckenschnitt: Untere Schranke

  1:04:17 Idee: Plane-Sweep-Algorithmen

  1:04:54 Plane-Sweep für orth. Streckenschnitt

  1:10:02 Analyse orth. Streckenschnitt

  1:12:03 Verallgemeinerung - aber erstmal ""nicht ganz""

  1:12:55 Verallgemeinerung - Grundidee

  1:16:48 Verallgemeinerung - Korrektheit

  1:17:46 Verallgemeinerung - Implementierung

  1:23:05 Verallgemeinerung - Beispiel

  1:24:05 Verallgemeinerung - Analyse

  ...more

  ---

• January 20, 2017Algorithmen II, Vorlesung, WS 2016/17, 18.01.2017, 22

  22 |

  0:00:00 Starten

  0:00:42 13 Onlinealgorithmen

  0:05:35 Examples

  0:08:09 Competitive analysis

  0:09:19 A typical online problem: ski rental

  0:11:31 Upper bound for ski rental

  0:14:33 Lower bound for ski rental

  0:18:07 Paging

  0:20:16 Definitions

  0:21:49 Paging algorithms

  0:25:11 Longest Forward Distance is optimal

  0:27:34 Using the claim

  0:29:01 Proof the claim

  0:29:44 Comparison of algorithms

  0:34:33 A general lower bound

  0:38:53 Resource augmentation

  0:40:14 Conservative algorithms

  0:43:26 Competitive ratio

  0:46:50 Counting the faults of OPT

  0:47:32 Conclusion

  0:48:30 Competitive analysis

  0:49:57 Notes

  0:51:02 New results

  0:54:25 Randomized algorithms

  0:55:38 Three types of adversaries

  1:00:46 Markig Algorithm

  1:04:28 Analysis of REMARk

  1:06:21 Lower bound for OPT

  1:07:42 Discussion

  1:08:50 Why competitive analysis?

  1:16:24 Disadvantages of competetive analysis

  ...more

  ---

• January 19, 2017Algorithmen II, Vorlesung und Übung, WS 2016/17, 11.01.2017, 21

  21 |

  0:00:00 Starten

  0:00:07 Burrows-Wheeler-Transformation

  0:12:23 Datenkompression

  0:18:42 Verlustfreie Textkompression

  0:30:39 Wörterbuchbasierte Textkompression

  0:33:02 Lempel-Ziv Kompression

  0:33:45 Naive Lempel-Ziv Kompression

  0:43:15 Naive LZ Dekompression

  0:45:08 LZ Beispiel

  0:45:16 LZ-Verfeinerung

  0:46:37 Begin Übung 11

  0:48:29 Suche mit Suffix-Arrays (1)

  0:56:41 LCP-Array

  1:03:46 Schnelle Suche mit Suffix-Arrays

  1:10:29 Suche mit Suffix-Arrays (2)

  ...more

  ---

• January 19, 2017Algorithmen II, Vorlesung, WS 2016/17, 10.01.2017, 20

  20 |

  0:00:00 Starten

  0:00:07 Wiederholung: Asymmetrisches Divide-and-Conquer

  0:03:50 Implementierung

  0:06:04 Verallgemeinerung: Differenzenüberdeckungen

  0:10:34 Verbesserungen / Verallgemeinerungen

  0:11:23 Suffixtabellenkonstruktion: Zusammenfassung

  0:12:00 Suche in Suffix Arrays

  0:14:13 LCP-Array

  0:15:56 Beispiel

  0:32:42 LCP-Array: Berechnung

  0:39:53 Suffix-Baum aus SA und LCP

  0:41:20 Beispiel

  0:53:45 Suche in Suffix-Bäumen

  0:55:41 Datenkompression

  0:55:55 Burrows-Wheeler-Transformation

  ...more

  ---

• January 12, 2017Algorithmen II, Vorlesung und Übung, WS 2016/17, 21.12.2016, 19

  19 |

  0:00:00 Starten

  0:00:09 Wiederholung: Suffix Tree und Suffix Array

  0:02:28 Kapitel 8 - Stringology (Zeichenkettenalgorithmen)

  0:03:37 Etwas ""Stringology""-Notation

  0:05:26 Suffixe Sortieren

  0:05:59 Anwendungen

  0:07:05 Volltextsuche

  0:07:28 Suffix-Baum

  0:08:33 Alphabet-Modell

  0:09:24 Geordnetes --> ganzzahliges Alphabet

  0:10:30 Verallgemeinerung: Lexikographische Namen

  0:11:20 Ein erster Teile-und-Herrsche-Ansatz

  0:15:17 SA1 berechnen

  0:17:08 Berechne SA0 aus SA1

  0:19:50 Asymmetrisches Divide-and-Conquer

  0:23:22 Beispiel

  0:50:06 Rekursion, Beispiel

  0:50:41 Least Significant Digit First Radix Sort

  0:51:11 Stabiles Ganzzahliges Sortieren

  0:51:44 Analyse

  0:53:31 Übung 10

  0:53:36 Themenübersicht

  0:53:44 Parametrisierte Algorithmen

  1:02:24 in-place Multikey Quicksort

  1:16:25 Beispiel

  ...more

  ---

• January 12, 2017Algorithmen II, Vorlesung, WS 2016/17, 20.12.2016, 18

  18 |

  0:00:00 Starten

  0:00:07 Stringology (Zeichenkettenalgorithmen)

  0:00:59 Top 10 query completion (Suchvolumina)

  0:04:18 Weitere Anwendungen

  0:10:19 Naives Pattern Matching

  0:17:29 Besserer Algorithmus

  0:27:53 Fallanalyse Palindrome

  0:41:09 Berechnung der Verschiebetabelle

  1:00:26 Multi Key Quicksort for Strings

  1:11:00 Matching von k pattern gegen einen Text der Länge n

  1:12:46 Suffix Tree und Suffix Array

  ...more

  ---

• December 20, 2016Algorithmen II, Übung, WS 2016/17, 14.12.2016, 17

  17 |

  0:00:00 Starten

  0:00:07 Übung 9 – Algorithmen 2

  0:00:27 Themenübersicht

  0:02:21 Parallelverabeitung

  0:06:11 PRAM

  0:08:27 Verbindungsnetzwerke

  0:14:26 Anwendungen

  0:33:58 Parallele Programmierung

  0:35:53 Übung 8 – Algorithmen 2

  0:36:07 Anwendungen

  0:38:33 Themenübersicht

  0:40:20 Approximationsalgorithmen

  1:06:46 Parametrisierte Algorithmen

  ...more

  ---