TU Wien:Algorithmics VU (Szeider)/Exam 2023-01-26

• 5 point question: two questions about heuristics of A*, about monotonicity and a heuristic for Sudoku
• Provide an FPT algorithm for a problem where every vertex has one of two colors, can you delete k neighbours so it's a valid coloring (no two vertices of the same color are neighbours). Additional questions: which parameter is missing in the definition of a problem, how can you get an FPT algorithm if you have a kernelization.
• 5 point question: A MILP was given, variables were defined, constraints were described in text and had to be written as formulas.
• Show the treewidth of a given graph by providing lower and upper bound. Write an MSO formula for MINIMUM 3-DOMINATING SET.
• Determine a flow. Draw circulation for matrix rounding of a given matrix.
• Sweep line algorithm to find sheep outside of fences. The algorithm was provided, for some lines the correct ones had to be selected. Some additional questions had to be answered eg if the fences wouldn't be convex - would the algorithm still work? If not how can you fix it.