Pro­se­mi­nar Ef­fi­zi­en­te Al­go­rith­men

Dozent: Prof. Dr. Christian Scheideler

Zeit und Ort: wird noch bekannt gegeben

  • Erstes Treffen: am Mittwoch, den 09.10. um 18 Uhr im F2.211
  • Treffen ab 3. Vorlesungswoche: Montag, 18-20 Uhr, F1.110
  • Wahl des ICPC Wettbewerbs für Präsentation im Januar: bis 2. Dezember

Vorstellungen ausgewählter ACM ICPC Probleme:

  • 06.01: ACM ICPC 2014
  • 13.01: ACM ICPCs 2005 und 2015
  • 20.01.: ACM ICPCs 2009 und 2013
  • 27.01.: ACM ICPC 2000

Für jedes Problem gibt es 15 Minuten Zeit zur Vorstellung des Problems und der Lösung. Für jedes Problem ist die Wertung wie folgt:

  • 0 Punkte: Problem ist nicht gelöst worden.
  • 1 Punkt: Lösungsweg ist richtig, aber die Präsentation war schwer nachzuvollziehen oder die Implementierung ist nicht akzeptiert worden.
  • 2 Punkte: Lösungsweg ist richtig, die Präsentation war gut nachzuvollziehen, und die Implementierung ist akzeptiert worden.

Inhalt

Ziel des Proseminars ist es, zu lernen, wie die in der Vorlesung "Datenstrukturen und Algorithmen" vorgestellten Methoden verwendet und erweitert werden können, um algorithmische Probleme, die im renommierten International Collegiate Programming Contest (ICPC) erschienen sind, lösen zu können. Dazu wird es wöchentliche Treffen geben, in denen jeweils eine bestimmte Klasse von Problemen behandelt wird. Weiterhin werden einige dieser Probleme pro Treffen als Hausaufgabe aufgegeben, die von studentischen Teams bestehend aus bis zu 3 Leuten gelöst werden müssen, und jedes Team muss am Ende einen der ICPC Wettbewerbe aufarbeiten und die Lösungen in einem Treffen präsentieren. Dabei reicht es, wenn ein Team bestehend aus k Mitgliedern 2k der Probleme eines ICPC Wettbewerbs auswählt.

Schein

Einen Schein bekommt, wer regelmäßig am Proseminar teilnimmt, mindestens 60% der Probleme korrekt gelöst hat, und am Ende mindestens 50% der Punkte für die Lösung und Präsentation der ausgewählten ICPC Probleme bekommen hat. Die Endnote ergibt sich über die finale Punktzahl. Dabei gibt es für jede korrekt gelöste Hausaufgabe 1 Punkt und für jede korrekte und gut vorgestellte Lösung eines ICPC-Problems in der Präsentationsphase 2 Punkte.

Übersicht über die Themen

ICPC Wettbewerbe

Einige Beispiele sind:

Alle Wettbewerbe können auf der Webseite https://icpcarchive.ecs.baylor.edu gefunden werden. Klickt man auf einen Wettbewerb, wird auch mitgeteilt, wie schwer die Probleme sind, so dass das helfen sollte, einen geeigneten Wettbewerb auszuwählen.

Übungsaufgaben

  • Aufgabe 1 (Abgabe 21.10.): 156 Ananagrams
  • Aufgabe 2 (Abgabe 28.10.): 261 The Window Property
  • Aufgabe 3 (Abgabe 28.10.): 10132 File Fragmentation
  • Aufgabe 4 (Abgabe 4.11.): 855 Lunch in Grid City
  • Aufgabe 5 (Abgabe 11.11.): 701 The Archeologist's Dilemma oder  10247 Complete Tree Labeling
  • Aufgabe 6 (Abgabe 18.11.): 294 Divisors
  • Aufgabe 7 (Abgabe 25.11.): 10119 Tourist Guide
  • Aufgabe 8 (Abgabe 2.12.): 318 Domino Effect
  • Aufgabe 9 (Abgabe 9.12.): 10003 Cutting Sticks
  • Aufgabe 10 (Abgabe 16.12.): 10160 Servicing Stations

Die Probleme können unter http://www.cs.uleth.ca/%7Echeng/contest/hints.html nachgeschlagen werden. Die Programme müssen zusammen mit der Bestätigung des Servers, dass sie akzeptiert worden sind, und den Namen der Gruppenmitglieder bis spätestens zum angegebenen Abgabetag um 18:00 Uhr per Email an den Dozenten geschickt werden (der Zeitstempel der Email zählt).

Hilfsmittel

Sie interessieren sich für: