课程名称︰演算法设计与分析 课程性质︰必修 课程教师︰苏雅韵 开课学院：电资学院 开课系所︰资工系 考试日期（年月日）︰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)