Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

(Advanced) Competitive Programming 2

BSc/MSc Vorlesung - Winter 2022/23

Personen: Prof. Dr. Tobias Friedrich, Philipp Fischbeck, Hans Gawendowicz, Christopher Weyand (KIT)
Links: Lehrveranstaltungsliste Bachelor/Master, Algorithm Engineering Moodle*

*Wenn du keinen Zugang zum Moodle hast (z.B., weil du nicht am HPI eingeschrieben bist), kontaktiere Philipp Fischbeck.

Beschreibung

Diese Vorlesung ist eine Fortsetzung der Veranstaltung (Advanced) Competitive Programming. Im Verlauf des Semesters werden Algorithmen und Datenstrukturen vorgestellt, welche aufgrund ihrer Effizienz und vergleichsweise kurzen Implementierung Anwendung in Programmierwettbewerben finden.  Während es im vorherigen Semester um grundlegende Themen und Algorithmen ging, fokussieren wir uns in diesem Semester auf fortgeschrittene Algorithmen und Themen, z.B. Treaps, Cost-Flow, Lazy Segment Trees.

Zu jedem Themengebiet (Strings, Zahlentheorie, Graphen, Treaps, etc.) müssen praktischen Übungsaufgaben implementiert werden. Höhepunkte der Veranstaltung sind die Live-Contests, in denen sich die Studierenden in Teams miteinander messen.

In diesem Jahr planen wir wieder, den Kurs in Zusammenarbeit mit dem Institut für Theoretische Informatik am KIT in Karlsruhe zu halten. Die Details werden noch geklärt, es wird jedoch mindestens ein gemeinsames Scoreboard geben, sodass sich HPI- und KIT-Teams direkt messen und Lösungsideen miteinander teilen können.

Voraussetzungen

Zur Zulassung setzen wir die Veranstaltung (Advanced) Competitive Programming voraus.

Wer schon einmal die Veranstaltung "Competitive Programming 2" (Bachelor) erfolgreich belegt hat, kann diese Veranstaltung im Master nicht belegen.

Lern- und Lehrformen

Die Vorlesung soll maßgeblich von einer lebhaften interaktiven Diskussion unterschiedlicher Lösungsansätze und Tipps und Tricks geprägt sein. Zudem werden im Laufe des Kurses hilfreiche Konzepte eingeführt.
Im Laufe des Kurses stellen wir verschiedene fortgeschrittene Themen im Competitive Programming vor. Zu diesen Themen gibt es regelmäßig Aufgaben, die zuhause gelöst werden sollen. Zusätzlich werden die Teilnehmenden an Live-Contests teilnehmen. Die Aufgaben des Wochen-Contests löst jeder Student allein, um die in der Vorlesung gelernten Methoden anzuwenden; die Live-Contests werden in Teams bearbeitet. Die Aufgaben werden per Online-Judge ausgewertet und in der Veranstaltung diskutiert. Am Ende des Semesters findet ein Endcontest statt.

Leistungserfassung

In die Bewertung gehen die Programmieraufgaben und Live-Contests während 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)

Termine

Die Veranstaltung wird vor Ort stattfinden, im Raum TBD.
Offiziell findet die Veranstaltung freitags 13:30-15:00 und 15:15-16:45 statt.

Der End-Contest findet TBD um 10:00-15:00 Uhr statt. Dieser Termin gilt auch als Prüfungstermin im Rahmen der 8-Tage-Regel für die Prüfungsanmeldung.

Vorlesungsteam

Die Vorlesung wird veranstaltet vom Fachgebiet Algorithm Engineering. An der Durchführung sind die folgenden Personen beteiligt:

Philipp Fischbeck

Dozent

Office: K-2.13
E-Mail: Philipp.Fischbeck(at)hpi.de

Hans Gawendowicz

Dozent

Office: K-2.08
E-Mail: hans.gawendowicz(at)hpi.de

Jonas Schmidt

Tutor

E-Mail: Jonas.Schmidt(at)student.hpi.de