推 Peter034 :友情推 第四題是重點!! XD 01/15 01:45
推 ketsu1109 :已收入精華區 01/15 03:06
課程名稱︰演算法
課程性質︰系訂選修
課程教師︰張耀文
開課學院：電資學院
開課系所︰電機系
考試日期（年月日）︰2009/01/14
考試時限（分鐘）： 150min
是否需發放獎勵金： yes
（如未明確表示，則不予發放）
試題 :
Instructions. This is a 150-minute test, with a total of 106 points available.
There are four pages and six (seven) sets of problems. Below please see an
algorithms in the text that may be useful for answering some of the given
problems. Reusing the following codes, you only need to give the modified
codes. Also, you may just give the names of the algorithms to answer the
questions if the algorithm have been discussed in class, without rewriting
their codes. Pace yourself and Good Luck!
┌─────────────────────────────┐
│B(W) │
│1. n ← rows[W]; │
│2. D(0) ← W; │
│3. for k ← 1 to n │
│4. for i ← 1 to n │
│5. for j ← 1 to n │
│6. d(k)ij ← min( d(k-1)ij, d(k-1)ij+d(k-1)ij ); │
│7. return D(n). │
└─────────────────────────────┘
Problem 1. (40 pts total) Please give a brief answer for each of the following
questions.
(a) Professor Chang reduces a job assignment problem into the maximum-flow
problem discussed in class. The reduction and the maximum-flow solving take
O(VE√lgC) time, where V, E, C are the number of vertices, the number of
edges, and the maximum edge capacity in the flow network, respectively. He
claims this job-assignment algorithm to be polynomial-time solvable. Argue
if his claim is correct.
(b) Does either Prim's or Krusal's minimum-spanning-tree algorithm work if
there are negative edge weights? Why?
(c) Let P be a shortest path from some vertex s to some other vertex t in a
graph. If the weight of each edge in the graph is increased by one, will P
still be a shortest path from s to t? Why?
(d) Let G = (V,E) be a weighted directed graph. The capacity of a path is
defined as the minimum edge weight among all the edges on the path. Suppose
that we want to find a maximum capacity path between each pair of vertices.
Show how to modify Floyd-Warshall's all-pair shortest-path algorithm to
solve this problem in O(V^3) time.
(e) Let G = (V,E) be a weighted directed graph, where edge weights are given by
the function w：E → R. Define another edge-weight function w'：E → R by
w'(u,v) = w(u,v) - outdegree(u) + outdegree(v),
where outdegree(u) is the number of edges going out of the vertex u. Then,
G contains a negative-weight cycle under w if and only if G contains a
negative-weight cycle under w'. Prove or disapprove the statement.
(f) Given a maximum flow f on a flow network G = (V,E) with source s and sink
t, can a minimum cut seperating s from t be found in O(V+E) time. Why?
(g) Professor Chang claims the apparent paradox between statements S1 and S2.
Nevertheless, he may not be wrong (i.e., both S1 and S2 could be true
simultaneously). Give two possible reasons for this phenomenon.
S1: P ≠ NP. In other words, there does not exist a polynomial time
algorithm for any NP-complete problem.
S2: There exists a transformation (reduction) from some particular instance
of the NP-complete HP problem to a shortest path problem solvable by
Dijkstra's algorithm.
(h) Consider the Degree-Constrained Spanning-Tree problem (DCST) described
below.
－ Instance: G = (V,E), a positive interger K ≦│V│.
－ Question: Is there a spanning tree for G in which no vertex has degree
(number of edges connected to a vertex) larger than K?
We know that the Hamiltonian path (HP) problem of finding a simple path
that visits each vertex in a given graph exactly ince is NP-complete. Is
DCST NP-hard. Why?
Problem 2. (12 pts total) Consider the chessboard shown below. Note that some
squares are shaded, denoting blockages. We wish to determine a shortest path,
if one exists, that starts at the square designated by s and after visiting
the minimum number of squares, ends at the square designated by t. The tour
must not visit any shaded square.
(a) (7pts) Formulate this problem on an approptiately defined graph. Give an
efficient algorithm to solve this problem. What is the time complexity of
your algorithm?
(b) (5pts) Suppose that each boundary of two squares models the penalty or
profit for passing through it, i.e., the cost could be positive or
negative. Formulate this problem on an appropriately defined graph. Give an
efficient algorithm to solve this problem. What is the time complexity of
your algorithm?
ｓ■■□■
□□□□■
□■□□□
□□■□■
■□□□ｔ
Problem 3. (12 pts total) (Acyclic graphs)
(a) (4 pts) Suppose that the constraint graph G = (V,E) corresponding to a
linear-programming system of difference constraints is acyclic. Give a
linear-time algorithm for finding a solution for the problem of the system
of difference constraints.
(b) (8 pts) A longest path is a directed path from node s to node t with the
maximum length. Give a linear-time algorithm for determining a longest path
in an acyclic graph with nonnegative edge lengths.
Problem 4. (12 pts total) A Chinese delegate stays at the Grand Hotel, located
at node s, in the network below. He would like to meet the Taiwanese president
at the Taipei Hall, located at node t. Nevertheless, so mant Taiwanese and
Tibetan people want to protest this delegate by posting their "national" flags
for some recent Chinese suppression over them, along the roads shown in the
network. For some untold reason, the chief-of-police of Taiwan is ordered to
remove all the protesting people with their "national" flags along the roads.
For each road/edge (i,j), the chief-of-police has determined the number of
officers that must be deployed along the road/edge to ensure that those people
would be removed if the delegate were to travel on that road. These numbers are
written adjacent to the edges in the network. For example, if the chief-of-
police deploys five police officers on road (a,c), the people with their
"national" flags will be removed with certainty if the delegate chooses to
travel on that road. The chief-of-police wishes to determine the minimum number
of police officers he must deploy to be certain that all those people will be
removed before the delegate arrives at the Taipei Hall.
(a) (9pts) Apply a polynomial-time algorithm discussed in class to solve the
chief-of-office's problem step by step. What is the minimum number of
police officers he needs to deploy for the situation shown in the network?
Show only the changed part of the network step by step (instead of the
whole netowrk to save your time).
(b) (3pts) Explain why the final result that you obtained is maximum.
5 5
ａ──→ｃ──→ｔ
↑↖2 ↗│╲ ↑
8│ ╳ │2 ╲2 │12
│╱4 ╲↓ ↘∣
ｓ──→ｂ──→ｄ
3 5
Problem 5. (12 pts total) In this year of great depression, a realtor needs to
maximize the number of apartments sold; otherwise, shw will soon go into
bankruptcy. She has p apartments to sell and q potential customers for these
apartments. She has m salesmen working for her. Each salesman is assigned a
list of apartments and clients interested in these apartments. A salesman can
sell an apartment to any of his customers. Salesman i can sell at most bi
apartments. Also, any apartment cannot be owned by more than one person. For
m = 2, p = 4, q = 5, b1 = b2 = 2, and the following assignments of customers
and apartments to the salesmen, construct the flow network for the underlying
problem. How to find the maximum number of apartments that can be sold?
Salesman Customers Apartments
1 1,2,3,4 1,2,3
2 3,4,5 3,4
Problem 6. (18 pts total) An independent set of a graph G = (V,E) is a subset
V' ⊆ V of vertices such that each edge in E is incident on at most one vertex
in V'. The Independent-Set Problem (ISP) is to find a maximum-size independent
set in G.
(a) (6pts) Give an efficient algorithm to solve the ISP when G is biparite.
Justify the correctness of your algorithm.
(b) (2pts) Formally describe the decision problem of ISP. Let it be ISPD.
(c) (10pts) The 3-CNF-SAT problem (3SAT) is defines as follows:
－ Definition: 3SAT = {<φ>: boolean formula φ in 3-conjunctive normal
form is astisfiable}.
Prove that ISPD is NP-complete by usibg the reduction from 3SAT shown
below. Notice that no partial credit will be given for any reduction not
from 3SAT. (Hint: What is the size of the independent set and its relation
with the corresponding 3SAT?)
(x1Ｖx2Ｖx3)Λ(┐x1Ｖ┐x2Ｖ┐x3)Λ(┐x1Ｖx2Ｖx3)
┌─────────────┐
x1─────(┐x1) (┐x1)
╱ ╲ ╱ ╲ ╱ ╲
(x2)─(x3) (┐x2)─(┐x3) (x2)─(x3)
╲＿＿＿╳＿＿＿╳＿＿＿╳＿＿＿／
Problem 7. (bonus) (This problem can be answered by email by 5pm January 18
after the final exam.) Please list the corrections to the class notes and
lectures you made in this semester, if any. Please give specific information on
the corrections, e.g., page numbers of the class notes, if possible.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.112.182.61