Week Seven

Monday,
---------- Oct. 23 2008

Today's lecture was presented by Nick Cheng from UTSC because Danny was at UTM doing some kind of a survey regarding CSC207. We discussed the meaning of program correctness. One of the definitions we came up with was; “a program is correct if it produces the correct output given that the input was correct."
From this definition, we started talking about pre-and-post conditions. It is interesting how careful we should be when defining them. For example, if you have a function that returns the index of the first occurrence of some x in a list L, you have to say in the postcondition that L remains unchanged. Otherwise, doing something like L[0] = x and then returning 0 will be perfectly right.

Wednesday,
---------- Oct. 25 2008
We proved the correctness of binary search. The proof was long but difficult. There are several cases which we need to trace as follows: If the value at the middle(call it L[m]) is less that x and x is in L, if L[m] is less that x and x is not in L, if L[m] is greater than x and x is in L, and finally, if L[m] is greater than x and x is not in L.
Doing Question 4/Assignment 2 was a great practice because it requires a very similar kind of proof.


Friday,
---------- Oct. 27 2008
We worked on gcd(n,m) and pow(n, m) as examples of divide and conquer algorithms.