Question 2 (5 points each) Answer:
1. Θ(n2logn) 2. True
Question 3 (5 points) Answer: logn
Question 4 (10 points) Answer:
Copyright By PowCoder代写 加微信 powcoder
ECS 122A – Algorithm & Analysis Midterm 1 Solution
i input array for boo 1 A[0]
8 A[0..4] 16 A[0..8]
n A[0..n/2]
input size for boo 1
The runtime for the while loop is: 1+2+3+5+9+…+ n2 +1
= (0+1)+(1+1)+(2+1)+(4+1)+(8+1)+…+(n2 +1) = (0+1+2+4+8+…+ n2)+(1+1+1…+1)
= (20 +21 +22 +23 +…+2logn−1)+1×logn 1 − 2logn
= 1−2 +logn = Θ(n)
Therecurrencefor fooisT(n)=T(n2)+2T(n3)+Θ(n2) Note: No explanation is needed.
Question 5 (20 points) Answer:
Height of the tree = n
Number of 1’s at the leaves = 2n−1 Sum of the nodes in the tree:
T(n) = n+2(n−1)+4(n−2)+8(n−3)+…+2n−1 ×1
= 20(n − 0) + 21(n − 1) + 22(n − 2) + 23(n − 3) + … + 2n−1(n − (n + 1))
We know 20 + 21 + …2n−1 is O(2n). So guess T(n) is O(2n). Verify it using substitution method:
T(k) = 2T(k − 1) + k ≤ 2(c2k−1) + k
= c2k + k Need to make c2k + k ≤ c2k, which is not possible.
Try adding a lower order term: T(n) ≤ c2n + dn
T(k) = 2T(k − 1) + k ≤2(c2k−1 +d(k−1))+k = c2k +2dk−2d+k
Need to make c2k + 2dk − 2d + k ≤ c2k + dk:
c2k + 2dk − 2d + k ≤ c2k + dk dk − 2d + k ≤ 0
k(d + 1) ≤ 2d 2
Suppose d + 1 ≤ 0, i.e., d ≤ −1, then
Pick d = −1: k ≥ 0. Conclusion: T(n) is O(2n).
To make sure 2n is the tightest upper bound, verify that T(n) is Ω(2n) using substitution method:
T(k) = 2T(k − 1) + k ≥ 2(c2k−1) + k
Need to make c2k + k ≥ c2k, so k ≥ 0. Conclusion: T(n) is Ω(2n).
So 2n is the tightest upper bound. Question 6 (15 points)
Need to make ck2logk − ck2 + k2 ≤ ck2logk:
Conclusion: T(k) is O(n2logn). Question 7 (25 points)
Recurrence for algorithm A: T(n) = 3T(n2 ) + Θ(n2)
n2 is polynomially larger: n2 is Ω(nlog23+ε) where 0 < ε ≤ 2 − log23. Try case 3 of master theorem. Check the regulariy condition:
af(nb) ≤ cf(n) 3 ( n2 ) 2 ≤ c n 2
34 ≤ c < 1 3
T ( k ) = 4 T ( 2k ) + k 2
≤ 4 c ( 2k ) 2 l o g 2k + k 2
= c k 2 l o g 2k + k 2
= ck2logk − ck2 + k2
ck2logk − ck2 + k2 ≤ ck2logk −ck2 + k2 ≤ 0
The regularity condition is satisfied. So T(n) is Θ(n2).
Recurrence for algorithm B: T(n) = 4T( n4 ) + Θ(n)
n is Θ(nlog44) = Θ(n). So case 2 of master theorem applies. T(n) is Θ(nlogn).
Conclusion: Algorithm B runs faster.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com