Loop Invariants and Algorithm Correctness. In class, we showed the correctness o
ID: 3667446 • Letter: L
Question
Loop Invariants and Algorithm Correctness. In class, we showed the correctness of the insertion sort algorithm using a loop invariant, i.e., we showed that the three properties of initialization, maintenance, and termination held, and were then able to conclude that the entire array was sorted. Consider the following search problem: Input: A sequence of n integers A = (a_1, a_2,...a_n) and a value v. Output: An index i such that v = A[i] or the special value Nil if v does not appear in A. Write pseudocode for linear search, which scans through the sequence, looking for v. (Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.(State your loop invariant, and follow three steps explained in class.)Explanation / Answer
a)
After the Algorithm below terminates i will be the position of v in the array
A if v appears in the array A and otherwise i will be equal to nill
Linear-search(A,v)
1.i<- 1
2.while i<(or equal)length[A] and v=(not equal)A[i]
3.do i<-i+1
4.if i>length[A]
5.then i<-NIL
b)
At the begining of each iteration of the loop,we have A[j]=(not equal)v for all intejers j with 1<(orequal)j<(orequal)i-1
Intialization:
At the begining of the first iteration we have i=1 and the loop invariant is the empty statement because there does not exist and integer j with 1<(orequal)j<(orequal)0.In particular the loop variant is true in the first iteration
Maintenance:
suppose that in certain iteration we have A[j]=(notequal)v for1<(orequal)j<(orequal)i-1.
If A[i]=(notequal)v then the loop breaks and there will be no iterations.otherwise we get that A[j]=(notequal)v for 1<(orequal)j<(orequal)i.
In the loop we increase i by 1 this means that we still have that A[j]=(notequal)v for 1<(orequal)j<(orequal)i-1 in the next iteration
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.