Loop invariant of a running sum array?

Question

So I was given this algorithm :

Algorithm RunningSum(int[] A)
n = A.length;
for i = 2 to n do
A[i] = A[i] + A[i - 1]
end
return A;
end

and I need to find the loop invariant
but I can figure out what the output could be...
lets say I have a array

a[4]= {1,2,4,3}

will the output be a[4] = {1,3,6,7} from {1,(1+2),(2+4),(4+3)} or will it be a[4]={1,3,7,10} from {1,(1+2),(3+4),(7+3)}

Thanks in advance.

Answer 1

In computer science, a loop invariant is a property of a program loop that is true before (and after) each iteration.

Source: https://en.m.wikipedia.org/wiki/Loop_invariant

For

"property of a program loop" .. that is true

We can also say "logical condition" or just boolean. ;)

For the given code/loop/algorithm:

Algorithm RunningSum(int[] A)
  n = A.length;
  for i = 2 to n do
    A[i] = A[i] + A[i - 1]
  end
  return A;
end

We can surely state, that:

• i >= 2
• AND i <= n (< or <= ..depends on your "language"...to be exact:)
• AND accordingly (in the scope of i): A[i] == A[i] + A[i - 1] (equality! not assignment)
• (n == A.length, A == A ... + all "tautologies" ;)

.. are all true "before (and after) each iteration", thus our "loop invariant(s)" (of concern)

Regarding "output"/algorithm interpretation, i more tend to:

a[4]={1,3,7,10} from {1,(1+2),(3+4),(7+3)}

.#

Answer 2

This may vary in some programming languages, but most common languages will produce the output {1,3,7,10}. The best way to find out is just run the code and print the output.

Answer 3

This is a scan or prefix-sum operation. The invariant at the start of the loop body is that

in iteration i, A[i] is the sum of all previous A[j]

plus stuff about bounds and such.