Microsoft Word – CS70 Midterm Exam 3 a Fall 2014 solutions v2.docx
CS570
Analysis of Algorithms
Fall 2014
Exam III
Name: _____________________
Student ID: _________________
Email:______________________
Wednesday Evening Section
Maximum Received
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.
1) 20 pts
Mark the following statements as TRUE or FALSE. No need to provide any
justification.
All integer programming problems can be solved in polynomial time.
Fractional knapsack problem has a polynomial time greedy solution.
For any cycle in a graph, the cheapest edge in the cycle is in a minimum spanning
tree.
Every decision problem is in NP.
If P=NP then P=NP=NP-complete.
Ford-Fulkerson algorithm can always terminate if the capacities are real numbers.
A flow network with unique edge capacities has a unique min cut.
A graph with non-unique edge weights will have at least two minimum spanning
trees.
A sequence of O(n) priority queue operations can be used to sort a set of n numbers.
If a problem X is polynomial time reducible to an NP-complete problem Y, then X is
NP-complete.
2) 16 pts
Consider the complete weighted graph 𝐺 = (𝑉, 𝐸) with the following properties
a. The vertices are points on the X-Y plane on a regular 𝑛 × 𝑛 grid, i.e. the
set of vertices is given by 𝑉 = {(𝑝, 𝑞)|1 ≤ 𝑝, 𝑞 ≤ 𝑛}, where p and q are
integer numbers.
b. The edge weights are given by the usual Euclidean distance, i.e. the
weight of the edge between the nodes (𝑖, 𝑗) and (𝑘, 𝑙) is
5(𝑘 − 𝑖)! + (𝑙 − 𝑗)!.
Prove or disprove: There exists a minimum spanning tree of 𝐺 such that every node
has degree at most two.
3) 16 pts
You are trying to decide the best order in which to answer your CS-570 exam
questions within the duration of the exam. Suppose that there are 𝑛 questions with
points 𝑝”, 𝑝!, … , 𝑝# and you need time 𝑡$ to completely answer the 𝑖%& question. You
are confident that all your completely answered questions will be correct (and get you
full credit for them), and the TAs will give you partial credit for an incompletely
answered question, in proportion to the time you spent on that question. Assuming
that the total exam duration is 𝑇, give a greedy algorithm to decide the order in which
you should attempt the questions and prove that the algorithm gives you an optimal
answer.
4) 16 pts
An Edge Cover on a graph 𝐺 = (𝑉; 𝐸) is a set of edges 𝑋 ⊆ 𝐸 such that every vertex
in 𝑉 is incident to an edge in 𝑋. In the Bipartite Edge Cover problem, we are given a
bipartite graph and wish to find an Edge Cover that contains ≤ 𝑘 edges. Design a
polynomial-time algorithm based on network flow (max flow or circulation) to solve
it and justify your algorithm.
5) 16 pts
Imagine starting with the given decimal number n, and repeatedly chopping off a digit
from one end or the other (your choice), until only one digit is left. The square-depth
SQD(n) of n is defined to be the maximum number of perfect squares you could
observe among all such sequences. For example, SQD(32492) = 3 via the sequence
32492 → 3249 → 324 → 24 → 4
since 3249, 324, and 4 are perfect squares, and no other sequence of chops gives more
than 3 perfect squares. Note that such a sequence may not be unique, e.g.
32492 → 3249 → 249 → 49 → 9
also gives you 3 perfect squares, viz. 3249, 49, and 9.
Describe an efficient algorithm to compute the square-depth SQD(n), of a given
number n, written as a d-digit decimal number 𝑎!𝑎”…𝑎#. Analyze your algorithm’s
running time. Your algorithm should run in time polynomial in d. You may assume
the availability of a function IS_SQUARE(x) that runs in constant time and returns 1
if x is a perfect square and 0 otherwise.
6) 16 pts
The Longest Path is the problem of deciding whether a graph has a simple path of
length greater or equal to a given number k.
a) Show that the Longest Path problem is in NP (2 pts)
b) Show how the Hamiltonian Cycle problem can be reduced to the Longest Path
problem. (14 pts)
Note: You can choose to do the reduction in b either directly, or use transitivity of
polynomial time reduction to first reduce Hamiltonian Cycle to another problem (X)
and then reduce X to Longest Path.