Algorithmen Probleme

• Sortieren
  ⇒ Merge Sort O(n log n)

• Interval Scheduling Problem
  ⇒ Greedy Algorithmus O(n)

• Gewichtetes Intervall Sceduling Problem
  ⇒ Dynamische Programmierung Tabularization O(n log n)

• Rucksackproblem normal
  ⇒ Greedy Algorithmus O(n)

• Rucksackproblem gewichtet
  ⇒ Dynamische Programmierung Tabularization O(n log n)

• Levenshtein Distanz für Strings
  ⇒ Dynamische Programmierung 2D Tabularization $O(n\ast m)n=|s_{1|}m=|s_2|$

Graphen

• eulerisch (hat eine Eulertour)
  ⇒ Hierholzer Algrithmus O(n + m)

• Hamilton Kreis
  ⇒ NP-vollständig

• minimal aufspannender Baum
  ⇒ Algorithmus von Kruskal O(m log n)

• günstigsten Weg von einem Knoten zu einem anderen
  ⇒ Dijkstra O((m + n) log n)

• günstigster Weg in Graph mit negativen Kanten
  ⇒ Bellmann-Ford Algorithmus O(n * m)

• günstigster Weg von jedem Knoten zu jedem anderen Knoten
  ⇒ Floyd-Warshall Algorithmus O( n³ )

• Augmentierende Pfade in bipartiten Graphen
  ⇒ Breiten Suche O( n² )

• Max-Fluss Problem
  ⇒ Max Flow Problem O( m * M ) M = max Flusswert

• allgemeines Matching
  ⇒ Max-Fluss Problem

• Perfektes Matching Problem
  ⇒ Heiratssatz