Skip to content
MINH VO A working notebook
by an engineer in Vietnam
Foundation8 min read

Choosing test cases for a beginner algorithm

Choose algorithm tests from an argmax contract, expose negative-value and tie bugs, and combine exact examples with exhaustive checks and useful properties.

Pencil-drawn graph on beige paper, with olive paths connecting its nodes

Useful algorithm tests come from the result you promised, especially the parts that are easy to leave implicit. For a beginner implementing argmax, returning a position instead of a value already creates several decisions. Which position should win a tie? What happens on empty input? Are negative numbers allowed?

Use this contract: accept a nonempty list of integers and return the index of its first greatest value. Reject an empty list with ValueError. Do not modify the input. These sentences supply test cases before there is any code to inspect, which helps keep the tests independent of the implementation’s structure.

Turn each clause into a counterexample

An implementation that initializes its best value to zero fails on [-5, -2, -9]. An implementation that replaces the best position on >= instead of > returns the last maximum for [3, 8, 8, 1]. Returning -1 on empty input violates the error contract even if a caller happens to accept it.

Contract clauseInputRequired behaviorBug it can expose
Nonempty singleton[7]Return 0Loop skips the only value
Negative integers[-5, -2, -9]Return 1Best value initialized to zero
First tied maximum[3, 8, 8, 1]Return 1Equality replaces the first match
Maximum at the end[1, 2, 9]Return 2Last position never examined
Empty input[]Raise ValueErrorSentinel returned silently

The table is not a list of arbitrary edge cases. Every row isolates a meaningful condition. An all-equal list is especially useful for the tie rule because every update after the first would be suspicious. A maximum at the first position checks that the implementation can keep its initial candidate.

Argmax test map connecting contract clauses to a singleton, an all-negative list, a tied maximum, an end maximum, and an empty input errorView full-size image ↗

Keep the expected answers literal in small examples. If every expected answer is computed by copying the algorithm under test, a shared mistake can make both sides agree.

Write a small implementation and test its interface

The first element supplies a valid initial candidate. Each later element replaces it only when strictly greater. Keeping the earlier index on equality implements the tie rule directly.

def first_argmax(values):
    if not values:
        raise ValueError('argmax requires at least one value')
    best = 0
    for position in range(1, len(values)):
        if values[position] > values[best]:
            best = position
    return best

cases = [([7], 0), ([-5, -2, -9], 1), ([3, 8, 8, 1], 1), ([1, 2, 9], 2)]
for values, expected in cases:
    before = list(values)
    assert first_argmax(values) == expected
    assert values == before

try:
    first_argmax([])
except ValueError:
    pass
else:
    raise AssertionError('empty input did not raise ValueError')

These assertions are convenient for a short example. In a maintained Python suite, unittest offers assertions such as assertEqual and assertRaises, with isolated test cases and failure reports. Its basic example demonstrates that structure. Bare Python assertions can be disabled in optimized execution, so they should not enforce a production input contract.

Checking the input copy after the call verifies the no-mutation promise. That catches an implementation that sorts the list before taking its maximum, even if it somehow returns the correct original index for a few examples. The contract concerns behavior visible to the caller, not just the final integer.

Use exhaustive small inputs as a second layer

For lists up to length five drawn from the values minus two through two, there are 5 + 25 + 125 + 625 + 3125 = 3905 nonempty inputs. That space is small enough to enumerate completely. It contains many duplicate patterns and negative-value combinations that would be tedious to write separately.

from itertools import product

for size in range(1, 6):
    for values in product(range(-2, 3), repeat=size):
        actual = first_argmax(values)
        expected = max(range(size), key=values.__getitem__)
        assert actual == expected

Python’s max documentation states that the first encountered item wins when several items are maximal. That makes the reference expression match the declared tie rule. The reference is a separate standard-library operation rather than another hand-copied loop, although it still depends on the same ordering contract.

Passing every input in this finite domain proves behavior for that domain. It does not prove behavior for every possible integer or list length. The algorithm’s loop invariant supplies the general argument: after each iteration, best is the first maximum among the positions examined so far.

Properties can strengthen or weaken a test

For every returned index i, the index must be in bounds and no value may exceed values[i]. That property alone allows any occurrence of a tied maximum. Add the condition that every earlier position has a strictly smaller value to recover the first-occurrence rule.

Adding the same integer to every element should preserve the answer. Multiplying every element by a positive integer should also preserve it. Multiplying by a negative integer generally changes maxima into minima, so it is not a valid invariance property. These relationships can create follow-up tests without requiring you to compute a fresh expected index by hand.

A weak property can give false confidence. Checking only that the returned value appears somewhere in the input would accept almost any valid index. Likewise, repeatedly testing large random positive lists may never expose a zero-initialization bug. Keep focused examples for each contract clause, then use broader generation to find combinations you did not think to write individually. When a failure appears, retain the smallest input that demonstrates it as a regression test with an explicit expected result.

Check that the tests reject plausible wrong answers

A useful way to assess a small suite is to give it deliberately incorrect implementations. These are examples of mutation testing: introduce a specific behavioral fault and check whether an appropriate test fails. PIT’s basic-concepts documentation explains the same principle with Java bytecode mutations; the faults here are small Python functions. Passing such an experiment does not prove a suite can detect every bug; it establishes that these chosen faults are observable through its assertions.

def last_tie_argmax(values):
    return len(values) - 1 - values[::-1].index(max(values))


def zero_seed_argmax(values):
    best, best_value = 0, 0
    for position, value in enumerate(values):
        if value > best_value:
            best, best_value = position, value
    return best

witnesses = [
    ('singleton', [7], 0),
    ('negative', [-5, -2, -9], 1),
    ('tie', [3, 8, 8, 1], 1),
    ('last', [1, 2, 9], 2),
]
mutants = {'last_tie': last_tie_argmax, 'zero_seed': zero_seed_argmax}
caught = {
    name: [label for label, values, expected in witnesses
           if implementation(values) != expected]
    for name, implementation in mutants.items()
}
assert caught == {'last_tie': ['tie'], 'zero_seed': ['negative']}

The last-tie version passes the negative-only example, and the zero-seed version passes the positive tied maximum. Neither one fault nor one input category stands in for the other. These mutants are tested only on the declared nonempty witnesses here; empty-input rejection and mutation of the caller’s list remain separate interface checks.

A property such as adding a constant to every value will not detect the last-tie mutant. Translation preserves the order of equal maxima, so the wrong last occurrence remains the wrong last occurrence before and after the transformation. Positive scaling has the same limitation. Metamorphic relationships complement a precise expected result; they do not supply a missing tie rule by themselves.

Reduce a failing input without losing its failure

When a larger generated input fails, simplify it while checking that the same contract still fails. For the tied example, removing the initial three leaves [8, 8, 1]; removing the final one then leaves [8, 8]. The required index is zero and the mutant returns one. That two-element witness explains the fault more clearly than a long random list.

def shrink_by_deletion(values, implementation):
    current = list(values)
    while len(current) > 1:
        for position in range(len(current)):
            candidate = current[:position] + current[position + 1:]
            expected = max(range(len(candidate)), key=candidate.__getitem__)
            if implementation(candidate) != expected:
                current = candidate
                break
        else:
            return current
    return current

assert shrink_by_deletion([3, 8, 8, 1], last_tie_argmax) == [8, 8]

The last-tie bug survives deleting three from three eight eight one, then deleting one, leaving eight eight with expected index zero and actual index oneView full-size image ↗

The shrinker never tests an empty candidate because this failure is about the tie rule on nonempty inputs. Each accepted deletion shortens the list, so shrinking terminates. At the result, no single deletion considered by the procedure preserves the mismatch. That is a local deletion-minimal witness, not a guarantee of the smallest possible input under every transformation. It does not reduce integer magnitudes or search all combinations of removals.

Keep the final witness as a literal regression test, including the first-occurrence result. The generator and shrinker help discover and explain a failure; the saved example records exactly what the implementation must continue to do. Try running the same process on the zero-seed fault and explain why a single negative value may pass even though a two-value negative list exposes the error.

Sources & further reading

  1. Python documentation, unittest basic example
  2. Python documentation, max
  3. PIT documentation, Basic concepts
← Back to the journal
All notes

Illustration

100%