Subsection 8.4.8 Program (In)correctness and Proof by Counterexample
When we write code, we’d like to be able to prove that it’s correct. What we mean by that is that, in all circumstances, it does what it is supposed to do. Unfortunately, this is often difficult. We typically can’t do it by exhaustively enumerating all possible circumstances: there may be millions (or more) of them. Fortunately, there are other techniques that can be used, at least in some cases.
Sadly, it is sometimes easier to prove that a program is incorrect. All it takes is one counterexample. Finding this counterexample is often the job of the testing department. Of course, if they fail to find a counterexample, we’re still not sure that there are no bugs. All we know is that we haven’t found any yet.
Suppose that we are running an animal clinic. We have two technicians, Chris and Kelly, and each morning we want to split the animals between them in such a way that they each have the same number of animals to tend to that day.
Consider the following program (written in an easy to read pseudocode). Assume that animal_list is the list of animals to be tended.
Initialize both Chris’s and Kelly’s list to the empty list.
For odd values of i, starting at 1, and going to length(animal_list) - 1 do this:
Output the two lists.
Try simulating this program on a couple of possible animal_lists. On the basis of your experiments, do you think that this program works (i.e., all animals get assigned and both Chris and Kelly have the same number of animals to tend to):
All of the time.
Some but not all of the time. In this case, give an example where it does work and one where it does not.
Never.
Exercises Exercises
1.
Suppose that we have a list of sales that have occurred during each month this year. We want to go through and tally how many sales occurred on each day. So, for example, we might output a table like this, which we’ll call SUMMARY:
| 1 | 34 |
|---|---|
| 2 | 52 |
| 3 | 17 |
Consider the following program for doing this for the month of February. (The program is written in a hopefully easy to read pseudocode):
Initialize SUMMARY, an array that contains 28 rows: Set the values in the first column (corresponding to the date) to the sequence of integers 1, 2, …, 28. Set all values in the second column to 0.
-
Walk through the list of sales records. For each one do this:
Extract the date of the sale.
Add 1 to that date’s count in SUMMARY.
Output SUMMARY.
Try hand simulating this program. Which of the following is true of it:
It works all the time.
It works some but not all of the time. In this case, you should be able to give an example where it does work and one where it does not.
It never works.
Correct answer is B
2.
Suppose that we have a list of heights of all of the girls in the chess club. Call the list HEIGHTS. We want to compute the average height of the girls.
Consider the following pseudocode program for doing that:
1. Initialize SUM to 0. 2. Initialize NUMBEROFGIRLS to 0. 3. For each element of HEIGHTS do this: 1.1. Add that element of HEIGHTS to SUM. 1.2. Add 1 to NUMBEROFGIRLS. 4. Set AVERAGE to SUM/NUMBEROFGIRLS.
Try hand simulating this program. Which of the following is true of it:
It works all the time.
It works some but not all of the time. In this case, you should be able to give an example where it does work and one where it does not.
It never works.