CSC161 2010F Imperative Problem Solving

Class 25: Interactive Testing

Back to Unit Testing. On to Program Correctness and assert.

This outline is also available in PDF.

Held: Friday, 8 October 2010

Summary: We do some hands-on explorations of testing.

Related Pages:




What did you learn from the previous class?

Two stories

Printout-based Testing at Bell Labs

Doug McIlroy, a famous computer scientist, posted the following to The Risks Digest: Forum on Risks to the Public in Computers and Related Systems:

Sometime around 1961, a customer of the Bell Labs computing center questioned a value returned by the sine routine. The cause was simple: a card had dropped out of the assembly language source. Bob Morris pinned down the exact date by checking the dutifully filed reversions tests for system builds. Each time test values of the sine routine (and the rest of the library) had been printed out. Essentially the acceptance criterion was that the printout was the right thickness; the important point was that the tests ran to conclusion, not that they gave right answers. The trouble persisted through several deployed generations of the system.
McIlroy, Doug (2006). Trig routine risk: An Oldie. Risks Digest 24(49), December 2006.

If, instead of a thick printout, Bell Labs had arranged for a count of successes and a list of failures, they (and their customers) would have have been in much better shape.

Binary Search in Java

Josh Bloch, the software engineer responsible for implementing the binary search in the Java libraries, wrote the following:

The version of binary search that I wrote for the JDK contained the same bug. It was reported to Sun recently when it broke someone's program, after lying in wait for nine years or so.
The bug is in this line:
6: int mid =(low + high) / 2;
In Programming Pearls Bentley says that the analogous line "sets m to the average of l and u, truncated down to the nearest integer." On the face of it, this assertion might appear correct, but it fails for large values of the int variables low and high. Specifically, it fails if the sum of low and high is greater than the maximum positive int value (231 - 1).
Bloch, Josh (2006). Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken. Google Research Blog, available at (Dated June 2, 2006.)


Systematic Testing

Have you identified (another) bug? There is one. How did I find it? Incredibly systematic testing.

Back to Unit Testing. On to Program Correctness and assert.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Wed Dec 8 10:57:09 2010.
The source to the document was last modified on Fri Aug 13 15:41:47 2010.
This document may be found at

Samuel A. Rebelsky,