Fortgeschrittenes Algorithmisches Programmieren
Dozent: Thomas Bläsius, Christopher Weyand, Philipp Fischbeck from HPI, and David Stangl
Im Verlauf des Semesters werden Algorithmen und Datenstrukturen vorgestellt, welche aufgrund ihrer Effizienz und vergleichsweise kurzen Implementierung Anwendung in Programmierwettbewerben finden. Zu jedem Themengebiet (Strings, Zahlentheorie, Graphen, Treaps, etc.) müssen praktischen Übungsaufgaben implementiert werden. Höhepunkte der Veranstaltung ist ein Contest, in dem sich die Studierenden unter Wettbewerbsbedingungen miteinander messen. Aus den Teilnehmern der Veranstaltung werden außerdem die Teams ausgewählt, die die Universität Karlsruhe beim ACM ICPC Regionalwettbewerb der Region Nordwesteuropa (NWERC) vertreten werden.
Bewertung
In die Bewertung gehen die Programmieraufgaben und Live-Contests wärend des Semesters sowie ein End-Contest nach Ende der Vorlesungszeit ein.
- 40% Programmieraufgaben (Abgabe jeweils 2 Wochen nach jedem Thema)
- 30% Live-Contest (10% pro Contest)
- 30% End-Contest (30% pro Contest)
Ablauf
Die Veranstaltung findet immer Freitags von 14 bis 15:30 über Zoom statt. Im Anschluss (ca. 15:45-16:15) werden die Lösungen des vergangenen Themenblocks vorgestellt. Den Zoom-Link und alle weiteren Infos/Materialien gibt es im Discord und der Link zum Discord steht im ILIAS.
Terminplan
| Termin | Thema |
|---|---|
| 22.10. | Intro |
| 29.10. | Topic 1: Segment Trees (Lazy, Iterative, Prefix-Search, Sparse, Persistent) |
| 05.11. | Discussion |
| 12.11. | Topic 2: Treaps |
| 19.11. | Contest |
| 26.11. | Topic 3: Trees (Binary Lifting, HLD, Centroid) |
| 03.12. | Discussion |
| 10.12. | Topic 4: Flow (Dinitz, Decomposition, Cost-Flow) |
| 17.12. | Contest |
| 07.01. | Topic 5: Strings (Suffix-Sort, Hashing, Aho-Corasick) |
| 14.01. | Discussion |
| 21.01. | Topic 6: Math (Sieves, Miller-Rabin, Pollard-Rho) |
| 28.01. | Contest |
| 04.02. | Topic 7: Convolutions (FFT & more) |
| 11.02. | Discussion |