電子科技大學(xué)研究生算法設(shè)計與分析擬考題及答案評分細(xì)則 (2).doc

一、 Please answer T or F for each of the following statements to indicate whether the statement is true or false1. An algorithm is an instance, or concrete representation, for a computer program in some programming language. ( F )2. The following problem is a Decision Problem: What is the value of a best possible solution? ( F )3. The dynamic programming method can not solve a problem in polynomial time. ( F )4. Assume that there is a polynomial reduction from problem A to problem B. If we can prove that A is NP-hard, then we know that B is NP-hard. ( F ) 5. If one can give a polynomial-time algorithm for a problem in NP, then all the problems NP can be solved in polynomial time. ( F )6. In an undirected graph, the minimum cut between any two vertices a and b is unique. ( F )7. Linear programming can be solved in polynomial time, but integer linear programming can not be solved in polynomial time. ( T )8. We can solve the maximum independent set problem in a graph with at most 100 vertices in polynomial time. ( T )結(jié)論9. If an algorithm solves a problem of size n by dividing it into two subproblems of size n/2, recursively solving each subproblems, and then combine the solutions in linear time. Then the algorithm runs in O(nlogn) time. ( T )10. Neural Computation, Fuzzy Computation and Evolution Computing are the three research fields of Computational Intelligence. ( T )二、 Given the following seven functions f1(n) = n5 + 10n4, f2(n) = n2 + 3n, f3(n) = 210000, f4(n) = logn + (2logn)3, f5(n) = 2n+n!+ 5en, f6(n) = 3log(2n) + 5logn, f7(n) = 2nlogn+lognn. Please answer the questions:(a) Give the tight asymptotic growth rate (asymptotic expression with q) to each of them; (7分)(b) Arrange them in ascending order of asymptotic growth rate。 (3分)參考答案和評分標(biāo)準(zhǔn)：a)(1) n5 + 10n4 = q (n5) （1分，非最簡表達(dá)式或?qū)懗蒓或W不符合題意，不給分）(2) n2 +3n = q (3n) （1分，標(biāo)準(zhǔn)同上）(3) 210000 = q (n0.75) （1分，標(biāo)準(zhǔn)同上）(4) logn + (2logn)3 = q ( (logn)3) （1分，標(biāo)準(zhǔn)同上）(5) 2n+n!+ 5en = q (n!) （1分，標(biāo)準(zhǔn)同上）(6) 3log2n + 5logn = q (n) （1分，標(biāo)準(zhǔn)同上）(7) 2nlogn+lognn. = q (nn) （1分，標(biāo)準(zhǔn)同上）b)f4 f3 f6 f1 f2 f5 f7 (3分，每個錯誤位置扣0.5分，扣完為止）三、 Please answer the following questions:(a)。四、 In the interval scheduling problem, we are given n jobs each of which has a starting time s and a finishing time f, and the goal is to find a maximum set of mutually compatible jobs (two jobs are compatible if they dont overlap). Please answer the following questions:(a) Design a greedy algorithm for the interval scheduling problem and prove the correctness of it. (b) Assume that we are given 8 jobs with starting time and finishing time (s, t) being (0,2), (1,3), (8,9), (3,7), (7,8), (2,4）,(6,9), (4,5). Use your algorithm to find a solution to this instance. 參考答案及評分標(biāo)準(zhǔn)：a）將所有工作（jobs）按其完成時間的先后進(jìn)行排序； 在排好序的序列中用彈性法則，以此選取最小完成時間且和前面已選工作不沖突的工作。 證明用反證法，假設(shè)貪心算法不是最優(yōu)導(dǎo)出矛盾，課件中有證明。證明思路大體正確即可給全分。 b)答案是 (0,2),(2,4),(4,5),(7,8),(8,9). 五、 Find a minimum s-t cut in the following directed graph (the number beside the edge is the capacity of the edge). You are required to give the computation steps and show the cut and its size. （9分）參考答案： 18. 評分標(biāo)準(zhǔn)：說明計算該圖從s到T的最大流 （2分）給出第一個和增廣路徑 （2分）后面任意兩個增廣路徑 （1分一個）最后答案 18和這個cut （3分，任給一個cut即可，最后結(jié)果18錯誤則不給分） 六、 Prove that if we can check if a graph has a clique of size k in polynomial time then we can also find a clique of size k in polynomial time (a clique of a graph is a complete subgraph ). 參考答案及評分標(biāo)準(zhǔn)：設(shè)檢查算法為B，我們構(gòu)造一個找到解的算法A，該算法多項式次調(diào)用B。 （1分）算法A的步驟和思想：依次從圖中刪除一個點(diǎn)，再調(diào)用算法B來檢查是否還存在大小為k的clique，如果存在則直接從圖中刪除這個點(diǎn) （2分）；如果不存在，則將這個點(diǎn)放入解集，同時將圖中所有不和這個點(diǎn)相鄰的點(diǎn)全刪除，再刪除這個點(diǎn)本身，在剩余的圖中再檢查是否存在大小為k-1的clique。（3分）以上思想正確給全分，其它正確解法也給全分。七、 We know that finding a longest path in a graph is NP-hard. Please show that finding a longest path that passing through a given vertex is also NP-hard. (6分)參考答案及評分標(biāo)準(zhǔn)：將最長路徑問題歸約到通過某個點(diǎn)的最長路徑問題。思想如下：對于每個最長路徑問題G，我們對圖G中每個點(diǎn)得到一個通過這個點(diǎn)的最長路徑問題，總共得到n（n為G中點(diǎn)的個數(shù)）個問題，如果后一個問題存在多項式算法，則前一個問題也存在。以上思想正確給全分，否則最多給3分。八、 In a supermarket, there are n different types of goods for sale. Each type of goods has a price of dollars and a value of . Now you are asked to buy some goods such that: for each type of goods, at most 2 pieces are bought, the total value of the goods is at least V and the total money used is minium. Use a dynamic programming algorithm to solve the above problem. (a) Please define your subproblem; (b) Give the recurrence relation based on your subproblems; (c) Solve the following instance showed in Table 1 by using the bottom-up method, where V=10. You are required to give the computation steps (the table used to store the solutions to the subporblems).