Die Handout-Version der Folien und die Java-Sourcen werden regelmäßig aktualisiert bzw. erweitert.
Letzte Aktualisierung
18.8.2010 (Fehler auf Folie 237 korrigiert)Folien
im PDF-Format: 1-seitig, 2-seitig, 4-seitig, overlaysFehler in alten Folien:
- Auf Folie 21 muss es pop() anstelle von pull() heissen, und push() benötigt maximal 4 + 3n Ops.
- Auf Folie 51 fehlten in alten Versionen die Thetas in T(n) = Theta(n log(n)) ...
- Auf Folie 69: die Heap-Bedingung verlangt ein >=, nicht ein >.
- Auf Folie 77: Folie 77 ist nicht mehr eine Kopie von Folie 76, sondern erklärkt Schleifeninvarianten.
- Auf Folie 91: Im Basisfall der Induktion muss es n <= 2 heissen.
- Auf Folie 103: In der Overlay-Version ist jetzt Radix-Sort zu sehen.
- Auf Folie 109: Es ist r-l und nicht l-r.
- Auf Folie 113: quickSortMedian sollte sich selbst rekursiv aufrufen. Dementsprechend ändert sich auch die Laufzeit.
- Auf Folie 136 und 138: Falls der Knoten beim Suchen nicht den gesuchten Schlüssel hat, ist er nicht notwendiger Weise ein Blatt.
- Auf Folie 159: es werden die Werte 3,5,4 eingefügt, nicht die Werte 5,3,4. Dementsprechend ändern sich auch die Werte im Baum. (Die alte Version hätte einen Baum erzeugt, wo die Wurzel ein linkes Kind hat, und nicht ein rechtes.)
- Auf Folie 171: Der 1. und 5. Fall haben 66,6 Prozent binäre Knoten, nicht 60.
- Auf Folie 237: Die Formel für das quadratische Sondieren ist ... * (-1)i+1.
- Auf Folie 248: Es muss k,k' in K heissen, und nicht in H.
- Auf Folie 251: Der Zahlenraum ist {0,..,p-1}.
- Auf Folie 314: Es muss der Datentyp HashMap<Integer,Pair<HashSet<Integer>,HashSet<Integer>>> sein.
- Auf Folie 318: Es muss ord(v0) <= ord(vk) - k heissen.
- Auf Folie 330: Es ist (w,u) in E und nicht (u,w).
- Auf Folie 338: Es ist d[u] < d[v] < f[v] < f[u].
- Folien 341 und 342: Der vorgestellte Algorithmus ist von Kosaraju, nicht von Tarjan