Website der Vorlesung: http://www.thi.informatik.uni-frankfurt.de/lehre/ds/sose15.de

Logbuch der Vorlesung: http://www.thi.informatik.uni-frankfurt.de/lehre/ds/sose15/logbuch/

Literatursuche Uni-Bibliothek: https://www.ub.uni-frankfurt.de

Username und Passwort (wenn noch nicht geändert) http://www.ub.uni-frankfurt.de/benutzung/passwort.html

Survivalguide Bachelor, 2. Auflage, 2014 als PDF verfügbar

Pomodoro-Technik

Vokabelliste anfertigen, Übersicht verschaffen, Lernwegweiser erstellen (wie etwa hier), Prioritäten setzen

“Lernen heißt verstehen, nicht auswendig lernen!”

Online-Whiteboard: Twiddla

Übersicht der Übungsaufgaben

Data Structure Visualizations

Gnarley Trees: Data Structure Visualizations (Java Application)

Hausaufgaben (mit Lösungen und Tipps) können von jedem auch ohne Wiki-Account bearbeitet, ergänzt und verbessert werden. Achtung: Dort können auch neue und weiterführende Aufgaben stehen, die hier bei den Vorbereitungshausaufgaben nicht aufgeführt sind.

Themen, die wir nur ganz schnell angeschnitten haben, werden hier auf der Website ergänzt. Ich bemühe mich um besseres Zeitmanagement, damit das nicht mehr so nötig sein wird.

$f = O(g)$ heißt “f ist asymptotisch $\leq$ g” (bzw. f wächst höchstens so schnell wie g).

$f = \Omega(g)$ heißt “f ist asymptotisch $\geq$ g” (bzw. f wächst mindestens so schnell wie g).

$f = \Theta(g)$ heißt “f und g wachsen asymptotisch gleich schnell”

$f = o(g)$ heißt $f << g$ bzw. $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$

$f = \omega(g)$ heißt $f >> g$ bzw. $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$

Laufzeit-Hierarchie von $\Theta(1)$ bis $\Theta(n^n)$

$n! = o(n^n)$, aber $\log(n!) = \Theta(\log(n^n)) = \Theta(n \log(n))$. Achtung: Beim Logarithmieren und Exponenzieren können sich die Hierarchie-Beziehungen ändern! Das seht ihr auch an $n/2 = \Theta(n)$, aber $2^{n/2} = o(2^n)$.

Master-Theorem: nicht besprochen. Stattdessen: Rekursionsgleichung aufstellen, ein paar Mal einsetzen und dann eine geschlossene Formel “raten”. Streng genommen müsstet ihr diese geschlossene Formel noch per vollständiger Induktion beweisen. Für die Klausur reicht sehr wahrscheinlich die Angabe der Lösung. Rekursionsgleichungen werden wir immer dann üben, wenn wir rekursiv programmieren.

Zu Arrays, Listen, Stacks und Queues findet ihr Pseudocodes bei den Hausaufgaben (mit Lösungen und Tipps).

(2,3)-Bäume, Achtung: Beim Löschen von Schlüsseln verhält sich die Animation etwas anders als die Implementierung aus der DS-Vorlesung. Einfügen funktioniert aber gleich.