1) (40 points) Loop Invariant And Running Time Computation

(a) Consider the code below and invariant that follows then answer the questions that follow:

1. n=0 2. for i=0 to n 3. n = n + 2i

Loop Invariant: Before the start of the ith iteration, n = 2i - 1

(3 points) What does the code above do?

(10 points) Show the invariant is true at initialization, maintenance and termination of

the loop. Then use that fact to prove the correctness of the loop

(7 points) For each line of pseudocode above, show next to the line a cost ci for the cost

of the line, and an expression for the number of times that line is executed. Based on this, give a formula for the run time T(n) of the function. Based on this cost, estimate a -bound for T(n).

(b) Consider the code below then answer the questions that follow:

1. 2. 3. 4. 5. 6. 7. 

ifn<2 return false

while n != 1 if n % 2 != 0 

 return false n = n /2 ; 

return true

(2 points) What does the code above do?

(3 points) Write a loop invariant that can be used to prove the correctness of the code

above

(10 points) Show the invariant you wrote in part ii is true at initialization, maintenance

and termination. Then use that fact to prove correctness of the loop.

(5 points) For each line of pseudocode above, show next to the line a cost ci for the cost

of the line, and an expression for the number of times that line is executed. Based on this, give a formula for the run time T(n) of the function. Based on this cost, estimate a -bound for T(n).

COMP 2370 Fall 2018

2) (30 points) Growth Of Functions

(a) (20 points) For each pair of functions f(n) and g(n), fill in the table with Y (yes) or N (no) in each box to indicate whether the indicated relationship applies.

()	()	() = ()	() = ()	() = ()	() = ()	() = ()
-	.//
.//	1.013
85 +7 +10	5
23	239:
7	5

(b) (10 points) Using the definitions of , prove the following: a)7 58=(7)

b) 3? + = (7) :

3) (30 points) Solving Recurrences

(a) (14 points)

(7 points) (Using the tree method, compute an estimate of the following recurrence T(n) = 2T(n/2) + 3T(n/4) + cn2

(7 points) Using substitution, prove the estimate obtained in part i

COMP 2370 Fall 2018

(b) (16 points) For each of the following recurrences state whether the Master theorem can be applied to solve the recurrence or not. If the Master theorem can be used, then use it to determine running time for the recurrence. If the Master theorem cannot be applied, then specify the reason (you dont need to solve the recurrence).

a) T(n) = 4T(n/3) + n2

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

c) T(n) = 2T(n/3) + 1

d) T(n) = 2T(n/4) + 15n

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

f) T(n) = T(n/2) + 2T(n/5) + n

g) T(n) = T(n/2) + lg4 n

h) T(n) = 2T(n-3) + 1