一、 Please answer T or F for each of the following statements to indicate whether the statement is true or false
1. The knapsack problem can be solved in polynomial time by using dynamic programming. ( F )
2. Some problems in NP can be solved in polynomial time. ( T )
3. To show a problem is NP-hard, we can reduce it to a well-known NP-Complete problem. ( F )
4. In an undirected graph, the value of the maximum flow between two vertices is equivalent to the value of the minimum cut between them. ( T ) 5. . ( F )
二、 Arrange the following functions in ascending asymptotic order of growth rate: ，，，，.
参考答案：f2，f3，f1，f4，f5
三、 Please answer the following questions:
(a) What are the main steps of designing a dynamic programming algorithm?
参考答案：1.定义子问题；2根据子问题建立递归关系式；3用自底而上的方式求解（建立储存表）。
(b) What are the main steps of proving the NP-Completeness of a problem?
参考答案：1.证明该问题属于NP；2.选一个已知的NPC问题B；3.将问题B归约到该问题上。
四、 The Traveling salesman problem (TSP) is defined as follows: Given a graph, the task is to find a shortest possible route that visits each vertex exactly once and returns to the origin vertex.
Fig. 1
For the graph shown in Fig. 1,
(a) find a solution to TSP ((the route is starting from A and back to A); (b) find a longest directed cycle that contains vertex A. 参考答案：|
（a） A->D->C->B->A 35+12+30+20=97 （b） A->C->B->D->A 42+30+34+35=141
五、 Design an algorithm for the following Interval Scheduling problem: There are n jobs each of which has a starting time s and a finishing time f. Two jobs are compatible if they don't overlap. The goal of the problem is to find a maximum set of mutually compatible jobs. 参考答案及评分标准：
将所有工作（Interval）按其完成时间的先后进行排序；
在排好序的序列中用弹性法则，以此选取最小完成时间且和前面已选工作不冲突的工作。 六、 Find a minimum s-t cut in the following graph (the number beside the edge is the capacity of the edge). You are required to give the computation steps and show the size of the cut.
参考答案： 35. 有两个解：{S，4，3，8}和{S，1，2，3，4，5，6，7，8，9} 评分标准：说明计算该图从s到t的最大流 给出第一个增广连 后面任意两个增广连 （ 最后答案 35和这个cut
七、 Prove that if we can check if a graph has a path of length k in polynomial time then we can also find a path of length k in polynomial time.
参考答案及评分标准：依次从图中删除一条边，然后检查是否还存在长度为k的路径，如果存在则直接删除，如果不存在则保留该边。如此下去，最后图只剩下k条边。 以上思想正确给全分。
八、 A Hamiltonian cycle in a graph is a cycle that contains each vertex. The Hamiltonian Cycle problem is to find a Hamiltonian cycle in a graph. The Constrained Hamiltonian Cycle problem is to find a Hamiltonian cycle passing through some given edges in the graph.
Give a polynomial reduction from the Constrained Hamiltonian Cycle problem to the Hamiltonian Cycle problem.
参考答案及评分标准：在每个给出的要求通过的边上添加一个顶点（度数为2），这样Hamilton cycle就必须通过这些边了。 以上思想正确给全分。
九、 Answer the following questions.
Given a graph G with nonnegative vertex weight, the Weighted Vertex Cover problem is to find a minimum vertex set (the weight of vertices in the set is minimized) such that each edge in the graph has at least one endpoint in the set.
(a) Please give an integer programming formulation of the Weighted Vertex Cover problem. (b) Give a 2-approximation algorithm based on linear programming. (c) Prove that your algorithm guarantees the approximation ratio 2.
参考答案及评分标准： （a） （b） 将以上整数规划改为线性规划：将约束条件改为，并且将解中x_i值大于等于0.5的选入点覆盖中。
（c）证明在教材在有。大体思路对可以给全分。 十、 There are m machines and n=2m+1 jobs, where two of jobs has length of (m+1,m+2, m+3, ..., 2m) respectively, and one job has length of m. Each job must be processed contiguously on a machine and each machine can process at most one job at a time. You are asked to assign jobs to
machines to minimize the makespan (the longest processing time on any machine).
(a) Give an approximation solution by using the longest processing time first (LPT) algorithm. (give the main idea of LPT and the final solution) (b) Try to find an optimal solution for this problem.
参考答案及评分标准：
（a）LPT算法基本思想是将任务按照处理时间长度降序排列，总是将处理时间最长的任务分配到目前负载最低的机器上。 （b）The optimal solution of the minimizing the makespan is 3m+2. 因为所有任务长度之和是3m^2+2m, 共有m个机器，每个机器都分配相同长度的任务（3m^2+2m）/m=3m+2. 十一、 Given a graph, the Vertex Cover problem is to find a minimum subset of vertices such that each edge has at least one endpoint in it; the Independent Set problem is to find a maximum subset of vertices such that there is no edge between any two vertices in it, and the Clique problem is to find a maximum subset of vertices such that there is an edge between any two vertices in it. Please give a polynomial reduction from the Vertex Cover problem to the Independent Set problem and a polynomial reduction from the Independent Set problem to the Clique problem.
参考答案及评分标准：
VC到IS的归约：图中除去vertex cover中的点剩下的点就是一个independent set。
IS 到 Clique的归约：让G'为G的补图，则G中的independent set就是G'中的clique。
十二、 Use dynamic programming to solve the following knapsack problem: There are n different types of items and each type has two pieces (totally we have 2n items). Item has weight of kilograms and value of dollars. You have a knapsack that can contain at most kilograms. How to fill your knapsack with the items to maximum the value? (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. You are required to give the computation steps (the table used to store the solutions to the subporblems). Items Weight Value 1 1 2 2 2 3 3 4 8 4 3 2
电子科技大学研究生算法设计与分析拟考题及答案评分细则(3)
