Question

Loop Invariants.

I need help on the 15 point question. The 10 point question is the "procedure" from the previous question.
2: (10 points) Consider the algorithm for insertion sort shown below. The input to this algorithm is an array A. You must assume that indexing begins at 1. 1: for j = 2: A.length do key = A[j] i=j-1 while i > 0) and A[i] > key do A[i+1] = A[i] i=i-1 A[i+1] = key 3: 4: 5: 6: 7:

Answer 1

15 points

Given algorithm to find minimum integer in array A
//assuming array contains at least 1 item
Precondition://it is placed before the segment(loops/statements),it matches all requirements for program segement, inorder produce desire output
min=1 //here min denotes the minimum integer index of A,initially setting first integer as min value in array
//so that, we can compare it with remaining elements, to satisy loop invaraint
loop invariant:
before the jth iteration of loop, min(variable) contains the index minimum index of integer in subarray A[1:j-1]
//so, precondition is true by loop invariant
Postcondition://it is place after the segment/code
//after executing loop//breaks when j exceeds n
min contains the index of minimum integer in array A
//since precondition is true, and by loop invariant, min will always contains index of minimum integer in array A[1:n]