====== Fortgeschrittenes Algorithmisches Programmieren ======

**Dozent:** [[people:thomasblaesius|]], [[people:christopherweyand|]], [[https://hpi.de/friedrich/people/philipp-fischbeck.html|Philipp Fischbeck]] from HPI, and [[https://codeforces.com/profile/Felerius|David Stangl]]

**Links:** [[https://ilias.studium.kit.edu/goto.php?target=crs_1629270&client_id=produktiv|ILIAS]], [[https://campus.studium.kit.edu/ev/dRjeSMzkQN2B4aJ8sS-1qA/de|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.

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