CS6515 EXAM 3 NEWEST VERSION COMPLETE QUESTIONS AND CORRECT DETAILED ANSWERS (VERIFIED ANSWERS) |ALREADY GRADED A+

CS6515 EXAM 3 NEWEST VERSION COMPLETE QUESTIONS AND CORRECT DETAILED ANSWERS (VERIFIED ANSWERS) |ALREADY GRADED A+ 2. Demonstrate that problem B is at least as hard as a problem believed to be NPComplete. This is done via a reduction from a known problem A (A->B) a) Show how an instance of A is converted to B in polynomial time b) Show how a solution to B can be converted to a solution for A, again in polynomial time c) Show that a solution for B exists IF AND ONLY IF a solution to A exists - most prove both parts: if you you have a solution to B, you have a solution to A - If there is no solution to B, then no solution exists to A LP: Why optimum occurs at a vertex - ANSWER -Feasible region is convex LP: Optimum achieved at a vertex except: - ANSWER -1. Infeasible - feasible region is empty 2. Unbounded - optimal value of objective function is arbitrarily large Independent Set -> Vertex Cover - ANSWER -Lemma: I is an independent set of G(V, E) iff V - I is a vertex cover of G Simply check if there is a vertex cover of size V - b in G(V, E). If there is, output V - S 3SAT -> Independent Set - ANSWER -Lemma: f is satisfiable iff the resulting set has an independent set of size m (# of clauses in f) in G(V, E). To construct G(V, E), create a node for each literal in each clause and connect them by an edge. Also connect any literal with it's negation. Independent Set -> Clique - ANSWER -Lemma: G(V, E) has an independent set of size g iff G'(V, E) has a clique of size g. To construct G'(V, E), add all the vertices in G(V, E) to G'(V, E) and add edges to G'(V, E) if there is no edge in G(V, E) SAT - ANSWER -Input: C is a CNF with any # of variables (n) and clauses (m) Output: assignment of each variable s.t. the CNF is True 3SAT - ANSWER -Input: C is a CNF whose clauses have at most 3 literals Output: Assignment of each variable s.t. the CNF is True Clique - ANSWER -Input: G is an undirected, unweighted graph, k is the size of the clique Output: A Clique in G with at least k vertices Independent Set - ANSWER -Input: G is an undirected, unweighted graph, k is the size of the IS Output: An IS in G with at least k vertices VertexCover - ANSWER -Input: G is an undirected, unweighted graph, b is a budget of the vertex cover Output: A vertex cover of G with at most b vertices RudrataPath - ANSWER -Input: G = (V, E) is an undirected, unweighted graph, s is the starting node and t is the destination node. Output: A simple path starting at s and ending at t that passes through each vertex in the graph exactly once RudrataCycle - ANSWER -Input: G=(V, E) is an undirected, unweighted graph Output: A cycle that visits each vertex in the graph exactly once SubsetSum - ANSWER -Input: A is an array of integers and t is an integer Output: An array of integers that is a subset of A and sums to t KnapsackSearch - ANSWER -Input: W is an array of weights, V is an array of values, B is the capacity of the knapsack, and g is the goal. Output: Array of items of value at least g with weight less than or equal to B TSP - ANSWER -Input: G is a weighted, fully connected graph with weights for each n(n-1)/2 edges; b is a budget Output: A path that visits every vertex in the graph exactly once and has a total cost of b or less 3DMatching - ANSWER -Input: disjoint sets X, Y, Z of items to be matched. Collection of compatibility triples (X, Y, Z) Output: A disjoint set (no elements in common) of n compatible triples ZOE - ANSWER -Input: an mXn matrix A, all of whose entries are 0 or 1 Output: An n-vector x, all of whose entries are 0 or 1, such that AX = 1 Clique, Independent Set and Vertex Cover Relation - ANSWER -Lemma: Given an undirected graph G = (V, E) with n vertices and a subset V ′ ⊆ V of size k. The following are equivalent: