Datenstrukturen und Algorithmen - FS 2014
Übungsgruppe D4 (Deutsch) - Nachnamen 'Hei...' bis 'Kon...'
Assistent: Daniel Graf - ETZ H91 - Mittwochs 15.15-17.00 Uhr
Kontakt
Für Übungsabgaben, Fragen und Rückmeldungen melde dich bitte bei grafdan@ethz.ch.
Grader
Den Grader für meine Zusatzaufgaben findest du hier: Grader für die Zusatzaufgaben
Beachte auch die Hinweise und Templates unter Programmieraufgaben.
Links
Woche 1 - 26. Februar 2014
Woche 2 - 5. März 2014
Woche 3 - 12. März 2014
Woche 4 - 19. März 2014
Woche 5 - 26. März 2014
Woche 6 - 2. April 2014
- Handout 6a: Dynamische Programmierung: Theorie
- Handout 6b: Dynamische Programmierung: Aufgabensammlung
Woche 7 - 9. April 2014
Woche 8 - 16. April 2014
- Handout 8: Backtracking, Spielbäume, Min-Max, Branch & Bound
- Slides: praktische DP-Aufgabe 'Quersumme'
Woche 9 - 30. April 2014
Woche 10 - 14. Mai 2014
Woche 11 - 21. Mai 2014
Woche 12 - 28. Mai 2014
Diese Zusammenfassungen wurden von Sebastian Millius und Sandro Feuz erarbeitet.
Zum Grader
Woche 1 - 26. Februar 2014
- Maximum Subarray Problem (PDF) - Templates: Java C/C++
- Maximum Gap Problem (PDF) - Templates: Java C/C++
Woche 2 - 5. März 2014
- Mehrheitsvotum (Serie 2.4) (PDF) - Templates: Java C/C++
Woche 3 - 12. März 2014
- 3-SUM (Serie 3.2.c) (PDF) - Templates: Java C/C++
Woche 9 - 15. April 2014
- Flappy Bird (Dynamische Programmierung) (PDF) - Templates: Java
Hinweise
- Der Grader für diese Zusatzaufgaben akzeptiert Einsendungen in Java, C, C++, Python und Pascal.
- Um deinen Code einzusenden musst du ein Benutzername und Passwort wählen und dich damit einloggen.
(Am besten wählst du deinen Vor- und Nachnamen, das hilft mir bei Fragen deine Einsendungen zu finden.) - Für Einsendungen in Java muss die Klasse 'submission' heissen, vgl. die Templates oben.
- Bei Aufgaben mit grossen Eingaben (mehr als 100'000 I/O Operationen) beachtete folgende Hinweise:
- Für Java: verwende BufferedReader statt Scanner (siehe Template oben).
- Für C/C++: Benutze entweder printf/scanf oder verbessere die Performance von C++ streams indem du std::ios_base::sync_with_stdio(false); am Anfang von main inkludierst.
Damenproblem als Beispiel für Backtracking
- Problembeschreibung und Tabellen in Wikipedia
- FPGA-Implementierung: Video und Verilog-Code
Dynamische Programmierung angewandt: Image Retargeting
- Seam Carving als Beispiel für dynamische Programmierung (analog zum Marsrover-Problem (Blatt 7 Aufgabe 1)
SIGGRAPH 2007 Paper von Shai Avidan und Ariel Shamir: Webseite, Paper, Video und Wiki - Browser-Implementation des Verfahrens
- Meine App mit einem anderen Verfahren für das selbe Problem