Uni-Logo
Algorithms and Complexity
 


Informatik II - Algorithmen und Datenstrukturen
Sommersemester 2018
Fabian Kuhn

 



Vorlesung

Kursbeschreibung

Die Vorlesung widmet sich dem Entwurf und der Analyse von Algorithmen. Dabei werden die grundlegenden Algorithmen und Datenstrukturen besprochen. Unter anderem behandeln wir die folgenden Themen: Sortieren, Suchen, Hashtabellen, Suchbäume, (Prioritäts-)Warteschlangen, Graphenalgorithmen (z.B. kürzeste Wege, Spannbäume, Breiten- und Tiefensuche).

Zeitplan

  • Montag 14:00-16:00: 101-00-036
  • Mittwoch 14:00-16:00: 101-00-036

Klausur

  • Ergebnisse: Die Ergebnisse sind online.
  • Zweiter Einsichtstermin: Montag, 15.10.2018, Raum 106-00 015, von 12-13 Uhr. Bitte Studierendenausweis mitbringen.
  • Einsicht: Dienstag, 02.10.2018, Raum 106-00 015, von 15-16 Uhr für A-L (Anfangsbuchstaben des Nachnamen) und 16-17 Uhr für M-Z. Bitte Studierendenausweis mitbringen.

Aufzeichnungen / Folien

Aufzeichnungen der Vorlesung sowie die (annotierten) Folien


Übungen

Übungsblätter

Die Übungen werden online mit dem Kursverwaltungssystem Daphne durchgeführt. Es wird dabei meist einen theoretischen Teil und einen praktischen Teil geben.

Übungsblatt Dateien Musterlösung Ausgabe Abgabe

uebungsblatt-01 QuickSort.py QuickSort.py 18.04.2018 30.04.2018
uebungsblatt-02 Keine loesung-02 30.04.2018 07.05.2018
uebungsblatt-03 CountingSort.py, RadixSort.py, ListElement.py, DoublyLinkedList.py CountingSort.py, RadixSort.py, ListElement.py, DoublyLinkedList.py 07.05.2018 14.05.2018
uebungsblatt-04 HashTable.py loesung-04, HashTable.py 14.05.2018 28.05.2018
uebungsblatt-05 BinarySearchTree.py loesung-05, BinarySearchTree.py 28.05.2018 04.06.2018
uebungsblatt-06 Treap.py, BinarySearchTree.py loesung-06, plot, Treap.py, BinarySearchTree.py 04.06.2018 11.06.2018
uebungsblatt-07 Keine loesung-07 11.06.2018 18.06.2018
uebungsblatt-08 Graph.py, PriorityQ.py, Freiburg.txt, points.txt loesung-08, Graph.py, path.png, dijkstra.csv 18.06.2018 27.06.2018
uebungsblatt-09 Blocksatz.py, input.txt loesung-09, Blocksatz.py, output.txt 25.06.2018 09.07.2018
uebungsblatt-10 PatternSearch.py, text.txt, patterns.txt loesung-10, PatternSearch.py, result.txt 09.07.2018 20.07.2018
uebungsblatt-11 Keine loesung-11 20.07.2018 27.07.2018

Hinweis: Ausgabe und Abgabe der Übungsblätter ist stets um 14:00 Uhr!

Richtlinien zur Abgabe der Übungsblätter

Laden sie Ihre theoretischen und praktischen Lösungen immer in Ihr SVN Repository in einen Unterordner mit dem Namen uebungsblatt-XY wobei XY die aktuelle Nummer des Übungsblattes angibt (mit führender Null falls die Nummer einstellig ist)! Ihre praktischen Lösungen müssen direkt in uebungsblatt-XY hochgeladen werden (und nicht in einen weiteren unterordner) damit Jenkins diese findet.

Laden Sie Ihre theoretischen Lösungen als (einzelnes) PDF in den entsprechenden Unterordner uebungsblatt-XY. Am liebsten sind uns theoretische Lösungen die mit Latex angefertigt wurden. Word oder andere Zeichensetzungsprogramme sind OK. Scans müssen gut lesbar sein, bitte vorher überprüfen!

Die hier verlinkte Übersicht beschreibt die typischen Schritte die sie für die Abgabe der praktischen Lösung durchführen sollen.


Zusätzliches Material

Alte Klausuren

Bisher haben wir die folgenden alten Klausuren für das Fach Info II.
Klausur Winter 2016/17,
Klausur Sommer 2016,
Klausur Winter 2014/15,
Klausur Sommer 2014

Lehrmaterial

  • Introduction to Algorithms (3rd edition); T. Cormen, C. Leiserson, R. Rivest, C. Stein; MIT Press, 2009
  • Algorithmen und Datenstrukturen (5. Auflage); T. Ottmann und P. Widmayer; Spektrum Akademischer Verlag, Heidelberg, 2012
  • Algorithms and Data Structures; K. Mehlhorn und P. Sanders; Springer, 2008, online verfügbar
  • Links zu Vorlesungen mit Aufzeichnungen auf MIT Courseware:
    Introduction to Algorithms 2005    und    Introduction to Algorithms 2011