算法分析算法復(fù)習(xí)題(中英文).doc

（有翻譯）1. The O-notation provides an asymptotic upper bound. The W-notation provides an asymptotic lower bound. The -notation asymptotically a function form above and below. O型符號提供一個漸近的上限。符號提供一個漸近下界。-符號漸近函數(shù)形式的上方和下方。2. To represent a heap as an array，the root of tree is A1, and given the index i of a node, the indices of its parent Parent(i) return i/2; ，left child, Left(i) return 2*i; ，right child, right(i) return 2*i + 1; .代表一個堆中的一個數(shù)組，樹的根節(jié)點是A1，并且給出一個節(jié)點i，那么該節(jié)點的父節(jié)點是 左孩子 右孩子 3. Because the heap of n elements is a binary tree, the height of any node is at most Q(lg n).因為n個元素的堆是一個二叉樹，任意節(jié)點的樹高最多是 4. In optimization problems , there can be many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution to the problem.在 最優(yōu)化問題 中，有很多可能的解，每個解都有一個值，我們希望找到一個最優(yōu)解（最大或最?。?，我們稱這個解為最優(yōu)解問題。5. optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems. 最優(yōu)子結(jié)構(gòu) 中問題的最優(yōu)解，至少包含它的最優(yōu)解的子問題。6. A subsequence of X if there exists a strictly increasing sequence of indices of X such that for all j = 1, 2, ., k, we have xij = zj .Let X = and Y = be sequences, and let Z = be any LCS of X and Y.(1). If xm = yn, then zk = xm = yn and Zk-1 is an LCS of Xm-1 and Yn-1.(2). If xm yn, then zk xm implies that Z is an LCS of Xm-1 and Y.(3). If xm yn, then zk yn implies that Z is an LCS of X and Yn-1.7. A greedy algorithm always makes the choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution.貪心算法 經(jīng)常需要在某個時刻尋找最好的選擇。正因如此，它在當(dāng)下找到希望中的最優(yōu)選擇，以便引導(dǎo)出一個全局的最優(yōu)解。8. The greedy-choice property and optimal sub-structure are the two key ingredients of greedy algorithm.貪心選擇 和最優(yōu)子結(jié)構(gòu)是貪心算法的兩個重要組成部分。9. When a recursive algorithm revisits the same problem over and over again, we say that the optimization problem has overlapping subproblems.當(dāng)一個遞歸算法一遍一遍的遍歷同一個問題時，我們說這個最優(yōu)化問題是 重疊子問題。10. greedy-choice property is a globally optimal solution can be arrived at by making a locally optimal (greedy) choice. 貪心選擇性質(zhì) 是一個全局的最優(yōu)解，這個最優(yōu)解可以做一個全局的最優(yōu)選擇。11. An approach of Matrix multiplication can develope a (V4)-time algorithm for the all-pairs shortest-paths problem and then improve its running time to (V3 lg V). 一個矩陣相乘問題的解決可以一個 時間復(fù)雜度算法的所有路徑的最短路徑問題，改進后的時間復(fù)雜度是 。12. Floyd-Warshall algorithm, runs in (V3) time to solve the all-pairs shortest-paths problem.FW算法在 時間復(fù)雜度下可以解決最短路徑問題。13. The running time of Quick Sort is O(n2) in the worst case, and O(n lg n) in the average case.快速排序的平均時間復(fù)雜度是 O(n lg n) ，最壞時間復(fù)雜度是 O(n2) 。14. The MERGE(A,p,q,r) procedure in merge sort takes time (n). MERGE在歸并排序中所花費的時間是 。15. Given a weighted, directed graph G = (V, E) with source s and weight function w : E R, the Bellman-Ford algorithm makes |V| - 1 passes over the edges of the graph.給一個帶權(quán)重的有向圖G = (V, E)，權(quán)重關(guān)系w : E R,則the Bellman-Ford算法需經(jīng)過 條邊。16. The Bellman-Ford algorithm runs in time O(V E).Bellman ford 算法的時間復(fù)雜度是 。17. A decision tree represents the comparisons made by a comparison sort.The asymptotic height of any decision tree for sorting n elements is W(n lg n).一個決策樹代表一個比較類型，通過比較排序。N個元素的任意決策樹的漸進高度是 。True-false questions 1. An algorithm is said to be correct if, for some input instance, it halts with the correct output F如果給一個算法輸入一些實例，并且它給力正確的輸出，則認識這個算法是正確的。2. Insertion sort always best merge sort F插入排序總是優(yōu)越與歸并排序。3. (n lg n) grows more slowly than (n2). Therefore, merge sort asymptotically beats insertion sort in the worst case. T(n lg n)4. Currently computers are fast and computer memory is very cheap, we have no reason to study algorithms. F5. In RAM (Random-Access Machine) model, instructions are executed with concurrent operations. F6. The running time of an algorithm on a particular input is the number of primitive operations or “steps” executed. T7. Quick sorts, have no combining step: two subarrays form an already-sorted array. T8. The running time of Counting sort is O(n + k). But the running time of sorting is W(n lg n). So this is contradiction. F9. The Counting sort is stable. T10. In the selection problem, there is a algorithm of theoretical interest only with O(n) worst-case running time. T11. Divide-and-conquer algorithms partition the problem into independent subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem. In contrast, dynamic programming is applicable when the subproblems are not independent, that is, when subproblems share subsubproblems. T12. In dynamic programming, we build an optimal solution to the problem from optimal solutions to subproblems. T13. The best-case running time is the longest running time for any input of size n. F14. When we analyze the running time of an algorithm, we actually interested on the rate of growth (order of growth). T15. The dynamic programming approach means that it break the problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblems recursively, and then combine these solutions to create a solution to the original problem. T16. Insertion sort and merge sort both use divide-and-conquer approach. F17. (g(n) = f (n) : there exist positive constants c1, c2, and n0 such that 0 c1 g(n) f (n) c2 g(n) for all n n0 18. Min-Heaps satisfy the heap property: AParent(i) Aifor all nodes i 1. F19. For array of length n, all elements in range An/2 + 1 . n are heaps. T20. The tighter bound of the running time to build a max-heap from an unordered array isnt in linear time. F21. The call to BuildHeap() takes O(n) time, Each of the n - 1 calls to Heapify() takes O(lg n) time, Thus the total time taken by HeapSort() = O(n) + (n - 1) O(lg n)= O(n) + O(n lg n)= O(n lg n). T22. Quick Sort is a dynamic programming algorithm. The array Ap.r is partitioned into two non-empty subarrays Ap.q and Aq+1.r, All elements in Ap.q are less than all elements in Aq+1.r, the subarrays are recursively sorted by calls to quicksort. F23. Assume that we have a connected, undirected graph G = (V, E) with a weight function w : E R, and we wish to find a minimum spanning tree for G. Both Kruskal and Prim algorithms use a dynamic programming approach to the problem. F24. A cut (S, V - S) of an undirected graph G = (V, E) is a partition of E. F25. An edge is a light edge crossing a cut if its weight is the maximum of any edge crossing the cut. F26. Kruskals algorithm uses a disjoint-set data structure to maintain several disjoint sets of elements. T27. Optimal-substructure property is a hallmark of the applicability of both dynamic programming. T28. Dijkstras algorithm is a dynamic programming algorithm. F29. Floyd-Warshall algorithm, which finds shortest paths between all pairs of vertices , is a greedy algorithm. F30. Given a weighted, directed graph G = (V, E) with weight function w : E R, let p = be a shortest path from vertex v1 to vertex vk and, for any i and j such that 1 i j k, let pij = be the subpath of p from vertex vi to vertex vj . Then, pij is a shortest path from vi to vj. T31. Given a weighted, directed graph G = (V, E) with weight function w : E R,If there is a negative-weight cycle on some path from s to v , there exists a shortest-path from s to v. F32. Since any acyclic path in a graph G = (V, E) contains at most |V| distinct vertices, it also contains at most |V| - 1 edges. Thus, we can restrict our attention to shortest paths of at most |V| - 1 edges. T33. The process of relaxing an edge (u, v) tests whether we can improve the shortest path to v found so far by going through u. T34. In Dijkstras algorithm and the shortest-paths algorithm for directed acyclic graphs, each edge is relaxed exactly once. In the Bellman-Ford algorithm, each edge is also relaxed exactly once . F35. The Bellman-Ford algorithm solves the single-source shortest-paths problem in the general case in which edge weights must be negative. F36. Given a weighted, directed graph G = (V, E) with source s and weight function w : E R, the Bellman-Ford algorithm can not return a Boolean value indicating whether or not there is a negative-weight cycle that is reachable from the source. F37. Given a weighted, directed graph G = (V, E) with source s and weight function w : E R, for the Bellman-Ford algorithm, if there is such a cycle, the algorithm indicates that no solution exists. If there is no such cycle, the algorithm produces the shortest paths and their weights. F38. Dijkstras algorithm solves the single-source shortest-paths problem on a weighted, directed graph G = (V, E) for the case in which all edge weights are negative. F39. Dijkstras algorithm solves the single-source shortest-paths problem on a weighted, directed graph G = (V, E) for the case in which all edge weights are nonnegative. Bellman-Ford algorithm solves the single-source shortest-paths problem on a weighted, directed graph G = (V, E), the running time of Dijkstras algorithm is lower than that of the Bellman-Ford algorithm. T40. The steps for developing a dynamic-programming algorithm:1. Characterize the structure of an optimal solution. 2. Recursively define the value of an optimal solution. 3. Compute the value of an optimal solution in a bottom-up fashion. 4. Construct an optimal solution from computed information. T三 Each of n input elements is an integer in the range 0 to k, Design a linear running time algorithm to sort n elements.四Design a expected linear running time algorithm to find the ith smallest element of n elements using divide and conquer strategy.五Write the INSERT-SORT procedure to sort into non-decreasing order. Analyze the running time of it with RAM Model. Whats the best-case running time, the worst-case running time and average case running time. Write the MERGE-SORT procedure to sort into non-decreasing order. Give the recurrence for the worst-case running time T(n) of Merge sort and find the solution to the recurrence.六 What is an optimal Huffman code for the following set of frequencies, 七 The traveling-salesman problem (TSP): in the traveling-salesman problem, we are given a complete undirected graph G=(V,E) that has a nonnegative integer cost c(u,v) associated with each edge (u,v)E , and we must find a tour of G with minimum cost. The following is an instance TSP. Please compute a tour with minimum cost with greedy algorithm. 八Given items of different values and weights, find the most valuable set of items that fit in a knapsack of fixed weight C .For an instance of knapsack problem, n=8, C=110,value V=11,21,31,33,43,53,55,65 weight W=1,11,21,23,33,43,45,55. Use greedy algorithms to solve knapsack problem. 九Use dynamic programming to solve Assembly-line scheduling problem: A Motors Corporation produces automobiles that has two assembly lines, numbered i=1,2. Each line has n stations, numbered j=1,2n. We denote the jth station on line i by Sij. The following figure is an instance of the assembly-line problem with costs entry time ei, exit time xi, the assembly time required at station Sij by aij, the time to transfer a chassis away from assembly line I after having gone through station Sij is tij. Please compute the fastest time and construct the fastest way through the factory of the instance. 7 9 3 4 8 4 2 3 2 3 1 3 4entrance exit 2 1 2 2 1 4 28 5 6 4 5 7十. The matrix-chain multiplication problem can be stated as follows: given a chain of matrices, where for i=1，2，n, matrix Ai has dimension P i-1 Pi, fully parenthesize the product A1,A2,An in a way that minimizes the number of scalar multiplication. We pick as our subproblems the problems of determining the minimum cost of a parenthesization of Ai Ai+1 Aj for 1 i j n. Let mi, j be the minimum number of scalar multiplications needed to compute the matrix Ai.j; for the full problem, the cost of a cheapest way to compute A1.n would thus be m1, n. Can you define mi, j recursively? Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is 十一 In the longest-common-subsequence (LCS) problem, we are given two sequences X = and Y = and wish to find a maximum-length common subsequence of X and Y. Please write its recursive formula and determine an LSC of Sequence S1=ACTGATCG and sequence S2=CATGC. Please fill in the blanks in the table below. C A T G CACTGATCG 十二 Proof: Any comparison sort algorithm requires (nlgn) comparisons in the worst case.Howmanyleavesdoesthetreehave?（葉節(jié)點的數(shù)目）Atleastn!(eachofthen!permutationsiftheinputappearsassomeleaf)n!l（至少n!個，排列）Atmost2hleaves（引理，至多2h個）n!l2hhlg(n!)=(nlgn)十三Proof: Subpaths of shortest paths are shortest paths. Given a weighted, directed graph G = (V, E) with weight function w : E R, let p = be a shortest path from vertex v1 to vertex vk and, for any i and j such that 1 i j k, let pij = be the subpath of p from vertex vi to vertex vj . Then, pij is a shortest path from vi to vj.十四Proof : The worst case running time of quicksort is (n2) 十五Compute shortest paths with matrix multiplication and the Floyd-Warshall algorithm for the following graph.十六 Write the MAX-Heapify() procedure to for manipulating max-heaps. And analyze the running time of MAX-Heapify().三（10分)1CountingSort(A, B, k)2for i=1 to k3Ci= 0;4for j=1 to n5CAj += 1;6for i=2 to k7Ci = Ci + Ci-1;8for j=n downto 19BCAj = Aj;10CAj -= 1;四算法描述3分The best-case running time is T(n) = c1n + c2(n - 1) + c4(n - 1) + c5(n - 1) + c8(n - 1)= (c1 + c2 + c4 + c5 + c8)n - (c2+ c4 + c5 + c8). This running time can be expressed as an + b for constants a and b that depend on the statement costs ci ; it is thus a linear function of n.This worst-case running time can be expressed as an2 + bn + c for constants a, b, and c that again depend on the statement costs ci ; it is thus a quadratic function of n.分析2分算法描述2分(1) if n = 1T(n) = 2T(n/2) + (n) if n 1.遞歸方程和求解3分五7 RAND-SELECT(A, p, r, i) (5分)if p = r then return Apq RAND-PARTITION(A, p, r)k q p + 1 if i = k then return Aqif i kthen return RAND-SELECT(A, p, q 1, i )else return RAND-SELECT(A, q + 1, r, i k )Randomized RANDOMIZED-PARTITION(A; p; r) (5分) i RANDOM(p, r) exchange Ar Aireturn PARTITION(A; p; r)PARTITION(A; p; r) x Ari p-1for j p to r-1do if Aj xthen i i+1exchange Ai Ajexchange Ai+1 Arreturn i+1六首先畫出它對應(yīng)的圖，加上標(biāo)號，假設(shè)從1出發(fā)，每次貪心選擇一個權(quán)重最小的頂點作為下一個要去的城市。(算法策略5分)求解過程5分七 a:1 b:100 c:101 d:111 e:1100 f:1101 八 V=11,21,31,33,43,53,55,65 weight W=1,11,21,23,33,43,45,55按照單位重量的價值排序，然后按照該順序往背包中放。九遞歸方程4分f11=9 f21=12f12=18 f22=16f13=20 f23=22f14=24 f24=25f15=32 f25=30f16=35 f26=37the fastest time is 38 and the fastest way is:station 1:line 1station 2:line 2station 3:line 1station 4:line 2station 5: line 2station 6: line 1求解過程6分十遞歸方程4分m1,1=0 m2,2=0 m3,3=0 m4,4=0m1,2=m1,1+m2,3+p0*p1*p2=60m2,3=m2,2+m3,3+p1*p2*p3=30m3,4=m3,3+m4,4+p2*p3*p4=30m1,3=minm1,2+m3,3+p0*p2*p3, m1,1+m2,3+p0*p1*p3=54m2,4=minm2,3+m4,4+p1*p3*p4, m2,2+m3,4+p0*p2*p4=48m1,4=minm1,1 +m2,4+p0*p1*p4, m1,2