TU Wien:Algorithmics VU (Szeider)/Exam 2019-01-14

• Draw residual graph + find augmenting path + find min-cuts + matrix rounding + MC questions
• You have P parking spaces and K cars with variable lengths, each parking space has max L space but x parking spaces may violate this condition. Write a MILP minimizing the difference between the "shortest" and "longest" parking space
• You have a graph with red and blue nodes, parameterized with k. Can you find a set of max size k such that no blue vertex has more than 4 red neighbours? Design a FPT algorithm to answer this question
• Show that Max-Clique is parameterized by treewidth (Hint: use MSO), Determine tw of a given graph + MC questions
• Do an A* search on a given graph, is the path optimal, is the heuristic (manhattan distance) monotonic + MC questions
• A rectangle filled with lines, determine which scanline from [above|right|bottom|left] will find the intersection first + MC questions