举报 相似

算法导论-课后题答案

第 1 页 / 共 26 页
亲,该文档支持全文预览,点击此可以查看更多
资源描述:
Partial Solutions for Introduction to algorithms second edition Professor: Song You TA: Shao Wen ACKNOWLEDGEMENT CLASS ONE: JINZI CLASS TWO: LIUHAO, SONGDINMIN, SUNBOSHAN, SUNYANG CLASS FOUR:DONGYANHAO, FANSHENGBO, LULU, XIAODONG, CLASS FIVE:GAOCHEN, WANGXIAOCHUAN, LIUZHENHUA, WANGJIAN, YINGYING CLASS SIX: ZHANGZHAOYU, XUXIAOPENG, PENGYUN, HOULAN CLASS: LIKANG,JIANGZHOU, ANONYMITY The collator of this Answer Set, SHAOWen, takes absolutely no responsibility for the contents. This is merely a vague suggestion to a solution to some of the exercises posed in the book Introduction to algorithms by Cormen, Leiserson and Rivest. It is very likely that there are many errors and that the solutions are wrong. If you have found an error, have a better solution or wish to contribute in some constructive way please send an Email to shao_wen_buaa@163.com It is important that you try hard to solve the exercises on your own. Use this document only as a last resort or to check if your instructor got it all wrong. Have fun with your algorithms and get a satisfactory result in this course. Best regards, SHAOWen Chapter one Exercises 1.1-2 Other than speed, what other measures of efficiency might one use in a real-world setting? 空间,硬件资源等 Exercises 1.1-4 (class two 刘浩刘浩) How are the shortest-path and traveling-salesman problems given above similar? How are they different? 相似点:找出最短路径 不同点:shortest-path 不一定经过所有点,而 traveling-salesman 得经过所有点 Exercises 1.2-2 Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in 64n lg n steps. For which values of n does insertion sort beat merge sort? 插入排序的性能优于合并排序也就是:插入排序所用的步数少: 所以有:8n2≤ 64nlgn ? n 0 and A[i] key 6 do A*i+1+ ← A*i+ 7 i ← j – 1 8 A*i+1+ ← key 图解: 31 41 59 26 41 58 31 41 59 26 41 58 31 41 59 26 41 58 26 31 41 59 41 58 26 31 41 41 59 58 26 31 41 41 58 59 Exercises 2.3-1 (class five 高晨高晨) Using Figure 2.4 as a model, illustrate the operation of merge sort on the array A = 〈〈3, 41, 52, 26, 38, 57, 9, 49〉〉. 如下所示: 3,9,26,38,41,49,52,57 3,26,41,52 9,38,49,57 3,41 26,52 38,57 9,49 3 41 52 26 38 57 9 49 Exercises 2.3-3 (class six 侯岚侯岚) Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence ? ? = ? ?? ? = ? ?? ? ? +? ?? ? = ? ?,??? ? 1 is T(n)=nlgn. 由题意得: 根据数学归纳法: 给出基本条件(base case) : 当 n=2 时,T(2)= 2 lg2 = 2。符合条件。 给出假设: 当 n=2t 时,T(2t)= 2t lg2t成立。 那么, 当 n=2t+1 时,T(2t+1)= 2 T(2t+1 /2)+ 2t+1 = 2T(2t)+2t+1 = 2(2tlg2t)+2t+1 = 2t+1lg2t+1 所以,得证! Exercises 2.3-5 Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. Binary search is an algorithm that repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is Θ(lg n). 给出一个递归算法. 显然最坏情况的运行时间为(lg n). BINARY-SEARCH(A, v, p, r) if p ≥ r and v ≠ A[p] then return nil end if?n/2? j←A[? (r - p)/2?] if v = A[j] then return j else if v A[mid] then 21 Low ← mid + 1 22 for i ← mid to j – 1 23 A[i+1] ← a[i] 24 A[mid] ← key 在最坏情况下,二分查找的时间复杂度是 nlgn,但插入时数组移动的时间复杂度仍是 n2。 故总体运行时间不能改善为 Θ(n lg n)。 (但若排序中采用链表的数据结构,则可改善。 ) Problems 2-1: Insertion sort on small arrays in merge sort (class two 刘浩刘浩) Although merge sort runs in Θ(n lg n) worst-case time and insertion sort runs in Θ(n2) worst-case time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense to use insertion sort within merge sort when subProblems become sufficiently small. Consider a modification to merge sort in which n/k sublists of length k are sorted using insertion sort and then merged using the standard merging mechanism, where k is a value to be determined. a. Show that the n/k sublists, each of length k, can be sorted by insertion sort in Θ(nk) worst-case time. 在最坏情况下,插入排序的运行时间为 Θ(n2),由于每个字列表的长度为 k,则对每个 字列表进行插入排序需要的时间为 Θ(k2),而一共有 n/k 个字列表,则所需总时间为 n k × Θ k2 = Θ(nk) b. Show that the sublists can be merged in Θ(n lg (n/k) worst-case time. 在最坏情况下,按照条件: T n = ck, n = k 2T n 2 + cn, n ? 其中k为一常数 画出递归树, 递归树每层的代价都为cn,其中最后一层有n k 个规模为ck的节点,而递 归树一共有lg(n k)+1层。所以总代价为cnlg( n k)+cn,为Θ(n lg(n/k)) Problems 2-2: Correctness of bubblesort (class five 董亮董亮) Bubblesort is a popular sorting algorithm. It works by repeatedly swapping adjacent elements that are out of order. BUBBLESORT(A) 1 for i ← 1 to length*A+ 2 do for j ← length*A+ downto i + 1 3 do if A[j] Nf时,f(n)≥0, 同时, 当 n Ng时, g(n) ≥0.所以, 我们取 N0=max{Nf,Ng},此时, 当 nN0时,同时有 f(n)≥0, g(n) ≥0. 下面我们取 C1=1/2,C2=1,根据 f(n),g(n)的非负性保证,当 nN0时,有: f n +g(n) 2 ≤ max f n ,g n ≤ f n + g(n) .所以,得证! Exercises 3.1-4 Is 2n+1 = O(2n)? Is 22n = O(2n)? 2n+1 = O(2n) 因为 2n+1 = 2×2n≤2×2n, 所以成立 22n = O(2n) 不成立。用反证法:如果有 22n = O(2n)成立,根据定义需要有:22n≤c2n,由此需 要:n≤lgc.矛盾!对于任意大的 n 是不可能成立的,因为 c 是一个常数。 Exercises 3.1-5 (class five 高晨高晨) Prove Theorem 3.1. 首先证明充分性:即由 f(n)= Θ(g(n))推出 f(n)= O(g(n))且 f(n)= ? (g(n)) 根据 Θ 定义:有存在 N0,C0, , 使得:当 n N0时有:C0g n ≤ f n ≤ C1g(n),在根据 O,和 ? 定义有 f(n)= O(g(n))且 f(n)= ? (g(n)). 在证明必要性:即由 f(n)= O(g(n))且 f(n)= ? (g(n))推出 f(n)= Θ(g(n)) 根据 O,和 ? 定义有:存在 N1, C1 使得:当 n N1时有f n ≤ C1g(n),同样地,存在 N2, C0 使得:当 n N2时有C0g n ≤ f n ,此时,我取 N0=max(N1, N2),则有如下事实成立:当 n N0 时有:C0g n ≤ f n ≤ C1g(n),即 f(n)= Θ(g(n)).所以,得证! Exercises 3.1-7 (class six 彭运彭运) Prove that o(g(n)) ∩∩ ω(g(n)) is the empty set. Solution: Let f∈o (g(n))∩ ω(g(n)). That means f= o (g(n))= ω(g(n)). By the definition of o, we have lim n→∞(f(n)/g(n))= 0 But the definition ofω, we have lim n→∞(f(n)/g(n))=∞ Because of 0≠∞, we have a obvious contradiction. Problems 3-2: Relative asymptotic growths Indicate, for each pair of expressions (A, B) in the table below, whether A is O, o, ?, ω, or Θ of B. Assume that k ≥ 1, ? 0, and c 1 are constants. Your answer should be in the form of the table with “yes“ or “no“ written in each box. A B O o ? ω Θ a. lgk n nε n n y y n b. nk cn n n y y n c. n nsin n n n n n n d. 2n 2n/2 y y n n n e. nlg c clg n y n y n y f. lg(n!) lg(nn) n n y y n Chapter four Exercises 4.1-1 Show that the solution of T (n) = T (?n/2?) + 1 is O(lg n). 因为包含上取整函数,又要找一个上界,所以我们要用一些技巧: 假设:T(n)≤c lg(n - b),对?n/2?成立,进而,我们有: T(n)≤c lg(?n/2?-b) + 1 ≤c lg(n/2 - b + 1) + 1 = c lg(n ? 2b + 2 2 ) + 1 = c lg(n - 2b + 2) - c lg 2 + 1 ≤c lg(n - b) 最后一个不等号成立需要,b≥ 2,c≥1 所以,得证! Exercises 4.1-2 (class two 刘浩刘浩) We saw that the solution of T (n) = 2T (?n/2?) + n is O(n lg n). Show that the solution of this recurrence is also ?(n lg n). Conclude that the solution is Θ(n lg n). 当 n = 1 时,T(n) = 1, T(n) ≥ cn lg n = c × 1 × lg 1 = 0 假设 T(n) ≥ cn lg n 对 n/2 成立 T(n) ≥ 2(?cn/2? lg(?n/2?)) + n ≥ cn lg(n/2) + n = cn lg n – cn lg 2 + n = cn lg n – cn lg 2 + n = cn lg n – cn + n ≥cn lg n ( 当 c N0时 T(n) ≤C0nlgn. 假设:T(?n/2?+ 17)≤C0 (?n/2?+ 17)lg(?n/2?+ 17) 我们有: T(n) ≤2C0(?n/2?+ 17)lg(?n/2?+ 17)+n ≤2C0(n/2+ 17)lg(n/2+ 17)+n =C0(n+34)[lg(n+34)-1]+n =C0nlg(n+34)-C0n+34C0lg(n+34)-34C0+n ??(*1) 我们取C0≥2 则有(*1) ≤C0nlg(n+34)+34C0lg(n+34)-n -34C0 N0时,有 C0nlg(n+34) –C0nlgn + 34C0lg(n+34) –n≤0 此时即有:(*2)N0时,有 C0nlg(n+34) –C0nlgn + 34C0lg(n+34) –n≤0 所以,得证! Exercises 4.1-6 (class five 高晨高晨) Solve the recurrence ? ? = ?? ? +? by making a change of variables. Your solution should be asymptotically tight. Do not worry about whether values are integral. T(n)=2T( n)+1 令 m=lgn,则有 n=2m, n=2m/2,则原式可以化为 T(2m)=2T(2m/2)+1,再令 S(m)=T(2m),则有 S(m)=2S(m/2)+1 。利 用递 归树 或者 主方 法 可得 : S(m)=O(m), 再利 用代 换可 得 : T(n)=T(2m)=S(m)=O(m)=O(lgn) Exercises 4.2-1 (class five 应莹应莹) Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) = 3T(? ?n/2? ?) + + n. Use the substitution method to verify your answer. 证明: 画出递归树,我们发现对于第i层,每个节点的规模不超过n/2i,(这句话针对式子T(n) = 3T(?n/2?) + n中的第一项来说) 所以,每一层的贡献最多为:n(3/2)i(这句话针对式子T(n) = 3T(?n/2?) + n中的第二项来说),而在最后一层中,我们假设解决T(1)=1,(规定为常数c,更具 有普遍意义,这里做了简化,不影响一般性) ,所以最后一层的贡献为n(3/2)lgn 所以,我们有: T(n)=3T(?n/2?)+n ≤ n + 3 2 n + (3 2)2n + ?… + ( 3 2)lgnn = n ( 3 2) i lgn i=0 = n 1 ? (3 2) lgn 1 ? 3 2 = 2n(2/3)lgn ? 2n = 2·3lgn-2n = Θ(nlg3) 以上是我们的猜测,我们可以用替换法给出一个证明,但我们可以用主方法直接得出答案。 Exercises 4.2-3(class five 应莹应莹) Draw the recursion tree for T (n) = 4T (? ?n/2? ?)+cn, where c is a constant, and provide a tight asymptotic bound on its solution. Verify your bound by the substitution method. 此题和上一题的思路完全一样,只是数字不用而已,这里不在赘述。套用上题的过程,即可 得出答案,Θ(n2) Exercises 4.3-1 Use the master method to give tight asymptotic bounds for the following recurrences. a. T (n) = 4T(n/2) + n. b. T (n) = 4T(n/2) + n2. c. T (n) = 4T(n/2) + n3. a. T(n) = 4T(n/2) + n. 因为 n = O(n2?ε) ,第一种情况,所以有 T(n) = Θ(n2). b. T(n) = 4T(n/2) +n2. 因为 n2= Θ(n2) ,所以有 T(n) =Θ(n2 lg n). c. T(n) = 4T(n/2) + n3. 因为 n3 = Ω(n2+ε) 第三种情况,所以有 T(n) = Θ(n3). Exercises 4.3-2 (class six 彭运彭运) The recurrence T(n) = 7T (n/2)+n2 describes the running time of an algorithm A. A competing algorithm A′′ has a running time of T′′(n) = aT′′(n/4) + n2. What is the largest integer value for a such that A′′ is asymptotically faster than A? 解: (在此题中,具体套用主定理的过程省略)应用主定理我们知道算法 A 的时间复杂度为 T(n)= Θ(nlg7),我们分类讨论 a 的取值: a16 时,T’(n)= Θ(nlg a) 此时,若要 A’比算法 A 更快,则需要lg a A[i-1,f(i-1)]+ A[i,f(i)]成立, 这是因为 A[i-1,f(i-1)]+ A[i,f(i)]都是本行最小的 元素,故其与 Monge 矩阵相矛盾。 因此对于任意的 i(1≤i n 6 then dest ← dest -n 7 B*dest+ ← A*i+ 8 return B Show that each element A[i] has a 1/n probability of winding up in any particular position in B. Then show that Professor Armstrong is mistaken by showing that the resulting permutation is not uniformly random. 在从 1 到 n 的数之中,dest 与 offest 一一对应。 由于 offset 在 1 到 n 之中任意数 i 的概率是 P(i)=1/n,因此 dest 在 1 到 n 中取任意数的概 率是 1/n,所以对于 i 确定的 A[i], A[i]在 B 中的任意位置的概率是 1/n.但是这种算法产生 的 B 仅有 n 中可能的序列,每种序列的概率是 1/n,而不是 1/n!,这显然不是随机序列。 Chapter fifteen Exercises 15.1-1 Show how to modify the PRINT-STATIONS procedure to print out the stations in increasing order of station number. (Hint: Use recursion.) PRINT-STATIONS(l, j, n) i ← l* if j=0 then return else if(j1) i ← li[j] PRINT-STATION(l, j-1, n) if j = n then i ← l* print “line“ i “, station“ j else i ← li[j+1] print “line“ i “, station“ j Exercises 15.1-2 (class two 刘浩刘浩) Use equations (15.8) and (15.9) and the substitution method to show that ri(j), the number of references made to fi[j] in a recursive algorithm, equals 2n - j. 1.j = n 时,由(15.8), ri (j) = 1 = 2 n-n 成立 2.假设当 j = k 时, ri (k) = 2 n-k 当 j = k – 1 时 ri (k-1) = r1 (k) + r2(k) = 2 n-k + 2 n-k = 2 n-(k-1) 成立 3.综上,得证 Exercises 15.1-4 (class two 刘浩刘浩) Together, the tables containing fi[j] and li[j] values contain a total of 4n - 2 entries. Show how to reduce the space requirements to a total of 2n + 2 entries, while still computing f* and still being able to print all the stations on a fastest way through the factory. 原来 fi[j]含有 2n 个表项 ,li[j]含有 2n-2 个表项,li[j]保持不变,而将 fi[j]改为四个表项,两个 记录 fi[j - 1],两个记录 fi[j ]。因为每次求 fi[j ]只需知道上一步的 fi 值,没有必要将所有 i 的 fi 值都记录。这样,空间需求便缩减到了 2n+2,而仍能输出通过工厂的最快路线上的所有 装配站。 Exercises 15.1-5 Professor Canty conjectures that there might exist some ei, ai,j, and ti,j values for which FASTEST-WAY produces li[j] values such that l1[j] = 2 and l2[j] = 1 for some station number j. Assuming that all transfer costs ti,j are nonnegative, show that the professor is wrong. 证明:如果 l1[j]=2,则有 f2(j-1)+t2,j-1+a1,j N0时,有P n ≥ c2n 所以,得证 Exercises 15.3-1 (class six 徐晓鹏徐晓鹏) Which is a more efficient way to determine the optimal number of multiplications in a matrix-chain multiplication problem: enumerating all the ways of parenthesizing the product and computing the number of multiplications for each, or running RECURSIVE-MATRIX-CHAIN? Justify your answer. 用枚举法和运行 RECURSIVE-MATRIX-CHAIN 来计算矩阵列乘法中的最优次数的效率是一样的。 首先,使用枚举法时,计算其全部括号的重数。设 P(n)表示一串 n 个矩阵可能的加全部括号 的方案数。 当 n=1 时, 只有一个矩阵, 因此只有一种方式来加全部括号矩阵乘积。 当 n≥2 时, 一个加全部括号的矩阵乘积, 就是两个加全部括号的矩阵子乘积的乘积, 而且这两个子乘积 之间的分裂可能发生在第 k 个和第(k+1)个矩阵之间,其中 k=1,2,?,n-1。因此可得 递归式 P(n)= 1 if n=1 ∑P(k)+P(n-k) if n≥2 可以计算出,解的个数是 n 的指数形式。所以用枚举法时,计算效率是 n 的指数形式。 其次,运行 RECURSIVE-MATRIX-CHAIN 来计算时, RECURSIVE-MATRIX-CHAIN 重复调用子 问题,实际上与枚举法相比并未提高计算效率,在计算所有可能性的过程中,重复计算了 子问题。所以得到的递归式为: T(1) ≥1 T(n) ≥1+∑(T(k)+T(n-k)+1) for n1 根据计算容易证明: T(n) ≥2n-1 所以调用 RECURSIVE-MATRIX-CHAIN(p,1,n)的工作总量至少为 n 的指数形式。 综上所述,使用两种方法的工作量都是 n 的指数形式的。所以两种算法的效率相同,都是 低效率的算法。 /*以下是另一个同学的答案,仅供参考 使用枚举法时,计算其全部括号的重数。设P(n)表示一串n个矩阵可能的加全部括号的方 案数。当n=1 时,只有一个矩阵,因此只有一种方式来加全部括号矩阵乘积。当n≥2 时, 一个加全部括号的矩阵乘积, 就是两个加全部括号的矩阵子乘积的乘积, 而且这两个子乘积 之间的分裂可能发生在第k个和第(k+1)个矩阵之间,其中k=1,2,?,n-1。因此可得递 归式 ? ? = 1 ? = 1 ? ? ? ? ?? ? ≥ 2 ??1 ?=1 书上给出了这个算法的一个下界:?(4 ? ? 3 2) (见书:中文版 198页,英文版333页) 另一方面:用递归的方法时:有如下递归公式: T(1)=C0 (C0是一个常数,对应英文版书上345页算法中第1,2行) ? ? = ?0 + ? ? +? ? ? ? +?1 ? ≥ 2 ??1 ?=1 (其中,C1是算法中6,7行所需要的常数时间) 书上给出了它的一个下界T(n)= ?(2?),在这里,我们给出它的一个上界:T(n)=O(3n) 我们用替换法给出他的一个简单的证明: 要证明此上界我们需要一个比较强的假设条件: T(n) ≤Cm(3n-1)/2, 其中Cm=max{C0,C1} 1. T(1)=C0Cm(31-1)/2=Cm, 成立! 2. 假设T(s) ≤Cm(3s-1)/2,对任意s≤n,都成立,则有: T(n) ≤ Cm + (T k +T n? k + Cm) n?1 k=1 ≤ Cm+ Cm (3 k ? 1 2 + (3n?k? 1) 2 + 1) n?1 k=1 ≤ Cm(1 + 1 2 (3k+3n?k) n?1 k=1 ) = Cm(1+ 3k n?1 k=1 ) = Cm 3k n?1 k=0 = Cm 1 ? 3n 1 ?3 = Cm(3n?1)/2 成立! 综上,我们证明了用递归的方法所用时间的上界:T(n)=O(3n),同时,穷举法所用时间的下 界为:?(4 ? ? 3 2). 注意到: ??? ?→∞ 3? 4? ? 3 2 = 0 , 由此就说明了递归方法的效率高! */ Exercises 15.3-3 (class four 肖咚肖咚) Consider a variant of the matrix-chain multiplication problem in which the goal is to parenthesize the sequence of matrices so as to maximize, rather than minimize, the number of scalar multiplications. Does this problem exhibit optimal substructure? 这个问题同样具有最优子结构。下面进行分析: 采用动态规划法的第一步就是寻找最优子结构, 然后利用这一子结构, 就可以根据子问题的 最优解结构造出原问题的一个最优解。 用记号 Ai…j表示对乘积 AiAi+1?Aj的求积结果,其中 i (注:没有标箭头的数字,就是对应书中指向左上角的箭头。红色的数字是 LCS。 ) Yi 0 1 0 1 1 0 1 1 0 Xi 0 0 0 0 0 0 0 0 0 0 1 0 ↑ 0 1 ← 1 1 1 ← 1 1 1 ←1 0 0 1 ↑1 2 ←2 ← 2 2 ←2 ← 2 2 0 0 1 ↑1 2 ↑2 ↑ 2 3 ←3 ← 3 3 1 0 ↑ 1 2 ↑ 2 3 3 ↑ 3 4 4 ←4 0 0 1 ↑2 3 ↑3 ↑ 3 4 ↑4 ↑ 4 5 1 0 ↑ 1 2 ↑ 3 4 4 ↑ 4 5 5 ↑5 0 0 1 2 3 ↑4 ↑ 4 5 ↑5 ↑ 5 6 1 0 ↑ 1 2 ↑ 3 4 5 ↑ 6 6 6 ↑6 Exercises 15.4-5 (class two 刘浩刘浩) Give an O(n2)-time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers. 设原序列为 A,首先将序列 A 进行递增排序,可在Θ (n lg n)时间完成,得到序列 B,然后求 A 和 B 的最长公共子序列 C,可在 O(n2)时间完成,而 C 即为 A 的最长的单调递增子序列。 Exercises 15.5-1(class four董延昊董延昊) Write pseudocode for the procedure CONSTRUCT-OPTIMAL-BST(root) which, given the table root, outputs the structure of an optimal binary search tree. For the example in Figure 15.8, your procedure should print out the structure ? k2 is the root ? k1 is the left child of k2 ? d0 is the left child of k1 ? d1 is the right child of k1 ? k5 is the right child of k2 ? k4 is the left child of k5 ? k3 is the left child of k4 ? d2 is the left child of k3 ? d3 is the right child of k3 ? d4 is the right child of k4 ? d5 is the right child of k5 c
展开阅读全文