MATH2014 Algorithms
SEMESTER 2 EXAMINATION 2018/19
1. Consider the following weighted undirected bipartite graph G = (V, E).
(a) Find a maximum-weight matching in the graph. Report, for each iteration of the algorithm, a copy of the graph G (in which the current matching is highlighted) and the corresponding auxiliary graph G0 (in which the augmenting path you have found is highlighted). [10 marks]
(b) State and justify the complexity of the algorithm. [10 marks]
2. Consider the following undirected graph.
(a) Find a minimum-cost spanning tree in it using the Jarnik-Prim-Dijkstra algorithm starting from node 1.
You can use either version of the algorithm (O(n
3
) or O(n
2
)). You can either draw as many copies of the graph as the number of iterations (indicating in each of them the values of the labels), or draw a single copy (showing how the labels are updated iteration by iteration as done in the problem class). Make sure that the set of edges contained in the tree you have found are highlighted in your drawings. [10 marks]
(b) Find a (not necessarily optimal) solution to the undirected metric TSP problem on the previous graph by applying the 2-approximate algorithm seen in the lectures. Draw the solution you have found and report its cost. [10 marks]
(c) Show that the algorithm you applied in point (b) yields a 2-approximate solution. [10 marks]
3. Consider the following two decision problems:
PARTITION: Given a positive integer nP , a set IP := {1, . . . , nP }, and a function wP : IP → R
+, is there some XP ⊆ IP such that wP (XP ) = 2/wP (IP)?
KNAPSACK-d: Given a positive integer nK, a set Ik := {1, . . . , nK}, two functions cK, wK : Ik → R
+, and two values LK, BK ∈ R
+, is there some XK ⊆ IK such that cK(XK) ≥ LK and wK(XK) ≤ BK?
(a) Show that PARTITION is in N P by showing that we can certify in polynomial time that a given a solution is indeed a solution to the problem. [4 marks]
(b) Show that KNAPSACK-d is in N P by showing that we can certify in polynomial time that a given solution is indeed a solution to the problem. [4 marks]
(c) Show that PARTITION reduces polynomially to KNAPSACK-d. [10 marks]
(d) Assuming now (as it is the case) that PARTITION is N P-complete, what does your polynomial reduction in part (c) imply on the complexity class of KNAPSACK-d? [2 marks]
4. (a) Solve the following instance of SAT with the partial enumeration algorithm:
(y1∨y2∨y3∨y4)∧(y1∨−y2)∧(−y1∨−y3)∧(−y1∨y3)∧(y4∨−y1)∧(−y2∨−y4)
[10 marks]
(b) Does the algorithm you applied run in polynomial time? Explain your answer. [5 marks]
5. Consider the following instance of the knapsack problem with capacity 7 and 5 items with the following values (v) and weights (w):
Solve the problem with dynamic programming.
[15 marks]