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 页，共 8 页
https://www.coursehero.com/file/40103771/CSCI-570-Exam-3-2014-Fallpdf/
Th
is
stu
dy
re
so
ur
ce
w
as
sh
ar
ed
v
ia
C
ou
rs
eH
er
o.
co
m
https://www.coursehero.com/file/40103771/CSCI-570-Exam-3-2014-Fallpdf/
1) 20 pts
Mark the following statements as TRUE or FALSE. No need to provide any
justification.
[ TRUE/FALSE ]
All the NP-hard problems are in NP.
[ TRUE/FALSE ]
Given a weighted graph and two nodes, it is possible to list all shortest paths between
these two nodes in polynomial time.
[ TRUE/FALSE ]
In the memory efficient implementation of Bellman-Ford, the number of iterations it
takes to converge can vary depending on the order of nodes updated within an
iteration
[ TRUE/FALSE ]
There is a feasible circulation with demands if .
[ TRUE/FALSE ]
Not every decision problem in P has a polynomial time certifier.
[ TRUE/FALSE ]
If a problem can be reduced to linear programming in polynomial time then that problem is
in P.
[ TRUE/FALSE ]
If we can prove that P NP, then a problem A P does not belong to NP.
[ TRUE/FALSE ]
If all capacities in a flow network are integers, then every maximum flow in the
network is such that flow value on each edge is an integer.
[ TRUE/FALSE ]
In a dynamic programming formulation, the sub-problems must be mutually
independent.
[ TRUE/FALSE ]
In the final residual graph constructed during the execution of the Ford–Fulkerson
Algorithm, there’s no path from sink to source.
第 2 页，共 8 页
https://www.coursehero.com/file/40103771/CSCI-570-Exam-3-2014-Fallpdf/
Th
is
stu
dy
re
so
ur
ce
w
as
sh
ar
ed
v
ia
C
ou
rs
eH
er
o.
co
m
https://www.coursehero.com/file/40103771/CSCI-570-Exam-3-2014-Fallpdf/
2) 16 pts
In the Bipartite Directed Hamiltonian Cycle problem, we are given a bipartite
directed graph and asked whether there is a simple cycle which visits
every node exactly once. Note that this problem might potentially be easier than
Directed Hamiltonian Cycle because it assumes a bipartite graph. Prove that Bipartite
Directed Hamiltonian Cycle is in fact still NP-Complete.
第 3 页，共 8 页
https://www.coursehero.com/file/40103771/CSCI-570-Exam-3-2014-Fallpdf/
Th
is
stu
dy
re
so
ur
ce
w
as
sh
ar
ed
v
ia
C
ou
rs
eH
er
o.
co
m
https://www.coursehero.com/file/40103771/CSCI-570-Exam-3-2014-Fallpdf/
3) 16 pts
A tourism company is providing boat tours on a river with consecutive segments.
According to previous experience, the profit they can make by providing boat tours
on segment is known as . Here could be positive (they earn money), negative
(they lose money), or zero. Because of the administration convenience, the local
community of the river requires that the tourism company should do their boat tour
business on a contiguous sequence of the river segments, i.e, if the company chooses
segment as the starting segment and segment as the ending segment, all the
segments in between should also be covered by the tour service, no matter whether
the company will earn or lose money. The company’s goal is to determine the starting
segment and ending segment of boat tours along the river, such that their total profit
can be maximized. Design an efficient algorithm to achieve this goal, and analyze its
run time (Note that brute-force algorithm achieves , so your algorithm must do
better.)
第 4 页，共 8 页
https://www.coursehero.com/file/40103771/CSCI-570-Exam-3-2014-Fallpdf/
Th
is
stu
dy
re
so
ur
ce
w
as
sh
ar
ed
v
ia
C
ou
rs
eH
er
o.
co
m
https://www.coursehero.com/file/40103771/CSCI-570-Exam-3-2014-Fallpdf/
4) 16 pts
Consider the following matching problem. There are students and a
set of companies . Each student can work for only one company,
whereas company can hire up to students. Student has a preferred set of
companies at which he/she is willing to work. Your task is to find an
assignment of students to companies such that all of the above constraints are
satisfied and each student is assigned. Formulate this as a network flow problem and
describe any subsequent steps necessary to arrive at the solution. Prove correctness.
第 5 页，共 8 页
https://www.coursehero.com/file/40103771/CSCI-570-Exam-3-2014-Fallpdf/
Th
is
stu
dy
re
so
ur
ce
w
as
sh
ar
ed
v
ia
C
ou
rs
eH
er
o.
co
m
https://www.coursehero.com/file/40103771/CSCI-570-Exam-3-2014-Fallpdf/
5) 16 pts
Consider a directed, weighted graph G where all edge weights are positive. You have
one Star, which lets you change the weight of any one edge to zero. In other words,
you may change the weight of any one edge to zero. Give an efficient algorithm using
Dijkstra’s algorithm to find a lowest-cost path between two vertices s and t, given that
you may set one edge weight to zero. Note: you will receive 10 pts if your algorithm
is efficient. You will receive full points (16 pts) if your algorithm has the same run
time complexity as Dijkstra’s algorithm.
第 6 页，共 8 页
https://www.coursehero.com/file/40103771/CSCI-570-Exam-3-2014-Fallpdf/
Th
is
stu
dy
re
so
ur
ce
w
as
sh
ar
ed
v
ia
C
ou
rs
eH
er
o.
co
m
https://www.coursehero.com/file/40103771/CSCI-570-Exam-3-2014-Fallpdf/
6) 16 pts
You are given n rods; they are of length , respectively. Our goal is to
connect all the rods and form a single rod. The length after connecting two rods and
the cost of connecting them are both equal to the sum of their lengths. Give an
algorithm to minimize the cost of connecting them to form a single rod. State the
complexity of your algorithm and prove that your algorithm is optimal.
第 7 页，共 8 页
https://www.coursehero.com/file/40103771/CSCI-570-Exam-3-2014-Fallpdf/
Th
is
stu
dy
re
so
ur
ce
w
as
sh
ar
ed
v
ia
C
ou
rs
eH
er
o.
co
m
https://www.coursehero.com/file/40103771/CSCI-570-Exam-3-2014-Fallpdf/
Additional Space
第 8 页，共 8 页
https://www.coursehero.com/file/40103771/CSCI-570-Exam-3-2014-Fallpdf/
Th
is
stu
dy
re
so
ur
ce
w
as
sh
ar
ed
v
ia
C
ou
rs
eH
er
o.
co
m
Powered by TCPDF (www.tcpdf.org)
https://www.coursehero.com/file/40103771/CSCI-570-Exam-3-2014-Fallpdf/
http://www.tcpdf.org