Uni-Konstanz Uni-Konstanz
Fachbereich Informatik und Informationswissenschaft   Datenstrukturen & Algorithmen
Wagner / Willhalm

> Ankündigung im Veranstaltungsverzeichnis
> Vorlesung: Di 8.30-10.00 Uhr/G201 (V\Ü (14tägig im Wechsel)) und Do 8.30-10.00 Uhr/R 712
> Praktische Übung: Di 8.30-10.00 Uhr/G201 (V\Ü (14tägig im Wechsel))
> Theoretische Übung: Di 12.30-14.00 Uhr/G305 oder Mi 12.30-14.00 Uhr/D431
Theoretische Aufgaben
Die theoretischen Aufgaben werden immer donnerstags in der Vorlesung ausgegeben. Sie sind bis zum Freitag der darauffolgenden Woche 12 Uhr schriftlich zu bearbeiten und in den bereitgestellten Fächern vor dem Sekretariat E212 abzugeben. Die abgegebenen Aufgaben werden korrigiert und in Kleingruppen besprochen.


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

Es ist so gedacht, dass alle praktischen Aufgaben in Zweiergruppen gelöst werden, d.h. dass das Testprogramm keine Fehler mehr findet.

Beschreibung der Klassen.

Die jar-Dateien, die die zu implementierenden Interfaces enthalten:

  • 1. Übung und Lösung (Fibonacci) bis Montag, den 29. Oktober
  • 2. Übung und Lösung (Liste) bis Montag, den 12. November
  • 3. Übung und Lösung (Merge- und Quicksort) bis Montag, den 26. November
  • 4. Übung und Lösung (Heaps) bis Montag, den 17. Dezember
  • 5. Übung und Lösung (AVL-Bäme) bis Montag, den 21. Januar
  • 6. Übung (Graphen) bis Montag, den 4. Februar
    Bei dieser Übung ist kein Testprogramm enthalten, da es Teil der Aufgabenstellung ist, ein solches zu schreiben. Außerdem sollen einfache Algorithmen auf dem Graphen implementiert werden. Vorschläge dafür sind:
    1. Überprüfen, dass die Anzahl der Kanten gleich der Summe der Ein- bzw. Aus-Grade ist.
    2. Test, ob der Graph schleifenfrei ist
    3. Test, ob der Graph einfach ist
    4. Tiefensuche
    5. Breitensuche
    6. Test, ob der Graph einen Euler-Kreis enthält (ÜA 12.1)
    7. Suche nach kantendisjunkten Wegen (ÜA 12.3)
    8. Test, ob der Graph zusammenhängend ist (ÜA 13.1a)
    9. Suche nach einem aufspannenden Baum (ÜA 13.1b)
    10. kürzeste Wege finden (ÜA 13.2b)
    11. Dijkstra
    12. starke Zusammenhangskomponenten (ÜA 13.4)
    Falls jemand sein Testprogramm oder einen Algorithmus mit einer Einverständniserklärung zur Veröffentlichung an mich schickt, stelle ich sie gerne an dieser Stelle den anderen zur Verfügung!

Klausur

Haupttermin:

Donnerstag

14. Febr.

08:30 - 10:00 Uhr

R 712

Nachtermin:

Freitag

12. April

14:00 - 16:00 Uhr

R 711


letzte Änderung: 19.07.2016

Valid HTML 4.01!