Table of Contents
Algorithms for Competitive Programming (SoSe 2023)
| Veranstalter | Mart Hagedoorn |
| Modul | Fachprojekt - Bachelor Informatik/Angewandte Informatik |
| SWS | 4 |
| Zeit | Mittwochs von 12h bis 16h |
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 GCPC 2023 (Link zum GCPC von 2022) teilzunehmen.
Zeitplan und Ablauf
Jeden Mittwoch von 12 bis 16 Uhr findet das Fachprojekt statt. In den ersten beiden Stunden werden spezifische Techniken zur Lösung von Wettbewerbsproblemen behandelt. Die letzten beiden Stunden sind der Bearbeitung von Übungsaufträgen gewidmet.
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!
| Woche | Thema |
|---|---|
| Woche 1 - 05.04.2023 | Einführung, Gruppen bilden, Themenvergabe |
| Woche 2 - 12.04.2023 | Tipps & Tricks |
| Woche 3 - 19.04.2023 | Systemeinführung, Programming Challenges Online Judge, Standard IO |
| Woche 4 - 26.04.2023 | Datenstrukturen und Algorithmen-entwurfsmethoden |
| Woche 5 - 03.05.2023 | Such- und Sortieralgorithmen |
| Woche 6 - 10.05.2023 | Strings |
| Woche 7 - 17.05.2023 | Interner Wettbewerb |
| Woche 8 - 24.05.2023 | Graphtraversierung |
| Woche 9 - 31.05.2023 | Flow- und Matching- Probleme |
| Woche 10 - 07.06.2023 | Algorithmische Geometrie |
| Woche 11 - 14.06.2023 | GCPC Vorbereitung |
| Woche 11 - 17.06.2023 | GCPC '23 |
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
- 30 min 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