课程名称︰演算法设计与分析 课程性质︰资工系 大二上 必修 课程教师︰蔡欣穆 开课学院：电机资讯学院 开课系所︰资讯工程学系 考试日期（年月日）︰2014/1/8 考试时限（分钟）：180 minutes 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : total score : 123 points 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. (16 points. For each question, 1 point for the true/false answer and 3 points for the explanations.) 1. If P = NP, then NPC ⊆ P. 2. If NPC ⊆ P, then P = NP. 3. When performing an amortized analysis with the potential method, we usually want the potential after any given number of operations to be larger than or equal to the initial potential. 4. 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 rejects L in polynomial time}. Then P1 = P2. Problem 2. " Short answer " questions : (29 points) 1. Why is it hard to discover bugs created by race conditions ? (3 piints) How to avoid race condition in a multithreaded algorithm ? (3 points) 2. Explain, in evidence-based scheduling, how to use Monte Carlo simulation to estimate the range of possible time duration for a sofeware engineer to complete a task. (4 points) 3. Analyze the work and the span of the following pseudo code program. Assume T(A) = T(B) = T(C) = O(logn), T(D(i)) = O(i). Please gives the work, the span and the parallelism of the given program in terms of n. (9 poionts) spawn A() spawn B() spawn C() parallel for i = 1 to n D(i) sync 4. Give one advantage and one disadvantage of using a paper prototype in software development. (4 points) 5. Define parallelism, ρ, using the work and the span of a multithreaded algorithm, and explain its meaning (3 points). What does it mean when P > ρ, where P is the number of processors in the system ? Please explain. (3 points) Problem 3. The CSIE network administrators need to deploy many WiFi APs (access points) in the CSIE building to provide wireless Internet connections throughout the building. That is not an easy task; if the distance between two APs is smaller than the transmission range, then two APs would interfere with each other. Although the administrators can avoid this problem by configuring the APs to use different channels, but the number of non-overlapping channels which can be utilized by the AP is limited. For example, when IEEE 802.11b/g/n is used, there are only 3 non-overlapping channels (channel 1, 6, 11). We define the problem as the following. Given a number of APs, the number of channels c, and the interfering relations of them (whether two APs would interfere with each other), can the network administrators find a way to allocate channels to APs so that no two APs would interfere with each other ? (28 points) Example : Two channels 1, 6 are available (c = 2). The line between two APs implies that they are too close and would interfere with each other (see figure 1). Here's the URL of fugure 1 : http://ppt.cc/1YLa Assume that channel 1 is reserved for research purposes in the CSIE building. Thus, only channel 6 and 11 are available (c = 2). 1. Provide an algorithm (in pseudo code or C code) to solve this problem in polynomial time. (6 points) 2. Analyze the time complexity of your algorithm. Then explain why this problem belongs to the complexity class P. (6 points) 3. Now, the network administrators decide to also utilize channel 1 ( c = 3). Prove that the problem becomes a NP-Complete problem. We can use a reduction from 3-CNF-SAT problem, which is already proven to be a NP-Complete problem in the lecture. The following outlines the reduction algorithm. The three channels 1, 6, 11 can represent the 3 states of a variable, True, False, Other, respectively. Given a formula φ of m clauses on n variables x_1, x_2, ..., x_n, we can construct an AP network as follows (see Figure 2) (a) Create 3 special APs with respectively the channels True, False, Other; these 3 special APs form a triangle (they interfere with each of the two other APs) (b) Create APs that represents each variable x and its negation. APs representing x_i and its negation ~x_i, for all i = 1 to n, interfere with each other. Link all 2n APs created so far to the special AP that uses the channel " Other ". (c) Create 5 APs for each clause, and the interfering relations are shown in Figure 2. Show that this reduction can be done in polynomial time. (6 points) Here's the URL of figure 2 : http://ppt.cc/7f3~ 4. Now prove that φ is satisfiable if and only if you can solve the 3-channel APs problem of the reduced instance. You can then show that this 3-channel APs problem is NP-hard. (6 points) 5. Prove that this problem (c = 3) is NP and thus also NP-Complete. (4 points) Problem 4. Give a multithreaded algorithm to multiply an n × n matrix A by an n-vector X that achieves θ(n^2/logn) parallelism while maintaining θ(n^2) work. Show this by calculating the work, the span, and the parallelism of your algorithm in terms on n. Note that you cannot use the following algorithm, as race condition occur in this algorithm. (10 points) Y=MAT-VEC-WRONG(A,X) n = A.rows let Y be a new vector of length n parallel for i = 1 to n parallel for j = 1 to n Y(i) = Y(i) + A(i,j) * X(j) return Y Problem 5. Consider the following multithreaded pseudo code for transosing an n × n matrix A in place : (24 points) P-TRANSPOSE(A) n = A.rows parallel for j = 2 to n parallel for i = 1 to j-1 exchange A(i,j) with A(j,i) 1. Draw the computation DAG of P_TRANSPOSE(A) in the case of n = 4. (6 points) 2. Analyze the work, span, and parallelism of this algorithm in terms of n. (3 points each) 3. Suppose that we replace the second parallel for loop in line 3 of P-TRANSPOSE with an ordinary for loop. Analyze the work, span, and parallelism of the resulting algorithm in terms of n. (3 points each) Problem 6. Consider an ordinary binary min-heap data structure with n elements supporting the instructions INSERT and EXTRACT_MIN in O(logn) worst-case time. Give a potential function φ such that the amortized cost of INSERT is O(logn) 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.) (12 points, 4 points each) 1. Define your potential function φ. Prove that it always satisfies φ(D_i) >= φ(D_0) for every i, where D_i is the data structure after performing the i-th operation. 2. Show that the amortized cost of INSERT is O(logn). 3. Show that the amortized code of EXTRACT-MIN is O(1). Problem 7. I understand that many of you feel that we have too much homework or the homework is too difficult that you have to spent too much time on it, while it seems that your grade does not sufficiently reflect your efforts. If you were the instructor of ADA, how would you do to reduce the homework work load, while at the same time, you can still motivate the students to spend enough time on the course materials to absorb them ? Feel free to comment on any other aspect of the course too. (4 points) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.243.26 ※ 编辑: andyyuan 来自: 140.112.243.26 (01/12 00:43) ※ 编辑: andyyuan 来自: 140.112.243.26 (01/12 00:50)