Übungen zur Vorlesung „Algorithmen und Datenstrukturen“ (WS 2010/2011)
|
Die Nachklausur findet am Dienstag, 5.4.2011, von 10:00-12:00 Uhr in Raum R 611 statt. |
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, A. Karrenbauer) | Di 08:30 – 10:00 (A 703) Mi 08:30 – 10:00 (A 702) |
| Übung (M. Mader, J. Lerner) | Mo 12:30 – 14:00 (G309) Mo 14:15 – 15:45 (F425) |
| Prüfungen | Klausur (100min) 1. Termin: Montag, 21.2., 10:00 Uhr (Raum A 703) 2. Termin: Dienstag, 5.4., 10:00 Uhr (Raum R 611) |
Übungsblätter
Die Übungsblätter sind jeden Mittwoch, 10 Uhr als PDF-Datei auf dieser Seite erhältlich. Die Aufgaben sind innerhalb von einer Woche zu bearbeiten. Die Abgabe der Übungsblätter ist bis Mittwoch, 10 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 ist Voraussetzung für die Teilnahme an der Klausur.
Abgabe der Praktischen Aufgaben
- Die Java-Klassen sollten dem Interface-Namen entsprechen; verwenden Sie z.B. für das Interface
IFibonacci.javaden Klassen-NamenFibonacci.java. - Falls nicht anders angegeben, dürfen für die
praktischen Aufgaben keine Klassen außer
java.lang.*importiert werden. - Geben Sie Ihren vollen Namen im
author-Tag Ihres Klassenkommentars an. - Achten Sie darauf, Ihre Klassen mit ausreichenden Kommentaren zu versehen. Falls Ihr Programm nicht funktioniert sind ausschließlich die Kommentare Grundlage für die Bewertung der Abgabe!
- Bitte weder für Dateinamen noch im Quellcode Sonderzeichen (Umlaute usw.) verwenden.
- Falls nicht anders angegeben, sollen die Klassen nach dem Schema
u01.nachname1_nachname2.Classname.javain Packages organisiert werden – Ersetzen Sie die zweistellige Zahl hier und im Folgenden mit der Nummer des entsprechenden Übungsblattes, und schreiben Sie die Nachnamen klein. - Benutzen Sie möglichst ein aktuelles Java Runtime Environment (Java 1.6 Update 22)
- Die Dateien müssen dann
auch in den entsprechenden Ordnern liegen, also z.B. die
Datei
Fibonacci.javainu01/nachname1_nachname2/(mehr Informationen zu Packages). - Die
*.java-Dateien sollen in eine einzige ZIP-Datei gepackt werden, benannt nach dem Schema01_nachname1_nachname2.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_nachname1_nachname2 /foo/bar/u01/). Dabei relative Pfade verwenden, so dassu01/...im „Wurzelverzeichnis“ des ZIP-Archivs liegt. - ZIP-Datei als E-Mail-Attachment an
ad_u_W10@inf.uni-konstanz.deschicken, textlose E-Mail mit Betreff nach dem SchemaAlgodat 01 nachname1 nachname2genügt
- Die Lösungen der Aufgaben sollen mit der eclipse IDE entwickelt weden. Die Materialien werden über ein SVN Repository zur Verfügung gestellt, ebenso erhät jedes Team einen Ordner im Repository für die Bearbeitung der Aufgaben
- Die Repository-Addresse ist
https://svn.uni-konstanz.de/algo/ad_w10 - Genauere Hinweise zur Nutzung des Repositories
- Mit Ausgabe der Übungsblätter können Materialen für die praktischen Aufgaben, wie z.B. Interfaces, über das Projekt
materialausgecheckt werden. - Die studentischen Ordner werden zu den auf den Übungsblättern angegebenen Abgabeterminen von den Übungsgruppenleitern ausgecheckt. Diese Version gilt als die Abgabe.
- Erstellen Sie für die Abgabe von zusätzlichen Materialien, wie z.B. Laufzeitdiagrammen, einen Ordner "data" in Ihrem Projektverzeichnis, und committen Sie diesen und entsprechende Dateien ebenfalls ins Repository.
Abgabe der Theoretischen Aufgaben
- Bitte auf den Lösungen die Namen aller Gruppenmitglieder angeben – sonst wissen wir nicht, wer die vielen Punkte bekommen soll! Bitte schreiben Sie auch auf die Lösungen an welchem Übungstermin Sie teilnehmen – das erleichtert die Rückgabe der korrigierten Blätter.
- Abgabe
- per E-Mail-Attachment an
ad_u_W10@inf.uni-konstanz.deseparat als eine einzige PDF-Datei im DIN A4-Format (kein *Office, keine Bilddateien), benannt nach dem Schema01_nachname1_nachname2.pdf– textlose E-Mail mit Betreff nach dem SchemaAlgodat 01 nachname1 nachname2genügt. - oder auf Papier in die mit "Algorithmen und Datenstrukturen/Abgabe" beschrifteten Ablagefächer im E2-Treppenhaus, bitte alle Einzelblätter zusammenheften,
- per E-Mail-Attachment an
Alle Aufgaben können und sollen in Zweiergruppen abgegeben werden.
Einige Dateien sind nur lokal an der Universität Konstanz lesbar.
Skript
Das Skript aus den vergangenen Semestern wird regelmäßig korrigiert und aktualisiert. Im Wintersemester 2008/09 wurde die Vorlesung aufgezeichnet.
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.)
- K. Mehlhorn, P. Sanders: Algorithms and Data Structures. Springer, 2008
- 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 zu Benutzer-Accounts
- Benutzung SVN repository
- gnuplot homepage
- Java Generics Tutorial (Sun)
- xSortLab Applet - Ablauf und Vergleich von Sortieralgorithmen