[試題] 102上 蔡欣穆 演算法設計與分析 期末考
課程名稱︰演算法設計與分析
課程性質︰資工系 大二上 必修
課程教師︰蔡欣穆
開課學院：電機資訊學院
開課系所︰資訊工程學系
考試日期（年月日）︰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)