课程名称︰演算法设计与分析 课程性质︰必修 课程教师︰苏雅韵 开课学院：电资学院 开课系所︰资工系 考试日期（年月日）︰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)