Hier findet ihr meine Mitschrift zur Vorlesung Algorithmen und Programmierung 3 der FU Berlin.
Mehr Infos zur Veranstaltung sind auf der entsprechenden Veranstaltungshomepage zu finden.

1. Vorlesung – Die Analyse von Algorithmen wurde speziell am Beispiel von vier Sortieralgorithmen behandelt.
2. Vorlesung – Die Analyse wurde fortgesetzt. Heute ging es um Quicksort und die Wahl des Pivot-Elements. Zudem wurden die Algorithmen verglichen.
3. Vorlesung – Allgemeines zu Analyse und Algorithmen wurde gesagt. Z.B. wie man mathematisch Formalisieren kann und wie das mit dem Funktionswachstum ist.
4. Vorlesung – Herr Alt wurde vertreten und bei dem vorgestellten Quickselect und der Analyse hab ich nichtwirklich durchgeblickt (dementsprechend ist da meine Mitschrift). Um anderen Sortierverfahren wie Bucketsort ging es dann auch noch.
5. Vorlesung – Wir haben uns Radixsort angesehen und analysiert.
6. Vorlesung – In dem zweiten Kapitel der Vorlesung wird es um die Datenabstraktion und der Realisierung in Java gehen. Wir haben heute mit Listen angefangen.
7. Vorlesung – Es ging um verkettete und doppelt verkettete Listen.
8. Vorlesung – Wir haben einen Exkurs zu abstrakten Klassen und Interfaces gemacht.
9. Vorlesung – Der Exkurs ging weiter, jetzt über parametrische Polymorphie und Iteratoren.
10. Vorlesung – Nachdem wir intensivst uns nochmal mit Iteratoren und der for-Schleife beschäftigt haben, sind wir auf ein neuen ADT gekommen, auf die Datenstruktur Stack.
11. Vorlesung – Nach einem kleine Einschub über Typkonvertierung ging es weiter im Text mit Stacks.
12. Vorlesung – War nicht da.
13. Vorlesung – War nicht da. Ging wohl aber um Bäume bzw. Binärbäume
14. Vorlesung – Ein wenig noch über Binärbäume. Dann haben wir im Zuge von Prioritätswarteschlangen die Datenstruktur Heap angeschaut.
15. Vorlesung – Zu den Heaps haben wir uns eine Anwenung angeschaut – das Heapsort.
16. Vorlesung – Der Datentyp Wörterbuch wurde angefangen. Im Zuge dessen haben wir uns Hashing angeguckt mit allem drum und dran.
17. Vorlesung – Binärsuche und Skip-Listen als Datenstruktur für Wörterbücher wurdne besprochen.
18. Vorlesung – Weiter mit Wörterbüchern. Heute die Umsetzung mit Binären Suchbäumen.
19. Vorlesung – Immer noch bei Wörterbüchern. Heute dann die Umsetzung mit AVL-Bäumen.
20. Vorlesung – Und dann die Umsetzung mit (a,b)-Bäumen angefangen.
21. Vorlesung – Weiter mit (a,b)-Bäumen: Haben die Wörterbuchoperationen besprochen und analysiert.
22. Vorlesung – Abschließend für das Wörterbuchproblem haben wir uns noch die Datenstruktur des Tries vorgenommen.
23. Vorlesung – Heute ein neues Kapitel: Es geht jetzt um Graphenalgorithmen. Haben aber erstmal nur Graphen definiert etc.
24. Vorlesung – Wir haben uns den abstrakten Datentyp des Graphen mit seinen Operationen angesehen. Dann haben wir noch Tiefensuche als Graphtraversierung besprochen.
25. Vorlesung – Nach der Breitensuche ging es dann auch noch um das topologische Sortieren in azyklischen, gerichtetn Graphen.
26. Vorlesung – Wir haben uns das topologische Sortieren weiter angeschaut und sind dann über gegangen zu kürzesten Wegen und dem Dijkstra-Algorithmus.
27. Vorlesung – Herr Alt hat sich von dem guten Herrn Hoffmann vertreten lassen. Dieser hat uns dann noch ein paar Algorithmen auf Graphen vorgestellt, z.B. den von Floyd und Warshall, wie man die transitive Hülle bestimmt und die längsten Wege in azyklischen Graphen.
28. Vorlesung – Wir haben gelernt, wie man mit dem Algorithmus von Prim kürzeste Spannbäume berechnet.
29. Vorlesung – Wir haben uns mit schweren Problemen beschäftigt, bzw. eingeführt und rumdefiniert, was NP und P für Klassen sind.
30. Vorlesung – SAT und 3SAT wurde besprochen.
31. Vorlesung – Noch mehrere schwere Probleme besprochen, wie Clique, überdeckene Knotenmenge und so.
    So. Und das war’s dann auch mit ALP 3. An alle: Viel Erfolg bei der Klausur.

Download ALP 3 Mitschrift

Natürlich gibt es auch von Adrian wieder eine Mitschrift.