課程名稱︰演算法設計與分析
課程性質︰資工系 大二 必修
課程教師︰蔡欣穆
開課學院：電機資訊學院
開課系所︰資訊工程學系
考試日期（年月日）︰2014/11/13
考試時限（分鐘）：180分鐘
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
132 points in total
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 explanation.)
1. Showing a counterexample of a certain greedy choice proves the the pronlem
does not have the greedy property.
2. The bug report is usually closed by the person who fixed the bug.
3. nlogn is asymptotically larger than n.
4. √(nlogn) is polynomially larger than √n.
Problem 2. "Short answer" questions: (30 points)
1. Explain the difference between a functional specification and a technical
specification. (3 points)
2. What are the maximum numbers of edges in an undirected graph with n
vertices and a directed graph with n vertices, respectively? Assume that
there is no self-edge and they are not multigraph. (6 points)
3. Why is it necessary for the software tester to minimize the number of steps
to generate a bug? (3 points)
4. What are the 3 things that need to be in a bug report in a bug tracking
system? (6 points)
5. Write down the recurrences that represent the running time of the quick
sort algorithm in the worst case, and solve the recurrences. Assume that
the first number is always selected as the pivot in the quick sort
algorithm. The solution needs to be in the Θ-notation. (6 points)
6. Write down the recurrences that represent the running time of the quick
sort algorithm in the best case, and solve the recurrences. Assume that
the first number is always selected as the pivot in the quick sort
algorithm. The solution needs to be in the Θ-notation. (6 points)
Problem 3. In the lecture, we have shown you how to solve the closest pair of
2-dimensional points using a divide-and-conquer algotrithm that runs in
O(nlogn)-time. The problem gives you n 2-dimensional points (x1,y1),(x2,y2),..
..,(xn,yn), and asks you to find from these n points a pair of points that has
the smallest Euclidean distance,given by distE(A,B) = √((xA-xB)^2+(yA-yB)^2),
and to return the distance between this pair of points. (18 points)
1. Briefly describe the merge step of the divide-and-conquer algorithm
introduced in the lecture and explain why it can run in O(n)-time.
(6 points)
2. Now, instead of considering points in regular 2-dimensional space, consider
points in a "pacman-style" 2-dimensional space. This space is still
2-dimensional, but has a fixed width W and a fiexd height H. Therefore, we
have 0≦xi≦W and 0≦yi≦H, 1≦i≦n. In addition, the left and right
boundaries of the space are connected, and the top and bottom boundaries of
the space are also connected. For example, if W = H = 5, then the distance
between (1,1) and (1,4) and the distance between (1,1) and (4,1) are both
2, not 3; the distance between (1,1) and (4,4) is √8. Describe how you
would modify the existing algorithm to find the distance between the
closest pair of given points in the "pacman-style" 2-dimensional space.
(6 points)
3. Instead of using the definition of Euclidean distance, we would like to use
Manhattan distance to define "closeness". Manhattan distance between two
2-dimensional points is given by distM(A,B) = |xA - xB| + |yA - yB|.
Describe how you would modify the existing algorithm to find the distance
between the closest pair of given points (in regular 2-dimensional space,
not "pacman-style"). In particular, please describe in detail why the merge
step in the algorithm can run in O(n)-time. (6 points)
Problem 4. In the year of roughly 1997-2000, during the so-called dot-com
bubble, a large of high-speed fiber optical links were laid in many countries
in anticipation of a great increase of communication capacity around the
world. However, after the bubble burst, a large portion of these fiber links
were never fully utilized or even completely abandoned.
This also happened to Mizuki Kingdom. As explained before in the homework,
Mizuki Kingdom uses a highway to connect the cities. In particular, there is a
straight highway with cities alongside the highway. For convenience, the
highway is represented as an integer axis, and the position of each city is
denoted by a single integer coordinate. You can assume that there are no two
cities in the same position. There are n cities in Mizuki Kingdom, and the
coordinate of city i is c_i.
There are m abandoned fiber links in the Kingdom; the i-th fiber link runs
from coordinate s_i to coordinate e_i. These fiber links are all connected to
an old national network core center that is still operational, and thus any
city that is located in the range of a particular fiber link (i.e.,
s_i ≦ c_i ≦ e_i is satisfied), if the link is re-activated, is considered
online and is able to communicate with another city that is online (which can
be on another fiber link). The government of Mizuki Kingdom intends to bring
all cities online, using these abandoned high-speed fiber links; however, to
minimize the cost, the government would like to re-activate the least number
of fiber links to achieve the goal of having each city covered by at least one
fiber link. Your algorithm only needs to return the minimum required number of
fiber links to bring every city online. (26 points)
1. Show that this problem exhibits optimal substructure. Please clearly define
your subproblem in the proof. (4 points)
2. The SuperFast consulting agency comes up with a quick solution. The
solution uses a greedy choice which states that a fiber link that covers
the largest number of cities should always be selected first; if there are
multiple such links, then an arbitrary one among these links is selected.
Please present a counterexample to prove that this greedy choice dose not
always lead to an optimal solution. (4 points)
3. The NTU CSIE consulting agency decides to come up with another greedy
choice that works. Please come up with a greedy choice, and show that it
can always lead to an optimal solution. (6 points)
4. Assume the list of c_1,c_2,...,c_n is already sorted. Develop an algorithm
that runs in O(nm)-time to solve the problem, Write down the pseudo code
of your algorithm and analyze its time complexity. (6 points)
5. Develop an improved version of the algorithm that runs in O((n+m)log(n+m))-
time. Write down the pseudo code of your algorithm and analyze its time
complexity. (6 points)
Problem 5. The Longest Increasing Subsequence (LIS) problem is to fing the
length of the longest subsequence of a given sequence <a1,a2,...,an> of length
n such that all elements of the subsequence are sorted in increasing order.
This subsequence does not need to be contiguous in the original given
sequence. For example, the length of LIS for <10,22,9,33,21,50,41,60,80> is 6
and LIS is <10,22,33,50,60,80>. Assume that all numbers in the given sequence
are unique. Your algorithm only needs to return the length of LIS. (28 points)
1. Use an example to show that the number of increasing subsequence can be
superpolynomail in n. (4 points)
2. Suppose we would like to develop a dynamic programming algorithm to solve
this problem. We first define the subproblem S_i as finding LIS ending with
a_i, the i-th number in the given sequence. Write down the recurrences that
determines the length of LIS ending with a_i, L(i), 1≦i≦n. (4 points)
3. Show that this subproblem definition exhibits optimal substructure
property. (4 points)
4. Develop an O(n^2)-time dynamic programming algorithm to solve this problem.
Write down the pseudo-code of your algorithm and analyze its time
complexity. (6 points)
5. One way to improve the speed of the algorithm is to consider a greedy
choice stated as follows. Suppose there are k LIS of length m ending with
a_σ1,a_σ2,...,a_σk, m ≦σ1,σ2,...,σk ≦ n. When considering which of
these k LIS should be part of the solution of a larger subproblem (LIS of
a larger subproblem), we only need to consider LIS ending with min(a_σi),
1≦i≦k
i.e., the one with the smallest last number out of these k LIS. Prove that
this greedy choice exhibits greedy property. (4 points)
6. The greedy choice stated in the pervious problem implies that when
considering a number of LIS to be selected as part of the solution, we only
need to consider the choices of LIS of different lengths. Utilizing this,
develop an O(nlogn)-time algorithm to solve this problem. Write down the
pseudo-code of your algorithm and analyze its time complexity.
Hints: (a) Maintain a table which saves the last number of LIS of each
length. (b) Take advantage of the face that the entries in this table is
also an increasing sequence. (c) Note the logn term in the target O(nlogn)
time complexity. (6 points)
Problem 6. Use a recursion tree to determine a tight asymptotic upper bound on
the recurrence T(n) = 2T(n-1) + 1. Assume that T(1) = 1. Use the substitution
method to verify your answer. (8 points)
Problem 7. I have the tradition of letting the students write some feedbacks
about the course in the exam and I would like to continue this tradition.
Please write 3 things you like about this course and 3 things that you would
like to see some changes (and your suggestion about how we should change
them). Note that I have promised that you will have less difficult and less
amount of homework for the second half the semester, and thus there is no need
to include this in your 3 things. :) (6 points)