=========================================================================== 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).