Please do problem3 In this problem we are given a sequence a

Please do problem3

In this problem, we are given a sequence a_1, a_2, ..., a_n of integers and we want to return a list of all terms in the sequence that are greater than the sum of all previous terms of the sequence. For example, on an input sequence of 1, 4, 6, 3, 2, 20, the output should be the list 1, 4, 6, 20. The following algorithm solves this problem. procedure PartialSums(a_1, a_2, ..., a_n: a sequence of integers with n greaterthanorequalto 1) total:= 0 Initialize an empty list L. for i:= 1 to n if a_i > total Append a_i to list L. total:= total + a_i return L Prove the following loop invariant by induction on the number of loop iterations: Loop Invariant: After the i^th iteration of the for loop, total = a_1 + a_2 + ... + a_t and L contains all elements from a_1, a_2, ..., a_t that are greater than the sum of all previous terms of the sequence. Use the loop invariant to prove that the algorithm is correct, i.e., that it returns a list of all terms in the sequence that are greater than the sum of all previous terms of the sequence.

Solution

Loop invariants is all about using intution for what the code does .it just tells wheather the code is true or false for each time the loop runs .

properties of loop invarients :

1) initialisation

2)maintainence

3)termination.

if all these properties holds for the given program then we can say that the program is correct.

so we will proof all these properties inorder to satisfy the proof invarient

Initialisation :

for the very first time if the loop holds true then we say that the property satisfy .

for i=0 // when list is empty

total =0 // this is what the value is set to so it holds true

in the above example the sum of all previous terms will always be less than the first term so we can say that the initialisation holds true .

maintenance

for (i=1 to n-i ) // every intermediate itteration

if a_i >total //checks the values of a in ith iteration with variable total

append a_i to list L the value is appended to the list then

total =total+a_i // the value of total is updated

if we take ant value of i and put it in the above code segment we can easily see that the code holds true .

given the loop holds for arbitrary operations so it also hold for the next iteration , it does not change the answer .so this property is also satisfied .

termination :

for i=n // last iteration

When the for-loop terminates i=n. Now the loop invariant gives: The variable total contains the finalvalue . This is exactly the value that the algorithm should output, and which it then outputs. Therefore the algorithm is correct.