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.