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. Beim ACM-ICPC geht es darum, dass Teams von drei Studenten einer Uni an einem Computer möglichst viele Probleme gemeinsam lösen. 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).
In der Veranstaltung bringen wir euch bei, wie ihr verschiedene Arten von Problemen erkennt, einen Lösungsalgorithmus entwerft und diesen in C++ (oder Python) umsetzt. Nach erfolgreicher Teilnahme seid ihr nicht nur gut vorbereitet für Coding-Interviews, sondern seid auch bessere Software-Ingenieure geworden: Ihr kennt C++ besser, erkennt verschiedene algorithmische Probleme und ihre Lösung schnell, und habt dabei immer die Laufzeit und den Speicherverbrauch im Blick. Auch das Debugging von komplexen Algorithmen fällt euch leichter.
Wöchentlich werden euch einzelne Themen nähergebracht, und ihr wendet das Gelernte in Programmieraufgaben an. Neben den wöchentlichen Aufgaben wird es mehrere Live-Contests geben, in welchen wir einen echten Progammierwettbewerb simulieren. Zudem können HPI-Teams an deutschlandweiten und europäischen Competitive Programming Wettbewerben teilnehmen und so noch mehr Praxiserfahrung sammeln.
Auch in diesem Jahr werden wir den Kurs in Zusammenarbeit mit dem Institut für Theoretische Informatik am KIT in Karlsruhe halten. Es wird ein gemeinsames Scoreboard und gemeinsame Contests geben, sodass sich HPI- und KIT-Teams direkt messen und Lösungsideen miteinander teilen können.
Voraussetzungen
Voraussetzungen sind gute Programmierkentnisse in C/C++ und ein Basiswissen über Algorithmik, beispielsweise aus den Veranstaltungen Theoretische Informatik 1 , Algorithmic Problem Solving 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
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 der Vorlesung hilfreiche Konzepte eingeführt.
Leistungserfassung
Im Laufe des Kurses wird es wöchentlich Programmieraufgaben geben, deren Lösungen 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 Teilnahme an den Contests findet voraussichtlich in Zweier-Teams statt, die wöchentlichen Aufgaben werden alleine gelöst.
Die Bewertung der Veranstaltung basiert zu 40% auf den wöchentlichen Aufgaben und zu 60% auf den Contests im Laufe des Semesters, mit einem finalen Contest mit hoher Gewichtung.
Termine
Wöchentlich freitags von 13:30 - 16:45 Uhr, der erste Termin ist der 22.04.2022. Die Veranstaltung wird im Hörsaal 3 stattfinden.
Immer dienstags von 15:15 - 16:45 Uhr wird ein optionales Tutorium angeboten. Am 26.04. und 03.05. im Raum L-1.06, danach im Raum H-E.51.
Prüfungstermin: Der End-Contest wird am Freitag, den 12.08.2022, stattfinden.
