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
COSC-311 Sample Final Questions
of 3
Report
Tell us what’s wrong with it:
Thanks, got it!
We will moderate it soon!
Free up your schedule!
Our EduBirdie Experts Are Here for You 24/7! Just fill out a form and let us know how we can assist you.
Take 5 seconds to unlock
Enter your email below and get instant access to your document