Knowledge and Data Engineering
Uni Kassel

Algorithmen und Datenstrukturen

3.7.2009. Prüfungsanmeldungen von Studenten aus externen Fachbereichen bitte im jeweiligen Heimat-Fachbereich vornehmen sowie per E-Mail an kde-office@cs.uni-kassel.de unter Angabe von Name, Matr.-Nr. und FB.
Für Prüfungsanmeldungen von Studenten aus dem FB 16 genügt die Anmeldung in der OKA. Vielen Dank.
1.9.2009.Die Klausur gliedert sich in Theorie- und Praxisteil à 40 bzw. 90 Minuten. Beide Teile decken jeweils den ganzen Vorlesungs- und Übungsstoff ab. Der Praxisteil zeichnet sich dadurch aus, dass man größere Aufgaben am Stück bearbeitet/rechnet, während im Theorieteil mit mehreren kleineren Aufgaben die thematische Spannweite abgefragt wird. Für den Theorieteil sind keine Unterlagen erlaubt. Für den Praxisteil dürfen beliebige nicht-elektronische Unterlagen, z.B. Bücher, Notizen, Vorlesungsfolien oder Übungsaufgaben mit Lösungen verwendet werden. Nicht erlaubt sind Taschenrechner, Laptops oder ähnliche Geräte.
Erster Veranstaltungstag:
Montag, 20. April 2009, 14:15 in Raum 1603 (Neubau WA 73/Emilienstraße)
Ort und Zeit:
Montags, 14.15 h - 15.45 h, in Raum 1603
Hausaufgaben:
  • Hinweise zur Abgabe von Aufgaben.
  • Link zum Abgabesystem
  • Bitte senden Sie Fragen zur Veranstaltung sowie Fragen zum Abgabesystem an Herrn Eisterlehner oder Herrn Benz.
  • Bitte verwenden Sie in allen E-Mails den Betreff "AlgoDS".
Übungen:
Dienstags, 8.00 h - 9.30 h, in Raum 0446 (Altbau WA 73). Beginn 21. April
Dienstags, 12.00 h - 13.30 h, in Raum 1114 (Altbau WA 71). Beginn 21. April
Donnerstags, 10.00 h - 11.30 h, in Raum -1607 (Neubau WA 73/Emilienstraße). Beginn 23. April
Donnerstags, 16.00 h - 17.30 h, in Raum -1606 (Neubau WA 73/Emilienstraße). Beginn 23. April
Cip-Pool-Übung:
Mittwochs, 8.00 h - 10.00 h, in Raum -1201 (Altbau WA 73). Beginn 22. April
Wettbewerb:
Der Programmierwettbewerb läuft. Eine Beschreibung des Wettbewerbs befindet sich auf dem 9. Hausübungsblatt.
Täglich aktualisierte Zwischenergebnisse sind hier zu finden. Aktuelles (insbesondere der Tagessieger) wird über twitter mitgeteilt.
Angesprochener HörerInnenkreis:
Informatik Bachelor, Mathematik Bachelor, Elektrotechnik Diplom I
Vorkenntnisse:
Einführung in die Programmierung
Leistungsnachweis:
Klausur; Studienleistung (b/nb)
Veranstalter:
Prof. Dr. Gerd Stumme , Dipl.-Inform. Dominik Benz, Dipl.-Inform. Folke Eisterlehner

Wir haben keine festen Sprechstunden, unsere Türen stehen aber meistens offen. Kommen Sie einfach vorbei!

Inhalt:
Die Teilnehmer lernen grundlegende Algorithmen und Datenstrukturen der Informatik wie Such- und Sortierverfahren, rekursive Algorithmen, Bäume, Hashverfahren etc. kennen. Dabei werden neben algorithmischen Ideen verschiedene Techniken für die Analyse des Zeitbedarfs und den Nachweis der Korrektheit vermittelt. Beispielprogramme vertiefen und erweitern die Programmierkenntnisse in Java. In den begleitenden Übungen sammeln die Teilnehmer weitere Programmiererfahrungen in Java und erwerben Fertigkeiten in der Algorithmenanalyse sowie im Entwickeln eigener algorithmischer Ideen.
Errata:
  • 3-27: Die return-Zeile muss lauten: return r1.area - r2.area;
  • 3-60: Alle runden Klammern hinter "count(...)" durch eckige Klammern ersetzen.
  • 3-60: Die letzte for-Schleife geht bis N-1.
  • 3-60: Die letzte Zeile muss heissen: a:=b;
  • 3-61: In NB-Zeile "dk" durch "dk" ersetzen.
Folien:
  • 0_Organisatorisches_Handout.pdf PDF-Download
  • 1_Einfuehrung_Handout.pdf PDF-Download
  • 2_Eigenschaften_Handout.pdf PDF-Download
  • 3_Sortieralgorithmen_Handout.pdf PDF-Download
  • 4_GrundlegendeDatenstrukturen_Handout.pdf PDF-Download
  • 5_JavaCollectionFramework_Handout.pdf PDF-Download
  • 6_Baeume_Handout.pdf PDF-Download
  • 7_Hashing_Handout.pdf PDF-Download
  • 8_Werbung_Handout.pdf PDF-Download
  • 9_Graphen_Handout.pdf PDF-Download
Präsenzübungsblätter:
Hausaufgabenblätter:
Aufgabe Material Lösungsvorschlag
1. Hausübung Anagramm.java      aufgabe01 - Lösungsvorschlag  AnagrammLsg.java      
2. Hausübung     aufgabe02 - Lösungsvorschlag     
3. Hausübung   DataSearch.java  DataSource.java    aufgabe03 - Lösungsvorschlag    BinarySearch.java  LinearSearch.java  StopWatch.java   
4. Hausübung   ExampleJobs.java  Job.java    aufgabe04 - Lösungsvorschlag     
5. Hausübung   DataSort.java  DataSource2.java  Merge4SortTest.java     
6. Hausübung   Calculator.java  expressions.txt  Stack.java     
7. Hausübung      
8. Hausübung   LectureTest.java     
9. Hausübung   DataPivot.java  DataSort.java  DataSource2.java  DataSource3.java  PivotOpt.java  ReferenceDataSource.java     
10. Hausübung ArithmeticTreeTest.java    expressions.txt  TreeCalculator.java     
11. Hausübung   BinaryTreeNode.java  DataSource2.java  DataSource4.java  PrintingBinarySearchTree.java  SearchTree.java     
12. Hausübung AbstractAVLTree.java    AVLNode.java  DataSource3.java  PrintingAVLTree.java  TreeStatisticsCalculator.java  TreeVisitor.java     
13. Hausübung   DataSort.java  DataSource4.java  Heap.java  HeapSort.java  HeapSortRunner.java  IntegerComp.java     
14. Hausübung AbstractGraph.java    Color.java  Edge.java  Graph.java  GraphTest.java  IntegerGraphReader.java  testgraphs.txt     
Errata:
  • 3. Hausübung: Bei der Beispielausgabe der main-Methode der Klasse StopWatch ist bei den Werten von n jeweils eine Zehnerpotenz zu wenig (d.h. n=1000 statt n=10000, n=1000000 statt n=10000000, ...). Korrekt sind die Werte aus der Aufgabenstellung (jeweils die grössere Zehnerpotenz).
  • 8. Hausübung:
    • 1. Aufgabe (Queue als Liste) "Im Falle einer leeren Liste soll enqueue null zurückliefern." Richtig ist: "... soll dequeue null..."
    • 2. Aufgabe (Datenstruktur Lectures): An zwei Stellen ist von Namen von Studenten die Rede; korrekterweise muss von Matrikelnummern gesprochen werden, da in der Datenstruktur nur die Matrikelnummer und nicht der Name eines Studenten abgespeichert wird.
  • 10. Hausübung: Die Beispielausgabe der Zusatz-Aufgabe (Parsen von Postfix-Notation) muss richtigerweise lauten:
    Parsing expression 2
    Postfix-Notation:
     7 3 5 6 * + *
    Infix-Notation:
    (7*(3+(5*6)))
    Wert des Ausdrucks:
    231
     
    (Die alte Ausgabe war semantisch korrekt, jedoch in abgeänderter Reihenfolge)
  • 12: Hausübung: Es wird nach der Anzahl strukturell verschiedener (2,4)-Bäume der Höhe 3 gefragt
Lösungsvorschläge:
Die Lösungsvorschläge zu den Präsenz- und Hausaufgabenblättern finden Sie innerhalb der Lernplattform Moodle.
Literatur zur Vorlesung:
  • Gunter Saake, Kai-Uwe Sattler: Algorithmen und Datenstrukturen - Eine Einführung mit Java, dpunkt-Verlag, 2006. Die Einzelkapitel sind relativ preiswert als E-Book erhältlich, für die Vorlesung nützlich sind voraussichtlich die Kapitel 5, 7, 8, 13, 14, 15 und 16.
  • Robert Lafore: Data Structures & Algorithms in Java, Sams Publishing, 2003.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Algorithmen - Eine Einführung, Oldenbourg Verlag, 2007.
  • Heinz-Peter Gumm et al.: Einführung in die Informatik. Oldenbourg Verlag, 2006, Kapitel 4.
  • Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen. Spektrum Akademischer Verlag, 2002.
  • Gustav Pomberger, Heinz Dobler: Algorithmen und Datenstrukturen, Pearson, 2008
  • B. Owsnicki-Klewe: Algorithmen und Datenstrukturen, Wissner, 1994
  • Siehe auch Semesterapparat der Bereichsbibliothek 7

Kontakt: