Question

Consider the code below

int s =1;

for (int i=1; i<N; i++){

//Assertion: s =

s = s+(2*i+1);}

printf("%d", s);

a) What is a reasonable assertion for the main loop?

b) What does the code accomplish?

c) Using the method of initalization-maintenance-termination, prove that the invariant holds, and that the final output is correct.

Answer 1

a)

What is a reasonable assertion for the main loop?

In main loop we use assertion as s==i*i (reason in part b)   

int s =1;

       for (int i=1; i<N; i++){

       //Assertion: s =

              assert(s == i*i);

              s = s+(2*i+1);

       }

b) What does the code accomplish?

This code is finding the sum of first N odd numbers. We are starting with s=1 and then we are adding below :

When i=1;           we are adding   2*i+i =3

i=2;         we are adding   2*i+1 =5

i=3;         we are adding 2*i+1 =7

i=4;         we are adding 2*i+1 =9

i=5;         we are adding 2*i+1 =11

and so on…

Now sum of first N odd numbers is N*N so that’s why our assertion is i*i for sum of first i terms.

Checked in c program :

c) Using the method of initalization-maintenance-termination, prove that the invariant holds, and that the final output is correct.

We must show:

1. Initialization: It is true prior to the first iteration of the loop.
2. Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
3. Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

Suppose N = 10

Initialization:

When loop starts s=1 which is sum of first odd number and it is correct.

Maintenance:

Now when it enters the loop it updates the value of s as shown below:

Start Value	Value of i	Updated Value	Expected Value	Correctness
S=1	1	S=1+(2*1+1) = 4	2*2=4	True
S=4	2	S=4 +(2*2+1) = 9	3*3=9	True
S=9	3	S=9+(2*3+1) = 16	4*4=16	True
S=16	4	S=16+(2*4+1) = 25	5*5=25	True
S=25	5	S=25+(2*5+1) = 36	6*6=64	True
S=36	6	S=36+(2*6+1) = 49	7*7=49	True
S=49	7	S=49+(2*7+1) = 64	8*8=64	True
S=64	8	S=64+(2*8+1) = 81	9*9=81	True
S=81	9	S=81+(2*9+1) = 100	10*10=100	True

Termination:

Sum of first N(i.e 10) odd numbers should be 100 which is 10*10 and we are getting the same results.

Hence final output is correct