Algorithm Design

Exercise lab sessions given as a student assistant.

Topics (in German Language)

• Einleitung
• Laufzeitanalyse von Algorithmen
  • Die Groß-O-Notation und ihre Verwandten
  • Rekursionsgleichungen
  • Schnelle Polynom-Multiplikation
  • Strassens schnelle Matrix-Multiplikation (SMM)
• Greedy-Algorithmen und Scheduling-Probleme
  • Greedy-Strategien
  • Intervall-Scheduling
  • Scheduling mit mehreren Prozessoren
  • Scheduling mit Deadlines
  • Das Caching-Problem
  • Gewichtetes Intervall-Scheduling
  • Schwierige Scheduling-Probleme
  • Graph-Färbung
• Dynamische Programmierung
  • Matrizen-Produkte
  • Größte gemeinsame Teilsequenz
  • String-Alignment – Editierdistanz
  • Pseudo-Polynomialzeit
  • Weitere Partitionsprobleme
• Graphen und Wege-Probleme
  • Grundbegriffe der Graphentheorie
  • DFS: die Tiefensuche
  • Kürzeste Pfade in einem Graphen
    • Dijkstras Algorithmus für das SSSP-Problem
    • Distanzprobleme mit negativen Kantenkosten
    • Das APSP-Problem
  • Longest-Path, Hamiltonscher Kreis
  • Fluss-Probleme
    • Das MAXFLOW-MINCUT-Theorem
    • Implementierungen von General-MAXFLOW
  • 2-dimensionales Matching 3-dimensionales Matching und Überdeckungsprobleme
• Dynamische Datenstrukturen und abstrakte Datentypen
  • Prioritätswarteschlangen
  • Binominalbäume
  • B-Bäume
  • Suchbäume für höherdimensionale Universen
  • Tries
  • Union-Find
  • Hashing
    • Kollisionsbehandlung durch Verkettung der Überläufer
    • Offenes Hashing mit einer Sondierungsfolge
    • Uniformes Sondieren
    • Double-Hashing
    • Komplexere Sondierungsstrategien
    • Cuckoo-Hashing
    • Coalesced Hashing
    • Dynamisches Hashing
    • Bloom-Filter
• Online Probleme und Algorithmen
  • Das Skifahrer-Problem: Leihen oder Kaufen
  • Die kompetitive Rate
  • Das Listenzugriffsproblem LZP
  • Potentialfunktionen
  • Untere Schranken
  • Das k-Server-Problem
• Approximations-Algorithmen
  • Approximationsrate
  • Approximation von metrischem TSP
  • Approximation der Lastverteilung
  • Schranken für die Approximierbarkeitsrate
  • Min-SET-COVER und Marginalkosten
  • Approximation von Min-VERTEX-COVER
• Randomisierte Algorithmen
  • Gleichheitstest für Matrizen und Polynome
  • Fingerprinting für Strings
  • Stochastische lokale Suche: Random Walks, evolutionäre und genetische Algorithmen
• Diskrete Optimierungsprobleme
  • Cliquen, Kreise und Färbungen
  • Überdeckungs- und Packungsprobleme
  • Parametrisierung von Optimierungsproblemen