| Datum |
Stoff |
Material |
|
17.04.07 |
Insertion sort | 2.1 |
|---|
| 20.04.07 | Merge Sort | 2.3.1 |
| Asymptotik mit O,Omega,Theta | 3.1 (erste Hälfte) |
| Hauptsatz der Master Methode | 4.3 |
| 27.04.07 | Beweis des Hauptsatzes fuer exakte Potenzen | 4.4.1 |
|---|
| Dabei Wdh und Anwendung der O-Notation. |
| Definition von klein-o und klein-omega |
| O-Notation bei Induktionsbeweisen | 4.1 | |
| 04.05.07 | Heapsort mit Analyse | 6.1-6.4 |
| 08.05.07 | Prioritaetsschlange mit Heaps | 6.5 |
|---|
| Quicksort | 7.1-7.3 |
|---|
| 11.05.07 | Analyse von Randomised Quicksort. Bemerkung: Um die Probleme (waehrend des Vortrags)
mit 0*ln(0) zu vermeiden, bedenkt man, dass T(0) konstant ist und dem Theta(n) zugeschlagen werden kann. Siehe Folie 50. | Aufgabe 7-2 von [Cormen] |
|---|
| Untere Schranke fuer vergleichsbasiertes Sortieren.
| 8.1 |
|---|
| Maximum und Minimum | 9.1 |
| 15.05.07 | Untere Schranke an Vergleichskomplexitaet von Maximum-und-Minimum mit Adversary-Argument. | Aufgabe 9.1-2 von [Cormen], siehe auch Folien 60,61.
|
|---|
Weitere Adversary-Argumente finden sich in Mike Paterson. Progress in Selection. Scandinavian Workshop on Algorithm Theory. 1997. (Nur fuer Interessierte; kein Pruefungsstoff!!).
| | Selektionsaufgabe, noch ohne Analyse.
| 9.2, 9.3 (erste Haelfte) |
|---|
| 18.05.07 | Analyse des nichtrandomisierten Linearzeit-Selektionsalgorithmus. | 9.3 |
|---|
Binaere Suchbaeume (BST), Suchen, Einf, Loesch. Nur kursorisch, da Wdh von Info II | III-Einf, 12.1-3 |
| AVL-Baeume (Wdh), Rot-Schwarz-Baeume, Def, Bsp.
| 13.1 |
|---|
| 22.05.07 | Rot-Schwarz-Baeume: Bzhg Knotenzahl Hoehe | Lemma 13.1 |
|---|
Rot-Schwarz-Baeume, Bzhg zu
2-3-4-Baeumen | |
| Rot-Schwarz-Baeume: Einfuegen und Loeschen. Motiviert durch 2-3-4-Baeume.
| 13.3, 13.4 |
|---|
| 25.05.07 | Rot-Schwarz-Baeume: Loeschen Wdh u Bsp | 13.4 |
|---|
Rot-Schwarz-Baeume, Komplexitaet, Zusammenfassung
2-3-4-Baeumen | 13.4 Analysis |
| B-Baeume. Detailgrad nur wie Folien 84-89 .
| 18 |
|---|
| 01.06.07 | Hashtabellen. Direkte Adressierung, Kollisionsaufloesung durch Verkettung, Divisionsmethode, Multiplikationsmethode. | Kap. 11 bis einschl.11.3.2 |
|---|
| 08.06.07 | Hashtabellen. Offene Adressierung, Lineares u Quadratisches Sondieren, Uniform Hashing, probabilistische Analyse | Kap. 11.4 |
|---|
| 12.06.07 | Kap IV Allgemeine Entwurfs- und Optimierungsmethoden, Einfuehrung. | Teil IV |
|---|
Greedy Algorithmen (wir weichen hier etwas vom Buch ab, siehe daher auch Folien .): Einfaches Auswahlproblem, Steinitzscher Austauschsatz, Def. Praefixbedingung
| 16.1, 16.3 erste zwei Abschnitte. |
| 16.06.07 | Grafische Illustration des Greedy Algorithmus fuer das Auswahlproblem der letzten Woche, Deutung des Korrektheitsbeweises als Argumentationsstrategie gegenueber einem Zweifler. | |
|---|
Praefixcodes, Huffman Algorithmus, Beispiele. Korrektheitsbeweis begonnen, aber nicht ganz fertig.
| 16.3 |
| 19.06.07 | Korrektheitsbeweis Huffman | 16.3 |
|---|
Dynamische Programmierung: Generelle Vorgehensweise, Beispiele Fibonacci, Matrix-Kettenmultiplikation.
| Kap 15 Einf., 15.2 |
| 22.06.07 | Laengste gem. Teilfolge als Bsp zur dyn Prog | 15.4 |
|---|
Amortisierte Komplexitaet. Bsp Binaerzaehler, Aggregatmethode
| 17.1 |
| 29.06.07 | Amortisierte Komplexitaet: Aggregatmethode, Bankkontomethode, Potenzialmethode | 17.1-3 |
|---|
Union-Find: Problemstellung (nur ganz kurz)
| 21.1e |
| 03.07.07 | Union-Find, Union-By-Rank, Pfadkompression | 21.3 |
|---|
Schranke O(m log n) fuer Union-By-Rank, Schranke O(m log* n) (amortisiert) mit Pfadkompression. Beweis naechstes Mal. Siehe auch diese Folien.
| Exercise 21.4-4 |
| 06.07.07 | Beweis der O(m log*(n)) Schranke fuer Union - Find | Diese Folien. Siehe auch 21.4 |
|---|
Begriffsklaerung Backtracking, Branch and Bound, Iterative Deepening
| |
| 10.07.07 | Graphalgorithmen. Repraesentation von Graphen, Breitensuche, Tiefensuche | 22.1-22.3 |
|---|
| 13.07.07 | Topologische Sortierung, SCCs | 22.4 22.5 |
|---|
Minimale Spannbaeume. Def, Anw., Kruskals Algorithmus. Algorithmus von Prim wurde nicht behandelt.
| 23 |
| 17.07.07 | Kuerzeste Wege: Dijkstra Algorithmus | 24 Einf, 24.3 |
|---|
Algorithmus von Bellman-Ford
| 24.1 |
