課程名稱︰資料結構與演算法下
課程性質︰系必修
課程教師︰蔡欣穆
開課學院：電資學院
開課系所︰系訊系
考試日期（年月日）︰2011/4/22
考試時限（分鐘）：180min
是否需發放獎勵金：是的，感謝
（如未明確表示，則不予發放）
試題 :
Prob1.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.
(20 points. For each question, 1 point for the true/false answer and 3
points for the explanations.)
1.n㏒n is polynomially larger than n.
2.n^(1+10^(-100)) is polynomially larger than n㏒n.
3.As long as a problem exhitbits optimal substructure, it can be solved by
using a greedy algorithm.
4.The solution of T(n)=4T(n/2)+n^2 is T(n)=Θ(n㏒n).
5.As long as a recurrence is of the form T(n)=a(Tn/b)+f(n), it can be solved
by using the master method.
Prob2."Short answer" questions: (25 points)
1.What is the main job of a Quality Assurance(QA) engineer in a software
company?(4 points)
2.Give a formal definition of "uniform random permutation".(4 points)
3.Derive an optimal Huffman code for the frist n Fibonacci numbers, i.e.,
{C1:1 C2:1 C3:2 C4:3 C5:5 C6:8 C7:13 C8:21 ... Cn:F(n)}. in other words, show
the general form of the codeword for the i-th charater Ci(with F(i) as its
frequency). (5 points)
4.Give two reasons for implementing the paper prototype instead of the "real"
prototype in a software project. (4 points)
5.How do we roughly estimate the cost of a software product? (4 points)
6.Give two reasons for writing down the specifications of a software project
before we start writing codes.(4 points)
Prob3.Given a list of n distinct numbers (not sorted), please derive a divide-
and-conquer algorithm to return the first k smallest numbers in the list.
Your algorithm should have a running time of O(n). Note that you cannot
use the number selection algorithm taught in the class for k times, as
the running time will be Θ(kn)=O(n^2). Sorting does not work either as
it will take O(n㏒n). In addition to the algorithm, please write down the
recurrence representing the running time, solve the recurrence, and prove
your solution by induction.(15 points, 7 points for the algorithm, 3
points for the recurrence, and 5 points for the proof)
Prob4.Use the recursion-tree method to derive an asymptotic tight upper bound
for T(n)=T(n/2)+T(n/4)+T(n/8)+n. You can assume that T(n) is a constant
when n is sufficiently small. Prove that your bound is correct by
induction.(10 points, 5 points for the recursion-tree and 5 points for
proof)
Prob5.For bit strings X=X1...Xm, Y=Y1...Yn and Z=Z1...Zm+n, we say that Z is an
interleaving of X and Y if it can be obtained by interleaving the bits in
X and Y in a way that maintains the left-to-right order of the bits in X
and Y. For example if X=101 and Y=01 then X1X2Y1X3Y2=10011 is an
interleaving of X and Y, whereas 11010 is not.(15 points)
1.Please come up with the definition of the subproblem. Use your definition and
prove that this problem has optimal substructure. (5 points)
2.Give the most efficient algorithm you can to determine if Z is an
interleaving of X and Y. (7 points)
3.Analyze the time complexity of your algoithm as a function m=|X| and n=|Y|
Prob6.Consider the problem of making change for n dollars using the fewest
number of coins. Assume that each coin's value is an integer. The same
coin can be used for any number of times in the change. (25 points)
1.Prove that the problem exhibits optimal substructure. (5 points)
2.Assume the following set of coins is available to you:1,5,10,50. Prove that
under this codition, the problem ahs the greedy property. (5 points)
3.Describe a greedy algorithm to solve the problem with the coin set in 2.
4.Give a set of coins for which the greedy algorithm in 3 does not yield an
optimal solution. Your set should nclude a one-dollar coin so that there is a
solution to every value of n. Explain the intuition behind your choice of
coins in the set. (3 points)
5.Describe a dynamic programming algorithm which solve the problem with any
coin set with k different coins, assuming that one of them is a one-dollar
coin. (7 points)
Prob7.This problem examines three algorithms for searching for a value x in an
unsorted array A consisting of n elements(x appears in A for k times,
k≧0): (20 points)
˙Algorithm α: We pick a random index i into A. If A[i]=x, then we terminate;
otherwise, we continue the search by picking a new random index into A. We
continue picking random indices into A until we find an index j such that
A[j]=x or until we have checked every element of A. Note that we pick from
the whole set of indices each time, so that we may examine a give element
more than once.
˙Algorithm β: The algorithm searches A for x in order, considering A[1],A[2],
...,A[n] until either it finds A[i]=x or it reaches the end of the array.
Assume that all possible permutations of the input array are equally likely.
˙Algorithm γ:We uniformly and randomly permute the input array A and then run
Algorithm β
1.For each algorithm, derive the expected running time when (a)k=0 (b)k≧1.
(18 points, 3 points for each answer)
2.Which algorithm would you use? Please explain your answer. (2 points)
Prob8.This semestere we made lots of changes in the course compared to last
semester (homeworks, programming assignments, course content), and we
are curious about how you feel about the current form of the course. If
you have the power of changing 3 things in the course, what would these 3
things be and how would you change them? Your feedbacks are very
important to the teaching team; we thank you for your valuable opinion.:)
(10 points)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.193.6.232