# 1.11 Testing Algorithms Testing does not prove an algorithm correct, but it exposes mistakes in specifications, invariants, edge cases, and implementation details. A good test suite is built from the problem statement. It checks whether the implementation satisfies the input and output contract under ordinary, boundary, and adversarial conditions. Algorithm tests should not only ask, "Does this example pass?" They should ask, "What assumption would fail if this test failed?" Each test should have a reason. ## Problem You have an algorithm and need a reliable way to test whether the implementation matches the specification. ## Solution Build tests from five sources: ```text 1. Minimal valid inputs 2. Boundary cases 3. Ordinary representative cases 4. Adversarial cases 5. Random cases checked against a simple baseline ``` The strongest practical pattern is to pair an efficient algorithm with a slow, obviously correct implementation. The slow implementation acts as an oracle for small inputs. ## Example: Maximum Subarray Sum Specification: ```text Given a nonempty integer array A, return the maximum sum of any nonempty contiguous subarray. ``` Efficient algorithm: ```text max_subarray(A): best = A[0] current = A[0] for i = 1 to n - 1: current = max(A[i], current + A[i]) best = max(best, current) return best ``` Baseline algorithm: ```text max_subarray_slow(A): best = A[0] for left = 0 to n - 1: sum = 0 for right = left to n - 1: sum = sum + A[right] best = max(best, sum) return best ``` The slow algorithm tries every subarray, so it directly matches the specification. It is too slow for large input, but it is useful for testing small input. ## Fixed Tests Start with examples that target known boundary conditions. ```text [5] -> 5 [-5] -> -5 [-5, -2, -8] -> -2 [0, 0, 0] -> 0 [4, -1, 2, -7, 3] -> 5 [1, 2, 3] -> 6 [-1, 5, -1] -> 5 ``` Each test exists for a reason. The all-negative case checks initialization. The all-zero case checks neutral values. The increasing case checks that the whole array may be optimal. The last case checks that extending a subarray can be worse than restarting. ## Random Testing For small arrays, compare the efficient algorithm against the baseline. ```text for trial = 1 to 10000: n = random integer from 1 to 10 A = random array of length n with values from -20 to 20 assert max_subarray(A) == max_subarray_slow(A) ``` Random testing is effective because it explores many combinations that humans do not naturally write. It is especially useful for algorithms with many branches, such as dynamic programming, graph traversal, and pointer manipulation. ## Metamorphic Tests Some properties can be tested even without knowing the exact answer. These are called metamorphic properties. For maximum subarray sum: ```text If every element is increased by a nonnegative constant, the answer should not decrease. ``` For sorting: ```text sort(sort(A)) = sort(A) ``` For shortest paths with nonnegative edge weights: ```text Removing an edge cannot make the shortest path shorter. ``` For set union: ```text union(A, B) = union(B, A) ``` These tests do not replace exact expected values, but they add coverage across broad input families. ## Testing Invariants When possible, test internal invariants during execution. For example, in binary search, the current interval should always contain every possible remaining answer. In a heap, every parent should satisfy the heap property with respect to its children. In union-find, parent pointers should eventually lead to a representative. Invariant checks are often too expensive for production, but they are useful in debug builds. ```text assert heap_property(H) assert 0 <= left and right < n assert distance[v] <= distance[u] + weight(u, v) ``` These assertions turn vague assumptions into executable checks. ## Adversarial Tests Adversarial inputs are designed to trigger worst cases or common failures. | Algorithm Type | Adversarial Input | | ------------------- | --------------------------------------------------- | | Binary search | Empty array, single element, target outside range | | Quicksort | Already sorted input with bad pivot rule | | Hash table | Many keys with same hash bucket | | DFS recursion | Long chain graph | | Dijkstra | Dense graph or many repeated priority queue entries | | Dynamic programming | Inputs that force all states to be filled | Adversarial testing is especially important when the algorithm has a performance guarantee. A program that is correct on small examples may still fail by timing out, overflowing, or exhausting memory. ## Testing Output with Multiple Correct Answers When multiple outputs are valid, do not compare against one fixed answer. Write a checker. Example: ```text Problem: Return any pair of indices i, j such that A[i] + A[j] = target. ``` Checker: ```text check_pair(A, target, result): if result == none: verify no valid pair exists else: i, j = result assert i != j assert 0 <= i < n assert 0 <= j < n assert A[i] + A[j] == target ``` The checker encodes the acceptance condition from the problem statement. ## Common Pitfalls Do not test only happy paths. Boundary cases often reveal incorrect initialization or termination conditions. Do not use the optimized algorithm as its own oracle. A test must compare against the specification, a baseline, or an independently checked property. Do not hard-code one expected output when the problem allows several valid outputs. Do not ignore performance tests. Correctness on small input does not imply feasibility on maximum input. ## Takeaway Testing turns the specification into executable checks. Use fixed boundary tests, slow baselines, random generation, invariant assertions, and adversarial cases. The goal is not to replace proof, but to catch the mistakes that proofs and informal reasoning often miss.