Personen: Prof. Dr. Tobias Friedrich, Dr. Pascal Lenzner, Philipp Fischbeck, Christopher Weyand
Links: Lehrveranstaltungsliste Bachelor/Master, Algorithm Engineering Moodle

Beschreibung

Beim Competitive Programming geht es darum, möglichst schnell möglichst gut zu programmieren. Die Zeit zum Programmieren ist beschränkt. Die Korrektheit und Effizienz wird über eine Online-Judge mit unbekannten Test-Cases überprüft. Diese Art der Programmierwettbewerbe haben eine lange Tradition. Die Association for Computing Machinery (ACM) richtet seit 1970 jährlich den International Collegiate Programming Contest (ICPC) aus. An diesem Format werden wir uns orientieren.

Beim ACM-ICPC geht es darum, daß Teams von drei Studenten einer Uni an einem Computer möglichst viele Probleme gemeinsam lösen. Gewonnen hat, wer nach fünf Stunden mit seinen Programmen die meisten Aufgaben richtig gelöst hat. Es gibt fünf typische Arten von Aufgaben: Graphen-Probleme (z.B. Dijkstra), Suchprobleme (z.B. Backtracking), Geometrische Probleme (z.B. Schnittbildung), zahlentheoretische Probleme (z.B. Primzahl-Zerlegung), und sonstige Probleme (z.B. Brettspiele oder Parser). Das Problem Set Archive bietet über tausend Probleme, welche online gelöst werden können.

Das HPI hat schon mehrmals am europäischen Wettbewerb des ACM-ICPC teilgenommen. Das Ziel ist, auch für das Jahr 2020 ein HPI/UP-Team für den nordwesteuropäischen Regionalausscheid des ACM-ICPC (NWERC) aufzubauen und zu trainieren. Dies werden wir im Rahmen eines interaktiven Projektseminars umsetzen. Jeder Studierende am HPI und am IfI der UP ist dazu eingeladen.

Voraussetzungen

Voraussetzungen sind gute Programmierkentnisse in C/C++ und ein Basiswissen über Algorithmik, beispielsweise aus den Veranstaltungen Theoretische Informatik 1 , Einführung in die Algorithmik oder Algorithmix.

Wir setzen Grundkenntnisse in den Folgenden Bereichen voraus:

• Algorithmenentwurfsmethoden: Greedy, Divide and Conquer, dynamisches Programmieren, Backtracking und Rekursion
• Grundlegende Datenstrukturen: Arrays, Listen, Stacks, Queues, binäre Suchbäume, binäre Heaps, Adjazenzlisten und -matrizen
• Standardthemen der Algorithmik: O-Notation, Sortieren, Suchen, Hashing, einfache Graphenalgorithmen (z.B. Baumtraversierung, Breiten- und Tiefensuche)

Für Bachelor Studenten setzen wir zusätzlich die Veranstaltung Competitive Programming voraus.

Lern- und Lehrformen

Im Laufe des Seminars arbeiten sich Teams von 2-4 Studenten in fortgeschrittene Themen im Competitive Programming ein. Jedes Team gestaltet eine 90 Minuten Vorlesung, einen zugehörigen Wochen-Contest und einen unabhängigen Live-Contest. 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 und dienen als Training für den ICPC. Die Aufgaben werden per Online-Judge ausgewertet und im Seminar diskutiert. Am Ende des Semesters findet ein Endcontest statt.

Leistungserfassung

Die Bewertung der Veranstaltung basiert auf den Leistungen bei Wochen-Contests anderer Teams, dem Vortrag zum eigenen Thema, dem Erstellen der eigenen Contests und der Teilnahme am Endcontest. Die Note setzt sich wie folgt zusammen:

• 30% Vortrag (Team)
• 30% Wochen-Contests
• 20% Aufgaben erstellen (Team)
• 20% Endcontest (Team)
• 0% Live-Contests anderer Teams

Bis zu 5% Bonus kann durch den FAU Wintercontest, NWERC, oder GCPC erreicht werden.

Termine

Wöchentlich freitags von 13:30-16:45 Uhr digital (Zoom). Der Link ist im Moodle-Kurs zu finden.