Given a sequence of n numbers A = a1,a2,...,an and a target value v, you are ask

Question

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 A[i] > v; otherwise, the output is the special value NIL.

(a) Writepseudocodeforasimplelinear“combing”algorithm,whichwillscanthrough 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

Procedure/Algorithm findGreaterValue(A,v) returns index:

Step1 : Start

       2: Repeat        For I:=0 to length(A)-1 Step 1 //Repeat loop upto length vector A

       3:         If( A[I]>v ) Then //When greater element than v is found

       4:                  Return i //report its index location

       [End For]

       5: Return NIL //when not found return nothing

       6: Stop

Explanation: In the above pseudo code used For loop with initilization, maintenance and condition upto length of vector A. And compare each indexed I-th element with v, when found returns its index I. Otherwise return NIL/NULL.

Example: A=[45,2,89,33,67] //vector with 5 elements

v=33

==> It compares (45==33), (2==33) ,(89==33) not matched. And finally (33==33) matched will return index position 3.

I added comments to most of lines for better explanation(//<comments>). Message me for any clarification.

PLEASE POST YOUR VALUABLE REVIEW THUMSUP!!!

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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