Die Klausureinsicht zu der Vorlesung "Algorithmen und Datenstrukturen" findet am 10. November 2016 von 09:00 bis 12:00 Uhr im Raum Z 1050 (Zusebau) statt.

Die Klausurergebnisse von "Algorithmen und Datenstrukturen" sind im System eingetragen und über die Thoska Karte abrufbar.

Die Ergebnisse der Bonusklausur "Algorithmen und Datenstrukturen" können Sie in der Übung bzw. im Sekretariat des Institut TI erfragen.

Wenn Sie Gefallen an den in dieser Vorlesung besprochenen Themen gefunden haben, empfehlen wir einen Blick in die Themenliste für das Proseminar "Algorithmen und Komplexität" für Bachelorstudierende im kommenden Wintersemester.

Evaluation der Übung (Stefan Walzer)

Zur Klausurvorbereitung beachten Sie bitte folgende alte Klausuren:

Algorithmen und Datenstrukturen (neu)

• Klausur SS2015

Algorithmen und Datenstrukturen (alt)

• Klausur SS2014
• Klausur SS2013 (nur AuD)
  
• Klausur SS2012
• Klausur SS2011
• Klausur SS2010

Effiziente Algorithmen (mündliche Prüfung)

• Fragenkatalog mit Beispielfragen

Vorlesung:

Donnerstag, 15:00 - 16:30 Uhr, HU-Hs, Prof. M. Dietzfelbinger

Freitag, 13:00 - 14:30 Uhr, HU-Hs

Übungen:

Dienstag, 09:00 - 10:30 Uhr, Sr K 2026, C. Mattern

Mittwoch, 09:00 - 10:30 Uhr, Sr HU 202,  C. Mattern

Mittwoch, 11:00 -12:30 Uhr, Sr HU 210,  C. Mattern

Praktikum:

Donnerstag (G), 17:00 Uhr, LdV-Hs 2,  C. Mattern

• Spezifikation von Berechnungsproblemen und von abstrakten Datentypen
• Analyse von Algorithmen (Korrektheitsbeweise für iterative und rekursive Verfahren, Laufzeitbegriff, O-Notation, Laufzeitanalyse, Methoden für die Analyse von Laufzeit und Korrektheit)
• Grundlegende Datenstrukturen (Listen, Stacks, Queues, Bäume)
• Binäre Suchbäume, Mehrwegsuchbäume, balancierte Suchbäume (AVL- und/oder Rot-Schwarz-Bäume, B-Bäume)
• Einfache Hashverfahren, universelles Hashing
• Sortierverfahren: Quicksort, Heapsort, Mergesort, Radixsort. Untere Schranke für Sortieren
• Priority Queues mit der Implementierung als Binärheaps

2.Teil:

• Divide-and-Conquer: Multiplikation ganzer Zahlen, Matrixmultiplikation, Master-Theorem, Quickselect, Schnelle Fourier-Transformation
• Grundbegriffe der Graphentheorie, Datenstrukturen für Graphen (Adjazenzmatrix, Kantenliste, Adjazenzlisten, Adjazenzarrays). Durchmustern von Graphen: Breitensuche, Tiefensuche, Zusammenhangskomponenten, Entdecken von Kreisen, topologische Sortierung, starke Zusammenhangskomponenten
• Greedy-Strategie: Teilbares Rucksackproblem, Schedulingprobleme, Huffman-Kodierung, Kürzeste Wege 1: Algorithmus von Dijkstra, Minimale Spannbäume (Algorithmus von Kruskal, Union-Find), Algorithmus von Jarnik/Prim, randomisierter Algorithmus für minimale Schnitte
• Dynamische Programmierung: Editierdistanz, Ganzzahliges Rucksackproblem (mit/ohne Wiederholungen), Kürzeste Wege 2: Algorithmus von Floyd-Warshall, Kürzeste Wege 3: Algorithmus von Bellman-Ford, das Problem des Handlungsreisenden

Neben den Vorlesungsfolien empfehlen wir folgende Literatur:

• Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, 3rd Edition, MIT Press, 2009 (auch deutsche Ausgabe verfügbar)
• Mehlhorn, Sanders: Algorithms and Data Structures, The Basic Toolbox, Springer-Verlag, 2008
• Ottmann und Widmayer: Algorithmen und Datenstrukturen, 5. Auflage, Spektrum Akad. Verlag 2012
• Sedgewick: Algorithmen, Addison-Wesley, 2002

Für den zweiten Teil der Vorlesung empfehlen wir weiterhin:

• Dasgupta, Papadimitriou, Vazirani, Algorithms, McGraw-Hill, 2007
• Kleinberg, Tardos, Algorithm Design, Pearson Education, 2005
• Schöning, Algorithmik, Spektrum Akademischer Verlag, 2001
• Sedgewick, Algorithms, Part 5: Graph Algorithms, Addison-Wesley, 2003

Elementare Einführungen:

• Güting, Dieker: Datenstrukturen und Algorithmen, B.G. Teubner Verlag, 2004
• Weicker, Weicker: Algorithmen und Datenstrukturen, Springer-Vieweg, 2013