Microsoft Word – CS70 Midterm Exam 3 Spring 2018 v2.docx
CS570 Summer 2018: Analysis of Algorithms Exam III
Points
Problem 1 20
Problem 2 16
Problem 3 16
Problem 4 16
Problem 5 16
Problem 6 16
Total 100
Instructions:
1. This is a 2-hr exam. Closed book and notes
2. If a description to an algorithm or a proof is required please limit your description or proof to
within 150 words, preferably not exceeding the space allotted for that question.
3. No space other than the pages in the exam booklet will be scanned for grading.
4. If you require an additional page for a question, you can use the extra page provided within
this booklet. However please indicate clearly that you are continuing the solution on the
additional page.
5. Do not detach any sheets from the booklet. Detached sheets will not be scanned.
6. If using a pencil to write the answers, make sure you apply enough pressure so your answers
are readable in the scanned copy of your exam.
7. Do not write your answers in cursive scripts.
1) 20 pts
Mark the following statements as TRUE or FALSE. No need to provide any justification.
[ TRUE/FALSE ]
An undirected graph is said to be Hamiltonian if it has a cycle containing
all the vertices. Based on this definition, is the following true or false?
Any DFS tree on a Hamiltonian graph must have depth V-1.
[ TRUE/FALSE ]
At the termination of the Bellman-Ford algorithm, even if the graph
has a negative length cycle, a correct shortest path is found for a vertex for which
shortest path is well-defined.
[ TRUE/FALSE ]
The main difference between divide and conquer and dynamic programming is that divide
and conquer solves problems in a top-down manner whereas dynamic-programming does this
bottom-up.
[ TRUE/FALSE ]
If problem A is polynomial-time reducible to a problem B (i.e., A≤ p B ), and B is NP-
complete, then A must be NP-complete.
[ TRUE/FALSE ]
If problem A is polynomial-time reducible to a problem B (i.e., A≤ p B ), and A is NP-
complete, then B must be NP-complete.
[ TRUE/FALSE ]
Flow f is maximum flow if and only if there are no augmenting paths.
[ TRUE/FALSE ]
If P ≠ NP, then the general optimization problem TRAVELING-SALESPERSON has a poly-
time approximation algorithm with approximation factor 1.5.
[ TRUE/FALSE ]
We currently only have a weakly polynomial time solution for the 0/1 knapsack problem, but
not a strongly polynomial time solution.
[ TRUE/FALSE ]
Suppose that all edge capacities c(e) is a multiple of α. Then the value of the maximum flow
is also a multiple of α
[ TRUE/FALSE ]
Suppose that all edge capacities c(e) is a multiple of α. In a maximum flow f, the flow f(e) on
edge e is always a multiple of α
2) 16 pts.
Recall that in exam 1 (just a couple of weeks ago), you were asked to find a
polynomial time solution to this problem:
Input: Undirected, connected graph 𝐺 = (𝑉, 𝐸) with edge weights 𝑤). We are also given
U which is a subset of vertices of the graph ( 𝑈 ⊂ 𝑉 ).
Output: Find the spanning tree of minimum total weight such that all nodes of U
have degree 1.
Now prove that the following problem (MST-D2) is NP-Hard:
Input: Undirected, connected graph 𝐺 = (𝑉, 𝐸) with edge weights 𝑤). We are also given
U which is a subset of vertices of the graph ( 𝑈 ⊂ 𝑉 ).
Output: Find the spanning tree of minimum total weight such that all nodes of U
have degree 2 (if such a tree exists).
Solution:
Show that Hamiltonian Path ≤p MST-D2
Given G an undirected graph – an instance of the Hamiltonian Path problem, we will
construct G’ an undirected graph with unit weights on all edges. Then for every pair
of nodes in G (say v and u), we will call the black box that solves MST-D2 and set
U=V-{v,u}. There will be O(n2) calls to the black box. If any of these calls returns a
tree such that all nodes in the tree have degree 2 except for v and u, it means that we
have found a Hamiltonian Path in G with v and u as its end points. If none of the calls
to the black box manage to return such a tree, then we can conclude that G has no
Hamiltonian Paths.
Rubric:
8 pts if the transformation is correct and sound.
8 pts for the proof
3) 16 pts.
You are traveling by renting cars from car rental locations of cities. There are n cities
along the way. Also, a company named Trojan Rental dominates the car rental
market, and therefore there is only one car rental location in each city. Before starting
your journey, you are given for each 1 ≤ i < j ≤ n, the fee fi,j for renting a car from city
i to city j, which is arbitrary. For example, it is possible that f2,3 = 8 and f2,5 = 6. Also,
city j charges tj% in taxes on the fee (fi,j) collected in city j when the car is dropped
off.
You begin at city 1 and must end at city n. Your goal is to minimize the rental cost.
Give the most efficient algorithm you can for this problem. Be sure to prove that your
algorithm yields an optimal solution and analyze the time complexity.
a) Define (in plain English) subproblems to be solved (3 pts)
The sub problem is to calculate the minimum rental cost with taxes from a city i to n
where 1