0
$\begingroup$

Q) Consider the following program fragment:

var x,y:integer;  
x:=1; y:=0;  
while y < x do  
begin  
  x:=2∗x;  
  y:=y+1;  
end;

For the above fragment , which of the following is a loop-invariant ?

A) x=y+1
B) x=(y+1)2
C) x=(y+1)2y
D) x=2y
E) None of the above, since the loop does not terminate

Since, Loop-Invariant is something which is true before and after each iteration of a loop. So, according to the definition, I am getting answer as (D) but I have a doubt whether termination of that loop is necessary or not for the given code. One of the properties of algorithm says :- algorithm should always terminate after finite no. of steps. So, if the question is about Pseudocode then I will definitely mark answer as (D) but since it is program fragment, So I am confused between options (D) and (E).
So, My Doubt is definition of loop-invariant is also true for the loop in the code which is written in any language like C,C++ etc.
Please help.

$\endgroup$
0
$\begingroup$

The question asks for a loop invariant. This has nothing to do with termination. (D) does look reasonable but you may want to check with the usual tools such as Hoare logic, that (D) holds before the loop and is re-established by the loop body if the guard holds.

PS Your idea of an algorithm may need some work.

$\endgroup$
  • $\begingroup$ Thank you for the answer. Can you please tell me why are you saying "Your idea of an algorithm may need some work.". Is anything wrong in the question ? $\endgroup$ – ankit Apr 3 at 10:16
  • $\begingroup$ An algorithm can just as well describe a computation that doesn't necessarily terminate. $\endgroup$ – Kai Apr 3 at 10:19
  • $\begingroup$ Please check it on page 3 courses.cs.vt.edu/cs2104/Fall12/notes/T16_Algorithms.pdf . $\endgroup$ – ankit Apr 3 at 10:21
  • $\begingroup$ Here in finiteness property , it is mentioned that "The algorithm must always terminate after a finite number of steps." Is it wrong @Kai $\endgroup$ – ankit Apr 3 at 10:22
  • $\begingroup$ That's just bizarre. The concept of algorithm transcends the notion as defined in those slides and the fields of program verification and computability are the better for it. Based on a sample size of 1, I recommend against following that course. $\endgroup$ – Kai Apr 3 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.