====== Effiziente Kombinatorische Algorithmen ======


DFS:
  * Was ist eine nichttrivale Eigenschaft, die wir auf ungerichteten Graphen mit Tiefensuche berechnet haben? 
  * Was ist eine zweifache ZHK?
  * Definiere Artikulationspunkt.
  * Was ist der Superstrukturgraph? Eigenschaften?
  * Wie berechnen wir 2ZK genau?
  * Was haben Rückkanten im Tiefensuchbaum für Eigenschaften?
  * Warum funktioniert der Algorithmus?
  * Wie ist die Laufzeit?

VC:
  * Es wurde das Kapitel "parametrisierte Komplexität" kurz erläutert. Wie war die Überschrift dieses Kapitels?
  * Was haben wir für ein Beispiel behandelt?
  * Definiere Vertex Cover.
  * Wann nennen wir einen Algorithmus parametrisiert?
  * Wie sah der parametrisierte Algorithmus aus der Vorlesung zu Vertex Cover aus? (Dabei wurden noch die beiden Lemmata aus der Vorlesung gefordert)
  * Wie ist die Laufzeit?
  * Wie können wir nun aus dem Algorithmus für das Entscheidungsproblem einen Algorithmus für das Optimierungsproblem machen?
  * Was ist die Worst-Case Laufzeit dieses Algorithmus? Dafür sollte ich die beiden Laufzeitgraphen von Brute-Force und parametrisiertem Algorithmus hinzeichen. Der Schnittpunkt (Break-Even-Point), der gleichzeitig Maximum ist, ist dabei kleiner als die beiden Maxima der Algorithmen selbst.

DP:
  * Wir haben das TSP betrachtet. Definieren Sie dieses.
  * Wie können wir dieses Problem schneller als mit Laufzeit (n/e)^n lösen?
  * Warum funktionert das?
  * Wie ist die Laufzeit?