The following function is intended to return the value of a[1] + a[2] + … + a[n]

Question

The following function is intended to return the value of a[1] + a[2] + … + a[n] for n 1.
(The sum of the first n entries in an array of integers).
Prove that the function is correct, or explain why it does not produce correct results.

ArraySumA(integers n, a[1], a[2], … , a[n])
Local variables:
integers i, j
    i = 0
    j = 0
    while i n do
        i = i + 1
        j = j + a[i]
    end while
    // j now has the value of a[1] + a[2] + … + a[n]
    return j
end function ArraySumA

Q: j = a[1] + … + a[n – 1]
Q(0): j0 = a[1] + … + a[n – 1]
cannot be proven true for base case so the function is proven incorrect

none of these are correct

Q: j = a[1] + … + a[i – 1]
Q(0): j0 = a[1] + … + a[i0 – 1]
            true since j = 0, i = 1 before the loop is entered, so the equation becomes
            0 = a[1-1] which is 0 = a[0] and there is no a[0] term so the value is vacuously 0.
Q(k): jk = a[1] + … + a[ik – 1]
Q(k + 1): jk+1 = a[1] + … + a[ik+1 – 1]
            note: jk+1 = jk + a[ik] and ik+1 = ik + 1
            jk+1                                                    left side of Q(k + 1)
            jk + a[ik]                                            assignment rule
            a[1] + … + a[ik – 1] + a[ik]               inductive hyp
            ik+1 = ik + 1 so ik = ik+1 - 1               rewrite
            a[1] + … + a[ik – 1] + a[ik+1 - 1]       by substitution
This is the right side of Q(k + 1) so Q is our loop invariant
At loop termination j = a[1] + … + a[i- 1] and i = n + 1, so j = a[1] + … + a[n]

begins the sum with a[0]

makes one too many passes through the loop and adds a[n+1] to the sum

Q: j = a[1] + … + a[n – 1]
Q(0): j0 = a[1] + … + a[n – 1]
cannot be proven true for base case so the function is proven incorrect

none of these are correct

Q: j = a[1] + … + a[i – 1]
Q(0): j0 = a[1] + … + a[i0 – 1]
            true since j = 0, i = 1 before the loop is entered, so the equation becomes
            0 = a[1-1] which is 0 = a[0] and there is no a[0] term so the value is vacuously 0.
Q(k): jk = a[1] + … + a[ik – 1]
Q(k + 1): jk+1 = a[1] + … + a[ik+1 – 1]
            note: jk+1 = jk + a[ik] and ik+1 = ik + 1
            jk+1                                                    left side of Q(k + 1)
            jk + a[ik]                                            assignment rule
            a[1] + … + a[ik – 1] + a[ik]               inductive hyp
            ik+1 = ik + 1 so ik = ik+1 - 1               rewrite
            a[1] + … + a[ik – 1] + a[ik+1 - 1]       by substitution
This is the right side of Q(k + 1) so Q is our loop invariant
At loop termination j = a[1] + … + a[i- 1] and i = n + 1, so j = a[1] + … + a[n]

begins the sum with a[0]

makes one too many passes through the loop and adds a[n+1] to the sum

Explanation / Answer

ArraySumA(integers n, a[1], a[2], … , a[n])
Local variables:
integers i, j
i = 0
j = 0
while i n do   //This loop runs for value from i = 0 to n. Note: This is running till n, and not n-1, and this starts from 0, and not 1.
i = i + 1       //This statement increments i value before reading the array value, which makes sure its not reading from a[0].
               //But when i = n, the loop condition still satisfies, but now, i value is incremented to n+1.
j = j + a[i]    //And here comes the problem. It tries reading from a[n+1] at the end, which leads to array out of bounds.
end while
// j now has the value of a[1] + a[2] + … + a[n]
return j
end function ArraySumA

So, the answer is:

e. makes one too many passes through the loop and adds a[n+1] to the sum

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.