課程名稱︰演算法設計與分析
課程性質︰必修
課程教師︰蘇雅韻
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2011.11.18
考試時限（分鐘）：170分鐘
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題：
˙ Do not open this booklet until you are directed to do so. Read all the
instructions on this page.
˙ When the quiz begins, write your name on every page of this quiz booklet.
˙ This exam is closed book. You may use one handwritten A4 sheet.
˙ Do not waste time and paper rederiving facts that we have studied. It is
sufficient to cite known results.
˙ Do not spend too much time on any one problem. Read them all through first,
and attack them in the order that allows you to make the most progress.
˙ Show your work, as partial credit will be given. You will be graded not
only on the correctness of your answer, but also on the clarity with which
you express it. Be neat.
˙ Good luck!
Problem 1 Substitution method
[10 points, 3 points for (a) and 7 points for (b)]
For the recurrence of T(n) = T(n/2) + T(n/4) + n
(1) Draw a recursion tree to derive a guess for its upper bound
(2) Use substitution method to prove the upper bound you derived from (1)
Problem 2 True or False, and Justify
[30 points total, 3 points each]
Circle T or F for each of the following statement. If the statement is
correct, briefly state why. If the statement is wrong, explain why. Your
justification should be brief but to the point, and it is worth more points
than your true-or-false designation.
(1) Asymptotic notations. Note: please prove using definition.
a. T F If g(n) = O(f(n)) , and g(n) = Ω(f(n)), then g(n) = θ(f(n))
b. T F If g(n) = o(f(n)) , it is possible that g(n) = Ω(f(n))
c. T F If g(n) = ω(f(n)) , then g(n) = Ω(f(n))
d. T F If g(n) = O(f(n)) , then g(n) = o(f(n))
e. T F If g(n) = θ(nlogn) , then g(n) = ω(n)
f. T F If g(n) = θ(nlogn) , then g(n) = o(n^2)
(2) T F We covered a selection algorithm that can find the i-th smallest
element in an array of n elements in linear time. In the algorithm,
the input elements are divided into groups of 5. If the input
elements are divided into groups of 7, the total running time will
still be linear.
(3) T F The solution to the recurrence for T(n) = 3T(n/3) + O(nlgn) is
T(n) = θ(nlgn)
(4) T F If we need to be able to quickly determine if an edge connects two
vertices, adjacency list is the preferred way to represent a graph.
(5) T F Given a file with 31 characters and the following frequencies
┌─────┬──┬──┬──┬──┬──┐
│Character │a │b │c │d │e │
├─────┼──┼──┼──┼──┼──┤
│Frequency │16 │8 │4 │2 │1 │
└─────┴──┴──┴──┴──┴──┘
Using Huffman encoding, we need a total of 56 bits to encode this
file. (Please show the codeword for each character to receive full
credits.)
Problem 3 Graph
[20 points, 5 points each]
The diameter of a tree (sometimes called the width) is the number of nodes on
the longest path between two leaves in the tree.
(1) Please describe a brute-force algorithm for finding the diameter of a
binary tree based on BFS, and state your running time.
(2) Given a node V, which is on the longest path of the two leaves, describe
an algorithm which can determine the diameter of a binary tree in O(n)
time? (n: number of vertices. Hint: Given any two vertices on a tree,
there is a unique simple path between them.)
(3) Describe an algorithm that finds the diameter of a binary tree in O(n)
running time.
(4) Prove the correctness of your algorithm.
Problem 4 Dynamic Programming
[20%, 10 points for (1) and 5 points for (2) and (3) each]
A divide-and-conquer algorithm is presented to solve the maximum subarray
problem in class. You are given the same input: an array A of daily stock
prices, {P_1, P_2, ... ,P_n}, which is the price between day 1 ... n, and the
same trading rules. That is, you can buy one unit of stock only one time and
sell it at a later date.
(1) Design an algorithm that can determine (a) the maximum profit is and
(b) print out which day to buy and which day to sell the stock to maximize
your profit based on dynamic programming strategy.
(2) Analyze the time complexity of your algorithm.
(3) Prove the optimal substructure of your algorithm. That is, prove that the
solution to maximum subarray of array A[1 ... n] utilizes the solution to
maximum subarray of A[1 ... n-1].
Problem 5 Greedy algorithm
[15%, 5 point each]
You are given an array of elements, n elements in the array are marked, and a
number m. The index of marked elements is given to you as a sequence of
<i_1, i_2, ..., i_n>. You need to find m subarrays to cover all marked
elements. Please design an algorithm such that the total length of the m
subarrays is minimal.
Note the total length of m subarrays = Σ(i = 1 to m) length of subarray (i).
Also, we assume n≧m≧2.
For example, given the array below and four elements are marked
(Element 2, 5, 8, and 10 are marked, therefore, n=4). If m=2, then the minimum
total length is 7.
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│ │X │ │ │X │ │ │X │ │X │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
┌──┬──┬──┬──┐ ┌──┬──┬──┐
│ │ │ │ │ │ │ │ │
└──┴──┴──┴──┘ └──┴──┴──┘
Subarray 1, length = 4 Subarray 2, length = 3
Total length = 4+3 = 7
(1) Given the example above, what is the minimal total length if m = 3.
(a) Mark your subarrays 1, 2, and 3.
(b) Show the total length.
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│ │X │ │ │X │ │ │X │ │X │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
(2) Describe your greedy algorithm.
(3) Prove that your greedy choice is correct for your algorithm.
Problem 6 Graph
[20 points, 5 point each]
(1) Given the graph, please mark the finishing time of the DFS algorithm we
learned in class starting from A (assume vertices are explored in
lexicographical order, that is explore A before B). Assume vertices in
adjacency list are sorted in lexicographical order, e.g. when exploring
vertex D, explore D-E before D-F.
┌─┐
│Ｃ│
╱└─┘╲
┌─┐↙ │ ↘┌─┐
│Ａ│ │ │Ｅ│
└─┘ ↓ ↗└─┘
│↑ ┌─┐╱ │
││ │Ｄ│ │
↓│ └─┘╲ ↓
┌─┐ ↑ ↘┌─┐
│Ｂ│ │ │Ｆ│
└─┘↖ │ ╱└─┘
╲┌─┐↙
│Ｇ│
└─┘
(2) Show G^T of the graph from (1).
(3) Describe how you would find strongly-connected-components using the
information you derived from (1) and (2). Then, write down the
strongly-connected-components you found.
(4) Run BFS on the undirected version of on G (that is we consider edge
u→v and v→u to be the same) starting from A. Assume vertices in
adjacency list are sorted in lexicographical order. List the vertices in
the order in which the vertices are enqueued on the FIFO queue during the
exploration.
Ａ
￣ ￣ ￣ ￣ ￣ ￣ ￣
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.167.189.146
※ 編輯: rod24574575 來自: 218.167.189.146 (01/17 14:20)