Algorithms in a Nutshell

Principle: Writing Algorithms Is Hard—Testing Algorithms Is Harder

Because the algorithms we describe are predominantly deterministic (except for those from Chapter 11), it was rather straightforward to develop test cases to ensure that they behaved properly. In Chapter 7, we began to encounter difficulties because we were using path-finding algorithms to locate potential solutions that we did not know in advance. For example, although it was straightforward to write test cases to determine whether the GoodEvaluator heuristic was working properly for the 8-puzzle, the only way to test an A*Search using that heuristic is to invoke the search and manually inspect the explored tree to validate that the proper move was selected. Thus, testing A*Search is complicated by having to test the algorithm in the context of a specific problem and heuristic. We have extensive test cases for the path-finding algorithms, but in many cases they exist only to ensure that a "reasonable" move was selected (for either game or search trees), rather than to ensure that a specific move was selected.

Testing the algorithms in Chapter 9 was further complicated because of floating-point computations. Consider our approach to test Convex Hull Scan. The original idea was to execute a Brute Force Convex Hull algorithm—whose performance was O(n⁴)—and compare its output with the output from Andrew's Convex Hull Scan. During our extensive testing, we randomly generated two-dimensional data sets uniformly drawn from ...