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.

Vorkenntnisse:

Einführung in die Programmierung

Angesprochener HörerInnenkreis:

Informatik Bachelor, Mathematik Bachelor, Elektrotechnik Diplom I

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