CS计算机代考程序代写 ER algorithm CS570

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