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]
- Ohlebusch, E. (2013). Bioinformatics Algorithms. Oldenbusch-Verlag. [O] (neu online)
- 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 | |
| 2. | Knuth-Morris-Pratt | [SW 762-769] | Tobias Gottschalk | 14.7.21 | |
| 3. | Searching Sets of Patterns | [CHL 2.2], [O 2.5], [G 3.4] | Elidona Shiqerukaj | 14.7.21 | |
| 4. | Pattern Matching with Constant Extra Space | [CHL 3.5 | Tom Stein | 14.7.21 | |
| 5. | Seminumerical String-Matching | [G 4.2-4.3] | Tim Schrader | 14.7.21 | |
| 6. | Karp-Rabin-Fingerprints and Hashing Strings | [SW 774-779], [G 4.4], [SW 460] | Daniil Kaminskyi | 14.7.21 | |
| 7. | Edit-Distanz und Alignment-Algorithmen | [O 8.1] | Thorben Simon | 14.7.21 | |
| 8. | Regular-Expression-Search | [SW 788-804] | Yazan Farah | 15.7.21 | |
| 9. | Searching with Wildcards | [CHL 8.1] | Laura Molketeller | 15.7.21 | |
| 10. | Tries | [SW 730-752] | Meitong Li | 15.7.21 | |
| 11. | Key-Indexed Counting and Ternary Quicksort | [SW 703-705], [SW 719-723] | Zhala Abubaker | 15.7.21 | |
| 12. | Radix-Sort for Strings | [SW 706-718] | Wail Samjouni | 15.7.21 | |
| 13. | Faster Radix-Sort | [AHU 77-86] | Niklas Lindemann | 15.7.21 | |
| 14. | Suffix Arrays | [CHL 4.4], [G 7.14.2-7.14.3] | Daniel Huesmann | 15.7.21 | |
| 15. | Longest Common Prefixes | [O 4.2], [G 7.14.4-7.14.5] | Daniel Liebenau | 16.7.21 | |
| 16. | Suffixbäume | [O 4.4], [G 5], [G 7.1-7.4] | Philip Van Kempen | 16.7.21 | |
| 17. | Suffix-Automaten | [CHL 5.4-5.5] | Marvin Lazar | 16.7.21 | |
| 18. | Kompression: Huffman und Tunstall | [SW 810-838], [Say 3.7] | Simon Bartkowiak | 16.7.21 | |
| 19. | Kompression: Lempel-Ziv-Varianten | [SW 839-845] | Tran, Vu Duc | 16.7.21 | |
| 20. | Kompression: Prediction with Partial Matching | [Say 6.3] | Philipp Kutsch | 16.7.21 |
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.