Problem 2: Formulating a loop invariant for the purpose of proving the correctness of an iterative algorithm can be a bit of a challenge. However, for the following algorithm, finding a loop invariant is not difficult. Here is the algorithm: SumArray (A[1..N]): sum = 0 i = 1 for (i < N): { sum = sum + A[i] i=i+ 1 } return sum (a) State a loop invariant the can be used to prove the correctness of this algorithm (correct calculation of the sum of all values in A[1..N]). (b) Show the prove using your invariant in three steps: initialization, maintenance, and termination.

Problem 2: Formulating a loop invariant for the purpose of proving the correctness of an iterative algorithm can be a bit of a challenge. However, for the following algorithm, finding a loop invariant is not difficult. Here is the algorithm: SumArray (A[1..N]): sum = 0 i = 1 for (i < N): { sum = sum + A[i] i=i+ 1 } return sum (a) State a loop invariant the can be used to prove the correctness of this algorithm (correct calculation of the sum of all values in A[1..N]). (b) Show the prove using your invariant in three steps: initialization, maintenance, and termination.