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).

Pseudocode-Beispiele zu Arrays, Listen, Stacks und Queues besprochen

Visualisierungen von vielen Datenstrukturen

Bei Listen immer auf den current-Zeiger aufpassen: L.movetofront(), um den Zeiger auf das head-Element (an den Start) zurück zu setzen.

Stack durch eine Liste simuliert: Klick!

Wikipedia (en.) - Tree Traversal

Topologische Sortierung

Breitensuche (BFS), Tiefensuche (DFS) auf Bäumen und allgemeinen Graphen: Wie hängt die Laufzeit von der verwendeten Datenstruktur ab?

Kantentypen: Baumkanten, Querkanten, Vorwärtskanten und Rückwärtskanten: Achtung: Baumkanten sind für BFS und DFS auf gerichteten und ungerichteten Graphen definiert. Die anderen Kantentypen sind laut Skript (Algo 4.9) nur für die Tiefensuche auf gerichteten Graphen definiert. Zusatzinfo: Bei der BFS auf ungerichteten Graphen können nur Baumkanten und “Nichtbaumkanten” unterschieden werden, wobei diese Nichtbaumkanten noch am ehesten als Querkanten bezeichnet werden könnten. Bei DFS auf ungerichteten Graphen wäre eine Unterscheidung von Vorwärts- und Rückwärtskanten nicht möglich. Obwohl es im Skript keine formale Definition für Rückwärtskanten der Tiefensuche auf ungerichteten Graphen gibt, sagt Satz 4.3, dass in diesem Fall nur Baum- und Rückwärtskanten existieren.

Heaps: Darstellung eines Heaps als Array. insert(x), delete_min(x) und change_priority(wo, p) an einem Beispiel gezeigt. Achtung, nicht verwechseln: Bei Min-Heaps führt change_priority(wo, p) bei einer Erhöhung der Priorität zu repair_down() zum kleinsten Kind von H[wo], bei einer Verringerung zu repair_up() Bei Max-Heaps ist es genau umgekehrt. Der Reparatur-Aufwand ist jeweils durch die Tiefe des Heaps beschränkt: O(log(n)), wenn der Heap n Elemente enthält.

Heaps können zum Sortieren verwendet werden, siehe Heapsort.