Computers and Technology

Consider the following program specification: input: an integer n > 0 and an array - 1)] of n integers. output: the largest index s such that a[s] is the smallest value in - 1)].for example, if n = 10 and a = [ 4, 8, 1, 3, 1, 5, 4, 7, 1, 2 ] (so a[0] = 4, a[1] = 8, then the program would return 8, since the smallest value in a is 1 and the largest index at which 1 appears is index 8.consider the following implementation: indexofmin(n, a)(1) i ← 1(2) m ← a[0](3) s ← 0(4) while i < n(5) if a[i] ≀ m then(6) m ← a[i](7) s ← i(8) end(9) i ← i + 1(10) end(11) return s
in the implementation above, line numbers are given so you can refer to specific lines in your answers and ← is used to indicate assignment. part a (18 points)use induction to establish the following loop invariant right before the while test in line (4) is executed: 0< i ≀ nm = a[s]m = min a[0 .. (i - 1)] (i. e., m is the minimum value in that appears in the array a between indices 0 and i - 1, inclusive)s is the largest index at which min a[0 .. (i - 1)] appears
hints and tips: use only one induction proof and prove each of the four parts of the invariant in your base case and inductive step. you may assume that i and s will always be integers (i. e., you don't have to prove this).part b (7 points)prove the correctness of the implementation by arguing partial correctness and termination.

answer
Answers: 3

Similar questions

Do you know the correct answer?
Consider the following program specification: input: an integer n > 0 and an array - 1)] of n...

Questions in other subjects:

Konu
Mathematics, 01.09.2019 12:30