Prove correctness of algorithm using step: 1.state the loop invariant. 2.Prove t

Question

Prove correctness of algorithm

using step:

1.state the loop invariant.

2.Prove that the loop invariant's base case holds.

3. Prove the invariant holds for some arbitrary iteration: assume invariant holds for all indices 1, . . . , k and prove that it will also hold for index k + 1.

4.Prove that the loop terminates: Note: We will use the following mathematical theorem: a strictly increasing sequence of integers cannot be bounded from above.

5. Prove the correctness of the return value. Notice that since the last iteration index is t, the indices of local variable after the loop terminates are t + 1.

Explanation / Answer

Loop Invariant

Initialization: The invariant (s) is true prior to the first iteration of the loop

Maintenance: If the variant is true for iteration n, it is true for iteration n+1

Termination: When the loop terminates ,the invariant is true on the entire input.

Initialization:-

For R=0 and I=2 the invariant is respected, trivially have zero value   

Maintenance

For given value A Iteration is there from I till it will be less than and equal to A. It is checked that I is even or not If Even then Value of R is computed by increment of 1.The invariant is preserved till the condition is true and computed again value of R.

Termination

In last iteration value of I is greater than A, We find the number of Even number with given range from zero to the number given.

Return value of R

OR

The hypothesis is true for at the beginning of loop

Induction hypothesis – for R k =[k+1/2],I k =K+2 is R k =(Ik -1)/2 is Odd and R k=(Ik-1)/2 is even

1.I=0,R=0

2.If hypothesis is true for step I<=A then it should be true for I+1 steps.

At the start Check I is even or Not and If I is even Calculate value of R=R+1 else continue.

3. When the loop terminate ,the hypothesis implies the correctness of the algorithm.

The loop terminates when I>A and We get value of R

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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