2. (15 pts) Given a sequence of n numbers A-(al.a2.. . . , an) and a target valu
ID: 3744002 • Letter: 2
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 conditionsExplanation / 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
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.