Proseminar Effiziente Algorithmen

Dozent: Prof. Dr. Christian Scheideler

Modulinformation

  • Übergr. Modul II.5.1
  • 3 ECTS

Zeit und Ort

  • Mi, 18:15 Uhr, F2.211

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 als Hausaufgabe gegeben, die von studentischen Teams bestehend aus bis zu 3 Leuten gelöst werden müssen.

Schein

Einen Schein bekommt, wer regelmäßig am Proseminar teilnimmt und mindestens 60% der Probleme korrekt gelöst hat (d.h. der Einreichungsserver hat die Korrektheit bestätigt). Weiterhin muss mindestens einmal ein Mitglied des Teams eine korrekte Lösung vorgestellt haben.

Übersicht der Themen

Übungsaufgaben

  • Aufgabe 1: 156: Ananagrams (Abgabe: 18.10.)
  • Aufgabe 2: 261: The Window Property (Abgabe: 25.1130.)
  • Aufgabe 3: 10132: File Fragmentation (Abgabe: 8.11.)
  • Aufgabe 4: 855: Lunch in Grid City (Abgabe: 15.11.)
  • Aufgabe 5: (Abgabe: 22.11.)
    Option 1: 701: The Archeologist's Dilemma
    Option 2: 10247: Complete Tree Labeling
  • Augabe 6: 10168: Summation of Four Primes (Abgabe: 29.11.)
    Hinweis: Nutzen Sie Eulers Vermutung in Aufgabe 543 (Goldbach's Conjecture).
  • Aufgabe 7: 10199: Tourist Guide (Abgabe: 06.12.)
  • Aufgabe 8: 318: Domino Effect (Abgabe: 13.12.)
  • Aufgabe 9: 10003: Cutting Sticks (Abgabe: 20.12.)
  • Aufgabe 10: Keine Aufgabe über die Weihnachtsferien
  • Aufgabe 11: Aufgabe A oder B aus dem ICPC 2000 Wettbewerb (s.o.)
  • Aufgabe 12: Aufgabe B oder C aus dem ICPC 2001 Wettbewerb (s.o.)
  • Aufgabe 13: Eine beliebige Aufgabe aus dem ICPC 2003 Wettbewerb (s.o.)

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, 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: