1) (40 points) Loop Invariant And Running Time Computation (a) Consider the code

Question

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:

ifn<2
return false

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 don’t 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

()

()

() = ()

() = ()

() = ()

() = ()

() = ()

-

.//

.//

1.013

85 +7 +10

5

23

239:

7

5

Explanation / Answer

Solution:

Note: The first question is done as per Chegg guidelines, please repost others.

1 a)

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

(3 points) What does the code above do?

The code is adding multiple of 2 up to n.

like

2+4+6+8+10+12+....+2n

(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

The invariant is i>=0 && i<= n

at initialization i= 0, this means the invariant is true for initialization

i= 1 to i= n is the maintenance part in which also the invariant is true

i= n+1 is where the loop terminates.

(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 runtime T(n) of the function. Based on this cost, estimate a -bound for T(n).

1. n=0=============> T(n)= O(1)
2. for i=0 to n ========> T(n)= O(n)
3. n = n + 2i==========> T(n)= O(1), this will b executed n number of times

So the total complexity of the given code will be

T(n)= O(n)

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.