COM2109/COM2001/COM21001 1. a) Which of the following statements are true; which ones are false? (i) Let X be an NP-complete problem and let Y be an NP-hard problem. Then there is a polynomial-time reduction from X to Y . (ii) If P 6=NP, then there is no polynomial-time algorithm for the Hamiltonian Cycle problem. (iii) Let X be an NP-complete problem and let Y be an NP-hard problem. Then there is a polynomial-time reduction from Y to X. (iv) If there is a polynomial-time algorithm for the Satisfiability problem, then there is a polynomial-time algorithm for the Knapsack problem. [20%] b) (i) Write a function OptimumKnapsack in Pseudo-code that, given an instance I of knapsack (having n items with values v1, . . . , vn, weights w1, . . . , wn, and capacity C), finds the maximum total value V such that I has a solution of value V . The function is required to run in polynomial-time but can make calls to a function DecideKnapsack(I, V ) that, given an instance I of Knapsack and a total value V , returns true if I has a solution of total value at least V and otherwise false. Hint: You can use the function BinarySearch(l, u) that, given integers l and u uses binary search to find the largest value V between l and u such that DecideKnapsack(I, V ) returns true. [10%] (ii) Argue why the following “solution” to the above problem is not correct! OptimumKnapsack( I ) V=0 while DecideKnapsack( I, V ) V V + 1 return V 1 Hint: The function returns the correct value but is not correct for a di↵erent reason. [10%] QUESTION CONTINUED ON THE NEXT PAGE COM2109/COM2001/COM21001 3 TURN OVER COM2109/COM2001/COM21001 c) Consider the following problem: Magic Set Instance: A set S, a family (set) M ✓ 2S of subsets of S and an integer k. Parameter : k. Question: Does S contain a magic set D ✓ S containing at most k elements? A magic set is a set D ✓ S such that D enchants all sets in M, i.e., M \D 6= ; for every set M 2M. Example: Let S = {1, 2, 3, 4, 5} and let M consists of the sets M1 = {1, 2, 3}, M2 = {4, 5}, and M3 = {3, 4}. Then: • the elements 1 and 2 enchant only the set M1, • the element 3 enchants the sets M1 and M3 (but not M2), • the element 4 enchants the sets M2 and M3 (but not M1), • the element 5 enchants only the set F2, • the set {3, 4} is a magic set for the instance of size 2, and there is no magic set of size 1. (i) Write a function FindMagicSet in Pseudo-code that, given an instance I = (S,M, k) of the Magic Set problem finds a magic set for I of size at most k (you can assume that I is a Yes-instance). The function is required to run in polynomial-time but can make calls to the function DecideMagicSet that, given an instance of the Magic Set problem returns true if the instance is a Yes-instance and false otherwise. [20%] Hint: Use the notation M[u] to denote the set of all sets in M that contain u. (ii) Show that the Magic Set problem is in NP. Hint: A potential solution/witness to the Magic Set problem is a subset of S of size at most k. [20%] (iii) Show that the Magic Set problem is in NP-hard. Hint: Use a polynomial-time reduction from Vertex Cover. [20%] COM2109/COM2001/COM21001 4 CONTINUED COM2109/COM2001/COM21001 2. Consider the graph G illustrated in the following picture. 1 23 4 5 7 6 8 9 10 a) Calculate a lower bound for the size of a vertex cover of G obtained from a maximal matching and specify both the maximal matching and the obtained lower bound. [10%] b) Calculate an upper bound for the size of a vertex cover (and the corresponding ver- tex cover) using the greedy algorithm (based on maximum degree) from the lecture. Resolve ties (i.e., if there is more than one vertex with the same degree) using the natural order on the natural numbers (or lexicographical order). Specify the obtained vertex cover and its size. [10%] QUESTION CONTINUED ON THE NEXT PAGE COM2109/COM2001/COM21001 5 TURN OVER COM2109/COM2001/COM21001 c) Apply the branch-and-bound algorithm without degree-two rule for the Vertex Cover problem that was presented in the lecture (recall that the lower bound is computed using a maximal matching and the upper bound is computed using a greedy algorithm that always chooses a vertex of maximum degree) to G using the depth- first strategy (recursing first on the node corresponding to the chosen vertex and then recursing on the node corresponding to the neighbours of the chosen vertex) for the choice of the next subproblem/subinstance. Draw a possible branch-and-bound tree similar to the template given below. Provide the following for each node of the branch-and-bound tree: • a number corresponding to the step of the algorithm at which the node is con- sidered, • the remaining graph G0, • the current (already fixed) partial vertex cover (C), • the value of the (local) lower bound L together with the maximal matching M used to compute the lower bound, • the value of the (local) upper bound U together with the vertex cover V (on the remaining graph G0) used to compute the upper bound. Alternatively specify that the node does not correspond to a valid partial solution and state the reason why this is the case. Also specify the branching decision that an edge corresponds to at each edge of the branch-and-bound tree. Always (i.e., for the greedy upper bound algorithm and for the choice of the next vertex to branch on), resolve ties (i.e., more than one vertex with the same degree) using the natural order on the natural numbers (or lexicographical order). Tip: Try to always find a maximum matching (instead of a matching that is merely maximal) as this can reduce the size of the branch-and-bound tree. Step: 1 G ; L =? M U =? VStep: ? G0 C L =? M U =? V Step: ? G0 C L =? M U =? V N [v]some vertex v Example template for the branch-and-bound tree. [70%] d) Specify one node in the branch-and-bound tree, where an optimal vertex cover is found and provide the obtained optimal vertex cover together with its size. [10%] COM2109/COM2001/COM21001 6 CONTINUED COM2109/COM2001/COM21001 3. a) Invoke the FindTour algorithm for the travelling salesman problem (TSP) on the following 4-vertex graph G. Answer the following questions. a bc d 2 4 5 3 6 2 (i) What is the minimum spanning tree T of G? [20%] (ii) Write down an Eulerian tour of the graph that is obtained by duplicating edges in T . [20%] (iii) Write down the TSP tour output by the algorithm FindTour. [20%] b) In a lab, 80 robots sit peacefully in a circle. Suddenly, each robot randomly attacks the robot immediately to its left or right. What is the expected number of unattacked robots? Justify your answer. [40%] COM2109/COM2001/COM21001 7 TURN OVER COM2109/COM2001/COM21001 4. a) Suppose we have a randomised algorithm Alg that outputs a number R such that with probability 34 it holds that R is in the interval [1, 10], i.e., 1  R  10. (i) If we run the algorithm Alg twice, what is the probability that at least one of the numbers R1, R2 returned is in the interval [1, 10]? Justify your answer. [20%] (ii) If we run the algorithm Alg thrice, what is the probability that at least two of the three numbers R1, R2, R3 returned are in the interval [1, 10]? Justify your answer. [40%] b) Let Alg be a randomised algorithm for the PRIME problem, i.e., to decide if an integer is prime or not. Suppose that Alg runs in expected polynomial time and always outputs the correct answer. Use Alg to give a new randomised algorithm NewAlg for the PRIME problem such that NewAlg always runs in polynomial time and • if the input integer is prime, then it will be accepted with probability at least 56 ; • if the input integer is not prime, then it will always be rejected. Describe your algorithm and justify its correctness and running time. [40%] Hint: You may use Markov’s inequality: If X is a random variable assuming only non-negative values, then for any positive real number t, it holds that Pr[X t]  E[X] t . END OF QUESTION PAPER COM2109/COM2001/COM21001 8















































































































































































学霸联盟