edited by
4,358 views
24 votes
24 votes

Consider the following PASCAL program segment:

if i mod 2 = 0 then
    while i >= 0 do 
    begin
        i := i div 2;
        if i mod 2 < > 0  then i := i - 1;
        else i := i – 2;
    end;

An appropriate loop-invariant for the while-loop is ________

edited by

3 Answers

Best answer
32 votes
32 votes

Loop invariant is some condition which holds at the end of each iteration of the loop. i.e. it is "invariant" => does not vary (or change). It might change inside one iteration, but it will be true at the end of every iteration.

We often use loop invariants to prove that our algorithm works correctly.

In the given program, a loop invariant is:

i mod 2 = 0

i.e. i is even after every iteration.

One can verify this as follows:

  • Before the execution of first iteration the loop invariant is true, because of this line of code: 
    if i mod 2 = 0 then
  • In every iteration, we divide i by $2$, so now i will be either odd or even. 
    • If odd, we subtract 1 from i 
      if i mod 2 < > 0  then i := i - 1; 
    • so it's now even.
    • otherwise, if even, we subtract 2 from i 
      else i := i – 2;
    • so, it remains even
  • So, at the end of every iteration i remains even.

https://stackoverflow.com/questions/3221577/what-is-a-loop-invariant

selected by
18 votes
18 votes
A loop invariant is a condition that is always be same before the loop starts , while in the loop and after the loop ends for each iteration.

Here $i \mod2 = 0$ is the loop invariant.
edited by
11 votes
11 votes

A loop invariant is a condition [among program variables] that is necessarily true immediately before and immediately after each iteration of a loop. (Note that this says nothing about its truth or falsity part way through an iteration.)

Source: http://www.cs.uofs.edu/~mccloske/courses/cmps144/invariants_lec.html

In simple words, a loop invariant is some predicate (condition) that holds for every iteration of the loop.

  • For example, let's look at a simple for loop that looks like this:
                int j = 9;
                for(int i=0; i<10; i++)  
                    j--;

In this example it is true (for every iteration) that i + j == 9. A weaker invariant that is also true is that i >= 0 && i < 10 (because this is the continuation condition!) or that j <= 9 && j >= 0.

  • The loop invariants will be true on entry into a loop and following each iteration, so that on exit from the loop both the loop invariants and the loop termination condition can be guaranteed.
Solution : An appropriate loop-invariant for the while-loop is i mod 2 = 0
                (i.e. ' i ' must be even, else the loop breaks when ' i ' is odd)

Related questions

51 votes
51 votes
4 answers
1
Kathleen asked Sep 12, 2014
11,418 views
The maximum number of possible edges in an undirected graph with $n$ vertices and $k$ components is ______.
19 votes
19 votes
3 answers
2
Kathleen asked Sep 12, 2014
5,671 views
If the longest chain in a partial order is of length $n$, then the partial order can be written as a _____ of $n$ antichains.
16 votes
16 votes
1 answer
3
Kathleen asked Sep 12, 2014
3,136 views
A given set of processes can be implemented by using only parbegin/parend statement, if the precedence graph of these processes is ______
37 votes
37 votes
1 answer
4
Kathleen asked Sep 12, 2014
4,777 views
When two $4$-bit numbers $A = a_3a_2a_1a_0$ and $B=b_3b_2b_1b_0$ are multiplied, the bit $c_1$ of the product $C$ is given by ________