Thursday, May 24, 2007

Algorithm proof by mathematical induction.

In analysis of algorithms, we learned a technique similar to mathmatical induction whereby the algorithm is shown that if it is true for case N, it is true for case N+1. Then, it is shown to be true for some specific case.

There is a weakness in this method. Because computer programs are supposed to have a start and stop case and not be running infinitely, these cases must also be examined, individually, so, in addition to the proof in the first paragraph, we must also demonstrate that the algorithm handles the first case and the last case.

There is another special case that messes up many computer programmers: the zeroth case, i.e., the case where there are no records to process. Many programmers assume there will be an input, so their programs do stupid things, such as initialize counters at 1, rather than initializing at zero and allowing an increment only when the input actually happens.

No comments: