TU Wien:Algorithmics VU (Szeider)/Exam 2024-01-25

Not complete, I don't remember all of the exam unfortunately.

(10P) Planarity, A* and Randomized algorithms: Prove (non-)planarity of a given graph. What are the 2 major criteria we know about when a graph is monotonic? Is Quicksort a Monte Carlo or Las Vegas algorithm? What is the witness of the Miller-Rabin Primality Test? How many Miller-Rabin primality tests need to be performed to be sure that to some p the input is prime?

(5P) Network Flows and Matchings: A flow graph with capacities was given, detect which edges of the graph would decrease the maximum flow when one of the edges gets the capacity decreased by 1 unit.

(10P) Parameterized Algorithms:

(10P) Geometric Algorithms: Given Sweep-Line plot with all lines being connected to a single cycle (each vertex is of degree 2). Some lines cross. Give the sweep-line status at a given point in time. When is the first crossing detected? What happens at a specific point in time (own note: changes to the sweep-line status, which edges are tested for crossings))? Give an algorithm do detect all discs with a fixed radius in a 2d plot? Given hint: build a Voronoi diagram. Some checkbox questions: Is this true: face(edge(v)) = face(twin(next(edge(v))))? (kind of this example)

(10P) Linear and Mixed Integer Linear Programming: TSP problem, with costs. Find the best route using a MILP program. The parameter x_ijk gives the information if the salesman travels from city i to city j in iteration k. Hint, no further parameters necessary.

(5P) Structural Decompositions and Algorithms: