Dozent: Prof. Dr. Christian Scheideler

Modulinformation

• Übergr. Modul II.5.1
• 3 ECTS

Zeit und Ort

• Mi 14-16 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 ca. 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).

Übersicht der Themen

• Einführung
• Datenstrukturen
• Zeichenketten
• Suchen und Sortieren
• Arithmetik und Kombinatorik
• Zahlentheorie
• Graphdurchlauf
• Graphalgorithmen
• Divide & Conquer und Dynamische Programmierung
• Backtracking und Branch & Bound
• ICPC Wettbewerb von 2000
• ICPC Wettbewerb von 2001
• ICPC Wettbewerb von 2003

Übungsaufgaben

• Übungsaufgabe 1 (Abgabe 26.10.): 
  105: The Skyline Problem
• Übungsaufgabe 2 (Abgabe 2.11.):
  10107: What is the Median?
  10125: Sumsets
• Übungsaufgabe 3 (Abgabe 9.11.):
  760: DNA Sequencing
• Übungsaufgabe 4 (Abgabe 16.11.):
  855: Lunch in Grid City
• Übungsaufgabe 5 (Abgabe 23.11.):
  491: Tile Topology
• Übungsaufgabe 6 (Abgabe 30.11.):
  106: Fermat vs. Pythagoras
• Übungsaufgabe 7 (Abgabe 7.12.):
  10199: Tourist Guide
• Übungsaufgabe 8 (Abgabe 14.12.):
  10092: The Problem with the Problem Setter
• Übungsaufgabe 9 (Abgabe 21.12.):
  10003: Cutting Sticks
• Übungsaufgabe 10 (Abgabe 11.01.):
  10160: Servicing Stations
• Übungsaufgabe 11 (Abgabe 18.01.):
  Aufgabe A aus dem ICPC 2000 Wettbewerb (s.o.)
• Übungsaufgabe 12 (Abgabe 25.01.):
  Aufgabe F aus dem ICPC 2000 Wettbewerb (s.o.)
• Übungsaufgabe 13 (Abgabe 01.02.):
  Aufgabe C aus dem ICPC 2001 Wettbewerb (s.o.)
• Übungsaufgabe 14 (Abgabe 08.02.):
  Aufgabe H aus dem ICPC 2001 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ätenstens zum angegebenen Abgabetag um 14:00 Uhr per Email an den Dozenten geschickt worden sein (der Zeitstempel der Email zählt).

Hilfsmittel

• Spickzettel JHU
• Spickzettel TUM