# Recent questions tagged loop-invariants

1
2
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 ? $x=y+1$ $x=(y+1)^2$ $x=(y+1)2^y$ $x=2^y$ None of the above, since the loop does not terminate
3
What is loop invariant in general term ? PS: Insertion Sort has loop invariant . We have three things in loop invariant : a. Initialization b.Maintenance c.Termination
4
Consider the C program fragment below which is meant to divide $x$ by $y$ using repeated subtractions. The variables $x$, $y$, $q$ and $r$ are all unsigned int. while (r >= y) { r=r-y; q=q+1; } Which of the following conditions on the variables $x, y, q$ and $r$ before the execution of the fragment will ensure that ... $(q==0) \ \&\& \ (r==x) \ \&\& \ (y >0)$ $(q==0) \ \&\& \ (y>0)$
5
Consider the following psuedocode fragment, where $y$ is an integer that has been initialized. int i=1 int j=1 while (i<10): j=j*i i=i+1 if (i==y): break end if end while Consider the following statements: $(i==10)$ or $(i==y)$ If $y > 10$, then $i==10$ ... is/are TRUE at the end of the while loop? Choose from the following options. i only iii only ii and iii only i, ii, and iii None of the above
6
Consider the two program segments below: for i:=1 to f(x) by 1 do S end i:=1; While i<=f(x) do S i:=i+1 end Under what conditions are these two programs equivalent? Treat $S$ as any sequence of statement and f as a function.
7
Below figure is the flow-chart corresponding to a program to calculate the $\gcd$ of two integers, $M$ and $N$ respectively, $(M, N >0).$ Use assertions at the cut point $C_1$, $C_2$ and $C_3$ to prove that the flow-chart is correct.
8
List the invariant assertions at points $A, B, C, D$ and $E$ in program given below: Program division (input, output) Const dividend = 81; divisor = 9; Var remainder, quotient:interger begin (*(dividend >= 0) AND (divisor > 0)*) remainder := dividend; quotient := 9; (*A*) ... 1; remainder := remainder - divisor; (*C*) end; (*D*) quotient := quotient - 1; remainder := remainder + divisor; (*E*) end
9
Consider the following pseudo-code x:=1; i:=1; while (x <= 1000) begin x:=2^x; i:=i+1; end; What is the value of i at the end of the pseudo-code? 4 5 6 7
10
The following function computes $X^{Y}$ for positive integers $X$ and $Y$. int exp (int X, int Y) { int res =1, a = X, b = Y; while (b != 0) { if (b % 2 == 0) {a = a * a; b = b/2; } else {res = res * a; b = b - 1; } } return res; } Which one of the following conditions is TRUE before every ... the loop? $X^{Y} = a^{b}$ $(res * a)^{Y} = (res * X)^{b}$ $X^{Y} = res * a^{b}$ $X^{Y} = (res * a)^{b}$
11
Consider the program where $a, b$ are integers with $b > 0$. x:=a; y:=b; z:=0; while y > 0 do if odd (x) then z:= z + x; y:= y - 1; else y:= y % 2; x:= 2 * x; fi Invariant of the loop is a condition which is true before and after every ... will not terminate for some values of $a, b$ but when it does terminate, the condition $z = a * b$ will hold. The program will terminate with $z=a^{b}$
12
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 ... $s = \sum\limits^{i-1}_{j=0}b[j] \;\&\; 0 \leq i \leq N$
13
Consider the following pseudo code, where $x$ and $y$ are positive integers. begin q := 0 r := x while r ≥ y do begin r := r - y q := q + 1 end end The post condition that needs to be satisfied after the program terminates is $\{ r = qx + y \wedge r < y\}$ $\{ x = qy + r \wedge r < y\}$ $\{ y = qx + r \wedge 0 < r < y\}$ $\{ q + 1 < r - y \wedge y > 0\}$
1 vote
Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let $n = d_1\, d_2\, \ldots\, d_m$. int n, rev; rev = 0; while(n > 0) { rev = rev * 10 + n%10; n = n/10; } The loop invariant condition at the end of the $i^{th}$ ... $n \neq \text{rev}$ $n=d_1\, d_2 \,\ldots\, d_m \qquad \mathbf{or} \qquad \text{rev} =d_m \,\ldots\, d_2\, d_1$