===========================================================================
CSC 236 Tutorial Solutions for Week 7 Winter 2012
===========================================================================
Consider the following algorithm (from Exercise 3). I have added line
numbers to make it easier to refer to specific parts of the algorithm
during the proof, and extra comments for Question 3 below.
Mystery(A,b,e):
# A is a list and b,e are indices such that 0 <= b <= e+1 <= len(A)
1. if b > e: return 0
2. m = floor((b + e) / 4)
3. s = Mystery(A, b, b+m-1)
# loop precondition goes here...
4. for i = b+m to e-m:
5. s = s + A[i]
# loop postcondition goes here...
6. s = s + Mystery(A, e-m+1, e)
7. return s
1. State clear and precise preconditions for this algorithm.
(Note that this is partially answered by the comment at the start of the
algorithm.)
Intuitively: b and e must be valid indices into A; elements of A must
be numeric, because they are being added together
Formally:
- A is a list of numbers (values that can be added to each other)
- b,e are integers such that 0 <= b <= e+1 <= len(A)
2. State clear and precise postconditions for this algorithm.
Intuitively: the algorithm adds all the elements of A together
Formally:
- Mystery(A,b,e) returns A[b] + ... + A[e]
3. Prove the correctness of this algorithm -- you may assume that the loop
is correct without proof, as long as you state clear pre- and post-
conditions specifically for the loop (where indicated by comments).
Loop precondition: s = A[b] + ... + A[b+m-1] (s = 0 if m = 0)
Loop postcondition: s = A[b] + ... + A[e-m]
By induction on n = e - b + 1, we prove that Mystery(A,b,e) terminates
and returns A[b] + ... + A[e] for all lists of numbers A and integers
b,e such that 0 <= b <= e+1 <= len(A).
Base Case: Suppose A is a list of numbers and b,e are integers such
that 0 <= b = e+1 <= len(A).
Then, the call Sum(A,b,e) executes only line 1 and returns 0,
and 0 = sum of empty list.
Hence, Mystery(A,b,e) terminates and returns A[b] + ... + A[e].
Ind. Hyp.: Suppose n >= 1 and, for all integers b,e such that
0 <= e - b + 1 < n, Mystery(A,b,e) terminates and returns
A[b] + ... + A[e] for all lists of numbers A such that
0 <= b <= e+1 <= len(A).
Ind. Step: Suppose e - b + 1 = n and A is a list of numbers such that
0 <= b <= e+1 <= len(A).
Then, Mystery(A,b,e) executes the test on line 1 (which fails
since n >= 1 implies e >= b), followed by line 2.
The recursive call on line 3 is made on an input that satisfies
the preconditions (0 <= b <= b+m-1+1 = b+m <= len(A)) and the
input size is exactly b+m-1 - b + 1 = m = floor(n/4) < n so by
the Ind. Hyp., we know that this call will terminate and return
A[b] + ... + A[b+m-1].
This means that the loop on line 4 is entered with its
preconditions satisfied.
Hence, when the loop terminates, s = A[b] + ... + A[e-m].
When the recursive call on line 6 is made, the arguments meet
the precondition because 0 <= e-m+1 <= e+1 <= len(A), and the
input size is again exactly floor(n/4).
By the ind. hyp., thise call terminates and returns
A[e-m+1] + ... + A[e].
Therefore, the current call also terminates and returns
A[b] + ... + A[e-m] + A[e-m+1] + ... + A[e] = A[b] + ... + A[e].
Hence, for all b,e such that e - b + 1 = n, Mystery(A,b,e)
terminates and returns A[b] + ... + A[e], for all lists of numbers A
such that 0 <= b <= e+1 <= len(A).
By induction, Mystery(A,b,e) terminates and returns A[b] + ... + A[e]
for all lists of numbers A such that 0 <= b <= e+1 <= len(A).