Algorithmen I

Inhalt

Diese Vorlesung wird mit einer Reihe von konkreten Algorithmen, Prinzipien fuer den Algorithmenentwurf und deren Komplexitaetsanalyse vertraut machen. Themen die behandelt werden sind z.B. Asymptotische-Notationen, Rekursionsgleichungen, Sortier- und Selektionsalgorithmen, Hashmethoden, Algorithmen auf Graphen, Dynamisches Programmieren, Greedy-Methoden, algebraische und zahlentheoretische Algorithmen.

Übungen

BlattVorlesungsstoffMaterial / LinksKorrektur
Blatt 1Asymptotische Notationen, Worst-Case und Average-Case-Analyse, nützliche Abschätzungen

Programmieraufgabe

Notiz zu Aufgabe 1.4

Blatt 2Rekursionsgleichungen, Master-Theorem, SelektionsalgorithmenProgrammieraufgabe
Blatt 3Sortieralgorithmen: Quicksort, Heapsort, Mergesort

Programmieraufgabe

Beispieleingabe und dazu passende Ausgabe

Blatt 4Median-Bestimmung, HeapProgrammieraufgabe
Blatt 5Dynamisches Programmieren

Programmieraufgabe

Beispieleingabe und dazu passende Ausgabe


Blatt 6Greedy-Algorithmen, Matroide

Programmieraufgabe

Beispieleingabe und dazu passende Ausgabe

Lösung zur Aufgabe 6.2

Die Punkte der Aufgabe 6.2 und 6.5 werden als Bonuspunkte behandelt.

Blatt 7Repräsentation von Graphen, Algorithmen auf Graphen

Programmieraufgabe

Beispieleingabe und dazu passende Ausgabe

Blatt 8Netzwerkfluss, Hashing
Blatt 9Hashing, FFTProgrammieraufgabe
Blatt 10Euklid, Extended-Euklid, Chinesischer Restsatz
Blatt 11String-Matching-Algorithmen: Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp
Blatt 12Backtracking, Branch-and-Bound, Min-Max

Programmieraufgaben

Die Programmieraufgabe werden an den Sphere Online Judge geschickt.

Literatur

  • T.H. Cormen, C.E. Leiserson, R.L. Rivest: Introduction to Algorithms. MIT Press, 1990.
  • U. Schöning: Algorithmik. Spektrum Akademischer Verlag, 2001.

Vorlesungszeiten

Montag 14:00 - 16:00
Mittwoch 12:00 - 14:00
jeweils in O27/H20

Übungsleiter

Simon Gog

Tutorien

Di 14:00-16:00 Uhr in O27/123
bei Adrian Kügel

Mi 14:00-16:00 Uhr in O27/3211
bei Julian Rüth

Mi 16:00-18:00 Uhr in O27/123
bei Adrian Kügel

Weitere Informationen

LSF-Eintrag