《算法导论》第四章-思考题（参考答案）算法导论（第三版）

算法导论（第三版）参考答案：思考题4.1，思考题4.2，思考题4.3，思考题4.4，思考题4.5，思考题4.6
Problem 4.1 (Recurrence examples)

Give asymptotic upper and lower bound forT(n)in each of the following recurrences. Assume thatT(n)is constant forn≤2 . Make your bounds as tight as possible, and justify your answers.

T(n)=2T(n/2)+n4

T(n)=T(7n/10)+n

T(n)=16T(n/4)+n2

T(n)=7T(n/3)+n2

T(n)=7T(n/2)+n2

T(n)=2T(n/4)+n√

T(n)=T(n?2)+n2

主方法情况三， T(n)=Θ(n4)
主方法情况三， T(n)=Θ(n)
主方法情况二， T(n)=Θ(n2lgn)
主方法情况一， T(n)=Θ(n2)
主方法情况一， T(n)=Θ(nlg27)
主方法情况二， T(n)=Θ(n√lgn)
递归树法，假设n为偶数， T(n)=n2+(n?2)2+(n?4)2+?+T(2)=∑n2?1i=0(n?2i)2+T(2)=Θ(n3)

Problem 4.2 (Parameter-passing costs)

Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an N-element array is being passed. This assumption is valid in most systems because a pointer to the array is passed, not the array itself. This problem examines the implications of three parameter-passing strategies:

An array is passed by pointer. Time=Θ(1)

An array is passed by copying. Time=Θ(N) , whereNis the size of the array.

An array is passed by copying only the subrage that might be accessed by the called procedure. Time=Θ(q?p+1)if the subarrayA[p…q]is passed.

So:

Consider the recursive binary search algorithm for finding a number in a sorted array (see Exercise 2.3-5). Give recurrences for the worst-case running times of binary search when arrays are passed using each of the three methods above, and give good upper bounds on the solutions of the recurrences. LetNbe the size of the original problems and n be the size of a subproblem.

Redo part (a) for the MERGE-SORT algorithm from Section 2.3.1.

二分查找
a.
T(n)=T(n/2)+c=Θ(lgn)
b.
T(n)=T(n/2)+cN=2cN+T(n/4)=3cN+T(n/8)=∑lgn?1i=0(2icN/2i)=cNlgn=Θ(nlgn)c.
T(n)=T(n/2)+cn=Θ(n)
归并排序
a.
T(n)=2T(n/2)+cn=Θ(nlgn)
b.

T(n)=2T(n/2)+cn+2N=∑i=0lgn?1(cn+2iN)=∑i=0lgn?1cn+N∑i=0lgn?12i=cnlgn+N2lgn?12?1=cnlgn+nN?N=Θ(nN)=Θ(n2)
c.
T(n)=2T(n/2)+cn+2n/2=2T(n/2)+(c+1)n=Θ(nlgn)

Problem 4.3 (More recurrence examples)

Give asymptotic upper and lower bounds forT(n)in each of the following recurrences. Assume thatT(n)is constant for sufficiently small n. Make your bounds as tight as possible, and justify your answers.

T(n)=4T(n/3)+nlgn

T(n)=3T(n/3)+n/lgn

T(n)=4T(n/2)+n2n√

T(n)=3T(n/3?2)+n/2

T(n)=2T(n/2)+n/lgn

T(n)=T(n/2)+T(n/4)+T(n/8)+n

T(n)=T(n?1)+1/n

T(n)=T(n?1)+lgn

T(n)=T(n?2)+1/lgn

T(n)=n√T(n√)+n

主方法情况一， T(n)=Θ(nlog34)
利用积分求和的近似

T(n)=3T(n/3)+nlgn=nΘ(1)+∑i=0log3n?1nlgn?i=nΘ(1)+n∑i=1+lgn?log3nlgn1i=Θ(nlglgn)
?【《算法导论》第四章-思考题（参考答案）】
主方法情况三， T(n)=Θ(n2n√)
n足够大时，可以忽略-1。所以应用主方法情况二， T(n)=Θ(nlgn)
通过积分求和的近似，类似第2问

T(n)=2T(n/2)+nlgn=nΘ(1)+∑i=0lgn?1nlgn?i=nΘ(1)+n∑i=1lgn1i=Θ(nlglgn)

类似于练习4.4-6。 T(n)=Θ(n)
通过积分求和近似。

T(n)=T(n?1)+1/n=1n+1n?1+T(n?2)=∑i=0n?11n?i+Θ(1)=∑i=1n1i+Θ(1)=Θ(lgn)

递归树结构类似第7问

T(n)=lgn+T(n?1)=∑i=0n?1lg(n?i)=∑i=1nlgi+Θ(1)=Θ(lg(n!))=Θ(nlgn)

同样利用到积分求和的近似

T(n)=1lgn+1lg(n?2)+…+Θ(1)=∑i=0n/2?11lg(n?2i)=∑i=2n1lgi=∑i=1lgn1i=Θ(lglgn)

令S(n)=T(n)n? ，则S(n)=S(n√)+1? 。考虑n=2m?的情况，有S(2m)=S(2m/2)+1? 。令P(m)=S(2m)? ，得P(m)=P(m/2)+1? 。根据主定理情况二， P(m)=Θ(lgm)? 。则

T(n)=nS(n)=nS(2m)=nP(m)=Θ(nlgm)=Θ(nlglgn)
Problem 4.4 (Fibonacci numbers)

This problem develops properties of the Fibonacci numbers, which are defined by recurrence (3.22). We shall use the technique of generating functions to solve the Fibonacci recurrence. Define the generating function (or formal power series)Fas

>>F(z)>=∑i=0∞Fizi=0+z+z2+2z3+3z4+5z5+8z6+13z7+21z8+…,>>
where Fiis the ith Fibonacci number.

Show thatF(z)=z+zF(z)+z2F .

Show that

>>F(z)>>=z1?z?z2=z(1??z)(1??^z)=15√(11??z?11??^z)>>
where

>?=1+5√2=1.61803…>?^=1?5√2=?0.61803…>

Show that

>F(z)=∑i=0∞15√(?i??^i)zi>

Use part (c) to prove thatFi=?i/5√fori>0 , rounded to the nearest integer. (Hint: Observe that|?^|<1 .)

z+zF(z)+z2F(Z)==z+z∑i=0∞Fizi+z2∑i=0∞Fizi=z+∑i=1∞Fi?1zi+∑i=2∞Fi?2zi=z+0+∑i=2∞(Fi?1+Fi?2)zi=0+z+∑i=2∞Fizi=F(z)

根据第1问，可得

F(z)=z1?z?z2=z(1??z)(1??^z)=15√(11??z?11??^z)(?=1+5√2,?^=1?5√2)

根据几何级数的性质11?x=∑∞k=0xk当 |x|<1

F(n)=15√(11??z?11??^z)=15√(∑i=0∞?izi?∑i=0∞?^izi)=∑i=0∞15√(?i??^i)zi

Fi=?i??^i5√=?i5√??^i5√，又Fi={0,1,2,3,5,8,13...}。当i>0,|?^|<1 ，得|?^i5√|<0.5 。所以对一个整数，加/减去一个小于 0.5 的数，对所得结果舍入到最近的整数即可。

Problem 4.5 (Chip testing)

Professor Diogenes hasnsupposedly identical integrated-circuit chips that in principle are capable of testing each other. The professor’s test jig accomodates two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the professor cannot trust the answer of a bad chip. Thus, the four possible outcomes of a test are as follows.

Chip A says Chip B says Conclusion

B is good A is good both are good, or both are bad

B is good A is bad at least one is bad

B is bad A is good at least one is bad

B is bad A is bad at least one is bad

1. Show that if more thann/2chips are bad, the professor cannot necessarily determine which chips are good using any strategy based on this kind of pairwise test. Assume that the bad chips can conspire to fool the professor.
2. Consider the problem of finding a single good chip from among n chips, assuming that more thann/2of the chips are good. Show that?n/2?pairwise tests are sufficient to reduce the problem to one of nearly half the size.
3. Show that the good chips can be identified withΘ(n)pairwise tests, assuming that more thann/2chips are good. Give and solve the recurrence that describes the number of tests.

Chip A says	Chip B says	Conclusion
B is good	A is good	both are good, or both are bad
B is good	A is bad	at least one is bad
B is bad	A is good	at least one is bad
B is bad	A is bad	at least one is bad

因为好芯片检测准确，而坏芯片检测不确定（可能准确，也可能错误）。如果好芯片数量少于 n/2 ，则就会有同样数量的坏芯片，假设跟好芯片表现的一样（总能准确报告芯片的好坏）。按照这种策略，永远也没法区分这两类的好坏性了。
一种策略：从中取出两类，每类个 ?n/2? 。对这两类一一对应地比较，只保留满足情况一（都报告对方为好芯片）的芯片。也就是说，剔除出去的至少有一个坏的。剩下来的每对只挑选一个，加上可能为配对的芯片，组成一个新集合。这个集合仍然满足：超过一半的好芯片，同时规模减半。
第2问的策略递归式：

T(n)=T(n/2)+?n/2?
满足主方法情况三， T(n)=Θ(n)
Python code

import randomclass GoodChip: def good(self): return Truedef check(self, other): return other.good()class BadChip: def good(self): return Falsedef check(self, other): return [True, False][random.randint(0, 1)]def jig(a, b): return [a.check(b), b.check(a)]def diogenes(chips, verbose = False): def find_single(chips): if len(chips) <= 2: return chips[0] else: halfpoint = len(chips) // 2 pairs= zip(chips[0:halfpoint], chips[halfpoint:halfpoint * 2]) kept= [a for (a, b) in pairs if jig(a, b) == [True, True]]if len(chips) % 2 == 1: kept.append(chips[-1])return find_single(kept)good = find_single(chips) return [chip for chip in chips if jig(good, chip) == [True, True]]

Problem 4.6 (Monge arrays)

Anm×narrayAof real numbers is a Monge array if for alli,j,k,andlsuch that1≤i
>A[i,j]+a[k,l]≤A[i,l]+A[k,j]>
In other words, whenever we pick two rows and two columns of a Monge array and consider the four elements at the intersections of the rows and columns, the sum of the upper-left and lower-right elements is less than or equal to the sum of the lower-left and upper-right elements. For example, the following array is Monge:
>>10>17>24>11>45>36>7517222813443366131622632195128293417372153232324723634>>

Prove that an array is Monge if and onlyifor alli=1,2,…,m?1,andj=1,2,…,n?1we have

>A[i,j]+A[i+1,j+1]≤A[i,j+1]+A[i+1,j]>
(Hint: For the “if” part, use induction seperately on rows and columns)

The following array is not Monge. Change one element in order to make it Monge. (Hint: Use part (a).)

>>37>21>53>32>43>2363413212273091532103168>

Letf(i)be the index of the column containing the leftmost minimum element of the rowi . Prove thatf(1)≤f(2)≤…f(m)for anym×nMonge array.

Here is a description of a divide-and-conquer algorithm that computes the leftmost minimum element in each row of anm×nMonge arrayA :

Construct a submatrixA'ofAconsisting of the even-numbered rows ofA . Recursively determine the leftmost minimum for each row inA' . Then compute the leftmost minimum in the odd-numbered rows ofA .

Explain how to compute the leftmost minimum in the odd-numbered rows ofA(given that the leftmost minimum of the even-numbered rows is known) inO(m+n)time.

Write the recurrence describing the running time of the algorithm described in part (d). Show that its solution isO(m+nlogm) .

“仅当”证明，根据定义可以方便地得到。对于“当”的部分

A[i,j]+A[i+1,j+1]≤A[i,j+1]+A[i+1,j]?A[i,j]+A[k,l]≤A[i,l]+A[k,j]
对行使用归纳法，证明：

A[i,j]+A[i+1,j+1]≤A[i,j+1]+A[i+1,j]?A[i,j]+A[k,j+1]≤A[i,j+1]+A[k,j]
则
A[i,j]+A[k,j+1]≤A[i,j+1]+A[k,j](假设)A[k,j]+A[k+1,j+1]≤A[k,j+1]+A[k+1,j](已知)?A[i,j]+A[k,j+1]+A[k,j]+A[k+1,j+1]≤A[i,j+1]+A[k,j]+A[k,j+1]+A[k+1,j]?A[i,j]+A[k+1,j+1]≤A[i,j+1]+A[k+1,j]
在此基础上，同理对列使用归纳法。得证

将第一行第三列元素改为24。

37215332432363413212473091532103168

反证法。若f(i)>f(j)(i

A[i,f(i)]+A[j,f(j)] 所以当i

利用上述性质

T(m,n)=∑i=0m/2?1(μ2i+2?μ2i+1)=∑i=0m/2?1μ2i+2?∑i=0m/2?1μ2i+m/2=∑i=1m/2μ2i?∑i=0m/2?1μ2i+m/2=μm?μ0+m/2≤n+m/2=O(m+n)

T(m)=T(m/2)+cn+m/2=cn+dm/2+cn+dm/4+cn+dm/8+…=∑i=0lgm?1cn+∑i=0lgmdm2i+1=cnlgm+dm∑i=0lgm?112i+1 C code

typedef struct array { int m; int n; int step; int *data; } array; int get(array A, int i, int j) { return A.data[((i + 1) * A.step - 1) * A.n + j]; }array half(array a) { array result = { a.m, a.n, a.step * 2, a.data }; return result; }int height(array array) { return array.m / array.step; }int min_index(array A, int row, int left, int right) { int min = left; for (int i = left; i < right; i++) { if (get(A, row, i) < get(A, row, min)) { min = i; } }return min; }void find_minimums(array A, int *mins) { if (height(A) == 1) { mins[0] = min_index(A, 0, 0, A.n); } else { array evens = half(A); int even_minimums[height(evens)]; find_minimums(evens, even_minimums); int leftmost = 0; for (int i = 0; i < height(evens); i++) { leftmost = min_index(A, 2 * i, leftmost, even_minimums[i] + 1); mins[2 * i]= leftmost; mins[2 * i + 1] = even_minimums[i]; }if (height(A) % 2) { mins[height(A) - 1] = min_index(A, height(A) - 1, leftmost, A.n); } } }