Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

(Advanced) Competitive Programming

BSc/MSc Project Seminar - Summer 2021

Diese Lehrveranstaltung wird digital durchgeführt. Deshalb ist es wichtig, dass sich alle Teilnehmenden bis zum 15.04.2021 im Moodle des Kurses einschreiben. Beachtet, dass dieser Termin von der allgemeinen Einschreibefrist abweicht und die Registrierung zusätzlich zur normalen Einschreibung über das Studienreferat erfolgt. Im Moodle ist der Zoom-Link für die erste Veranstaltung zu finden, die am 15.04.2021 um 13:30 Uhr stattfindet.

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.

HPI-Teams haben bereits mehrfach erfolgreich and deutschlandweiten und europäischen Competitive Programming Wettbewerben teilgenommen. Das Ziel ist, auch für das Jahr 2021 HPI-Teams für solche Wettbewerbe aufzubauen und zu trainieren. Dies werden wir im Rahmen eines interaktiven Projektseminars umsetzen. Jeder Studierende am HPI ist dazu eingeladen.

Neu ist in diesem Jahr, dass wir den Kurs in Zusammenarbeit mit dem Institut für Theoretische Informatik am KIT in Karlsruhe halten werden. Es wird ein gemeinsames Scoreboard und gemeinsame Contests geben, so dass sich HPI- und KIT-Teams direkt messen können.  

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)

Lern- und Lehrformen

Das Projektseminar soll maßgeblich von einer lebhaften interaktiven Diskussion unterschiedlicher Lösungsansätze und Tipps und Tricks geprägt sein. Zudem werden im Laufe des Seminars hilfreiche Konzepte eingeführt.   

Leistungserfassung

Im Laufe des Seminars wird es wöchentlich Programmieraufgaben geben, deren Lösung dann per Online-Judge ausgewertet und im Seminar diskutiert werden. Neben den wöchentlichen Aufgaben wird es mehrere Live-Contests geben, in welchen wir einen echten Progammierwettbewerb simulieren. 

Die Bewertung der Veranstaltung basiert zu 30% auf den wöchentlichen Aufgaben und zu 70% auf den Contests im Laufe des Semesters.

Termine

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