Programming

Question 195

Consider the following pseudo-code fragment, where m is a non-negative integer that has been initialized:

     p = 0;
     k = 0;
     while(k < m)
           p = p + 2^k;
           k = k + 1;
     end while

Which of the following is a loop invariant for the while statement?

(Note: a loop variant for a while statement is an assertion that is true each time guard is evaluated during the execution of the while statement).

Options:

A	p = 2^k – 1 and 0≤k<m </m
B	p = 2^k+1 – 1 and 0≤k<m </m
C	p = 2^k – 1 and 0≤k≤m
D	p = 2^k+1 – 1 and 0≤k≤m

ProgrammingprogrammingUGC-NET CS 2018 DEC Paper-2

Question 195 Explanation:

For k=0, P = 0+20 = 1
k=1, P = 1+21 = 3
k=2, P = 3+22 = 7
k=3, P = 7+23 = 15
Only the option-3 satisfied to the loop variant.
Ex: m=2, The loop will execute for 3 times for k value is 0,1 and 2.
Then options-3 gives P=1, P=3 and P=7 for the k values 0,1 and respectively.

Correct Answer: C

Question 195 Explanation:

For k=0, P = 0+20 = 1
k=1, P = 1+21 = 3
k=2, P = 3+22 = 7
k=3, P = 7+23 = 15
Only the option-3 satisfied to the loop variant.
Ex: m=2, The loop will execute for 3 times for k value is 0,1 and 2.
Then options-3 gives P=1, P=3 and P=7 for the k values 0,1 and respectively.

UGC-NET CS 2018 JUNE Paper-1

GATE 2014 [Set-1]

UGC-NET CS 2018 JUNE Paper-1

GATE 2014 [Set-1]

Programming

Monika Bansal