Microsoft Word – CS70 Midterm Exam 1 Summer 2019 v5 (1).doc
CS570 Summer 2019: Analysis of Algorithms Exam II
Points Points
Problem 1 20 Problem 5 15
Problem 2 15 Problem 6 10
Problem 3 15 Problem 7 10
Problem 4 15
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 ]
In a flow network, a flow f is a max flow if and only if there exists no cut with the
same capacity as v(f)
[ TRUE/FALSE ]
If we replace each directed edge in a flow network with two directed edges in
opposite directions with the same capacity and connecting the same vertices, then
the value of the maximum flow remains unchanged.
[ TRUE/FALSE ]
It is possible for a circulation network to not have a feasible circulation even if all
edges have unlimited capacity.
[ TRUE/FALSE ]
If subset sum can be solved in polynomial time, then 3SAT can be solved in
polynomial time.
[ TRUE/FALSE ]
If problem A is NP-complete and A≤p B, then problem B is also NP-complete.
[ TRUE/FALSE ]
Some problems in the set P do not have efficient certifiers.
[ TRUE/FALSE ]
If an NP-hard problem can be solved in polynomial time then P=NP
[ TRUE/FALSE ]
A dynamic programming algorithm always uses some type of recurrence relation
[ 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 ]
A dynamic programming solution will always have a polynomial running time.
2) 15 pts
Let G= (V, E) be an undirected, bipartite graph.
a- Prove that the following algorithm is a ½ approximation to the maximum
matching in G. (10 pts)
Start with M=Null (an empty set)
While there are more edges in G
Select a random edge e in G and add it to M
Remove e and all edges that share a node with e from G
Endwhile
Return M
b- Show an example of a graph with no more than 6 edges where this algorithm
could produce a matching that is exactly half the size of its maximum matching.
(5 pts)
3) 15 pts
For each of the following problems, sketch an efficient algorithm or give an NP-
completeness proof. You may draw on results from class or the textbook. (Note: In
this problem, path length is the number of edges).
a- Longest path in a directed acyclic graph: Given vertices s and t, find a maximum
length path from s to t. (5 pts)
b. Path of length K: Given a directed graph, vertices s and t, and an integer K, find a
path of length exactly K between s and t. (5 pts)
c. Longest simple path. Given a directed graph and vertices s and t, find the longest
simple path between s and t. (Recall that a simple path is a path with no
repeated vertices.) (5 pts)
4) 15pts
Let G= (V, E) be a directed graph with distinguished vertices s and t. Describe an
algorithm using N/W flow to compute a minimum sized set of vertices to remove to
separate s and t. Your algorithm should identify the actual vertices to remove (and
not just determine the minimum number of vertices that could be removed).
5) 15 pts
A bus rental company has to solve the following problem daily and need an efficient
algorithm to help with their planning. They have n buses, m drivers, and they need to
plan for k trips. Each bus is suitable only for certain types of trips. For example, a trip to
the mountains may require shorter and more powerful buses. They also know that not
every driver can drive every bus. Note: a driver and a bus are assigned to a trip for the
whole day. n>k, m>k
a- Describe a NW Flow based solution to determine, given k trips (with type of trip
specified) if they can satisfy all k trips for that day. (10 pts)
b- If they cannot meet all the demand for trips on a given day, they want to know
whether it is due to the fact that they don’t have an appropriate set of drivers or
a suitable set of buses, or both. Describe how they can make that determination.
(5 pts)
6) 10 pts
In the MERGE-SORT algorithm we merge two sorted lists into one sorted list in O(n)
time. Describe an O(n log k)-time algorithm to merge k sorted lists into one sorted list,
where n is the total number of elements in all the input lists. Be sure to explain why
your algorithm runs in O(n log k)-time.
7) 10 pts
Duckwheat is produced in Kansas and Mexico and consumed in New York and
California. Kansas produces 15 shnupells of duckwheat and Mexico 8. Meanwhile,
New York consumes 10 shnupells and California 13. The transportation costs per
shnupell are $4 from Mexico to New York, $1 from Mexico to California, $2 from
Kansas to New York, and $3 and from Kansas to California.
Write a linear program that decides the amounts of duckwheat (in shnupells and
fractions of a shnupell) to be transported from each producer to each consumer, so
as to minimize the overall transportation cost.
Additional Space
Additional Space