COSC-311 Sample Final Questions

COSC-311 Sample Final Questions Note: There will be four problems on the actual final exam. The problems on this handout are meant to give you a sense of the types of questions I might ask. This study guide is not comprehensive: there are topics we have covered in class that are not represented in the sample problems. Everything we have done in class or on homework is fair game for the exam. 1 Properties of Max Flows and Min Cuts Let G = (V, E) be a flow network, with a source node s, target node t, and positive integer edge capacities c(e) for each edge e ∈ E. For each of the following claims, state whether it is true or false. If it is true, explain why. If it is false, draw (and briefly explain) a flow network that shows a counterexample. (a) Claim 1: If f is a max flow, then f saturates every edge into t (i.e., f (e) = c(e) for all edges e into t). (b) Claim 2: Let (A, B) be a min cut. If we multiply the capacity of every edge in G by 2, then (A, B) is still a min cut. 2 Reductions (a) Consider the following claim: If X ≤P Y and Y ∈ P , then X ∈ P . Is this claim true or false? Give a short explanation of your answer. (b) Fill in the blanks to make the following claim true: Given two problems X and Y , then if Y is NP-complete, then if ≤P then X is NP-complete. Give a short explanation of your answer. 1 3 Residual Graphs Here is a flow network. Numbers in boxes represent the amount of flow currently being sent along an edge, and “unadorned” numbers represent edge capacities. (a) Draw the residual graph for this flow. (b) What is the definition of an augmenting path? (c) Is the current flow in this graph a max flow? Use the residual graph to explain why or why not. 4 Hamiltonian Cycles In class we showed that the Hamiltonian Cycle problem was NP-complete by reducing 3-SAT to Hamiltonian Cycle. Here is a (very trivial) instance of SAT (this is actually an instance of 2-SAT, not of 3-SAT, but the reduction still can be done): (x1 ∨ x̄2 ) (a) Show the input to Hamiltonian Cycle that our reduction produced. (b) Explain how we know that “yes” instances of 3-SAT map to “yes” instances of Hamiltonian Cycle. 2 5 Reductions Redux For each of the following claims, state whether the claim is true, false, or not known (meaning that in the current state of theoretical CS the answer is not known, not that you personally do not know!). Give a short explanation of your answer. (a) Claim 1: Minimum Spanning Tree ≤P Traveling Salesman. (b) Claim 2: Traveling Salesman ≤P Minimum Spanning tree. 6 Local Search Suppose we wanted to define a local search algorithm to give an approximate solution for Independent Set. We define the “Flip-One Neighborhood” of a possible solution S to be the set of valid solutions that can be obtained from either (1) adding a single vertex to S, or (2) removing a single vertex from S. Here is a graph in which we want to find the largest possible independent set: (a) Starting at the solution S = {a, b} given above, show the steps that a local search algorithm would take (including listing the neighboring solutions), using the termination rule that the algorithm terminates when it reaches a solution that has no higher-cost neighbors. Break any ties by choosing the last solution alphabetically. (b) Does your local search run from part (b) find the maximum independent set? If not, give a larger independent set. 3