課程名稱︰ 演算法
課程性質︰ 電機系 系定選修
課程教師︰ 張耀文
開課學院： 電資學院
開課系所︰ 電機系
考試日期（年月日）︰ 98/11/05
考試時限（分鐘）： 150分鐘
是否需發放獎勵金： 是
（如未明確表示，則不予發放）
試題 :
Instructions. This is a 150-minute test, with a total of 107 points available.
There are four pages and seven problems. Pace Yourself and Good Luck!
Problem 1. (15 pts total)
For each of the following recurrence relations, give the asymptotic growth
rate of the solution using the Θ notation. Assume for each case that T(n) is
Θ(1) for n≦8.
(a) (5 pts) T(n) = 3T(n/2) + n.
(b) (5 pts) T(n) = 2T(n/4) + nlgn.
(c) (5 pts) T(n) = 4T(√n) + (lgn)^2.
Problem 2. (32 pts total)
Please give a brief answer for each of the following questions.
Q1. For the following three functions, rand them from the slowest (with the
lowest complexity) to the fastest growing: (lgn)!, n^(1/lgn), (√n)^lgn.
Q2. Let f(n) and g(n) be asymptotically positive, is
max(f(n),g(n)) = O(f(n)+g(n))? Why?
Q3. Is it true that any comparison sort of 5 elements requires at least 7
comparisons in the worst case? Why?
Q4. Consider a variant of QUICKSORT, such that each time PARTITION is called,
the median of the partitioned array is found (by using the SELECT
algorithm) and used as a pivot. What is the running time of this algorithm?
Why?
Q5. Is it true that counting sort will always sort an array of n integers from
{1, 2, ..., m} in O(n) time? Why?
Q6. Can we put the numbers 1, 2, ..., 7 in a tree such that it is both a valid
max-heap and binary search tree at the same time? Why?
Q7. We typically need extra time to maintain the information for red-black
trees, why are they still useful as compared to standard binary search
trees?
Q8. Consider the following algorithm for computing the square root of a number:
SQUARE-ROOT(x)
for i=1, ..., x/2
if i^2 = x then output i.
Is it true that this algorithm runs in polynomial time? Why?
Problem 3. (10 pts total)
Let X[1..n] and Y[1..n] be two arrays, each containing n numbers already in
sorted order. Give an algorithm to find the median of all 2n elements in arrays
X and Y. (Partial credits will be given for an algorithm with higher time
complexity.)
Problem 4. (14 pts total)
Elephants (Brothers) and Lions (Uni-President) baseball teams are competing
for the 2009 CPBL Championship. Both teams play a series of games until one of
the teams wins n games. Assume that the probability of the Elephants Baseball
Team winning a game is the same for each game and equal to p and the
probability of losing a game is q = 1-p. (Hence, there are no ties.) Let P(i,j)
be the probability of Elephants winning the series if Elephants need i more
games to win the championship and Lions needs j more games to win the
championship.
(a) (6 pts) Find the optimal substructure (a recurrence relation for P(i,j)).
(b) (3 pts) A few Elephants players are involved with gambling scandals, and
thus the probability of the team winning a game is only 0.4. Find the
probability of the Elephants team winning a 3-game series.
/* 助教說明: 3-game series 為3戰2勝制 */
(c) (5 pts) Give a dynamic programming algorithm for solving the problem. What
are the time and space complexity of your algorithm?
Problem 5. (14 pts total)
Suppose you are given three strings of characters: X= x1x2...xm, Y= y1y2...yn,
and Z= z1z2...zm+n. Z is said to be a shuffle of X and Y if Z can be formed by
interspersing the characters from X and Y in a way that maintains the left-to-
right ordering of the characters from each string. For example,
"cchocohilaptes" is a shuffle of "chocolate" and "chips", but "chocochilatspe"
is not.
(a) (7 pts) Find the optimal substructure (i.e., derive the recurrence for a
problem and its subproblems). (Hint: Recall what we did for the LCS problem
discussed in class.)
(b) (7 pts) Design a dynamic programming algorithm Is_Shuffle that takes as
inputs X, Y, Z, m, and n, and determines whether Z is a shuffle of X and Y.
(Hint: Algorithm Is_Shuffle uses table s of Boolean entries to store the
results: s[i,j] is TRUE if and only if Zi+j = shuffle(Xi,Yj), for every
i,j, 1≦i≦m, 1≦j≦n.) What is the running tiem of your algorithm?
Problem 6. (18 points total)
Search trees. Partial pseudocodes for inserting/deleting a node in a red-black
tree are given in the next page. /* pseudocode講義、課本都有 這裡省略 */
(a) (4 pts) Give the binary search tree that results from successively inserting
the keys 7,8,2,1,4,3,5,9 into an initially empty tree.
(b) (4 pts) Label each node in the tree with R or B denoting the respective
colors RED and BLACK so that the tree is a legal red-black tree.
(c) (5 pts) Give the red-black tree that results from inserting the key 6 into
the tree of (b).
(d) (5 pts) Give the red-black tree that results from deleting the key 1 from
the tree of (b) (notice that it is (b), not (c)).
Problem 7. (4 pts total)
Please give two of your opinion(s)/comment(s) on this course (e.g., strengths
and weaknesses)? Any specific comments that may improve the quality of this
course are very much welcome. Thank you.
--
◢██ ◥██ ◢█◣ ◥█◣ ◥█◣ ◥ █ ◥█◣ ◢█◣◥██ ◣ ◥◣█
█◥▇ ◥ ▆█ ▆█ ▆█ ◣◥◤ ▊█ ▆█ ◥█ █ ◥█
▇█◥ ◥ ◥◣ ◥◣ ◤ ◥ ▏ ◥██ ◥◥
Ｐ２個版：starrydawn ψshinchen(ptt)
shincheng(ptt2)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.243.5