The following function is intended to return the value of a[1] + a[2] + … + a[n]
ID: 3787157 • Letter: T
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.
ArraySumB(integers n, a[1], a[2], … , a[n])
Local variables:
integers i, j
i = 1
j = 0
while i n do
j = j + a[i]
i = i + 1
end while
// j now has the value of a[1] + a[2] + … + a[n]
return j
end function ArraySumB
begins the sum with a[0]
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]
makes one too many passes through the loop and adds a[n+1] to the sum
none of these are correct
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
begins the sum with a[0]
b.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]
makes one too many passes through the loop and adds a[n+1] to the sum
d.none of these are correct
e.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
Explanation / Answer
This function provided is correct because..
(i) passing parameteres are correct. All array values are passing.
(ii) Loop is ending after processing all array values.
(iii) storing the sum values in j variable, and every number is keep on adding to j variable.
(iv) finaly returning the result.
--------------------------------------------------------------------------------------------------------------
So from given options...
(a) is correct, since array first starts from a[0]
(b) is wrong, since it states a[0] is vacously 0. But a[0] is valid and it has value.
(c) is wrong, since every element is passing only once and adding to sum
(d) is wrong, since already we proven first option is correct.
(e) is wrong, since above function is correct and already provided explanation at starting of this solution.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.