課程名稱︰演算法設計與分析
課程性質︰必帶
課程教師︰蔡欣穆
開課學院：電機資訊學院
開課系所︰資訊工程學系
考試日期（年月日）︰102/1/10
考試時限（分鐘）：180
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Algorithm Design and Analysis, Fall 2012
Final Examination
130 points
Time: 2:20pm-5:20pm (180 minutes), Thursday, January 10 ,2013
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 NPC = P, then P = NP.
2. If L_1,L_2⊂{0,1}* are languages such that L_1≦p L_2. If L_1∈NPC, then
L_2∈NPC.
3. The complexity class NP represents the problems which cannot be decided
within polynomial time.
4. When performing an amortized analysis, we usually require the total
amortized cost to be a lower bound of the total actual cost.
Problem 2. "Short answer" questions: (38 points)
1. Please derive the work T_1(A∪B∪C∪D) and the span T_∞(A∪B∪C∪D) of
the multithread algorithm shown in Figure 1 in term of T_1(s) and
T_∞(s), s ={A,B,C,D} (8 points)
2. When the estimate complete time for the software product does not meet
the original planned product ship date, why is it not a good idea to hire
more software engineers to complete the job? What should be done instead
to solve this problem? (4 points)
3. Supposed for each software engineer in your company, you have collected a
historic list of ratios of the estimated time to complete a programming
task and the actual time to complete it. Explain briefly how to use
evidence-based scheduling to utilize the lists to estimate the time to
complete a future task. (6 points)
4. In the form of pseudo code, give an example of an algorithm that will
result in race condition(s). Do not use the following one, which is
presented in the lecture. (4 points)
RACE-EXAMPLE()
x=0
parallel for i=1 to 2
x=x+1
print x
5. In the lecture, we discussed dynamic tables, whose main idea is to adjust
the table size based on its load factor α. Suppose that we would
contract a table by multiplying its size by 2/3 when α drops below 1/3.
Table contraction is done by allocating a new table with a smaller size
and moving all items from the old table to the new one. Let T.num be the
number of items in the table and T.size be the size if the table. You
can assume that the actual cost of a deletion in the table is 1, and the
actual cost of a table contraction is T.num (for moving the items). Use
the potenial function
Φ(T) = |2T.num-T.size| (1)
to show that the amortized cost of a table delete function that use this
strategy is bounded above by a constant. (Hint: calculate the amortized
cost for different conditions) (8 points)
Problem 3. As shown in the lecture, the following pseudo code function P-Square-
Matrix-Multiply calculates the multiplication of two matrices a and b.
(24 points)
P-Square-Matrix-Multiply(a,b)
n=a.rows
let c be a new n x n matrix
parallel for i=1 to n
parallel for j=1 to n
c[i][j]=0
for k=1 to n
c[i][j]=c[i][j]+a[i][k]*b[k][j]
return c
1. Draw the computation dag for computing P-Square-Matrix-Multiply on 2x2
matrices and labels how the vertices in your diagram correspond to
strands in the function. Use the convention that spawn and call edges
point downward, continuation edges point horizontally to the right, and
return edges point upward. (6 points)
2. Assume that each strand takes unit time, analyze the work, span, and
parallelism of the computation. (6 points)
3. Modify P-Square-Matrix-Multiply to have a span of O(logn). Note that you
cannot just use "parallel for k=1 to n",because the iterations are not
independent; they all use a common variable "c[i][j]". Feel free to use
"spawn" and "sync" instead of parallel loops and define a new function
for recursive calls. (Do not use OpenMP directives such as "private" or
"reduction". Please write down the actual implementation) (8 points)
4. Please show that your modified algorithm indeed has a span of O(logn).
(4 points)
Problem 4. Suppose that we have one machine and a set of n tasks a_1,a_2,...,a_n
,each of which requires time on the machine. We only have access to this machine
between time 0 and D. Each task a_j requires t_j time units on the machine (its
processing time), yields a profit of p_j, and is ready for execution at time s_j
(cannot be executed before then). The machine can process only one task at a
time, and task a_j must run without interruption for t_j consecutive time units.
If we complete task a_j, we receive a profit p_j. As an optimization problem, we
are given the end of access time duration D for the machine, processing times,
profits, and ready times for a set of n task, and we wish to find a schedule for
a subset of the given tasks or all the tasks so that the greatest amount of
profit can be obtained. The processing times, profits, and ready times are all
nonnegative numbers. (26 points)
1. State this problem as a decision problem. (2 points)
2. Show that the decision problem is NP-complete. For the purpose of
reduction, you can assume that the decision problem version of 0-1
knapsack problem is NP-complete. (We talked about 0-1 knapsack problem in
the first semester when we covered greedy algorithm 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 v_i dollars
and weighs w_i pounds, where v_i and w_i 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 should he take?) (8 points)
3. Assuming that all processing times and ready times are integers from 1 to
n, show that the (optimization) problem exhibits optimal substructure (as
usual, you need to define your subproblem). (8 points)
4. Give a polynomial-time dynamic programming algorithm for the decision
problem, assuming that all processing times and ready times are integer
from 1 to n. (8 points)
Problem 5. Consider an ordinary binary search tree augmented by adding to each
node x the attribute x.size giving the number of keys stored in the subtree
rooted at x. Let α be a constant in the range 1/2≦α＜1. We say that a given
node x is α-balanced if x.left.size≦α‧x.size and x.right.size≦α‧x.size.
The tree as a whole is α-balanced if every node in the tree is α-balanced.
(28 points)
1. A (1/2)-balanced tree, in a sense, as balanced as it can be. Given a node
x in an arbitary binary search tree, show how to rebuild the subtree
rooted at x so that it become (1/2)-balanced. Your algorithm should run
in time O(x.size), and it can use O(x.size) auxiliary storage (space)
(6 points)
2. Given α, show that performing a search in an n-node α-balanced binary
search tree takes O(logn) worst-case time. (Hint: derive a recurrence to
search in a tree rooted at node x in terms of the time to search in its
subtree.) (4 points)
For the remainder of this problem, assume that the constant α is strictly
greater than 1/2. Suppose that we implement INSERT and DELETE as usual for an
n-node binary search tree, except that after every such operation, if any node
in the tree is no longer α-balanced, then we rebuild the subtree rooted at the
highest such node in the tree so that it becomes (1/2)-balanced.
We shall analyze this rebuilding scheme using the potential method. For a
node x in a binary search tree T, we define
Δ(x) = | x.left.size - x.right.size | (2)
,and we define the potential of T as
Φ(T) = c Σ Δ(x) (3)
X∈T:Δ(x)≧2
,where c is a sufficiently large constant that depend on α.
3. Argue that any binary search tree has nonnegative potential and that a
(1/2)-balanced tree has potential 0. (4 points)
4. Suppose that m units of potential can pay for rebuilding and m-node
subtree. How large must c be in terms of α in order for it to take O(1)
amortized time to rebuild a subtree that is not α-balanced? (Hint: Think
about the potential before and after you rebuild the subtree. To be able
to have an O(1) amortized cost, you need to make sure that the change of
the potential is smaller than actual cost, m) (8 points)
5. Show that inserting a node into or deleting a node from an n-node
α-balanced tree cost O(logn) amortized time. (6 points)
Problem 6. What would you do, if you were the instructor of the ADA course, to
improve the atmosphere in the classroom? In other words, how do you encourage
more students to participate interactively in the lecture and to pay more
attention to the instructor? Feel free to comment on any other aspect of the
course too. (6 points)
┌────┐ ┌────┐
│ Ａ │－－→│ Ｂ │
↗└────┘＼ └────┘＼
＼ ＼ ↘
＼ ↘┌────┐ ↗＼
＼ │ Ｃ │／ ↘
＼ └────┘ ↗
＼ ／
＼ ／
＼ ┌────┐ ／
↘ │ Ｄ │／
└────┘
Figure 1: The block diagram of a multithreaded algorithm
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.249.220