Testing, Debugging, and Error Detection

A Correct-Looking Algorithm Can Still Be Wrong

Suppose we want to return the larger of two numbers:

IF a > b
    RETURN a
ELSE
    RETURN a
END IF

The structure looks complete, but both branches return \(a\).

Testing with

does not reveal the problem because the output \(8\) happens to be correct.

Testing with

does reveal it:

A useful test is therefore not merely an input. It includes an expected behavior.

What Is Testing?

Testing evaluates an algorithm on selected inputs and checks whether the observed behavior matches the expected behavior.

Testing may examine:

• final outputs,
• intermediate states,
• error messages,
• termination,
• performance,
• required conditions or invariants.

The purpose is to gather evidence about whether the algorithm behaves correctly over the intended problem domain.

Test Cases

A test case is a selected input together with the expected result or behavior.

For a function

a test case might be:

A table helps organize several cases:

Normal Cases

A normal case is an ordinary input well inside the expected domain.

For an algorithm computing

a normal test might be

The expected output is

Normal cases check whether the main path of the algorithm works as intended.

Boundary Cases

A boundary case lies at or near an important limit in the problem.

Boundary tests are especially valuable because inequalities and loop limits often fail there.

Example

Suppose a rule accepts values satisfying

Important tests include

and often nearby values such as

These cases reveal mistakes involving \(<\) versus \(\leq\).

Invalid and Exceptional Cases

A robust algorithm should also be tested with inputs that violate its preconditions.

For division,

the case

should not be treated like an ordinary valid input.

The expected behavior might be:

• reject the input,
• return an error message,
• request a replacement value.

Testing invalid input checks whether the algorithm protects its own domain.

Expected versus Actual Results

Testing depends on comparison.

The expected result should come from:

• a known mathematical result,
• a hand calculation,
• a trusted reference method,
• a stated specification.

If the expected result itself is wrong, the test is not reliable.

The Test-Debug-Retest Cycle

What Is Debugging?

Debugging is the process of finding, understanding, and correcting the cause of incorrect behavior.

A useful debugging question is not merely:

“Why is the answer wrong?”

It is:

“At what step does the actual state first differ from the expected state?”

That question turns a large failure into a smaller local problem.

Tracing State

Trace tables are one of the most effective debugging tools for simple algorithms.

Consider:

total = 0

FOR i = 1 TO 4
    total = total + 2
END FOR

Expected final total:

If the actual trace differs at iteration \(3\), the problem is likely near the third update rather than somewhere vaguely “in the loop.”

Kinds of Errors

In an actual programming language, there can also be syntax or runtime errors. At the algorithmic level, the categories above are more general.

Assertions and Checks

An assertion is a condition that is expected to be true at a particular point in a process.

Example

If an algorithm is computing a probability, we may assert:

If the result is

the assertion fails and signals a problem.

Assertions turn mathematical expectations into error-detection rules.

Invariants as Error Detectors

An invariant is a property expected to remain true throughout a process.

Example: Running Count

Suppose an algorithm has processed exactly \(k\) values. Then we may expect:

If a trace shows

but

the invariant has been violated.

Invariants are useful both for proofs of correctness and for debugging.

Independent and Redundant Checks

Important computations are often checked in more than one way.

Example: Rectangle Area

Suppose a spreadsheet reports

An independent mental estimate

makes \(96\) plausible.

For higher-stakes work, a second formula, alternate algorithm, or independent calculation may provide a stronger check.

Testing Properties, Not Just Examples

Instead of checking only a few exact outputs, we can also test general properties.

Example: Absolute Value

For every real input, a correct absolute-value algorithm should satisfy

It should also satisfy

These are properties that can be tested across many inputs.

Property-based tests are especially useful when the exact output is difficult to compute independently but a general mathematical relationship is known.

Regression Testing

When a bug is corrected, the failing input should often be saved as a future test.

Suppose an algorithm once failed at

After fixing the zero case, keep \(x=0\) in the test set.

A regression test checks that later changes do not reintroduce an error that was already fixed.

What Testing Cannot Prove

Passing many tests is evidence of correctness, but it is not automatically a proof.

A program can pass

test cases and still fail on the \(1001\)st.

For finite domains, exhaustive testing may be possible. For large or infinite domains, formal reasoning is often needed to establish correctness for every valid input.

A Practical Debugging Workflow

1. Reproduce the failure. Find a specific input that reliably causes it.
2. State the expected result. Know what should happen before investigating.
3. Trace intermediate state. Locate the first incorrect value or branch.
4. Isolate the smallest cause. Narrow the problem to one rule, condition, or update.
5. Correct the cause. Avoid merely hiding the visible symptom.
6. Retest the failing case. Confirm the correction works.
7. Run related tests. Make sure the correction did not break another case.
8. Keep the case as a regression test.

Practical Applications

Software Development

Test suites check functions, interfaces, error handling, and later changes.

Spreadsheets

Check cells, balance identities, and representative row formulas help detect reference mistakes.

Numerical Methods

Residuals, error bounds, and convergence checks help detect failed approximations.

Engineering

Independent calculations and tolerance checks help identify design or measurement problems.

Mathematics

Counterexamples test conjectures, while proof establishes claims over an entire domain.

Worked Examples

Example 1: Boundary Bug

An algorithm should accept ages \(18\) and above:

IF age > 18
    output "eligible"
ELSE
    output "not eligible"
END IF

Test:

Expected:

Actual:

The bug is the boundary operator. The condition should be

Example 2: Wrong Accumulator Start

Suppose we want the product

But the algorithm starts:

product = 0

FOR each x
    product = product * x
END FOR

Every result remains \(0\).

The multiplicative accumulator should start at

Example 3: Missing Invalid Input Check

An average algorithm receives an empty list.

Then

so the formula

attempts division by zero.

A test with the empty list reveals that a guard condition is required.

Example 4: Trace a Logic Error

x = 5
y = x + 2
x = y + 1
y = x * 2

If someone expected \(y=14\), the trace shows the expectation was based on an older value of \(x\). The algorithm may be correct; the expected result may be wrong.

Example 5: Property Test

For a sorting algorithm, every output list should satisfy:

It should also contain the same elements as the input.

These two properties can detect many sorting failures without knowing the exact output in advance for every test.

Example 6: Regression Test

A formula once failed when

After correcting the zero case, add \(x=0\) permanently to the test set so future changes are checked against the known failure mode.

Common Errors

1. Testing Only Easy Inputs

Normal cases may miss boundary, invalid, or rare paths.

2. Using the Same Incorrect Method to Compute the Expected Answer

A test is weaker if the expected result repeats the same mistake as the algorithm under test.

3. Fixing the Symptom Instead of the Cause

A special-case patch may hide one failure while leaving the underlying logic wrong.

4. Changing Several Things at Once

Large simultaneous changes make it harder to identify which correction actually solved the problem.

5. Forgetting to Retest Earlier Cases

A fix for one input can accidentally break another.

6. Treating a Passing Test Suite as a Mathematical Proof

Testing provides evidence. Proof establishes a claim for an entire stated domain.

7. Ignoring Unexpected but Plausible Outputs

Not every error produces an obviously absurd number. Comparison with an expected result is still necessary.

Practice

Boundary Test

A rule accepts

Which input is especially important to test?

Invalid Input

What special case should be tested for an algorithm computing \(a/b\)?

Accumulator Bug

A sum accumulator is initialized to \(1\) instead of \(0\). What kind of error is this most naturally?

Assertion

A computed probability is \(1.2\). Which assertion detects the error?

Testing versus Proof

If an algorithm passes \(10{,}000\) tests over an infinite input domain, has correctness been proved?

The Deeper Idea

Testing and debugging make algorithmic reasoning empirical.

We begin with a specification:

Then we compare it with execution:

A mismatch gives us a counterexample to the claim that the algorithm is correct for that input.

This creates a strong connection with mathematical reasoning:

• test cases are examples,
• failing tests are counterexamples,
• assertions are propositions about state,
• invariants express persistent structure,
• formal proof generalizes beyond selected examples.

Testing therefore does more than “check code.” It teaches a general habit: make expectations explicit, compare them with evidence, and investigate the first place where the two diverge.

Summary

• Testing compares actual algorithm behavior with expected behavior on selected inputs.
• A test case includes an input and an expected result or outcome.
• Normal cases check ordinary behavior.
• Boundary cases test endpoints and transition values.
• Invalid and exceptional cases test whether preconditions are enforced.
• Debugging finds and corrects the cause of incorrect behavior.
• Trace tables help locate the first state that differs from expectation.
• Errors may arise from the specification, logic, boundaries, input handling, arithmetic, or termination behavior.
• Assertions encode conditions that should be true at specific points.
• Invariants can detect violations of expected structure during execution.
• Independent checks are stronger than repeating the same computation.
• Property-based tests check general mathematical relationships across many inputs.
• Regression tests preserve previously failing cases so bugs do not quietly return.
• Passing tests provides evidence of correctness but does not always prove correctness over the full domain.
• A disciplined debugging workflow reproduces, traces, isolates, corrects, and retests a failure.

Reliable computation depends on more than writing an algorithm that appears reasonable. We need ways to challenge it, observe it, detect when expectations fail, and trace those failures back to their cause. Testing finds the evidence; debugging explains it; error detection helps catch the problem sooner.

Algorithms and Computational Thinking

• Previous: Termination and Stopping Conditions
• Algorithms and Computational Thinking — return to the lesson directory.