Differences

This shows you the differences between two versions of the page.

--- fischer:teaching:tir-ws2018 [2018-10-09 09:39]
+++ fischer:teaching:tir-ws2018 [2018-12-11 17:38]
@@ Line 3: / Line 3: @@
 ===== Neuigkeiten =====
-  * 9.10.18: Skript+Übungsblatt 1 online
+  * 11.12.18: neues Skript + Übungsblatt 9 online
-  * 17.8.2018: Seite online
+  * 10.12.18: neues Skript online
+  * 27.11.18: Skript+Übungsblatt 8 online
+  * 27.11.18: Zuordnung und Terminierung der Abschlussprojekte
+  * Doodle für Abschlussprojekte läuft!
 ===== Inhalt =====
@@ Line 24: / Line 26: @@
 ===== Stundenplan Vorlesung =====
-TBA
+  * 8.10.: Tries
+  * 15.10.: Suffixbäume in O(n) Zeit, Suffix-Arrays in O(n log n) Zeit
+  * 22.10.: Suffix-Arrays in O(n) Zeit
+  * 29.10.: LCP-Arrays und LZ77 in O(n) Zeit
+  * 5.11.: LZ78 in O(n log σ) Zeit, Suche in Suffixarrays in O(n log n) und O(n+log n) Zeit, O(1)-RMQs in O(n log n) Platz
+  * 12.11.: RMQ und LCA in O(1) Zeit und O(n) Platz
+  * 19.11.: BWT und Einführung in die Rückwärtssuche
+  * 26.11.: Rückwärtssuche; Rank in Bitvektoren, Wavelet Trees
+  * 03.12.: Y-fast Tries und Approximate Pattern Matching
+  * 10.12.: Komprimierter FM-Index
 ===== Skriptum =====
-  * {{fischer:teaching:tir-ws2018:script-tir-ws18.pdf |Version}} vom 09.10.18. (Wird forlaufend erneuert.)
+  * {{fischer:teaching:tir-ws2018:script-tir-ws18.pdf |aktuelle Version}} (Wird forlaufend erneuert.)
 ===== Übungsblätter =====
   - {{:fischer:teaching:tir-ws2018:ue1.pdf|Übungsblatt 1}},{{:fischer:teaching:enwiki-titles.part.txt.gz|Wortliste}} für Aufgabe 2 und 3
+  - {{:fischer:teaching:tir-ws2018:ue2.pdf|Übungsblatt 2}}
+  - {{:fischer:teaching:tir-ws2018:ue3.pdf|Übungsblatt 3}}
+  - {{:fischer:teaching:tir-ws2018:ue4.pdf|Übungsblatt 4}}
+  - {{:fischer:teaching:tir-ws2018:ue5.pdf|Übungsblatt 5}}
+  - {{:fischer:teaching:tir-ws2018:ue6.pdf|Übungsblatt 6}}
+  - {{:fischer:teaching:tir-ws2018:ue7.pdf|Übungsblatt 7}}
+  - {{:fischer:teaching:tir-ws2018:ue8.pdf|Übungsblatt 8}}
 ===== Abschlussprojekte =====
-Die letzten 4 Übungstermine nutzen wir zu einem Mini-Seminar, bei dem jeder Stud. eine Thema präsentieren soll.
+Die letzten 3 Übungstermine nutzen wir zu einem Mini-Seminar, bei dem jeder Stud. ein Thema präsentieren soll. Ziel ist es, einen die Vorlesung ergänzenden Aspekt aus einem wissenschaftlichen Artikel oder aus einem Buch in ca. 25 Minuten vorzustellen.
-==== Theorieprojekte ====
-Ziel ist es, einen die Vorlesung ergänzenden Aspekt aus einem wissenschaftlichen Artikel oder aus einem Buch in ca. 25 Minuten vorzustellen.
+=== 7.1.19 ===
-  * Der Φ-Algorithmus aus Kärkkäinen, J., Manzini, G., & Puglisi, S. J. (2009): Permuted longest-common-prefix array. In //Annual Symposium on Combinatorial Pattern Matching// (pp. 181-192). Springer Berlin Heidelberg.
+  - U. Beier: //On Undetected Redundancy in the Burrows-Wheeler Transform//. Proc. CPM'18, article no. 3. LIPIcs Band 105. **Osthues**
-  * Der DC3-Algorithmus zur Suffixsortierung (Kapitel 4.1.1 aus Ohlebuschs Buch "Bioinformatics Algorithms")
+  - Platzeffiziente Konstruktion der BWT (Kapitel 9.3 in Mäkinen et al.'s Buch "Genome Scale Algorithm Design") **Böcker**
-  * Ultraschnelle LZ77-Faktorisierung (Kapitel 5.2.2 aus Ohlebuschs Buch "Bioinformatics Algorithms")
+  - Bidirektionale BWT (Kapitel 9.4 in Mäkinen et al.'s Buch "Genome Scale Algorithm Design") **Michaelis**
-  * Ultraschnelle Textsuche mit dem Suffix-Array (Kapitel 7.14.4 aus Gusfields Buch "Algorithms on Strings, Trees, and Sequences")
+  - BWT für Bäume (Abschnitt 2 in P. Ferragina et al.: //Compressing and Indexing Labeled Trees, with Applications//. J. ACM 57(1), Article No. 4, 2009.) **Metz**
-  * kompakte Suffix-Automaten (Kap. 5.5 aus Crochemore et al.'s Buch "Algorithms on Strings")
-  * Platzeffiziente Konstruktion der BWT (Kapitel 9.3 in Mäkinen et al.'s Buch "Genome Scale Algorithm Design")
+=== 13.1.19 ===
-  * Bidirektionale BWT (Kapitel 9.4 in Mäkinen et al.'s Buch "Genome Scale Algorithm Design")
+  - Range Min-Max-Trees (Kapitel 7.1 aus Navarros Buch "Compact Data Structures: A Practical Approach"). Hier bitte eine geeignete Auswahl treffen (d.h. reduzieren)! **Haldimann**
-  * Die Wavelet-Matrix (Kapitel 6.2.5 aus Navarros Buch "Compact Data Structures: A Practical Approach")
+  - LZ77: Ultraschnelle Berechnung (Kapitel 5.2.2 aus Ohlebuschs Buch "Bioinformatics Algorithms") **Bertram**
-  * Range Min-Max-Trees (Kapitel 7.1 aus Navarros Buch "Compact Data Structures: A Practical Approach")
+  - LZ-Index (Abschnitt 13.2.2 in Navarros Buch "Compact Data Structures: A Practical Approach", mit den notwendigen Ergänzungen aus vorangegangenen Kapiteln) **Brümmer**
+=== 20.1.19 ===
+  - Compressed Suffix Arrays (Kapitel 11.1 aus Navarros Buch "Compact Data Structures: A Practical Approach") **Pink**
+  - obere Schranke für die Anzahl an Runs (Abschnitt 3 in H. Bannai et al.: //The "Runs" Theorem//. SIAM J. Computing 46(5), pp 1501-1514, 2017) **Bode**
+  - Runs-Berechnung in O(n) Zeit (Abschnitt 4.1 in H. Bannai et al.: //The "Runs" Theorem//. SIAM J. Computing 46(5), pp 1501-1514, 2017.) **Schinner**
-==== Praxisprojekte ====
-Ziel ist es, in der Vorlesung eingeführte Algorithmen und Datenstrukturen gut zu implementieren und anhand von realistischen Eingaben auf Platzbedarf und Laufzeit zu testen sowie mit konkurrierenden Verfahren zu vergleichen. Auch hier soll am Ende eine ca. 25-minütige Präsentation stehen.
-  * Vergleich von Suffix Arrays und Inverted Indexes bei der Beantwortung von Suchanfragen
-  * Effiziente Implementierungen von dynamischen Tries
-  * Praktische Evaluation der Level-Ancestor-Datenstruktur
-  * Vergleich von Wavelet Trees und Wavelet Matrices mit der sdsl
 ===== Ort und Zeit =====
   * Vorlesung: Mo 14-16 c.t. (SRG1 1.001)
   * Übungsgruppe: Mo 16-18 s.t. (SRG1 1.001)

Chair 11

Teaching

Research Groups

Differences