算法导论第三版（英文）第三四章习题答案

Yuln Ren ID:13146922 CS521 Homework 1 10/09/2013 Problem 3-2,3-4,3-6,4-1,4-4,4-6 A B O o Ω ω Θ a lgk n ne Y Y N N N b nk Cn Y Y N N N c √ n nsin n N N N N N d 2n 2n/2 N N Y Y N e nlgC Clgn Y N Y N Y f lg(n!) lg(nn) Y Y N N N a. because lim n→∞ lgk n ne = 0 , lg k n = O(ne) b. because lim n→∞ nk Cn = 0 , n k = O(Cn) c. sin n not convergence, cannot compare two d. because lim n→∞ 2n 2n/2 = ∞ , 2 n = Ω(2n/2) e. nlgC = Clgn, nlgC = Θ(Clgn) f. lg(n!) = Θ(n lg n)& nlg n = O(lg nn), lg(n!) = O(lg(nn)) � 1 Result as follows: a. No, f(n)=O(g(n)), does not imply g(n)=O(f(n)). Example: nlogn=O(n2), but n2 6=O(nlogn) b. No, f(n)+g(n) is not Θ(min (f(n),g(n))). Example: n+1 6= Θ(min (n,1)) c. Yes, if f(n)=O(g(n)) then lgf(n)=O(lgg(n)), f(n)≤g(n), lgf(n) is increasing func- tion. so lgf(n)≤lgg(n) then lgf(n)=O(lgg(n)) d. No, f(n)=O(g(n)) does not imply 2 f (n) = O(2g(n)) if f(n)≤g(n)<0, 2 f (n) = ω(2g(n)) e. Depends, (1) f(n)<1, f(n) 6= O( f (n)2) (2) f(n)≥1, f(n)=O( f (n)2) f. Yes, f(n)=O(g(n)) implies g(n)=Ωf(n) g. No. 2n � 2n/2 h. Depends, (1) if C1,C2, n0 > 0 when n>n0, C1 f (n) ≤ f (n) + o f (n) ≤ C2 f (n), then f (n) + o f (n) = Θ( f (n)) (2) if C, n1 > 0 when n>n1, 0 ≤ o f (n) ≤ C f (n), then f (n) + o f (n) 6= Θ( f (n))� 2 f(n) c f ∗c (n) a n-1 0 n b lgn 1 lg∗ n c n/2 1 lg n d n/2 2 lg n− 1 e √ n 2 lg(lg n) f √ n 1 ∞ g n 1 3 2 lg(lg n)lg 3 h nlg n 2 as follow h. (1) Aysmptotic upper bound for f(n)=n/lgn, f*(n)=f*(n/lgn)+1≤f*(n/2)+1=O(lgn) which is f ∗c (n) = O(lgn) (2) Aysmptotic lower bound for there’s k≤ n f*(n)=f*(n/lgn)+1≥1+(lgk-2)/lg(lgn)≥lgk/lg(lgn) which is f ∗c (n) = Ω(lgk/lg(lgn)) � Result as follows: (a) show that T(n)=2T(n/2)+n4=2(2T(n/4)+(n2 ) 4) + n4· · ·= 2iT( n2i ) + n 4 2i−1 + n4=Θ(n4) (b) show that T(n)=T(7n/10)+n≤ clg(7n/10) + n = clgn+ clg7− clg10 + n ≤ clgn so T(n)=Θ(lgn) (c) show that T(n)=16T(n/4)+n2, as the master theoremlogba = 2, so nlogba=n2 = f (n) = n2, T(n)=Θ(n2lgn) (d) show that T(n)=7(n/3)+n2, as the master theoremlogba = log37, sonlogba< f (n) = n2, f(n)=Ω(nlog37), so T(n)=Θ(n2) (e) show that T(n)=7(n/2)+n2, as the master theoremlogba = log27, sonlogba> f (n) = n2, f(n)=O(nlog27), so T(n)=Θ(nlog27) (f) show that T(n)=2T(n/4)+ √ n, as the master theorem nlogba= √ n = f (n) =√ n, so T(n)=Θ( √ nlgn) (g) show that T(n)=T(n-2)+n2, as the master theorem f(n)=Ω(n), so T(n)=Θ(n2)� 3 Result as follows: (a). f (z) f 0 + f1z+ f2z2 · · · −z f (z) − f 0z− f1z2 · · · −z2 f (z) − f 0z2 · · · for f 0 = 0, f1 = 1, so f (z)− z f (z)− z2 f (z) = f0 + ( f1 − f0)z = z so f (z) = z+ z f (z) + z2 f (z) (b). 1− z− z2 = (1− αz)(1− βz) then α = 1+ √ 5 2 ,β = 1−√5 2 from (a), f (z) = z1−z−z2 = z (1−αz)(1−βz) = 1√ 5 ( 11−φz − 11−φˆz ) for φ = 1+ √ 5 2 = 1.61803 · · · , φˆ = 1− √ 5 2 = 0.61803 · · · (c). because (b) z (1−αz)(1−βz) = 1√ 5 ( 11−φz − 11−φˆz ) so we can get f (z) = 1√ 5 ∞ ∑ i=0 φizi − 1√ 5 ∞ ∑ i=0 φˆ2zi= ∞ ∑ i=0 ( 1√ 5 φi − 1√ 5 φˆi)zi (d) f i = 1√5φ i − 1√ 5 φˆi= 1√ 5 (1+ √ 5 2 ) i − 1√ 5 (1− √ 5 2 ) i is to the nearest integer. � 4 Result as follows: (a). If the number of bad one is larger than [n/2], bad ones can collude to fool the professor. They would fool that themselves are good ones, and good ones are bad. And good ones also say that they are good, bad ones are bad. Then , no matter, good or bad ones, all define themselves are good ones. Thus, we cannot find out the real good ones. (b). Devide this question into two situation (1) n is even, because good ones are larger than [n/2], it means good one at least two more then bad ones. When two bad ones into a pair, it generate a new pair of good ones. So the Good-Good pairs will more than bad pairs, which re- veal the result of Good-Good pair.(Even when bad pairs pretend to be good ones) Thus, find all the Good-Good pairs, from each of the Good-Good pair, choose one of them to form a new sequence of circuits. The length would be less than [n/2], and more than half of them will be good ones. (2) n is odd, put the single one away, and put it after [n/2] sequence. (c) From (b), we can get T(n)=T(n/2)+n/2, from master theorem, T(n)=Θ(n) � 5