[試題] 101上 蔡欣穆 演算法設計與分析 期中考
課程名稱︰演算法設計與分析
課程性質︰必帶
課程教師︰蔡欣穆
開課學院：電機資訊學院
開課系所︰資訊工程學系
考試日期（年月日）︰101/11/8
考試時限（分鐘）：180
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Algorithm Design and Analysis, Fall 2012
Midterm Examination
128 points
Time: 2:20pm-5:20pm (180 minutes), Thursday, November 8 ,2012
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.(20 points. For each question,
1 point for the true/false answer and 3 points for the explanations.)
1.nlogn is asymptotically larger than n.
2.√n √logn is polynomially larger than √n.
3.The specification should be written by a group of people, as the result
of teamworks.
4.We can initialize a heap with only O(n) time.
5.Usually the bottom-up approach is less efficient than the top-down
approach when implementing a dynamic programming algorithm.
Problem 2. "Short answer" questions: (38 points)
1.Derive a Huffman code for the following frequencies of characters:
{a:100, b:300, c:300, d:400, e:600, f:700}.Draw the decoding tree for the
code you derive. (6 points)
2.Explain when the master theorem cannot be applied to solve the
recurrences (4 points)
3.Explain what a paper prototype is. Give two advantage of using a paper
prototype. (6 points)
4.Write down the recurrences that represent the running time of the quick
sort algorithm in the worst case, and solve the recurrences. (6 points)
5.Write down the recurrences that represent the running time of the quick
sort algorithm in the best case, and solve the recurrences. (6 points)
6.Explain the difference between functional specifications and technical
specifications. (4 points)
7.Recall the divide-and-conquer algorithm that we introduce to solve the
closest pair of points in 2D space problem in the lecture. Explain why
it only takes O(n) time to combine the solutions of the subproblems.
(6 points)
Problem 3. A palindrome is a string which is not changed when it is reversed.
For example, "ADA" and "BOB" are both palindromes. Derive an algorithm which
will convert a given string to a palindrome with a minimum number of insertions
of characters to the input string. Note that the maximum number of insertions
required for any input string with a length of n is n-1.
Examples:
abcd -> 3insertions, abcdcba
abababaabababa -> 0 insertions, abababaabababa
abcdbnmzabcd -> 7 insertions, abcdcbanzmznabcdcba
(22 points)
1.Write down recurrences which represent the cost of converting the string
to a palindrome. Please explain clearly what the parameters of your cost
function represent. (6 points)
2.Prove that this problem exhibits the optimal substructure property.
(6 points)
3.Write down the algorithm which uses dynamic programming to solve this
problem and outputs the minimum number of insertions. (6 points) What is
the time complexity of the algorithm? (4 points)
Problem 4. n people wish to cross a bridge at night. A group of at most two
people may cross at any time, and each group must have a flashlight. Only one
flashlight is available among the n people, so some sort of shuttle arrangement
must be arranged in order to return the flashlight so that more people may
cross. Each person has a different crossing speed and as a result the time for
different persons to cross the bridge is different. The time for two people to
cross the bridge is determined by the slower of the two. You are given a list
of people and the respective time for them to cross the bridge,{t_1,t_2,...,t_n
}. Your jobs is to determine the minimum time that gets all n people across the
bridge. (22 points)
1.Show that this problem exhibits the optimal substructure property and how
you define a subproblem. (6 points)
2.Derive the cost function using the recurrences. Explain what each
parameter of the cost function means. (6 points)
3.If you use dynamic programming to solve this problem, what would be the
time complexity? Please explain. (4 points)
4.Show a greedy strategy (choice) and prove that it exists in the optimal
solution. (6 points)
Problem 5. Use a recursion tree to give an asymtotically tight solution to the
recurrence T(n) = T(αn) + T((1-α)n) + cn, where α is a constant in the range
0<α<1 and c>0 is also a constant. Then, use the substitution method to prove
the solution. (10 points)
Problem 6. Assume you have an array A[1..n] of n elements. A majority element of
A is any element occurring in more than n/2 positions (so if n=6 or n=7, any
majority element will occur in at least 4 positions). Assume that elements
cannot be ordered or sorted, but can be compared for equality. (You might think
of the elements as chips, and there is a tester that can be used to determine
whether or not two chips are identical.) (10 points)
1.Design an efficient divide-and-conquer algorithm to determine whether a
majority element exists. (6 points)
2.Determine the time complexity of your algorithm. (4 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 down 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).
(6 points)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.25.108
※ 編輯: asjh612 來自: 140.112.25.108 (11/10 11:12)
推
11/10 18:10, , 1F
11/10 18:10, 1F
推
11/14 18:15, , 2F
11/14 18:15, 2F