Algorithms for Competitive Programming (WiSe 2022/23)
| Veranstalter | Dr. Carolin Rehs, Mart Hagedoorn, Antonia Kalb |
| Modul | Fachprojekt - Bachelor Informatik/Angewandte Informatik |
| Moodle | https://moodle.tu-dortmund.de/course/view.php?id=36387 |
| SWS | 4 |
Beschreibung
Beim Competitive Programming geht es darum, für konkrete Probleme algorithmische Lösungen zu entwickeln und in möglichst kurzer Zeit zu implementieren. In dieser Veranstaltung wird einerseits das Verständnis für grundlegende effiziente Algorithmen vertieft, andererseits das Anwenden der Algorithmen und Programmieren unter Zeitdruck geübt. Die Association for Computing Machinery (ACM) richtet seit 1970 jährlich den International Collegiate Programming Contest (ICPC) aus, an welchem wir uns orientieren werden.
In unserer Veranstaltung werden wichtige Algorithmen und Datenstrukturen zur Lösung von Problemen aus früheren Jahren des ICPCs in Vorträgen vorgestellt und Lösungsansätze gemeinsam diskutiert. Neben den Vorträgen werden Aufgaben in einer simulierten Wettbewerbssituation in 3er-Teams gelöst und programmiert. Am Ende des Semesters besteht die Möglichkeit, am deutschen Winter Contest teilzunehmen.
Zeitplan und Ablauf
Programmiersprache: C, C++, Java oder Python (Hauptsache Sie finden zwei weitere Teilnehmer für ihre präferierte Sprache)
Kurssprache ist deutsch, die Problembeschreibungen/Aufgabenstellungen werden jedoch auf englisch sein!
Voraussetzungen
- Programmierkenntnisse (Praktika DAP 1 und 2)
- Datenstrukturen, Algorithmen und Programmierung 2
- 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, Heaps, Adjazenzlisten und -matrizen
- Standardthemen der Algorithmik: O-Notation, Sortieren, Suchen, Hashing, einfache Graphenalgorithmen (z.B. Baumtraversierung, Breiten- und Tiefensuche)
- Grundkenntnisse über Matching- und Flussalgorithmen (EA) sind hilfreich, aber nicht notwendig
Prüfungsleistung
alle Modulabschlussleistungen finden als 3er-Team statt
- 30min Vortrag inklusive Handout über eine Datenstruktur oder Programmierparadigma sowie das Anleiten des Kurses zur Lösung von dazugehörigen Aufgabentypen
- 3 von 5 der wöchentlich gestellten Probleme pro Aufgabentyp gelöst
- erfolgreiche Teilnahme am internen Programming Challenge