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 Nac

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 Problemst

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:

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

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

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

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:

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

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

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 Rek