Outline of Class 19: Assertions

Miscellaneous

• As I mentioned earlier, I've been spending this week working on the rough draft of a grant proposal. The intent of the grant is to provide multimedia-based examples in 103, 151, 152, and 153. I'd appreciate your comments on my sample exercise: one on cut detection and one on facial distortion.
• Any questions on the readings?
• Wyatt and Chris will be presenting their case study today. Their case study can be found at http://www.math.grin.edu/~debeer/roundingerror.html.
• Any volunteers for next week? If not, I'll choose the volunteers.

Program correctness

• It is no secret that programs regularly contain bugs, even programs written by professional programmers who use modern techniques (like structured and object-oreinted design) and who have studied software engineering.
• Why? For a number of reasons.
• Are these bugs serious? Most eventually have some impact on the users of the program. In some cases, the consequences are deadly.
• Suppose you were required to write a program upon which your friends' lives depended (e.g., if your friends were scuba divers and you had to write the "oxygen left" computation they used). How could you ensure that your program was correct?

Detour: Binary search

• As Bently suggests, many programmers even fail to implement binary search correctly, even when given good specifications.
• I've replicated his results in other classes, but we'll try it again here. Write a binary search routine (in pseudocode) using the following specification:

  This is a slight variation on a specification of iterative binary search due to Bentley and is from column four of Programming Pearls (Addison-Wesley 1986).

  We are to determine whether the sorted array X[1..N] contains the element T. We calculate P, the position of T in X. When P is zero, T is not in X[1..N]. Otherwise, 1<=P<=N and T=X[P].

  We know that N>gt;=0 and that X[1] <= X[2] <= ... <= X[N]. When N=0 the array is empty. The types of T and the elements of X are the same.

  Binary search solves the problem by keeping track of a range within the array in which T must be if it is anywhere in the array. Initially, the range is the entire array. The range is shrunk by comparing its middle element to to T and discarding half the arrange. The process continues until T is discovered in the array or until the range in which it must lie is known to be empty.