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
- Einführung
- Datenstrukturen
- Zeichenketten
- Sortieren, selektieren und suchen
- 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
- ICPC Wettbewerb von 1997
Ü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