课程名称︰演算法 课程性质︰系订选修 课程教师︰张耀文 开课学院：电资学院 开课系所︰电机系 考试日期（年月日）︰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