- Vorlesungsskript

1. Einführung
2. Suchen und Sortieren
   1. Binäre Suche
   2. Naive Sortieralgorithmen
   3. Mergesort
   4. Heapsort
   5. Quicksort
3. Asymptotische Laufzeitabschätzung: \(O\)- und \(\Omega\)-Notation
   1. Laufzeitabschätzhung: Numerische Experimente
   2. Laufzeitabschätzhung: Definitionen und Beweise
4. Datenstrukturen: Suchen, Einfügen, Löschen
   1. Hintergrund: Speicherplatz im Rechner
   2. Beschränkter Zugriff: Stacks und Queues
   3. Binäre Suchbäume
   4. Binäre Suchbäume mit Zufall: Treaps
   5. B-Bäume
   6. Rot-Schwarz-Bäume
   7. Hashing
5. Arithmetische Algorithmen
   1. Einfache Operationen
   2. Schnelle Matrixexponentiation
   3. Multiplikation
6. Graphenalgorithmen
   1. Beispiele, Definition, Repräsentierung
   2. Zusammenhang, Kreise finden, Tiefensuche, Breitensuche
   3. Gerichtete Graphen
   4. Topologisches Sortieren
   5. Starke Zusammenhangskomponenten
   6. Programmierprojekt: Längste Pfade in DAGs
7. Graphen mit Kantenkosten
   1. Dijkstras Algortithmus für kürzeste Pfade
   2. Kürzeste Pfade bei negativen Kosten: Bellman-Ford
   3. Minimale Spannbäume: Kruskals Algorithmus
   4. UnionDatenstruktur-Problem: Union-Find
   5. Union by Rank
   6. Union by Rank with Path Compression
8. Testataufgaben