CSC240 Winter 2021 Homework Assignment 8
due Tuesday March 23, 2021
Define (a, b) to be a pair of locations containing closest numbers in an array of numbers L[1..n] if 1 ≤ a < b ≤ n and the absolute value of the difference between L[a] and L[b] is less than or equal to the absolute value of the difference between the values in every two different locations of L[1..n]. For example, (4,7) and (1,5) are pairs of locations containing closest numbers in [4,15,10,8,3,1,9] and (2,4) is a pair of locations containing closest numbers in [4,10,15,10,5,23,22,20].
Consider the following algorithm: Closest(L, s, e):
1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
ife=s+1
then return (s, e)
c←s+1 fori←s+2toedo
if |L[s] − L[i]| < |L[s] − L[c]|
then c ← i
(u, v) ← Closest(L, s + 1, e) if |L[s] − L[c]| ≤ |L[u] − L[v]| then return (s, c)
else return (u, v)
If you prefer, you may replace line 4 by the two lines 4′. i←s+2
4′′. whilei≤edo and add the line 6′. i←i+1 after line 6.
1. Give clear specifications for Closest(L,s,e) that fully describe the relationship between its possible inputs and outputs.
2. State all loop invariants satisfied by the loop on lines 4–6 that you need for your solution to question 4. Explicitly state at what point in the loop these invariants hold.
3. Prove that all the statements in your solution to question 2 are loop invariants.
4. Prove that Closest is correct with respect to the specifications in your solution to question 1.
Note that, if your specifications do not fully describe the relationship between the possible inputs and outputs of Closest, you may not get full marks for the other questions, even if they are correct.