課程名稱︰演算法設計與分析 課程性質︰資工系 大二 必修 課程教師︰蔡欣穆 開課學院：電機資訊學院 開課系所︰資訊工程學系 考試日期（年月日）︰2015/01/15 考試時限（分鐘）：180分鐘 試題 : 132 points in total Problem 1. In each of tje following question, please specify if the statement is true or false. If the statement is true, explain why it is true. If it is false, explain what the correct answer is and why. (40 points. For each question,1 point for the true/false answer and 3 points foe the explaination.) 1. If L ∈ NPC and L ∈ P, then P = NP _ 2. If L ∈ NP then L ∈ NP. _ 3. If L ∈ P then L ∈ P. 4. If P = NP then NP = co-NP. 5. NPC ⊆ NP. 6. NP ⊇ P. For the following 4 questions, please refer to DFS(G) and DFS-VISIT(G,v) after the problem description. 7. There is no back edge in terms of the depth-first forest produced by a DFS on an undirected graph. 8. There is no cross edge in terms of the depth-first forest produced by a DFS on an undirected graph. 9. There is no back edge in terms of the depth-first forest produced by a DFS on a directed acyclic graph. 10. In DFS, when we visited an edge e = (u,v), if v's color is BLACK and u.d < v.d, then e is a cross edge. DFS(G) 1 for each vertex u ∈ G.V 2 u.color = WHITE 3 u.pi = NIL 4 time = 0 5 for each vertex u ∈ G.V 6 if u.color == WHITE 7 DFS-VISIT(G,u) DFS-VISIT(G,u) 1 time = time + 1 2 u.d = time 3 u.color = GRAY 4 for each v ∈ G.Adj[u] 5 if v.color == WHITE 6 v.pi = u 7 DFS-VISIT(G,v) 8 u.color = BLACK 9 time = time + 1 10 u.f = time Problem 2. Briefly explain in evidence-based scheduling how you can "simulate the future" ─ use the past history to estimate the time require to complete a task. (6 points) Problem 3. Please answer the following questions related to minimum cost spanning tree (MST) of connected graph G = (V,E). (24 points) 1. Please write down the pseudo code of Kruskal's algorithm. (4 points) 2. Please show that your algorithm in the previous problem runs in O(|E|log|E|). You can assume that running m of the following operations: MAKE-SET(v), FIND-SET(v), and UNION(u,v), takes O(mα(n))-time, where n is the number of MAKE-SET(v) operations, and α(n) is a very slowly growing function that α(n) ≦ 4 in all practical situations. (4 points) 3. Suppose that all edge weights in a graph are integers in the range from 1 to |V|. Please give a modified Kruskal's algorithm and show that is runs in O(|E|α|V|). (4 points) 4. Please write down the pseudo code of Prim's algorithm. (4 points) 5. Please show that your algorithm in the previous problem runs in O(|E|log|V|). (4 points) 6. Suppose that all edge weights in a graph are integers in the range from 1 to some constant W. Please give a modified Prim's algorithm and show that it runs in O(|E|). (4 points) Problem 4. We would like to implement a dynamic table data structure that supports two operations, TABLE-INSERT and TABLE-DELETE. TABLE-INSERT looks at the table to check if it is full. If not, then the item is directly inserted to the table. Otherwise, it doubles the size of the table, moves all data from the old table to the new table. TABLE-DELETE will remove the item from the table. If after the removal the table is less than 25% full, then it halve the table size and move all data from the old table to the new table. Assume that allocating the table space takes negligible time. Inserting, removing, or moving an item takes one unit if time. Show that the amortized cost of the two operations are both bounded above by a constant using the potential method. The potential function is given by 2 x T.num - T.size if T.num/T.size ≧ 1/2 Φ(T) = { T.size / 2 - T.num if T.num/T.size ＜ 1/2 where T.num is the number of items in the table and T.size is the size of the table. Note that you need to discuss different cases, including the ones that do not involve table expansion or contraction and the ones that do.(16 points) Problem 5. In this problem, we ask you to answer the following questions related to an directed graph G shown in Figure 2. (16 points) Figure 2. http://imgur.com/i47tCKL 1. Please use the Dijkstra Algorithm to determine the costs of the shortest path (the number next to the edges in the graph are the costs for travelling through them) from vertex 1 to all other vertices. Use Table 1 to show how the algorithm is executed in each iteration. (6 points) 2. Please use the Bellman-Ford Algorithm to determine the costs of the shortest path (the number next to the edges in the graph are the costs for travelling through them) from vertex 1 to all other vertices. Use Table 2 to show how the algorithm is executed in each iteration. (6 points) 3. Explain why Dijkstra Algorithm cannot handle edges with negative weights. (4 points) Problem 6. In this problem,we ask you to prove that NODE-COVER is NP-complete. The problem description is as follows. Given a graph G = (V,E), we say N ⊆ V, a vertex set, is a node cover for G if every edge in E has at least one end in N. The problem NODE-COVER is: given a graph G and a "budget" k, does G have a node cover of k or fewer nodes? (20 points) 1. Please show that NODE-COVER ∈ NP. (4 points) 2. To show that NODE-COVER is NP-hard, we will construct a reduction function f(x) that reduces an instance of 3-CNF-SAT to an instance of NODE-COVER, described as follows. (a) Create G with the following description. For each clause (xＶyＶz) in the 3-CNF fornula, construct a "column" of three nodes, all connected by vertical edges. Add a horizontal edge between nodes that represent any variable and its negation. (b) Let the budget k be twice the number of clauses. Example: (xＶyＶz)Λ(~xＶ~yＶ~z)Λ(xＶ~yＶz)Λ(~xＶyＶ~z) is reduced to G shown in Figure 1 with k = 8. Figure 1. http://imgur.com/dXvJvUF Please show that this reduction is correct, i.e., x ∈ 3-CNF-SAT if and and only if f(x) ∈ NODE-COVER. (12 points) Please also briefly explain why the reduction algorithm that calculates f(x) runs in polynomail time. (4 points) Problem 7. Out of all the lectures this semester, which one do you enjoy the most and which one do you want to skip the most? Why? And please also give constructive suggestion to the style and the content of the homework assignments. Thanks! (10 points) --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.231.38.225 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1421826852.A.FC3.html ※ 編輯: c081215 (61.231.38.225), 01/21/2015 16:04:03