ECS 122A – Algorithm & Analysis Homework 01 Solution
Question 1: Inductive Proof
1. (20 points) Prove by induction that ∑n 1 = n . i=1 i(i+1) n+1
Base case: When n = 1, ∑1 1 = 1 and
Copyright By PowCoder代写 加微信 powcoder
1 = i=1 i(i+1)
∑ i(i + 1) = ∑ i(i + 1) + (k + 1)(k + 2)
i=1 i(i+1) 1(1+1)
Let k be an arbitrary positive integer. Assume that ∑k
k . Need to prove that ∑k+1 k+1
1 i=1 i(i+1)
k+1 (k+1)(k+2) k(k+2)+1
(k+1)(k+2) k2+2k+1 (k+1)(k+2) (k+1)2 (k+1)(k+2)
2.(20points)Letanbethesequencedefinedbya1 =1,a2 =8,andan =an−1+2an−2forn≥3. Prove by induction that an = 3 × 2n−1 + 2(−1)n for all non-negative integers n. (Hint: There are two base cases.)
Answer: Base cases:
• Whenn=1,a1 =1and3×20+2(−1)1 =3−2=1. • Whenn=2,a1 =8and3×21+2(−1)2 =6+2=8.
Let k be an arbitrary positive integer. Assume that ak = 3 × 2k−1 + 2(−1)k. Need to prove that
ak+1 = 3 × 2k + 2(−1)k+1.
ak+1 = ak + 2ak−1
= (3 × 2k−1 + 2(−1)k) + 2(3 × 2k−2 + 2(−1)k−1) = 3×2k−1 +2(−1)k +3×2k−1 +2(−1)k
= 2×3×2k−1 +2×2×(−1)k
= 3 × 2k + 2(−1)k+1
Question 2: Basic Code Analysis
What is the tightest Big-O of each of the following code segments, assume n is the input and is a positive number? (Briefly explain your solution.)
1. (20 points)
1 2 3 4 5 6 7
2. (20 points)
3. (20 points)
1 2 3 4 5 6 7 8 9
for i = 0 to n inclusive:
for j = 0 to 1 inclusive: if j == 0:
x=x*2 else:
Answer: O(n).
The outer loop has n + 1 iterations. For each iteration of the outer loop, the inner loop has 2 iterations. The total number of iterations is (n + 1) × 2. In each iteration, a constant runtime of operations is executed.
for i = 0 to n inclusive:
for j = 0 to i inclusive: x=x+1
Answer: O(n2).
The total number of iterations is 1 + 2 + 3 + …(n + 1) = (n+1)(n+2) . 2
while (i > 1) {
while (j < n) {
while (k < n) {
Answer: O(nlog2n)
i number of iterations of the second loop n n−n
Total number of iterations of the first two loops: (n−n)+(n− n2)+(n− n4)+...+1
= (n− n )+(n− n )+(n− n )+...+(n− 20 21 22
= (n− n )+(n− n )+(n− n )+...+(n−
20 21 = nlogn − nlognΣlogn 1
i=0 2i The third loop iterates n times every time.
= O(nlogn)
The total runtime is O(n(logn)2) = O(nlog2n).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com