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

1 Answer 1

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$
5
  • $\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, 2019 at 10:16
  • $\begingroup$ An algorithm can just as well describe a computation that doesn't necessarily terminate. $\endgroup$
    – Kai
    Apr 3, 2019 at 10:19
  • $\begingroup$ Please check it on page 3 courses.cs.vt.edu/cs2104/Fall12/notes/T16_Algorithms.pdf . $\endgroup$
    – ankit
    Apr 3, 2019 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, 2019 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, 2019 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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