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.

Folien zur Vorlesung

Einführung

Sortier- und Selektionsalgorithmen

Dynamisches Pr ogrammieren

Greedy Algorithmen

Algorithmen auf Graphen

Hashing

Algebraische und zahlentheoretische Algorithmen

String Matching Algorithmen

Optimales Suchen in Bäumen

Übungen

Blatt	Vorlesungsstoff	Material / Links	Korrektur
Blatt 1	Asymptotische Notationen, Worst-Case und Average-Case-Analyse, nützliche Abschätzungen	Programmieraufgabe Notiz zu Aufgabe 1.4
Blatt 2	Rekursionsgleichungen, Master-Theorem, Selektionsalgorithmen	Programmieraufgabe
Blatt 3	Sortieralgorithmen: Quicksort, Heapsort, Mergesort	Programmieraufgabe Beispieleingabe und dazu passende Ausgabe
Blatt 4	Median-Bestimmung, Heap	Programmieraufgabe
Blatt 5	Dynamisches Programmieren	Programmieraufgabe Beispieleingabe und dazu passende Ausgabe
Blatt 6	Greedy-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 7	Repräsentation von Graphen, Algorithmen auf Graphen	Programmieraufgabe Beispieleingabe und dazu passende Ausgabe
Blatt 8	Netzwerkfluss, Hashing
Blatt 9	Hashing, FFT	Programmieraufgabe
Blatt 10	Euklid, Extended-Euklid, Chinesischer Restsatz
Blatt 11	String-Matching-Algorithmen: Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp
Blatt 12	Backtracking, Branch-and-Bound, Min-Max