电子科技大学研究生算法设计与分析拟考题及答案评分细则 (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 )结论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分)参考答案和评分标准：a)(1) n5 + 10n4 = q (n5) （1分，非最简表达式或写成O或W不符合题意，不给分）(2) n2 +3n = q (3n) （1分，标准同上）(3) 210000 = q (n0.75) （1分，标准同上）(4) logn + (2logn)3 = q ( (logn)3) （1分，标准同上）(5) 2n+n!+ 5en = q (n!) （1分，标准同上）(6) 3log2n + 5logn = q (n) （1分，标准同上）(7) 2nlogn+lognn. = q (nn) （1分，标准同上）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. 参考答案及评分标准：a）将所有工作（jobs）按其完成时间的先后进行排序； 在排好序的序列中用弹性法则，以此选取最小完成时间且和前面已选工作不冲突的工作。 证明用反证法，假设贪心算法不是最优导出矛盾，课件中有证明。证明思路大体正确即可给全分。 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. 评分标准：说明计算该图从s到T的最大流 （2分）给出第一个和增广路径 （2分）后面任意两个增广路径 （1分一个）最后答案 18和这个cut （3分，任给一个cut即可，最后结果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 ). 参考答案及评分标准：设检查算法为B，我们构造一个找到解的算法A，该算法多项式次调用B。 （1分）算法A的步骤和思想：依次从图中删除一个点，再调用算法B来检查是否还存在大小为k的clique，如果存在则直接从图中删除这个点 （2分）；如果不存在，则将这个点放入解集，同时将图中所有不和这个点相邻的点全删除，再删除这个点本身，在剩余的图中再检查是否存在大小为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分)参考答案及评分标准：将最长路径问题归约到通过某个点的最长路径问题。思想如下：对于每个最长路径问题G，我们对图G中每个点得到一个通过这个点的最长路径问题，总共得到n（n为G中点的个数）个问题，如果后一个问题存在多项式算法，则前一个问题也存在。以上思想正确给全分，否则最多给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).