Datenstrukturen und Algorithmen - HS 2016

Woche 1 - 26. September 2016

• Handout 1: Allgemeines, Asymptotische Analyse, Rekursionsgleichungen
• Lösungen zu den Zusatzaufgaben
• Detailliertere Erklärungen zur asymptotischen Analyse

Woche 2 - 3. Oktober 2016

• Handout 2: Induktionsbeweise (Beispiel: Kreisflächen)
• Kreisflächen zählen als Programmieraufgabe

Woche 3 - 10. Oktober 2016

• Handout 3: Divide & Conquer (Mergesort, Binäre Suche)

Woche 4 - 17. Oktober 2016

• In-Class Übungen: Algorithmenentwurf (Max Gap und Substring Oracle)

Woche 5 - 24. Oktober 2016

• Slides: Auswahlproblem (Median bestimmen mit QuickSelect oder mit dem Verfahren von Blum)
  (Detailinformationen: Vorlesungsmitschrift FS 2016)

Woche 6 - 31. Oktober 2016

• Handout 6: Sortierverfahren
• Lösung zur Zusatzaufgabe Heapsortme
• Suchalgorithmen implementiert
  • Heapsort
  • Quicksort
  • Radixsort

Woche 7 - 7. November 2016

• Handout 7a: Dynamische Programmierung: Theorie
• Handout 7b: Dynamische Programmierung: Aufgabensammlung

Grosse Teile dieser Handouts wurden von Sebastian Millius und Sandro Feuz erarbeitet.

Zum Grader

Woche 1 - 26. September 2016

• Maximum Subarray Problem (PDF) - Templates: Java C/C++
• Maximum Gap Problem (PDF) - Templates: Java C/C++

Woche 2 - 3. Oktober 2016

• Kreisflächen zählen auf dem UVA Online Judge

Woche 4 - 17. Oktober 2016

• 3-SUM (ähnliche Aufgabe wie in Serie 4.2) (PDF) - Templates: Java C/C++

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.