TIFR CSE 2010 | Part B | Question: 30

Question

Consider the following program for summing the entries of the array $b$: array $[0 .. N-1]$ of integers, where $N$ is a positive integer. (The symbol '$<>$' denotes 'not equal to').

var      
    i, s: integer;
Program
    i:= 0;
    s:= 0;
[*] while i <> N do
        s := s + b[i];
        i := i + 1;
    od

Which of the following gives the invariant that holds at the beginning of each loop, that is, each time the program arrives at point $[*]$ ?

• A. $s = \sum\limits^{N}_{j=0}b[j] \;\&\; 0 \leq i \leq N$
• B. $s = \sum\limits^{i=1}_{j=0}b[j] \;\&\; 0 \leq i < N$
• C. $s = \sum\limits^{i}_{j=0}b[j] \;\&\; 0 < i \leq N$
• D. $s = \sum\limits^{N}_{j=1}b[j] \;\&\; 0 \leq  i < N$
• E. $s = \sum\limits^{i-1}_{j=0}b[j] \;\&\; 0 \leq  i \leq N$

Comments

what about option B?

---

Why not option c? And also in option E what if  i=0?  j=0 from i-1= 0-1=-1?

Answer 1

Whenever we encounter the $[*]$, the variable $s$ holds the sum of all elements $b[0]$ to $b[i-1]$.

When we first enter the loop, $i=0$, and $s$ doesn't have any elements summed up.

When we last enter the loop, $i = (N-1)$ and $s$ contains the sum of elements $b[0]$ through $b[N-2]$.

We leave the loop when $i=N$, and $s$ gets the sum of elements $b[0]$ to $b[N-1]$

The only option that matches this behavior is option E.

$$s = \sum\limits^{i-1}_{j=0}b[j] \;\&\; 0 \leq  i \leq N$$

Comments

to understand invariants problems sachin mittal sir's comment on (gate 2015) question is best

---

insertion sort is a best example to understand these type of questions

---

In $1st$ iteration, $i=0$ and $s=0$, then according to $E$ option,

$s = \sum\limits^{i-1}_{j=0}b[j] = \sum\limits^{-1}_{j=0}b[j]$

When Upper limit of summation index is lower than Lower Limit of summation index then it is a sum with no summands or empty sum.

Since sum is empty, summation value is $0 \Rightarrow s = 0$

Useful resource: Upper limit of summation index lower than lower limit

Answer 2

I think we can even ans the question without doing a single iteration.

see when we reach first time [*] at that time i=0,s=0

the only option matches with this behaviour is Option E. Remaining all options are storing atleast one elements sum in s.

Comments

Actually we add N elements

from 0 to N-1

But no other option adding 0 to N-1 elements,rt?

---

Right for this particular situation but there may be several options which lead to correct O/P that is sum of N elements.

But Here We have to check what they have expected that is:-  invariant that holds at the beginning of each loop, that is, each time the program arrives at point [*] .

---

plz guide me any one i want to read more about this topic so which source is good???

---

NPTEL NPTEL NPTEL