PseudoCode; Loop Invariant 2. (15 pts) Given a sequence of n numbers A(a1,a2 , a

Question

PseudoCode; Loop Invariant

2. (15 pts) Given a sequence of n numbers A(a1,a2 , an) and a target value v, you are asked to decide if there is an element in A that is greater than v. If there is, the output is an index i such that Ali] > v; otherwise, the output is the special value NIL (a) Write pseudocode for a simple linear "combing" algorithm, which will scan through the input sequence A to decide if there is an element that is greater than v. (b) Using a loop invariant, prove that your algorithm is correct. Be sure that your loop invariant and proof covers the initialization, maintenance, and termination conditions.

Explanation / Answer

a)

Algoritham find_large(A,V)

{

for i in 1 to n

if A[i]>V

return i

else

return NIL

}

b)

Loop Invariant:

In this algorithm, the array is containing elements from 1 to n. A[1,2,...,n].

At the start of the iteration i, the subarray A[1..(i-1)] does not contain element greater than V.

Lets prove this,

Initialization: Before loop started the subarray is A[1..0]. i.e. empty array doesn't contain element greater than V.

Maintanance: let us assume before i th iteration A[1...(i-1)], if V is smaller . Then in the i th iteration, we check A[i] >V or not. If it satisfies then we return index i. If that is not true, then A[i]<=V for all j=1...i. Finaly, at the end of the loop iteration, when we increase i=i+1, invariant will remain true.

Termination: Loop will be terminated in two ways. one is by returning index i, if A[i]>V. other is by returning NIL, if the subarray A[1..n] doesn't contain element greater than V.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.