Die theoretischen Aufgaben werden immer dienstags in der Vorlesung verteilt. Sie sind bis vor Beginn der Dienstagsvorlesung der darauffolgenden Woche schriftlich zu bearbeiten und in der Vorlesung oder schon am Vorabend in den bereitgestellten Fächern im Treppenhaus vor dem Sekretariat E212 abzugeben. Die abgegebenen Aufgaben werden korrigiert, bewertet und freitags in Kleingruppen besprochen.

Im Laufe des Semesters müssen 50% der erreichbaren Punkte erzielt werden und zwar sowohl im Zeitraum vor Neujahr als auch in dem danach.

• 1. Übung (O-Notation, Laufzeit)
• 2. Übung (O-Notation, Laufzeit, Listen)
  Zum Angucken: Laufzeitgraphen [Farbe, SW]
  Musterlösung für Aufgabe 4 [pdf]
• 3. Übung (Schlange, Divide-and-Conquer, O-Notation)
• 4. Übung (Sortieren)
• 5. Übung (Bäume, Sortieren, Heaps)
• 6. Übung (Suchbäume)
• 7. Übung (Rot-Schwarz-Bäume, Prioritätssuchbäume, Heaps)
• 8. Übung (Sortieren, Prioritätsschlangen, Prioritätssuchbäume, Heaps)
• 9. Übung (Hashing)
• 10. Übung (Graphen)
• 11. Übung (Durchlaufstrategien, Triangulierungen)
• 12. Übung - 2 Dateien: [pdf, pdf] (Dijkstras Algorithmus, Bellman-Ford-Algorithmus, Matching, amortisierte Kosten)
• 13. Übung (Kürzeste Wege und Matrizen, minimale aufspannende Bäume)
  

Die praktischen Aufgaben werden in einem ca. 14-tägigen Rhythmus donnerstags gestellt und besprochen. Neben der Aufgabenstellung in Form des zu implementierenden Interfaces wird auf dieser Seite ein Testprogramm bereitgestellt, das - soweit möglich - die Korrektheit einer Implementation automatisch überprüft.

Es wird insgesamt 6 oder 7 praktische Übungen geben. Sie können in Einer- oder Zweiergruppen gelöst werden. Von den ersten drei und den letzten 3-4 Aufgaben müssen jeweils alle bis auf eine Aufgabe korrekt gelöst werden.

Die jar-Dateien, die die zu implementierenden Schnittstellen oder abstrakten Klassen enthalten:

• 1. Übung [jar, pdf] (Euklidischer Algorithmus)
  Abgabe bis Di, 22.10. (Besprechung am 24.10.)
• 2. Übung [jar, pdf] (Stack und umgekehrte polnische Notation)
  Abgabe bis Mo, 11.11. (Besprechung am 14.11.)
  Für Interessenten: In dem Artikel A Tutorial for Designing Flexible Geometric Algorithms (Algorithmica 2002) geht es unter anderem um full logical inspectability im Rahmen von generischem Programmieren in C++.
• 3. Übung [jar, pdf] (Sortierverfahren)
  Abgabe bis Mo, 2.12. (Besprechung am 5.12.)
• 4. Übung [jar]
  Abgabe von Teil I (einfacher Suchbaum) bis Mi, 18.12.02.
  Abgabe von Teil II (Prioritätssuchbaum) bis Mi, 08.01.03.
  Tipp 1: Bei kurzen oder kryptischen Fehlermeldungen alle *.class-Dateien löschen und mit Option -g neu kompilieren: javac -g */ex4/*.java
  Tipp 2: Es lohnt sich fürs Debugging, in der Klasse, mit der man die Knoten eines Prioritätssuchbaums implementiert, eine private Variable index vom Typ int anzulegen, die die Nummer des Knotens speichert und die bei der toString-Methode ausgegeben werden kann. Bei toString ist es sinnvoll, zusätzlich die Indizes der nicht-null-Kinder auszugeben.
• 5. Übung [jar]
  • Implementieren Sie ungerichtete Graphen mit einer Methode für Tiefensuche und zur Färbung seiner Zusammenhangskomponenten.
  • Verwenden Sie SimpleList für die Knotenliste Ihres Graphen und für die Listen der zu jedem Knoten inzidenten Kanten. Speichern Sie keine zusätzliche Listen der zu jedem Knoten adjazenten Knoten, sondern verwenden Sie die Kantenlisten, um die Methode Iterator adjacentNodes() der Klasse Node zu implementieren.
  • Abgabe bis Mi, 23.01.03.
• 6. Übung [jar]
  • Implementieren Sie einen Sweep-Line-Algorithmus, der in O(k + n log n) Zeit alle k Paare von sich schneidenden Rechtecken in einer Menge von n gegebenen Rechtecken bestimmt.
  • Abgabe bis Mo, 10.02.03.

• 1. Aufgabe [jar] als Folien [zip]
• 2. Aufgabe [jar] als Folien [zip]
• 3. Aufgabe [jar] als Folien [zip]
• 4. Aufgabe [jar] als Folien [zip]
• 5. Aufgabe [jar] als Folien [zip]

Eine Themenliste ist ebenfalls erhältlich.

Tim Rachor hat folgende Liste von Links zusammengestellt, wo viele der Algorithmen aus der Vorlesung visualisiert werden:

• Binäre Suchbäume
• Rot-Schwarz-Bäume
• Tiefensuche
• Breitensuche
• Algorithmus von Dijkstra
• Minimale aufspannende Bäume
• Algorithmus von Prim-Jarnik

Für die, die an der Nachklausur teilnehmen wollen oder müssen, gibt es hier die Aufgaben vom Haupttermin dieses Semesters [pdf], die genaue Punkteverteilung [txt] sowie eine Übersicht, die zeigt, in welchem Maß die Klausur direkt auf die praktischen und theoretischen Übungsaufgaben aufgebaut hat [txt].

Mein Tipp zur Vorbereitung: Ich würde mir alle theoretischen Übungsaufgaben des Semesters so klar machen, dass ich sie jemand anderem erklären kann, und mindestens ein oder zwei der praktischen Aufgaben 3-6 programmieren. Auf Aufgaben zu Rot-Schwarz-Bäumen werde ich wie beim Haupttermin verzichten. Alles Gute!

• T.H. Cormen, C.E. Leiserson, R.L. Rivest: Introduction to Algorithms. 2. Auflage, McGraw-Hill, 2001.
• M. Goodrich and R. Tamassia: Data Structures and Algorithms in JAVA. John Wiley & Sons, 1998.
• T. Ottmann und P. Widmayer: Algorithmen und Datenstrukturen. 3. überarb. Auflage, Spektrum Akademischer Verlag, Heidelberg 1993.
• R. Sedgewick: Algorithms. 2. Auflage, Addison-Wesley, Reading, Massachusetts 1988.