Fortgeschrittenes Algorithmisches Programmieren

Dozent: Thomas Bläsius, Christopher Weyand, Philipp Fischbeck from HPI, and David Stangl

Links: ILIAS, VVZ

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.

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