TU Wien:Algorithmics VU (Raidl)/Prüfung 2020-01-20

1. Berechne Max Flow & Min Cut. Zeichne Residual Graph. Markiere Edges, die, wenn die Capacity um 1 erniedrigt bzw. Erhöht wird, die Max-Flow erniedrigen bzw. Erhöhen (wenn alle anderen Edges gleich bleiben)
2. Berechne Miller-Rabin Test für n=19 & a=5. Was sagt das Ergebnis aus? Ist der Algorithmus Monte Carlo + Begründung?
3. FPT
   1. 1. Designe FPT Algorithmus für Problem. Graph heißt 4 Circle, wenn er einen Kreis aus 4 Vertices als Induced Subgraph beinhaltet. Er heißt 3 Circle, wenn er einen Kreis aus 3 Punkten beinhaltet. Kann man maximal k Edges hinzufügen, um aus dem 4 Circle Graph einen 3 Circle zu machen? + Runtime Estimate
   2. 4 Verschiedene Probleme aus Slides waren (teilweise) angegeben. Füge die fehlenden Informationen hinzu bzw. Erkenn, falls es das Problem nicht geben kann:
      1. Problem, das nicht FPT ist
      2. Problem, das nicht auf Graphen basiert
      3. Problem mit folgender Fragestellung: Does there exist a Hamiltonian cycle in G? (Name + Parameter hinzufügen)
      4. Problem, das in FPT ist, aber keinen Kernel hat
4. Ist Independent Dominating Set (Dominating Set, das auch Independent Set ist) FPT paramerized By treewidth?
5. MILP Problem: Projekte sollen gewählt werden pi i={1,...8} mit Gewinn gi. Maximiere Gewinn. Restrictions (gab ca. 8):
   1. Min 3 Projekte, Max 7
   2. Projekt 3 und 8 schließen sich aus
   3. Min 2 Projekte aus {1,2,3,4} oder min. 1 Projekt aus {5,6,7,8}
   4. Wenn 3 gewählt wird, muss auch 7 gewählt werden
   5. Etc
6. Graphen
   1. Delaunay Graph zeichnen.
   2. Beweis bzgl. Delauney Edges und SED
   3. Design Algorithmus, der für Punkt P alle Punkte in k euclidean distance aus einem (2d) Range tree aus gibt. Warum ist für diesen Algorithmus der Range Tree nicht sinnvoll (begründe mittels worst case).