2. (15 pts) Given a sequence of n numbers A-(al.a2.. . . , an) and a target valu

Question

2. (15 pts) Given a sequence of n numbers A-(al.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 Al> 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) Below is the Pseudo code Note that i am not posting a code as you just specified pseudocode but i will add a code if you require.Just tell me through comments

1.Run a loop from 1 to n (Considering that indexing is from 1) do

2. Check If the current element is greater than v than

i. return index

done

3. return NIL

b) A variable say "current_index" will be inititalized by 1 and termination condition will be current_index should be less than equals to number_of_elements

Now this condition is checked if found to be true then we enter the loop

In the loop we check whether the element at current_index is > v and if so then return current_index

Else the current_index increases by 1 and then the loop condition is checked again

Note that If any value in array is greater than v than return statement will be executed thus terminating the function but if no value > v than we reach the end of the array when current_index becomes number_of_elements + 1 hence we come out of the loop In the end NIL is returned indicating that none of the value of array is gretaer than v

Hope i have answered your question satisfactorily.Leave doubts in comment section if any.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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