Begleitmaterial

Skript: gezipptes PS PDF. Das Skript ist auch im Skriptenverkauf erhältlich.

Eure Fragen zur Vorlesung/zum Skript DAP 2 und Ergänzungen

Nr.	Frage	Antwort PS-Datei	Antwort PDF-Datei
1	Wie erklären sich die Indextransformationen beim Maxsummenproblem?	PS	PDF
2	Wie bekommt man (beim Algorithmus mit Dynamischer Programmierung) die Intervallgrenzen für das "beste Intervall" beim Maxsummenproblem heraus?	PS	PDF
3	Wie sieht das Rahmenprogramm für gerichtetes DFS aus?	PS	PDF
4	"Gilt Satz 2.9.2 wirklich"?	PS	PDF
5	Was wird als Antwort erwartet auf die Frage Nr. 24 in der Fragenliste ?
	Die Frage ist missverständlich gestellt: Gemeint ist: Was ist die durchschnittliche Tiefe eines zufällig ausgewählten Datums, wenn der Baum mittels zufälliger Einfügereihenfolge entstanden ist? Antwort: siehe S.68 ff. Die durchschnittliche Tiefe des zufälligen Baumes zu analysieren ist schwieriger und ist in dieser Frage nicht gemeint. (Übrigens: Dass die Analyse etwas schwieriger ist, sieht man daran, dass erst 1986 ein Artikel die Durchschnittstiefe 4.311...*ln n <= 3 log n gezeigt hat: Siehe den Artikel von L. Devroye, "A note on the height of binary search trees," Journal of the ACM, vol. 33, pp. 489-498, 1986. Noch weiter geht die Analyse in http://www.geometrie.tuwien.ac.at/drmota/bstree.ps.gz )

Folien zu DAP2A-Vorlesungen (Dozent T. Hofmeister)

Für Folien zur DAP2B-Vorlesung siehe die Webseite zu DS 2001/02, diese enthält unter dem Stichwort "Foliensammlung" pro Kapitel abrufbare Folien.

Ergänzungen und Korrekturen zum Skript

Ergänzungen

Ein Beweis, dass n^k = o(2ⁿ) ist: PS PDF Alternativ: PS PDF
Ein alternativer Beweis zu Lemma 2.8.3 auf Seite 50 im Skript PS PDF
Ein anderer Beweis für die durchschnittliche Einfügezeit beim idealen Hashing: (aus der DAP2A-Vorl.) PS PDF
Eine andere Vorgehensweise zur Lösung der Rekursionsgleichung T(n)=... von Seite 68. (aus der DAP2A-Vorl.) PS PDF

Korrekturen (mit den Namen der Personen, die den Fehler gemeldet haben)
(diese Korrekturen beziehen sich auf das Skript mit der Aufschrift "Sommersemester 2002", das (siehe ganz oben) auch als Datei vorliegt.)

S. 16: in Zeile 14 sollte nach "von i" der Satz beendet werden (und somit der Text "und sei k der kleinste Index mit i_k=0." gestrichen werden.) (Marc Bachstein)
S. 35: Zeile -7 (oberhalb der Tabelle): "durchgeführt werden," statt "durchgeführt,". (Beate Bollig)
S. 51, Zeile 5: "Pfadkomprimierung" statt "Pfadkompromierung" (TH)
S. 52, Zeile 3 von "3.": "Hardwareentwurf" statt "Hardareentwurf". (TH)
S. 53, Zeile 3: "konstante Funktion" statt "Konstante Funktion" (TH)
S. 53, Zeile 12: "Hardwaremoduls" statt "Harwaremoduls". (Markus Müller-Olm)
S. 54, Zeile 15: "Knotenmenge" statt "Kontenmenge" (Markus Müller-Olm)
S. 56, Zeile 9: "OBDDs" statt "OBBDs" (Christian Andersen)
S. 64, Zeile 16: "Durchschnitt" statt "Durschnitt" (TH)
S. 64, Zeile 20: "geschlossenen" statt "geschlossen" (TH)
S. 68, Zeile 8 bis Zeile 5 von unten: "Rekursionsgleichung" statt "Rekursionsgleichnung" (3mal) (TH)
S. 68 unten: Hier könnte man erwähnen, dass T(0)=0 ist. (Beate Bollig)
S. 76, Abb. 3.4.5: In der rechten Struktur sollte der Zeiger, der momentan q heißt, p heißen. (IW)
S. 79, im rechten Baum des Bildes fehlt ein Zeiger auf den Knoten mit den Daten x,y.
S. 80 (Hinweis für uns selbst): Im Bild links oben könnte man x,y mehr zentrieren. (Beate Bollig)
S. 87, Zeile 6 unter der Abbildung 3.6.3: sollte bal(v)=0, bal(x)=-1, bal(w)=0 heißen (statt "bal(v)=0, bal(x)=-1, bal(x)=0") (TH)
S. 89, Zeile 11: ein "als der" zuviel (Beate Bollig)
S. 108, Satz 4.5.6: "wesentlichen Vergleichen" (Beate Bollig)
S. 108, Zeile 4 im Beweis von Satz 4.5.6: Die Anzahl an wesentlichen Vergleichen sollte
gaussunten log (gaussunten(log (n-1)))+1 heißen.
S. 126, zwei Zeilen vor der E(T)-Gleichung: Das Wort "innere" streichen! (Jens Schmidt)
S. 132, Zeile 12: "mit minimalem d_k-Wert" (Beate Bollig)
S. 133, Mitte: "der d- und N-Werte" sollte "der d- und V-Werte" heißen. (Beate Bollig)
S. 135, Zeile 14 von unten: "können. Dies " (Punkt fehlt) (Beate Bollig)
S. 136, Zeile 4 von unten: "des relaxierten Problems" (Beate Bollig)
S. 148, Zeile 2 und 5: Ersetze in diesen beiden Zeilen p^* durch p'. (Beate Bollig)
S. 150, Zeile 3 von unten: Kein Komma nach "Beträgen" (TH)
S. 151, Zeile 20: Kein " " vor dem Komma. (TH)
S. 151-52: Die Beschreibung der Spielbaumauswertung bzw. die Aktualisierung der s*-Werte enthielt einen kleinen Fehler: Hier die neue Version der Seiten 151-152: PS PDF (TH)