Homework 2

1. Prove that sum = i

2 after every iteration of the for loop below:

Input: n: nonnegative integer

Output: n

2

1 sum = 0

2 for i = 1 to n do

3 sum = sum + 2i − 1

4 end

5 return sum

2. Use strong induction on n to prove that the algorithm below computes 2n

for all n ≥ 0.

Input: n: nonnegative integer

Output: 2

n

1 Algorithm: QuickPow

2 if n = 0 then

3 return 1

4 else if n is even then

5 t = QuickPow(n/2)

6 return t

2

7 else

8 t = QuickPow((n − 1)/2)

9 return 2t

2

10 end

1

## Reviews

There are no reviews yet.