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

 
Last modified: 2021-02-15 10:34 by Johannes Fischer
DokuWikiRSS-Feed