Übungen zur Vorlesung „Algorithmen und Datenstrukturen“ (WS 2008/2009)
|
Einsichtnahme in die 2. Klausur am 22.4., 15–16 Uhr in E 216. Ergebnisse der 2. Klausur am 16.4.2009 Ergebnisse der 1. Klausur am 10.2.2009 |
In der Vorlesung werden Standardalgorithmen und grundlegende Datenstrukturen behandelt. Darstellungsformen und Spezifikation von Algorithmen, elementare und höhere Datenstrukturen, Suchbäume, Hash-Tabellen, rekursive Algorithmen, Algorithmen zum Suchen und Sortieren, grundlegende Graphenalgorithmen und Zeichenkettenalgorithmen.
In theoretischen Übungen wird der Vorlesungsstoff vertieft, in praktischen Übungen werden Algorithmen und Datenstrukturen in Java implementiert. |
Termine
| Vorlesung (U. Brandes) | Di 08:30 – 10:00 (A 702) Mi 08:30 – 10:00 (G 201) Die Vorlesungen werden aufgezeichnet |
| Übung (C. Pich, S. Endele) | Mi 12:30 – 14:00 (D 432) Do 14:15 – 15:45 (F 425) |
| Prüfungen | zweistündige Klausur 1. Termin: Di., 10.2.2009, 8–10 Uhr in A702 2. Termin: Do., 16.4.2009, 10–12 Uhr in A 702 |
Übungsblätter
Die Übungsblätter sind ab jedem Freitag als PDF-Dateien auf dieser Seite erhältlich. Die Aufgaben sind innerhalb von zehn Tagen zu bearbeiten. Abgabe auf Papier oder per E-Mail ist jeweils bis Montag um 12 Uhr möglich.
Die abgegebenen Lösungen werden korrigiert und mit Punkten bewertet und in der Übung besprochen. Das Erlangen von mindestens der Hälfte der möglichen Punkte und die aktive Teilnahme an den Übungen (insbesondere mindestens einmal „Vorrechnen“) ist Voraussetzung für die Teilnahme an der Klausur.
Abgabe der Praktischen Aufgaben
- Die Java-Klassen sollen nach dem Schema
u01.kennung1_kennung2.ClassNamein Packages organisiert werden – die Dateien müssen dann auch in den entsprechenden Ordnern liegen, also z.B. die DateiClassName.javainu01/kennung1_kennung2/(mehr Informationen zu Packages). - Bitte weder für Dateinamen noch im Quellcode Sonderzeichen (Umlaute usw.) verwenden.
- Die
*.java-Dateien sollen in eine einzige ZIP-Datei gepackt werden, benannt nach dem Schema01_kennung1_kennung2.zip(kein bzip/tar/gz/rar/7z/... oder sonstiges Packformat). Bitte nur die selbst erstellten*.java-Dateien mit-zippen, keine der von uns bereitgestellten Interfaces oder Testklassen und keine kompilierten*.class-Dateien - In der ZIP-Datei unbedingt die
Unterverzeichnisstruktur mit-zippen (geht z.B. mit dem
Befehl
zip -r 01_kennung1_kennung2 /foo/bar/u01/). Dabei relative Pfade verwenden, so dassu01/...im „Wurzelverzeichnis“ des ZIP-Archivs liegt. - ZIP-Datei als E-Mail-Attachment an
ad_u_W08@inf.uni-konstanz.deschicken, textlose E-Mail mit Betreff nach dem SchemaAlgodat 01 kennung1 kennung2genügt - Falls nicht anders angegeben, dürfen für die
praktischen Aufgaben keine Klassen außer
java.lang.*importiert werden.
Abgabe der Theoretischen Aufgaben
- Bitte auf den Lösungen die Namen aller Gruppenmitglieder angeben – sonst wissen wir nicht, wer die vielen Punkte bekommen soll!
- Abgabe
- entweder auf Papier in die mit "Algorithmen und Datenstrukturen/Abgabe" beschrifteten Ablagefächer im E2-Treppenhaus, bitte alle Einzelblätter zusammenheften,
- oder per E-Mail-Attachment an
ad_u_W08@inf.uni-konstanz.deseparat als eine einzige PDF-Datei im DIN A4-Format (kein *Office, keine Bilddateien), benannt nach dem Schema01_kennung1_kennung2.pdf– textlose E-Mail mit Betreff nach dem SchemaAlgodat 01 kennung1 kennung2genügt (entweder zusammen mit den Programmieraufgaben, oder in zwei E-Mails; bitte aber nicht in obige ZIP-Datei packen)
- Entscheidend ist die zuletzt bis Montag 12 Uhr eingegangene Lösung.
Studierende, die noch keine inf-Kennung haben, erhalten
eine per Anmeldung zu dieser Lehrveranstaltung mit dem Account-Tool.
Wer schon eine inf-Kennung hat, meldet sich bitte ebenfalls
per Account-Tool an. Wer sich eingetragen hat, wird für
das laufende Semester der Unix-Gruppe
ad_W08 hinzugefügt, die auch als
Mail-Alias dient.
Wichtige Mitteilungen werden
über diesen Verteiler bekanntgegeben. Wer nicht
über die inf-Kennung E-Mails liest, kann die dorthin
eingehenden E-Mails per .forward-Datei an eine
andere Adresse weiterleiten lassen. Bei Fragen dazu bitte
melden!
Alle Aufgaben können und sollen in Zweiergruppen abgegeben werden.
Einige Dateien sind nur lokal an der Universität Konstanz lesbar.
Skriptum
Ein Skript wird im Laufe des Semesters erstellt. An dieser Stelle werden Vorabversionen der Kapitel zur Verfügung gestellt.
Literaturhinweise
- N. Blum: Algorithmen und Datenstrukturen. Oldenbourg, 2004
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Algorithmen - Eine Einführung. Oldenbourg, 2007 (2. Aufl.)
- T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen. Spektrum Akademischer Verlag, 2002 (4. Aufl.)
- U. Schöning: Algorithmik. Spektrum Akademischer Verlag, 2001
- M.A. Weiss: Data Structures and Algorithm Analysis in Java. Pearson, 2007 (2nd ed.)
Weitere Informationen
- Eintrag im Vorlesungsverzeichnis
- Hinweise zur Benutzung des Account-Tools
- gnuplot homepage
- Java Generics Tutorial (Sun)
- xSortLab Applet - Ablauf und Vergleich von Sortieralgorithmen