[試題] 100上 蘇雅韻 演算法設計與分析 期末考
課程名稱︰演算法設計與分析
課程性質︰必修
課程教師︰蘇雅韻
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2012.1.13
考試時限（分鐘）：170分鐘
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題：
˙ Do not open this booklet until you are directed to do so. Read all the
instructions on this page.
˙ There are a total of 11 pages including this page. Please make sure you
have all of them.
˙ This exam is closed book. You may use one handwritten A4 sheet.
˙ Do not waste time and paper rederiving facts that we have studied. It is
sufficient to cite known results.
˙ Do not spend too much time on any one problem. Read them all through first,
and attack them in the order that allows you to make the most progress.
˙ Show your work, as partial credit will be given. You will be graded not
only on the correctness of your answer, but also on the clarity with which
you express it. Be neat.
˙ When asked to give an algorithm, more credits will be given to faster
algorithms given the algorithm is correct.
˙ Good luck!
Problem 1 Minimum spanning tree
[20 points, 3 points each for (a)-(c), 11 points for (d) and (e)]
For parts (a), (b), and (c), consider the following weighted graph with 9
vertices and 14 edges. Note that the edge weights are distinct integers
between 1 and 14.
┌─┐ 2 ┌─┐
│Ｂ│───────│Ｇ│
╱└─┘╲ ╱└─┘
6╱ 14│ 7╲┌─┐╱8 │11
╱ │ │Ｅ│ │
┌─┐ 13 ┌─┐ 1 └─┘ ┌─┐
│Ａ│───│Ｃ│───┼───│Ｈ│
└─┘ └─┘╲ ￣╲ └─┘
╲ ╲ 12╲ │4
10╲ ╲5 ╲ │
╲┌─┐ 9 ╲＿＿＿┌─┐
│Ｄ│───────│Ｉ│
└─┘╲ └─┘
3╲┌─┐
│Ｆ│
└─┘
(a) Complete the sequences of edges added to a MST in the order that Kruskal's
algorithm includes them.
１
￣ ￣ ￣ ￣ ￣ ￣ ￣
(b) Suppose edge (E, F) of weight w is added to the graph. How would you
assign the value of w so that edge (E, F) is included in a MST?
(c) The weighted graph is repeated here for reference. Complete the sequences
of edges to a MST in the order that Prim's algorithm includes them. Start
Prim's algorithm from vertex A.
６
￣ ￣ ￣ ￣ ￣ ￣ ￣
(d) Suppose you know the MST of a weighted graph G. Now, a new edge (u, v) of
weight w is inserted into G to form a weighted graph G'. Design an O(V)
time algorithm to determine if the MST in G is also an MST in G'. You may
assume all edge weights are distinct. Your answer will be graded for
correctness, clarity, and conciseness.
(e) Explain briefly why your algorithm takes O(V) time.
Problem 2 Short answer questions
[8 points, 4 points each]
1. Circle the choice that describes a use of the following code.
┌───────────────┐
│for i = 1 to |G.V|-1 │
│ for u = 1 to |G.V|-1 │
│ for v in G.adj(u) │
│ if v.d > u.d + w(u,v) │
│ v.d = u.d + w(u,v) │
└───────────────┘
(a) To find the longest path in a weighted graph
(b) To compute the MST of a weighted graph
(c) To topologically sort a digraph
(d) To find shortest path in a weighted graph
(e) To implement DFS in a weighted graph
2. Given the weighted graph and the initial distance matrix below, what is the
value d_35 in matrix D^(2)
┌─┐
│２│
↗└─┘↖ ┌ 0 3 8 ∞ -4 ┐
3╱ ││ ╲4 │ │
╱ 7││1 ╲ │ ∞ 0 ∞ 1 7 │
┌─┐ ││ ┌─┐ (n) │ │
│１│ ──┼┼─→ │３│ D = │ ∞ 4 0 ∞ ∞ │
└─┘↖ ││ 8 └─┘ │ │
│ 2╲ ││ ↑ │ 2 ∞ -5 0 ∞ │
│ ╳ ╲ │ │ │
-4│ ↙ ╲ ↘ │-5 └ ∞ ∞ ∞ 6 0 ┘
│ ┌─┐ ┌─┐ │
└→│５│→│４│─┘
└─┘6 └─┘
(a) 5 (b) 11 (c) ∞ (d) 3 (e) None of the above
Problem 3 True or False and Justify.
[12 points, 3 points each]
For each question, circle either True or False. Then, give a brief
justification for your answer. Your question will be evaluated based on the
justification and not just the True/False answer alone.
1. T F Dijkstra's algorithm can be implemented with binary-heap or
Fibonacci-heap. Given a sparse graph where |E| = θ(|V|), the
Fibonacci-heap implementation is be asymptotically faster than the
binary-heap implementation.
2. T F Let G = (V,E) be a weighted graph and let T be a minimum spanning tree
of G. Then, for any pair of vertices s and t, the path in T must be a
shortest path in G.
3. T F Given a graph G = (V,E) with distinct weight on edges and a subset of
vertices S ≦ V. Let edge (u, v) be the minimum cost edge between any
vertex in S and any vertex in V-S. Then, the minimum spanning tree of
G must include the edge (u, v).
4. T F Let G = (V,E) be a directed graph with negative-weight edges, but no
negative-weight cycles. Then, one can compute all shortest paths from
a source vertex s ∈ V to all vertices v ∈ V faster than Bellman-Ford
using the technique of reweighting.
Problem 4 Maximum-flow
[20 points, 10 points for 1 (3/3/4) and 2 (5/5).]
1. The figure describes a flow assignment in a flow network. The notation a/b
describes a units of flow in an edge of capacity b. Please (1) briefly
state the Max-flow min-cut theorem. (2) Draw the minimum cut in the figure
(3) Explain whether the flow assignment in the figure is maximum flow using
the Max-flow min-cut theorem.
┌─┐ 4/5 ┌─┐
│ａ│──→│ｃ│
↗└─┘ └─┘╲3/6
1/4╱ ↑ ↗│ ╲
┌─┐╱ │ ╱ │ ↘┌─┐
│ｓ│ 3/7│ ╱ │1/4 │ｔ│
└─┘╲ │ ╱0/2 │ ↗└─┘
6/6╲ │╱ ↓ ╱
↘┌─┐ ┌─┐╱4/4
│ｂ│──→│ｄ│
└─┘ 3/3 └─┘
2. Suppose you have an algorithm A to solve the maximum flow problem. That is,
given a directed graph G, source node S, and sink node C, A will return the
value of maximum flow.
Today is the last day of this semester. After the exam, lots of people want to
go outside, but every place can accommodate a limit number of people. So, you
want to write a program to decide the maximum number of people that can go
outside. Given N persons {P_l, P_2, … , P_N}, the capacity of M places
{C_1, C_2, … , C_M}, and an N*M matrix K,
┌ 1, if person P_i is willing to go to the place j whose capacity
│ is C_j
K_ij = ┤
└ 0, otherwise
Please (1) given an algorithm that can determine the maximum number of people
that can go outside and (2) explain why your algorithm is correct.
More credits will be given to faster algorithms, provided that the analysis of
the algorithm is correct.
(HINT: You can use algorithm A in your algorithm)
Problem 5 Shortest paths
[15 points, 6 and 9 points each]
1. Given a DAG, please describe how to use topological sort to find shortest
paths.
2. We know that topological sort may output results of more than one kind of
ordering. Please explain why this does not affect the results of finding
shortest paths? (Hint: please focus on the case that if two vertices can
change their order but both orderings are legal topological ordering, why
this changing won't affect the answer.)
Problem 6
[10 points, 5 points each]
An edge disjoint path is that any two path with no sharing edges. Given a
directed graph, a source s and destination t, please (1) find k edge disjoint
path from s to t, and (2) briefly explain why your algorithm is correct.
(where 0 < k < maximum edge disjoint path). More credit will be given to
faster algorithms, provided that the analysis of the algorithm is correct.
Problem 7 NP-completeness
[20 points, 4, 6, and 10 points for 1, 2, and 3 respectively]
1. A problem A has a polynomial reduction to a problem B, and B has a
polynomial reduction to a problem C. Suppose B is in NP-complete.
(1) What can you say about A? (Note: there may be multiple correct answers)
(a) Nothing (b) It's in P (c) It's in NP (d) It's NP-complete
(e) It's NP-hard
(2) What can you say about C? (Note: there may be multiple correct answers)
(a) Nothing (b) It's in P (c) It's in NP (d) It's NP-complete
(e) It's NP-hard
2. SAT is the decision problem that takes as input a Boolean formula and
returns YES if the formula can be satisfied, NO if it cannot.
(1) What can you say about SAT?
(Note: there may be multiple correct answers)
(a) It's in P (b) It's in NP (c) It's NP-complete
(d) It's NP-hard (e) None of the previous answers
(2) Assume P = NP, What can you say about SAT?
(Note: there may be multiple correct answers)
(a) It's in P (b) It's in NP (c) It's NP-complete
(d) It's NP-hard (e) None of the previous answers
(3) Assume P != NP, What can you say about SAT?
(Note: there may be multiple correct answers)
(a) It's in P (b) It's in NP (c) It's NP-complete
(d) It's NP-hard (e) None of the previous answers
3. Assume there is an algorithm SOLVE_SAT to solve SAT that takes time T(n)
where n is the number of variables. SOLVE_SAT returns YES if the input
formula of size n can be satisfied and NO if the input cannot be satisfied.
Write in pseudocode an algorithm that utilizes SOLVE_SAT to return an
assignment of the formula (when it exists) that takes time O(nT(n)).
[Note: T is an increasing function]
Problem 8 Feedback
[Happy Chinese New Year bonus: 10 points]
Please tell us what you think about this class! Please write down (1) things
you like about this class and (2) things you would like to see we do that can
help you learn better.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.115.15
※ 編輯: rod24574575 來自: 61.230.115.15 (01/30 07:13)
→
01/30 10:57, , 1F
01/30 10:57, 1F