Grade by Grade
A. Programming Concepts and Skills · Algorithm Design and Analysis

Formal Test Plans for Algorithms: Unit, Integration and Regression Testing

A4.2 C2.1About 75 minutes
Learning goals
  • I can write a formal test plan for an algorithm, choosing test cases from its precondition, postcondition and edge cases.
  • I can write unit tests with Python's unittest module and run them.
  • I can design an integration test for functions that work together, and explain regression testing.
  • I can use randomized testing against a trusted result (a test oracle) to find hidden bugs.

Words to know

test plan
A document listing each test: its ID, purpose, input, expected result, actual result and pass/fail.
unit test
A test of one small unit of code (usually one function) on its own.
integration test
A test that checks several units working together correctly.
regression test
Rerunning existing tests after a change, to check that nothing that used to work has broken.
edge case
An input at the extreme of what is allowed: empty, one element, first or last position, largest or smallest value.
test oracle
A trusted way to know the correct answer, such as Python's sorted(), used to check another implementation.
randomized testing
Running an algorithm on many randomly generated inputs and checking each result against an oracle or a property.

A bug that hid for nine years

In 2006, Joshua Bloch, a software engineer at Google, reported that the binary search in Java's standard library (which he had written himself) had a bug that had gone unnoticed for about nine years. The line mid = (low + high) / 2 worked for every array anyone had tested, but for arrays with more than about a billion elements, low + high overflowed Java's 32-bit integers and became negative. (Python's integers do not overflow, which is why the lesson Binary Search: Halving the Problem could use (low + high) // 2 safely.)

The algorithm had been "proved" and used for years. The lesson: careful testing, especially of edge cases, is part of designing an algorithm, not an afterthought. Expectation A4.2 asks you to develop and implement a formal testing plan, for example with unit, integration and regression testing.

Remember from Grade 11

In Testing with a Test Plan: Expected versus Actual (ICS3U) you wrote test plans with normal, boundary and invalid data, compared expected with actual results, and met black-box, white-box, regression and user testing. Now you will apply them to the algorithms of this unit, automate them with Python's unittest module, and add integration and randomized testing.

Unit testsone function at a time: binary_search, merge, insert_atIntegration testsfunctions working together: add_score + rank_ofSystem / acceptance teststhe whole program, against the specificationRegression testing:rerun ALL of theseafter every change
Levels of testing. Unit tests check one function; integration tests check functions working together; system tests check the whole program. Regression testing reruns every test after each change.

Where test cases come from

The contract from Specifying Algorithms: Preconditions, Postconditions and Loop Invariants tells you what to test:

  • Postcondition: every promise is a test. If binary search promises "an index of target, or −1", test present and missing targets.
  • Precondition: test the smallest legal inputs (an empty list, one element). For a function that checks its precondition, test that illegal input is rejected (for example with assertRaises).
  • Edge cases for searches: target at the first index, the last index, the middle; missing targets below the smallest, between two elements, above the largest; duplicates.
  • Edge cases for sorts: empty, one element, two elements, already sorted, reversed, all equal, many duplicates, negative numbers.
  • White-box cases: read the code and make each branch and each loop run zero times, once and many times.
Test targets for binary search on a = [3, 8, 12, 19, 23, 31, 38]3812192331383first19middle38last1below20in a gap99aboveAbove the array: present targets (shaded cells). Below: missing targets. Also test thespecial lists [], [5] and an all-equal list such as [4, 4, 4, 4].
Black-box test targets for binary search, chosen from the specification: present targets at both ends and the middle, and missing targets below, between and above the elements.
IDPurposeInput (a, target)ExpectedActualPass?
BS1present, middlea, 1933✓
BS2present, first indexa, 300✓
BS3present, last indexa, 3866✓
BS4missing, in a gapa, 20−1−1✓
BS5missing, below smallesta, 1−1−1✓
BS6missing, above largesta, 99−1−1✓
BS7empty list[], 5−1−1✓
BS8one element, present / missing[5], 5 and [5], 40 and −10 and −1✓
BS9duplicates[4, 4, 4, 4], 4any of 0 to 31✓
A formal test plan for binary_search with a = [3, 8, 12, 19, 23, 31, 38]. The "Actual" column is filled in by running the tests; BS9 accepts any valid index, because the postcondition only promises "an index".

Unit tests with unittest

Python's standard unittest module turns a test plan into code that runs in a second. Each test is a method whose name starts with test_ inside a class that extends unittest.TestCase. Inside, assertion methods compare actual with expected: assertEqual(actual, expected), assertIn(x, collection), assertTrue(condition), assertRaises(ErrorType, function, arguments). setUp runs before every test to create fresh data.

import unittest
def binary_search(a, target):
"""Return an index of target in sorted list a, or -1."""
low, high = 0, len(a) - 1
while low <= high:
mid = (low + high) // 2
if a[mid] == target:
return mid
elif a[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
class TestBinarySearch(unittest.TestCase):
def setUp(self):
self.a = [3, 8, 12, 19, 23, 31, 38]
def test_middle(self):
self.assertEqual(binary_search(self.a, 19), 3)
def test_first_and_last(self):
self.assertEqual(binary_search(self.a, 3), 0)
self.assertEqual(binary_search(self.a, 38), 6)
def test_missing_inside(self):
self.assertEqual(binary_search(self.a, 20), -1)
def test_missing_outside(self):
self.assertEqual(binary_search(self.a, 1), -1)
self.assertEqual(binary_search(self.a, 99), -1)
def test_empty_and_single(self):
self.assertEqual(binary_search([], 5), -1)
self.assertEqual(binary_search([5], 5), 0)
self.assertEqual(binary_search([5], 4), -1)
def test_duplicates(self):
i = binary_search([4, 4, 4, 4], 4)
self.assertIn(i, [0, 1, 2, 3])
unittest.main(argv=["tests"], exit=False, verbosity=2)

The test results go to the error stream, one line per test (test_duplicates (...) ... ok, and so on for all 6), then Ran 6 tests in 0.000s (your time may differ) and OK. If a test fails, unittest prints FAIL with the expected and actual values. (argv and exit=False let this run inside IDLE or Thonny; in a separate test file you would write just unittest.main().)

Randomized testing with an oracle

Hand-picked tests only find the bugs you thought of. A randomized test generates many inputs and checks each result against a test oracle: a trusted way to get the right answer. For a sort, Python's sorted() is a perfect oracle. Small random lists with a small range of values produce lots of duplicates and edge cases automatically.

import random
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
def buggy_sort(a):
"""A 'sort' with a subtle bug: the inner loop stops one place too early."""
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j > 0 and a[j] > key: # should be j >= 0
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
def random_test(sort, trials=1000):
"""Compare sort against Python's sorted() on many random lists."""
random.seed(12)
for t in range(trials):
n = random.randint(0, 12)
data = [random.randint(-5, 5) for _ in range(n)] # small range: many duplicates
expected = sorted(data)
actual = data[:]
sort(actual)
if actual != expected:
return "FAIL on " + str(data) + ": got " + str(actual)
return "passed " + str(trials) + " random tests"
print("insertion_sort:", random_test(insertion_sort))
print("buggy_sort:", random_test(buggy_sort))

Output, one line each: insertion_sort: passed 1000 random tests, buggy_sort: FAIL on [-1, 5, 3, 5, 0, -3, 1]: got [-1, -3, 0, 1, 3, 5, 5]. The buggy version passes many hand tests (try [1, 3, 2] or [5, 7, 6]), because it only fails when a key must move all the way to index 0. The random test finds a failing input in a fraction of a second, and that input becomes a new unit test.

When there is no oracle, test properties instead. For any sort: the output is in order (each element ≤ the next) and it contains exactly the same elements as the input (compare sorted() of both, or count each value). For a search: if it returns i ≥ 0, then a[i] == target; if it returns −1, then target not in a.

Integration testing

Units that each pass their own tests can still fail together: one function may assume something the other does not guarantee (a sorted list, 0-based versus 1-based positions, integers versus decimals). An integration test runs the units on shared data, in a realistic order. Here a leaderboard uses the insertion-point binary search from Subprograms to Insert and Delete Array Elements for both adding scores and finding ranks.

def insertion_point(a, value):
"""Index of the first element greater than value (a is sorted)."""
low, high = 0, len(a) - 1
while low <= high:
mid = (low + high) // 2
if a[mid] <= value:
low = mid + 1
else:
high = mid - 1
return low
def add_score(board, score):
"""Insert score into the sorted list board, keeping it sorted."""
board.insert(insertion_point(board, score), score)
def rank_of(board, score):
"""Return the 1-based position of the first copy of score, or 0 if absent.
Precondition: board is sorted and all scores are integers."""
i = insertion_point(board, score - 1) # first index with value > score - 1
if i < len(board) and board[i] == score:
return i + 1
return 0
# Integration test: the units must work TOGETHER on a shared board.
board = []
for s in [70, 85, 60, 85, 99, 60]:
add_score(board, s)
assert board == [60, 60, 70, 85, 85, 99], board
assert rank_of(board, 60) == 1
assert rank_of(board, 85) == 4
assert rank_of(board, 99) == 6
assert rank_of(board, 75) == 0
print("integration tests passed:", board)

Output: integration tests passed: [60, 60, 70, 85, 85, 99]. Each assert is one integration test case. Note the precondition in rank_of: it searches for score - 1, which only works for whole-number scores: rank_of([60.5, 61.0], 61.0) returns 0 even though 61.0 is on the board. A test plan should include a decimal case, and either the code is fixed or the specification forbids decimals.

Worked example

Fixing a bug with a regression test

A user reports: "When two players have the same score, the rank shown for the second one is wrong." Describe a professional process for fixing it, using the test plan.

  1. 1. Reproduce: write a new unit test that shows the bug, before changing the code, e.g. assertEqual(rank_of([60, 60, 70], 60), 1). Run it and confirm that it fails (if it passes, you have not found the bug yet).
  2. 2. Fix the code until the new test passes.
  3. 3. Regression test: rerun all the unit and integration tests, not just the new one. A fix in insertion_point could break add_score.
  4. 4. Keep the test in the suite forever, so the same bug can never come back unnoticed.
  5. 5. Record it in the test plan: new ID, purpose ("tied scores, reported bug"), input, expected, actual, pass. In team projects, version control (the topic of Software Development: Managing a Team Software Project) keeps the tests with the code.

Write a failing test first, fix the code, rerun the whole suite (regression testing), and keep the new test in the plan.

Testing efficiency, too

Some promises are about speed, and you can test those as well. Add a counter to binary search and assert that it never makes more passes than the number of binary digits of n; or assert that merge sort makes at most n log₂ n comparisons. These tests catch a "correct but slow" regression, such as someone accidentally making the same recursive call twice.

Just for fun

A software tester walks into a café. Orders 1 coffee. Orders 0 coffees. Orders −1 coffees. Orders 99 999 999 coffees. Orders a lizard. Orders "asdfghjkl" coffees.

The first real customer walks in and asks where the washroom is. The café catches fire. (Edge cases: you can never think of them all, which is why randomized and user testing matter too.)

Hands-on activity

Build a test suite for your own algorithms

You need: a computer with Python, and the functions you wrote in this unit (or copies of the lesson versions).

  1. Choose two units: one search (binary search or first_index) and one sort (insertion sort or merge sort).
  2. Write a formal test plan table on paper or in a spreadsheet for each, with at least 8 cases: IDs, purpose, input, expected result. Use the edge-case lists from the lesson.
  3. Turn each plan into a unittest.TestCase class. Run it. Fill in the actual and pass/fail columns.
  4. Write a randomized test for your sort, comparing with sorted() on 1000 random lists.
  5. Bug hunt: ask a family member to secretly change one character in one of your functions (for example <= to <, or - 1 to + 1) while you are not looking. Run your whole suite. Did it catch the change? If not, add a test that does.
  6. Write an integration test in which a list is built with insert_sorted and then searched with binary search.

What to look for: a good suite catches almost every one-character change; the ones it misses show you which edge case is missing from the plan.

Your turn

1

Name the three levels of testing in the lesson and say what each checks.

2

List six edge cases you would include in a test plan for a sorting function.

3

Write a unittest assertion that checks binary_search([2, 4, 6], 6) returns 2.

4

What is a test oracle? Give one for testing a search function.

5

Why should you write a failing test before fixing a reported bug?

6

A function passes all its unit tests but the program still gives wrong answers. What kind of testing is missing, and what might be wrong?

More practice: warm-up

1

What does a test plan record for each test?

2

What is regression testing?

3

In unittest, what must a test method's name start with?

4

What does setUp do in a TestCase?

5

What two properties must the output of any sort have?

More practice: on your own

1

Write a test plan (ID, purpose, input, expected) of five cases for index_of_max(a) from the first lesson of this unit.

2

Write a unittest test method that checks average([]) raises AssertionError.

3

Write a property check for a search function find(a, x) (returns index or −1) that works without knowing the right answer in advance.

4

The buggy sort in the lesson passes the test [1, 3, 2]. Give a small input that makes it fail, and explain.

5

Why does randomized testing use small lists with a small range of values, such as 0 to 12 elements with values −5 to 5?

Challenge

1

Write a unittest test that checks merge sort's efficiency: for random lists of 1024 elements, it makes at most 1024 × 10 comparisons. What would this test catch?

2

Mutation testing deliberately makes small changes (mutants) to the code, such as < to <=, and checks whether the test suite fails. If a mutant survives, what does it mean? Find a mutant of binary_search that the six tests in the lesson would NOT catch.

3

Design an integration test plan for a program that reads scores from a CSV file (from Reading and Writing Text and CSV Files), sorts them with merge sort and prints the top 3. List at least five test cases across the units.

Check your understanding

Quiz

1.

Which kind of testing checks that several functions work correctly together?

2.

After fixing a bug in merge, what should you do next?

3.

Which input is an edge case for binary search?

4.

What is a test oracle?

5.

In unittest, which assertion checks that a function raises an error?

6.

Why does a randomized test of a sort use many small lists with repeated values?

For parents and teachers

Big idea: A4.2 asks students to develop and implement a formal testing plan (for example unit, integration and regression testing). This lesson applies it to the algorithms of this unit, using contracts (C2.1) to choose test cases, Python's unittest to automate them, randomized tests with an oracle, and an integration test. The team project unit (Software Development: Managing a Team Software Project) applies the same plan to a whole program.

How to help: Do the "bug hunt" from the activity: secretly change one character in your teen's code and see if their tests catch it. It is fun and shows exactly which edge cases they missed.

Common difficulties:

  • Testing only "normal" inputs and never the empty list, one element, ends or duplicates.
  • Writing expected results by running the code (that only tests that the code does what it does). Work out expected results from the specification first.
  • Fixing a bug without adding a test for it.
  • Forgetting integration tests: each piece works, but the pieces disagree.