Beschreibung
Beim Competitive Programming geht es darum, möglichst schnell algorithmische Probleme zu lösen und die Lösung zu implementieren. 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 Python oder C++ 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, ihr habt eine gut gefüllte Algorithmen-Toolbox, ihr erkennt verschiedene algorithmische Probleme und ihre Lösung schnell, und ihr habt dabei immer die Laufzeit und den Speicherverbrauch im Blick. Auch das Debugging von komplexen Algorithmen fällt euch leichter und ihr habt gelernt, wie ihr effizient im Team arbeitet.
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. Die Wettbewerbe sind hierbei eher spielerisch und dienen der Motivation und dem Aufzeigen der Wirkung von unterschiedlichen Lösungsansätzen. In die Bewertung fließt nur die Anzahl der gelösten Aufgaben ein, der direkte Vergleich mit den anderen Teilnehmern spielt dabei keine Rolle.
Neben den Wettbewerben in der Veranstaltung können HPI-Teams an deutschlandweiten und europäischen Competitive Programming Wettbewerben teilnehmen und so noch mehr Praxiserfahrung sammeln. Wir begleiten und helfen euch dabei mit unseren erfahrenen Coaches!
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.
Studierende im Master erhalten als Zusatzaufgabe noch Einblick in das Erstellen von Aufgaben. Jeder Masterstudierende muss hierbei eine eigene Aufgabe erstellen. All diese Aufgaben fließen dann in einen optionalen Trainings-Contest für alle Teilnehmer ein.
Termine
Wöchentlich freitags von 13:30 - 16:45 Uhr, der erste Termin ist der 21.04.2023. Der erste Termin findet in Raum L-E.03 statt.
Optional findet immer mittwochs von 15:15 - 16:45 Uhr ein Tutorium im Raum K-2.03 statt. Der erste Termin ist am 26.04.23.
