search
Log In

Recent questions tagged loop-invariants

0 votes
0 answers
1
5 votes
1 answer
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
asked Dec 18, 2018 in Programming Arjun 694 views
0 votes
1 answer
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
asked Jun 19, 2017 in Algorithms ashwina 176 views
25 votes
6 answers
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)$
asked Feb 14, 2017 in Programming Arjun 4.8k views
12 votes
4 answers
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
asked Dec 23, 2016 in Programming jothee 945 views
3 votes
2 answers
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.
asked Dec 19, 2016 in Programming jothee 604 views
3 votes
1 answer
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.
asked Dec 19, 2016 in Programming jothee 377 views
8 votes
1 answer
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
asked Nov 14, 2016 in Programming makhdoom ghaya 645 views
8 votes
3 answers
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
asked Jun 10, 2016 in Programming jothee 3k views
34 votes
7 answers
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}$
asked Feb 12, 2016 in Programming Akash Kanase 4.2k views
19 votes
2 answers
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}$
asked Oct 10, 2015 in Programming makhdoom ghaya 1.2k views
12 votes
2 answers
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$
asked Oct 8, 2015 in Programming makhdoom ghaya 1k views
44 votes
7 answers
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\}$
asked Feb 13, 2015 in Programming makhdoom ghaya 4.9k views
1 vote
1 answer
14
reversing the digits in a given integer to obtain a new integer letn=D1D2-------Dm 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 iteration is (A) n=D1,D2,-------Dm-i and rev=DmDm-1-----Dm-i+1 (B)n=Dm-i+1----Dm-1Dm and rev=Dm-1----D2D1 (C)n!=rev (D)n1=D1D2-----Dm and rev=DmDm-1---D2D1
asked Nov 23, 2014 in Algorithms Siramdas Vamshidhar 609 views
26 votes
5 answers
15
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$
asked Sep 19, 2014 in Programming Kathleen 3.7k views
19 votes
3 answers
16
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 &ndash; 2; end; An appropriate loop-invariant for the while-loop is ________
asked Sep 12, 2014 in Programming Kathleen 1.5k views
To see more, click for the full list of questions or popular tags.
...