a) Prove the following loop invariant by induction on the number of loop iterations:

Loop Invariant: After the kth iteration of the for loop, total = a1 + a2 + + ak and L contains

all elements from a1 , a2 , . . . , ak that are greater than the sum of all previous terms of the sequence.

b)

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.