Vorlesungsmitschriften Datenstrukturen und Algorithmen FS 2016

Die folgenden Kapitel entsprechen jeweils einer Vorlesung von 90 Minuten im Frühjahrssemester 2016 an der ETH Zürich (offizielle Vorlesungshomepage).

Grundlagen

1. Einführung. Algorithmenentwurf. Güte von Algorithmen.
2. Algorithmenentwurf durch einfache Induktion.

Suchen

3. Suchen I: Binäre und lineare Suche. Das Auswahlproblem. (Zusatz: Folien)
4. Suchen II: Hashing. (Zusatz: Skript)
5. Sortieren I: Elementare Verfahren. Heapsort.
6. Sortieren II: Mergesort, Quicksort.
7. Sortieren III: Untere Schranken. Radixsort. Wörterbücher I: Elementare Konzepte.

Datenstrukturen

8. Wörterbücher II: Natürliche Suchbäume. AVL-Bäume.
9. Amortisierte Analyse. Selbstanordnende Listen.

Dynamische Programmierung

10. Dynamische Programmierung I: Längste aufsteigende Teilfolge. Editierdistanz. Matrixkettenmultiplikation.
11. Dynamische Programmierung II: Partitionierungsproblem, Subset-Sum, Rucksack, TSP

Fortgeschrittene Algorithmen und Themen

13. Splay-Trees

To be continued…

Geometrie

23. Geometrie I: Konvexe Hüllen. Scanline-Algorithmen: Schnitt von orthogonalen Liniensegmenten.
24. Geometrie II: Scanline-Algorithmen: Schnitt von beliebigen Liniensegmenten.
25. Geometrie III: Scanline-Algorithmen: Rechteckschnitt. Rangebaum, Segmentbaum. Intervallbaum. Prioritätssuchbaum.