课程名称︰演算法设计与分析 课程性质︰必带 课程教师︰蔡欣穆 开课学院：电机资讯学院 开课系所︰资讯工程学系 考试日期（年月日）︰101/1/13 考试时限（分钟）：180 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : Algorithm Design and Analysis, Fall 2011 Final Examination 120 points Time: 9:10am-12:10pm(180 minutes),Friday, January 13, 2012 Problem 1. In each of the 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.(8 points. 1 point for true /false and 3 points for the explanation for each question) 1.The complexity class NP represents the problems which cannot be solved in polynomial time. 2.When the parallelism of a multi-thread algorithm, ρ=Ω(n), adding more processors to the system which runs the algorithm would always make the algorithm run faster. Problem 2. "Short answer" questions:(36 points) 1.Why is it hard to discover bugs caused by race conditions?(4 points) 2.Fill in blanks (a) through (d) in Figure 1 using T1(A),T1(B),T∞(A), and T∞(B).(8 points) ┌─┐ │A │ ┌──┐ ┌──┐ ↗└─┘↘ ─→│ A │─→│ B │─→ ↗ ↘ └──┘ └──┘ ↘ ┌─┐ ↗ ↘│B │↗ └─┘ Work:T1 (A∪B)=(a) Work:T1 (A∪B)=(c) Span:T∞(A∪B)=(b) Span:T∞(A∪B)=(d) Figure 1: The work and span of composed subcomputations 3.What are the two conditions that a language L ⊆ {0,1}* is NP- complete?(4 points) 4.Explain why Dijkstra's algorithm does not work when the edges in the graph can be negative.(4 points) 5.Explain when using Evidence-Based Scheduling, how we predict the time to complete a task.(4 points) 6.List two advantages of writing the functional specification before start implementing the software.(4 points) 7.Let T∞, Tp, T1 be the running time of multi-threaded algorithm A when having ∞,P,1 processors in the system, respectively. Write down the formulas for (1)the work law; and (2)the span law; using these 3 variables. (8 points) X1──|￣￣╲ ╴╴ X2──| )──── ╲ ╲ ┌─|╴╴╱ ∣ ╲ X3┴──────────｜ ＞── ────∣ ╱ ╱ ╱ ╱ |╲ ╱ ￣￣ X4─| O╴╱ |╱ Figure 2 : A Boolean Combinational Circuit Problem 3.Please answer the following questions about circuit satisfiability and formula satisfiability problems: (22 points) 1.Use the reduction algorithm we talked about in the lecture to reduce the circuit in Figure 2 to a general boolean formula.(4 points) 2.Use the reduction algorithm we talked about in the lecture to reduce a general boolean formula (~X1 ^ X2) V X3 to the 3-CNF form.(8 points) 3.In the class, we talked about how 3-CNF formula is a restricted form of the boolean formula, and how we do not want to restrict the form too much so that it is no longer a NP-complete problem anymore. 2-CNF formula is an example of restricting the form too much. Let 2-CNF-SAT be the set of satisfiable boolean formulas in CNF with exactly 2 literal per clause. Show that 2-CNF-SAT ∈ P. Make your algorithm as efficient as possible.(Hint: Observe that x V y is equivalent to ~x→y. Reduce 2-CNF-SAT to an efficient sovlable problem on a directed graph.) (10 points) Problem 4. Consider an ordinary binary min-heap data structure with n element supporting the instructions INSERT and EXTRACT-MIN in O(log n) worst-case time. Give a potential function Φ such that the amortized cost of INSERT is O(log n) and the amortized cost of EXTRACT-MIN is O(1), and show that it works :(Hint: one way to formulate the potential function involves the depths of the nodes in the heap. Think of a way to combine them.) (20 points) 1.Define your potential function Φ. Prove that it always satisfies Φ(Di)≧Φ(D0), ∀i, where Di is the data structure after performing the i-th operation.(4 points) 2.Show that the amortized cost of INSERT is O(log n).(8 points) 3.Show that the amortized cost of EXTRACT-MIN is O(1).(8 points) Problem 5. Answer the following questions about the complexity class co-NP. (12 points) 1. Use the language HAM-CYCLE ={﹤G﹥:G is a hamiltonian graph} as an example to explain what co-NP means; on what condition HAM-CYCLE ∈NP? (4 points) 2.Prove that P ⊆ co-NP. (8 points) Problem 6. Answer the following questions about graph.(20 points) 1.Use Prim's algorithm to obtain the minimum spanning tree of the graph in Figure 3. Please mark the order of adding the edge to the spanning tree on the figure. (4 points) 2.Please use the Bellman-Ford algorithm to determine the costs of the shortest paths (the number next to the edges in the graph are the costs for traveling through them) from vertex 1 to all other vertices in the graph in Figure 3. Use table 1 to show how the algorithm is executed in each iterations.(8 points) 3.Please use the Dijkstra's algorithm to determine the costs of the shortest path(the number next to the edges in the graph are the costs for traveling through them) from vertex 1 to all other vertices in the graph in Figure 3. Use Table 2 to show how the algorithm is executed in each iteration.(8 points) ⑤ ④ 2╱ ╲4 1╱ ╲3 ╱ 9 ╲ ╱ 5 ╲ ① ──── ⑦─────② ╲ ╱ ╱ 20╲ 10╱ ╱3 ╲ ╱ 2 ╱ ⑥────③ Figure 3: A Graph ┌─┬───────────┐ │ │ k │ │ │ dist [7] │ │k ├─┬─┬─┬─┬─┬─┤ │ │2 │3 │4 │5 │6 │7 │ └─┴─┴─┴─┴─┴─┴─┘ ┌─┬─┬─┬─┬─┬─┬─┐ │1 │∞│∞│∞│2 │20│9 │ ├─┼─┼─┼─┼─┼─┼─┤ │2 │ │ │ │ │ │ │ ├─┼─┼─┼─┼─┼─┼─┤ │3 │ │ │ │ │ │ │ ├─┼─┼─┼─┼─┼─┼─┤ │4 │ │ │ │ │ │ │ ├─┼─┼─┼─┼─┼─┼─┤ │5 │ │ │ │ │ │ │ ├─┼─┼─┼─┼─┼─┼─┤ │6 │ │ │ │ │ │ │ └─┴─┴─┴─┴─┴─┴─┘ Table 1 : Step-by step execution details of the Bellman-Ford algorithm ┌─────┬────────┬───────────┐ │ │ │ Distances │ │Iteration │Vertex Selected ├─┬─┬─┬─┬─┬─┤ │ │ │2 │3 │4 │5 │6 │7 │ └─────┴────────┴─┴─┴─┴─┴─┴─┘ ┌─────┬────────┬─┬─┬─┬─┬─┬─┐ │ Initial │ ─ │∞│∞│∞│2 │20│9 │ ├─────┼────────┼─┼─┼─┼─┼─┼─┤ │ 1 │ │ │ │ │ │ │ │ ├─────┼────────┼─┼─┼─┼─┼─┼─┤ │ 2 │ │ │ │ │ │ │ │ ├─────┼────────┼─┼─┼─┼─┼─┼─┤ │ 3 │ │ │ │ │ │ │ │ ├─────┼────────┼─┼─┼─┼─┼─┼─┤ │ 4 │ │ │ │ │ │ │ │ ├─────┼────────┼─┼─┼─┼─┼─┼─┤ │ 5 │ │ │ │ │ │ │ │ ├─────┼────────┼─┼─┼─┼─┼─┼─┤ │ 6 │ │ │ │ │ │ │ │ └─────┴────────┴─┴─┴─┴─┴─┴─┘ Table 2 : Step-by-step execution details of Dijkstra's algorithm Problem 7. Out of all topics we covered in the classes this semester, which one do you like the most? Which one do you dislike the most? Why? Please give some constructive suggestions. (2 points) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.244.207