Grundlagen: Algorithmen und Datenstrukturen

Dozent: Prof. Dr. H. Seidl Ort/Zeit: MI HS 1 / Di 12:00 - 13:30 und Do 12:15 - 13:00 ModulNummer: IN0007 Beschreibung:     Es werden grundlegende Algorithmen und Datenstrukturen und ihre Anwendung erklärt. Die Komplexität der zugehörigen Operationen und von (moderat komplexen) Algorithmen werden analysiert. Übung zu GAD Übung zu "Grundlagen: Algorithmen und Datenstrukturen"

Inhalt:

• Grundlagen der Komplexitätsanalyse
• Komplexität der Operationen von Listen, Stacks und Schlangen
• generische Kollektions-Datenstrukturen (Java collections)
• binäre Bäume und Algorithmen (preorder, inorder, postorder)
• binäre Suchbäume und balancierte Suchbäume (AVL, B-Bäume)
• Priority Queue
• Hashing inklusive erweiterbarem Hashing für Hintergrundspeicher
• Sortieren (Bubble-, Heap- und Quick-Sort) und sortierbasierte Algorithmen (Mengendurchschnitt)
• externes Sortieren
• Hash-basierte Algorithmen (Mengendurchschnitt)
• Graph-Darstellung und Graphalgorithmen (topolog. Sortieren, kürzeste Wege, Kruskal, DFS, BFS, TSP)
• Pattern Matching, Datenkompression (Huffman, Lempel-Ziv)
  

Klausur:

• Datum: Samstag 25. Juli 2009
• Anmeldung: TUMonline
• Merkblatt zur Klausur (Version 3: Hörsaaleinteilung korrigiert; Version 2: Kapitel 11 ist auch klausurrelevant!)
• Einsicht: am Montag, dem 24.08.09, um 14 Uhr (bis mindestens 15 Uhr). MI HS 1
  
• Notenschlüssel (ohne Bonus):

Klausur im Wintersemester:

• Datum: Samstag 10. Oktober 2009
• Uhrzeit: 9:00 - 11:00
• Anmeldung: TUMonline
• Einsicht: am Montag, dem 02.11.09, um 13 Uhr (bis mindestens 14 Uhr). Raum: 02.07.034
  
• Notenschlüssel (ohne Bonus):

Aufzeichnungen:

Folien:

Korrekturen:

Literaturvorschläge:

• K. Mehlhorn, P. Sanders.
  Algorithms and Data Structures - The Basic Toolbox.
  Springer, May 2008.
• Michael T. Goodrich, Roberto Tamassia.
  Algorithm Design: Foundations, Analysis, and Internet Examples.
  John Wiley & Sons, Inc., Hoboken, NJ, 2002.
• Volker Heun.
  Grundlegende Algorithmen: Einführung in den Entwurf und die Analyse effizienter Algorithmen.
  2. Auflage, Vieweg, Braunschweig-Wiesbaden, 2003.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
  Introduction to Algorithms.
  2. Auflage, MIT Press, Cambridge, MA, 2001.
• Jon Kleinberg, Eva Tardos.
  Algorithm Design.
  Pearson Education, Boston, MA, 2005.
• Uwe Schöning.
  Algorithmik.
  Spektrum Akademischer Verlag, Heidelberg, 2001.
• Robert Sedgewick.
  Algorithmen in Java. Teil 1-4.
  3., überarbeitete Auflage, Pearson Education, München, 2003.

Zur Diskussion von Entwurfsprinzipien implementierbarer Algorithmen:

• Karsten Weihe.
  A Software Engineering Perspective on Algorithmics.
  ACM Computing Surveys, 33(1), 89-134, 2001.