课程名称︰算法
课程性质︰电子所核心二选一必修、电信电机生医电资所选修
课程教师︰陈和麟
开课学院：电机系
开课系所︰电机电信所
考试日期（年月日）︰109.11.09
考试时限（分钟）：180
试题 :
Please answer the following questions on the answer sheets provided. Be sure
to write your name and student ID on all answer sheets you use. This is a clo-
sed book exam. No books, notes, or calculators may be used during the exam wi-
th the exception of one double-sided, hand-written A4 note. Read all questions
first. You may not request for clarification after 9:40 am.
You may assume that all pairwise comparisons and arithmetic operations(ex. ad-
ditions and multiplications) take Θ(1) time. If you want to apply any result
or theorem that has been taught in class(including homeworks), you may do so
but you must state the result or theorem clearly before using it.
Problem 1. Let all functions be positive functions. Prove or disprove the fol-
lowing three statements. You may only use the definitions of asymptotic notat-
ions. Any other property of asymptotic notations must be proved before using.
Answering true/false without any explanation will not receive any credit.
1. (4%) log_2n ∈ O(lon_{10}n).
2. (8%) If f(n) ∈ Ω(g(n)), then either f(n) ∈ ω(g(n)) orf(n) ∈ Θ(g(n)).
3. (8%) If f(n) ∈ Ω(h(n)) and g(n) ∈ o(h(n)), then f(n)-g(n) ∈ Ω(h(n)).
Problem 2.
1. (5%) Solve T(n) = 4T(n/2) + n^2ln{n}, T(1) = 1. You only need to obtain the
asymptotic solution (in Θ() notation). If you use the master theorem, you mu-
st specify all parameters and briefly verify all conditions.
2. (10%) Let T(n) = 4T(floor{n/2} + 1) + n, for all n ≧ 8. T(5) = T(6) = T(7)
= 1. Prove that T(n) ∈ O(n^2) using substitution method.
Problem 3. (15%) Given n distinct real number a_1, a_2, ..., a_n (not sorted),
a_1 = 0 and a_2 = n. Your goal is to find a pair of numbers ai and aj such that
|ai - aj| > 1, but there is no other a_k with value in between. Design an O(n)-
time algorithm which finds one such pairs. Briefly justify the correctness and
the running time of the algorithm. (For example, if the input is 0,4,4.2,1.3,
the algorithm may output either (0,1.3) or (1.3,4)). You may assume that n is a
power of 2.
Problem 4. (15%) Given k sorted arrays of n/k elements each. An algorithm A me-
rges all k arrays into a single sorted array of n elements using only pairwise
comparisons. Formally prove that the time complexity of algorithm A is
Ω(nlogk).
In Problem 5 and 6, we consider a variation of the meeting selection problems
discussed in class. One day, Prof. Chen has n meetings M_1, M_2, ..., M_n on
his schedule. Meeting M_i starts at time s_i and ends at time t_i for every i.
He wants to select a set of meetings to attend, but if he choose to attend a
meeting, he is not allowed to arrive late or leave early.
Problem 5 In this problem, Prof. Chen tries to maximize the number of meetings
he can attend. This is exactly the problem we talked about in class. Analyze
one of the following greedy algorithms. (You must choose one between 5-1 and 5-
2 and indicate clearly. If you try to solve both problem, only 5-1 will be gra-
ded.)
1. (15%) Assume that the optimal solution chooses k meetings. Consider the gre-
edy problem which always selects the meeting with the least number of conflicts
. Prove that this algorithm always choose at least ceil{k/2} meetings or provi-
de a counter example.
2. (10%) Assume that the optimal solution chooses k meetings. Consider the gre-
edy problem which always selects the shortest meeting. Prove that this algorit-
hm always chooses at least ceil{k/2} meetings or provide a counter example.
Problem 6 In this problem, Prof. Chen wants to maximize the total meeting time
(instead of the number of meetings). Also, assume that t_1 ≦ t_2 ≦ ... ≦ t_n
. Solve the following two problems. (The additional assumption in 6-1 does not
apply in 6-2 and vice versa.)
1. (10%) Given an addition assumption that Prof. Chen must attend at least k m-
eetings. Design an algorithm to find the optimal set of meetings (which maximi-
zes the total meeting time). The running time of your algorithm must be polyno-
mial in nk). Briefly justify the corectness and analyze the running time.
2. (10%) Given an addition assumption: For every i, M_i and M_{i+2} cannot both
be attended, even if the meeting time does not conflict each other. Design an
algorithm to find the maximum total meeting time (you do not need to find the
optimal set of meetings). The running time must be polynomial in n. Briefly ju-
stify the corectness and analyze the running time.