Vorlesungsmitschriften Datenstrukturen und Algorithmen FS 2016

# 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](http://www.cadmo.ethz.ch/education/lectures/FS16/DA/index.html)). ### Grundlagen 1. [Einführung. Algorithmenentwurf. Güte von Algorithmen.](https://hackmd.io/s/4ym0Mqvig) 2. [Algorithmenentwurf durch einfache Induktion.](https://hackmd.io/s/E1fqN-Ksl) ### Suchen 3. [Suchen I: Binäre und lineare Suche. Das Auswahlproblem.](https://hackmd.io/s/4kZ5SfvTjx) (Zusatz: [Folien](http://www.cadmo.ethz.ch/education/lectures/FS16/DA/slides-DNA03-Suchen.pdf)) 4. [Suchen II: Hashing.](https://hackmd.io/s/N1YXYNz2g) (Zusatz: [Skript](http://www.cadmo.ethz.ch/education/lectures/FS16/DA/notes-DnA04-Hashing.pdf)) 5. [Sortieren I: Elementare Verfahren. Heapsort.](https://hackmd.io/s/NJgntYUFhg) 6. [Sortieren II: Mergesort, Quicksort.](https://hackmd.io/s/EJeA3TQcnx) 7. [Sortieren III: Untere Schranken. Radixsort. Wörterbücher I: Elementare Konzepte.](https://hackmd.io/s/EkgR9TVXpe) ### Datenstrukturen 8. [Wörterbücher II: Natürliche Suchbäume. AVL-Bäume.](https://hackmd.io/s/NybEN3iNpl) 9. [Amortisierte Analyse. Selbstanordnende Listen.](https://hackmd.io/s/4JC8vpsTl) ### Dynamische Programmierung 10. [Dynamische Programmierung I: Längste aufsteigende Teilfolge. Editierdistanz. Matrixkettenmultiplikation.](https://hackmd.io/s/VJqHLkRRe) 11. [Dynamische Programmierung II: Partitionierungsproblem, Subset-Sum, Rucksack, TSP](https://hackmd.io/s/NyVd8k00l) ### Fortgeschrittene Algorithmen und Themen 13. [Splay-Trees](https://hackmd.io/s/VylNlXD1W) To be continued... ### Geometrie 23. [Geometrie I: Konvexe Hüllen. Scanline-Algorithmen: Schnitt von orthogonalen Liniensegmenten.](https://hackmd.io/s/rJ-6ZzVQ) 24. [Geometrie II: Scanline-Algorithmen: Schnitt von beliebigen Liniensegmenten.](https://hackmd.io/s/rJ6Apx27) 25. [Geometrie III: Scanline-Algorithmen: Rechteckschnitt. Rangebaum, Segmentbaum. Intervallbaum. Prioritätssuchbaum.](https://hackmd.io/s/SyTfRl2X)