# TU Wien:Algorithmics VU (Raidl)/Prüfung 2019-01-14

Jump to navigation
Jump to search

- 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