课程名称︰资料结构与演算法下 课程性质︰系必修 课程教师︰蔡欣穆 开课学院：电资学院 开课系所︰资讯系 考试日期（年月日）︰2011/6/24 考试时限（分钟）：180 是否需发放奖励金：是的，感谢 （如未明确表示，则不予发放） 试题 : 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.(12%, For each questions, 1% for the true/false answer and 3% for the explanations.) 1.Let P1 = {L为{0,1}*的父集: there exists an algorithm A that decides L in polynomial time} and P2 = {L为{0,1}*的父集: there exists an algorithm A that accepts L in polynomial time}. Then P1≠P2. 2.The person who solves the bugs should be the one to close the bug report. 3.When using the potential method to do amortized analysis, we define a potential function Φ which maps each data structure Di to a real number Φ(Di), the potential associated with teh data structure Di. To make sure that the total amortized cost gives an upper bound on the total actual cost, we usually need to make sure that Φ(Dn)≦Φ(D0). Problem 2. "Short answer" questions: (38 points) 1.Show that if one of the NP-complete problems can be solved in polynomial time, then any other NP problem can be solved in polynomial time.(5%) 2.Why is it hard to discover bugs caused by race conditions?(3%) 3.Give a short definition fo a "complete step" (in the context of multithreaded algorithms, of course). (3%) 4.What does a program manager do in a software company? (3%) 5.Define parallelism, ρ, using the work and the span of a multithreaded algorithm. What does it mean when P > ρ, where P is the number of processors in the system? Please explain(2% for the definition, 3% for the explanation.) 6.Fill in blanks (a) through (d) in Figure 1 using T1(A), T1(B), T∞(A),and T∞(B). ┌──┐ ┌──┐ work:T1(A∪B) = (a) ---> │ Ａ │----> │ Ｂ │---> └──┘ └──┘ span:T∞(A∪B) = (b) ┌──┐ │ Ａ │ └──┘ ↗ ↘ work:T1(A∪B) = (c) ↘ ↗ span:T∞(A∪B) = (d) ┌──┐ │ Ｂ │ └──┘ 7.The basic idea of Event-Based Scheduling is to simulate the future based on the past history of actual and estimated time to finish tasks. Explain in detail how one can use it to estimate the time to finish a task.(5%) 8.What are the 3 things that are needed in every bug report?(2% for each) Problem3.Consider the following multithreaded pseudocode for transposing an n*n matrix A in place:(18%) P-TRANSPOSE(A) 1 n = A.rows 2 parallel for j = 2 to n 3 parallel for i = 1 to j-1 4 exchange aij with aji 1.Analyze the work, span and parallelism of this algorithm.(3%) 2.Suppose that we replace the parallel for loop in line 3 of P-TRANSPOSE with an ordinary for loop. Analyze the work, span, and parallelism of the resulting algorithm.(3% each) Problem 4.Suppose that we have one machine and a set of n tasks A1, A2,...,An, each of which requires time on the machine. Each task Aj requires Tj time units on the machine(its processing time), yields a profit of Pj, and has a deadline Dj. The machine can process only one task at a time, and task Aj must run without interruption for Tj consecutive time units. If we complete task Aj by its deadline Dj, we receive a profit Pj, but if we complete it after its deadline, we receive no profit. As an optimization problem, we are given the processing times, profits, and deadlines for a set of n tasks, and we wish to find a schedulte that completes all the tasks and returns the greatese amount of profit. The processing times, profits, and deadlines are all nonnegative numbers(28%) 1.State this problem as a decision problem.(3%) 2.Show that the decision problem is NP-complete. For the purpose of reduction, you can assume that 0-1 knapsack problem is NP-complete.( We talked about 0-1 knapsack problem in the first half of the semester when we covered greedy algorithms in the lecture. To refresh your memory, the following is a description of the problem. A thief robbing a store finds n items. The ith item is worth Vi dollars and weighs Wi punds, where Vi and Wi are integers. The thief wants to take as valuable a load as possible, but he can carry at most W pounds in his knapsack, for some integer W. Which items shold he take?) (15%) 3.Give a dynamic programming lgorithm for the decision problem, assuming that all processing times are integers from 1 to n.(10%) Problem 5. Let G = (V,E) to be an undirected graph with distinct edge wights w(u,v) on each edge(u,v)属於E. For each vertex v属於V, let MAX(v) = argmax(u,v)属於E{w(u,v)} be the maximum-wight edge incident on that vertex.Let Sg = {MAX(v):v属於V} be the set of maximum-weight edges incident on that vertex, and let Tg be the maximum-weight spanning tree of G, that is, the spanning tree of maximum total weight. For any subset of E define, w(E')_ = Σ((u,v)属於E')W(u,v). (18%) 1.Prove that Sg为Tg的子集 for any graph G.(6%) 2.Prove that w(Sg)≧W(Tg)/2 for any graph G.(6%) 3.Give an O(V+E)-time algorithm to compute a 2-approximation to the maximum spanning tree. Explain why your algorithm is a 2-approximation algorithm. (6%) Problem 6.Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is linear in the size of the array. We can improve the time for insertion by keeping several sorted arrays. Specifically, suppose that we wish to support SEARCH and INSERT on a set of n elements. Let k = [㏒(n+1)], and let the binary representation fo n be <Nk-1, Nk-2,...,N0>.Ai is 2^i. Each array is either full or empty, depending on whether Ni = 1 or Ni = 0, respectively (in other words, depending on n, the number of elements stored in the array at the time). The total number of elements held in all k arrays is therefore Σ(i-0,k-1)Ni2^i = n. Although each individual array is sorted, elements in different arrays bear no particular relationship to each other. Here is how me perform the INSERT operation. We create a new sorted array of size 1 containing the new element to be inserted. If array A0(which has size 1) is empty, then we replace A0 with the new sorted array. Otherwise, we merge sort the two arrays into another sorted array of size 2. If A1 is empty, then we replace A1 with the new array; otherwise we merge sort the arrays as before and continue. Since array Ai is of size 2^im ifwe merge sort two arrays of size 2^i each, we obtain one of size 2^(i+1), which is the size of Ai+1. This method will result in another list of arrays in the same structure taht we had before. (15%) 1.Describe hwo to perform the SEARCH operation for this data structure. Analyze its worst-case running time.(6%) 2.Analyze the INSERT opertaion's worst-case and amortized running times(using the aggregate method).(3% for the worst-case, 6% for amortized) Problem 7.Feedback time again :P. This time please give us some suggestions for either the software company game we played in our last class, or general comments about the course.(6%) --

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