Veranstaltung

Inhalt:

Im Verlauf des Semesters werden Algorithmen und Datenstrukturen vorgestellt, welche aufgrund ihrer Effizienz und vergleichsweise kurzen Implementierung Anwendung in Programmierwettbewerben finden. Zu jedem Themengebiet (Strings, Zahlentheorie, Graphen, Treaps, etc.) müssen praktische Übungsaufgaben implementiert werden. Höhepunkt der Veranstaltung ist ein Contest, in dem sich die Studierenden unter Wettbewerbsbedingungen miteinander messen.

Aus den Teilnehmern der Veranstaltung werden außerdem die Teams ausgewählt, die die Universität Karlsruhe beim ACM ICPC Regionalwettbewerb der Region Nordwesteuropa (NWERC) vertreten werden.

Qualifikations- /Lernziele:

Nach erfolgter Teilnahme an der Lehrveranstaltung können die Studierenden

- problemorientiert effiziente Implementierungen mit bekannten algorithmischen Techniken in midestens einer Programmiersprache umsetzen,

- Laufzeit (in Sekunden) von Algorithmen und Implementierungen basierend auf der Eingabegröße abschätzen,

- Anwendungsfälle für existierende Algorithmen erkennen,

- algorithmische Methoden anpassen und kombinieren, um neue Algorithmen zu entwickeln.

Empfehlungen:

Grundkenntnisse über Algorithmen und Datenstrukturen (z.B. aus den Vorlesungen Algorithmen 1 + 2) und Programmierkenntnisse in C++ werden erwartet.

Erfolgreiche Teilnahme am Basispraktikum zum ICPC Programmierwettbewerb wird stark empfohlen.

Arbeitsaufwand:

Vorlesung mit 2 SWS, 6 LP

6 LP entspricht ca. 180 Arbeitsstunden, davon

1. 30 Std. Besuch der Vorlesung
2. 30 Std. Vor- und Nachbereitung
3. 100 Std. Bearbeitung der Übungsblätter
4. ca. 20 Std. Prüfungsvorbereitung

Erfolgskontrolle:

Die Erfolgskontrolle erfolgt in Form einer Prüfungsleistung anderer Art nach § 4 Abs. 2 Nr. 3 SPO.

Bewertet werden regelmäßige Programmieraufgaben und eine computergestützte Prüfung von i.d.R. 300 Minuten am Ende des Semesters.

Ein Rücktritt ist innerhalb von zwei Wochen nach Beginnn der Veranstaltung möglich.