TU München - Fakultät für Informatik Lehrstuhl III: Datenbanksysteme

Betreuer:

Veneta Dobreva, Benjamin Gufler, Andreas Scholz

Selected Fun Problems of the ACM Programming Contest

In diesem Proseminar werden die TeilnehmerInnen mit jeweils einem ausgewälten Problem des seit 1970 alljährlch stattfindenden ACM Programming Contest konfrontiert. Diese Probleme zeichnen sich einerseits durch recht spassige und interessante Aufgabenstellungen aus, andererseits erlauben diese Aufgaben Lösungen, die oft sehr elegant und kompakt sind (der Kern umfasst typischerweise weniger als 50 Zeilen Programmcode) und fast immer mit Aha!-Effekten einhergehen.

Die SeminarteilnehmerInnen werden jeweils das Problem vorstellen, eine möglichst elegante Lösung - formuliert in der Lieblingsprogrammiersprache der Teilnehmer - erarbeiten und diese wärend des Seminarvortrags präsentieren. (Falls es bei der Lösung des Problems "haken" sollte, ist das kein Show Stopper: wir geben dazu gerne Tipps - niemand muss deshalb dieses Seminar nicht bestehen.)

Allgemeine Hinweise

• Bitte schauen Sie regelmäßig hier nach, ob es irgendwelche Verschiebungen von Terminen oder andere Änderungen gegeben hat.
• Bitte beachten Sie die allgemeinen Hinweise für die Teilnahme an Seminaren.

Aktuelles

• Abgabefrist für die Ausarbeitung und die Folien ist der 22.07.2009 Bitte beachten Sie die Hinweise zu den Ausarbeitungen.
• Das Proseminar fängt ab jetzt um 16:15 Uhr an.
• Bitte ab jetzt alle E-Mails an schicken.

Organisatorisches

Themen (ACM ICPC Problemstellungen)

ACM ICPC Problem

• Insiders
• Water Shortage
• Fold-up Patterns
• Sisco's Galaxy
• Black Box
• Ro and Bot meet
• Period
• Merging Maps
• Wiring Assistant
• Rush Hour
• ALGOC
• Finding Seats
• Galou is Back
• Booby Traps
• The Flat Cupboard
• Tree
• Image is Everything
• The Unsinkable Ship
• Right Hand on the Wall
• Solver
• Lazy Math Instructor
• Mini Spreadsheet
• Gates
• DNA Consensus String
• Turn all the Lights off
• Collecting Luggage
• Master Mind

Hinweise zu den Vorträgen

Wichtig: Spätestens zwei Wochen vor Eurem Vortrag solltet Ihr einen Termin mit uns ausmachen, um Euren kompletten Foliensatz durchzusprechen. Dass sich daraus Änderungen an den Folien ergeben, ist die Regel (nicht die Ausnahme). Stellt also bitte sicher, dass Ihr Euch ein ausreichend grosses Zeitfenster für Änderungen einräumt.

• Die Länge der eigenlichen Vorträge beträgt jeweils maximal 30 Minuten. Die Erfahrung zeigt, dass in diesem Zeitrahmen nicht mehr als etwa 25 Folien sinnvoll präsentiert werden können. An die Vorträge schließt sich eine kurze offene Diskussion an, die sich auf den Inhalt des Vortrages aber auch auf den Vortrag an sich (Folien, Sprache) beziehen kann.
• Ihr findet weitere wertvolle Hinweise zum Aufbau eines Vortrages, zum Layout von Folien und dem Halten des Vortrages selbst, auf den folgenden Seiten:

1. How to give a good research talk
2. Der perfekte Seminarvortrag

• Der Inhalt des Vortrags sollte das durch den ACM Programming Contest gestellte Problem genau erläutern und vielleicht an 1-2 Beispielen demonstrieren. Dabei solltet Ihr betonen, was das Problem interessant und/oder knifflig macht. Den Rest des Vortrages solltet Ihr (1) auf die Diskussion möglicher Lösungsansätze (es kann durchaus mehrere denkbare Lösungen geben) und (2) die Darstellung der Realisierung der von Euch gewählten und implementierten Lösung verwenden.

Wichtig: Auf einer Folie Eures Vortrages sollet Ihr möglichst genau begründen warum Ihr gerade die von Euch gewählte Programmiersprache einsetzt. Falls Ihr nur eine Programmiersprache beherrscht, verwendet bitte diese Folie stattdessen darauf, 2-3 Features einer (fiktiven) Programmiersprache zu identifizieren, die Euch bei der Formulierung der Lösung besonders hilfreich gewesen wäre.

• Euer Programm zur Lösung des Problems wird typischerweise einen algorithmischen Kern - oft wenige Zeilen - beinhalten. Diesen Kern, evtl. gekürzt und vereinfacht falls angebracht, könnt und sollt Ihr während des Vortrags zeigen und erklären. Wenn sich der Code selbst nicht eignet, ist ein Flussdiagramm oder Ähnliches vielleicht eine bessere Alternative. Routinen oder Code-Teile, die Eingabe/Ausgabe implementieren sind oft sekundär und gehören nicht in Euren Vortrag.
• Beachtet, dass beim ACM Programming Contest allgemein wohlgeformte Inputs vorausgesetzt werden dürfen. Eine explizite Behandlung illegaler Eingaben könnt Ihr auch im Rahmen dieses Seminars ignorieren.
• Generell gilt: vermittelt das Prinzip Eure Lösung; eine genaue Studie des Codes ist nicht angebracht. Es ist auch denkbar, (Ausschnitte des) Code ausschliesslich ganz am Ende des Vortrages, auf sog. Backup-Folien in den Foliensatz aufzunehmen. Diese Folien zeigt man nur, wenn die Diskussion nach dem Vortrag oder spezifische Nachfragen dazu führen sollten.
• Der Vortrag von Matthias Reitinger aus dem SS 2007 setzt diese Vorgaben vorbildlich um (dieser Vortrag wurde mittels der LaTeX-Class Beamer realisiert: Shuffle Off to Milledgeville
• Die tatsächliche Demonstration Eures lauffäigen Programmes während des Vortrages kann sehr sinnvoll und motivierend für die Zuhörer sein. Auch hier gilt aber: kleine Beispiele, die den common case zeigen und nicht die vielleicht eher esoterischen Randfälle des Problems und seiner Lösung zum Inhalt haben.

Hinweise zu den Ausarbeitungen

• Die Ausarbeitung Eurer Vorträge erfolgt ausnahmslos in LaTeX. Für eine Einführung in LaTeX könnt Ihr Euch das Buch "LaTex" von Helmut Kopka aus der Bibliothek ausleihen. Das Buch "The LaTeX companion" von Frank Mittelbach sollte euch ausserdem alle weiterführenden Fragen beantworten. Für Bilder empfehlen wir Euch im Weiteren das Paket TikZ zu verwenden. Ein sehr gutes Online Latex Tutorial findet Ihr unter Latex Tutorial.
• Die folgende Ausarbeitung, die aus einem der früheren Selected Fun Problems-Seminare stammt, könnt Ihr als Orientierungshilfe für die Länge, Form und den Detailgrad Eurer Ausarbeitung verwenden
• Der Zeitrahmen für Abgabe der Ausarbeitungen dehnt sich bis zum Ende der Vorlesungszeit aus. Bitte schickt alle Ausarbeitungen im PDF-Format (also nicht die LaTeX-Quellen) per E-Mail an Veneta Dobreva.

Themenzuordnung und Termine