Table of Contents
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]
- 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
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 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.