====== Proseminar String-Algorithmen ======


===== Inhalt =====
Wir beschäftigen uns mit grundlegenden Algorithmen auf Zeichenketten (Strings): suchen, sortieren und indexieren. Hierfür verwenden wir die folgenden Lehrbücher:

  * Aho, A., Hopcroft, J., Ullman, J. (1974). The Design and Analysis of Computer Algorithms. [**AHU**]
  * Crochemore, M., Hancart, C., & Lecroq, T. (2007). //Algorithms on Strings.// Cambridge University Press. [**CHL**]
  * Gusfield, D. (1997). //Algorithms on Strings, Trees, and Sequences.// Cambridge University Press. [**G**]
  * [[http://www.uni-ulm.de/in/theo/m/ohlebusch/book-bioinformatics-algorithms.html | Ohlebusch, E. (2013). Bioinformatics Algorithms. Oldenbusch-Verlag.]] [**O**]
  * Sayood, K. (2012) Introduction to Data Compression. Morgan Kaufmann, 4. Auflage. [**Say**]
  * Sedgewick, R., & Wayne, K. (2011) Algorithms. Addison-Wesley, 4. Auflage. [**SW**].

Die Bücher [O], [Say] und [SW] sind im Universitätsnetz online verfügbar.
===== Lehrpersonen =====
  * [[staff:fischer|Prof. Dr. Johannes Fischer]]


===== Allgemeine Hinweise =====
Alle TN müssen zudem ein externes Seminar für Präsentationstechniken erfolgreich absolvieren, im Idealfall vor Ihrem Vortrag. Bitte erkundigen Sie sich rechtzeitig nach Plätzen.

Bitte beachten Sie die wichtigen Hinweise in diesem {{:fischer:teaching:allgemeine_proseminarhinweise.pdf|Merkblatt}}.


===== Themenliste =====

^ Nr. ^ Thema ^ Material ^ Teilnehmer ^ Termin ^ Betreuer ^ 
|  1.| Naives String Matching, Boyer-Moore, Boyer-Moore-Horspool | [SW 760-761 + 770-773], [O 2.3], [G 3.1] | Yannik Blomenkemper | 14.7.21 | Johannes Fischer |
|  2.| Knuth-Morris-Pratt | [SW 762-769] | Tobias Gottschalk | 14.7.21 | Johannes Fischer |
|  3.| Searching Sets of Patterns | [CHL 2.2], [O 2.5], [G 3.4] | Elidona Shiqerukaj | 14.7.21 | Johannes Fischer |
|  4.| Pattern Matching with Constant Extra Space | [CHL 3.5 | Tom Stein | 14.7.21 | Johannes Fischer |
|  5.| Seminumerical String-Matching | [G 4.2-4.3] | Tim Schrader | 14.7.21 | Johannes Fischer |
|  6.| Karp-Rabin-Fingerprints and Hashing Strings | [SW 774-779], [G 4.4], [SW 460] | Daniil Kaminskyi | 14.7.21 | Johannes Fischer |
|  7.| Edit-Distanz und Alignment-Algorithmen | [O 8.1] | Thorben Simon | 14.7.21 | Johannes Fischer |
|  8.| Regular-Expression-Search | [SW 788-804] | Yazan Farah | 15.7.21 | Johannes Fischer |
|  9.| Searching with Wildcards | [CHL 8.1] | Laura Molketeller | 15.7.21 | Johannes Fischer |
|  10.| Tries | [SW 730-752] | Meitong Li | 15.7.21 | Johannes Fischer |
|  12.| Radix-Sort for Strings | [SW 706-718] | Wail Samjouni | 15.7.21 | Johannes Fischer |
|  13. | Faster Radix-Sort | [AHU 77-86] | Niklas Lindemann | 15.7.21 | Johannes Fischer | 
|  14.| Suffix Arrays | [CHL 4.4], [G 7.14.2-7.14.3] | Daniel Huesmann| 15.7.21 | Johannes Fischer |
|  15.| Longest Common Prefixes | [O 4.2], [G 7.14.4-7.14.5] | Daniel Liebenau | 16.7.21 | Johannes Fischer |
|  17.| Suffix-Automaten | [CHL 5.4-5.5] | Marvin Lazar | 16.7.21 | Johannes Fischer |
|  18.| Kompression: Huffman und Tunstall | [SW 810-838], [Say 3.7] | Simon Bartkowiak | 16.7.21 | Johannes Fischer |
|  20.| Kompression: Prediction with Partial Matching | [Say 6.3] | Philipp Kutsch | 16.7.21 | Johannes Fischer |

===== Zeitlicher Ablauf =====
**Spätestens** 2 Wochen vor dem Vortrag sollen Sie in einem halbstündigen Treffen mit Ihrem Betreuer die bis auf Feinkosmetik **fertigen** Folien zeigen und erklären können. Bitte vereinbaren Sie dieses Treffen **rechtzeitig**, also mindestens 4 Wochen vor dem Vortrag.

Spätestens 2 Wochen nach dem Vortrag müssen Sie die schriftliche Ausarbeitung abgeben (per Email als pdf). Die formalen Voraussetzungen zur schriftlichen Ausarbeitung sind dem o.g. Hinweisblatt zu entnehmen. 

Beide Deadlines sind hart.

===== Voraussetzungen =====
Sie sollten Spaß an algorithmischen Problem und deren effizienter Lösung haben.

===== Ort und Zeit =====
Das Seminar findet als **Blockseminar** vom 14.-16.7.2021 statt, jeweils 9:00-17:00.

Es findet eine **Themenvergabe** in der letzten VL-Woche des WS20/21 statt.