Trace, test and correct algorithms

A program is meant to add every entry of the list [2, 5]. It prints 5. What should be compared first?

Test an algorithm against a precise specification

An algorithm is a finite sequence of precise steps. A program implements those steps using particular conventions

State the input, allowed values, required output and any special cases before running the program

Calculate an expected result independently. Trace the actual program in its stated order, recording the value after each assignment

Compare expected and actual results. Use a small input that distinguishes the faulty rule from the intended rule

Correct the cause, rerun the failing case and rerun earlier tests. This last step checks that the repair has not broken cases that already worked

Test loop boundaries, repeated entries, negative values and empty inputs when they are allowed. Then explain why the corrected steps meet the specification, rather than relying only on examples

Keep a position separate from its stored value

In this lesson, list positions start at one. A list preserves order and repeated entries

The value at position two is negative two; the position itself is not negative

This assignment changes only the second entry. Evaluate the right side using its old value, then store the result on the left

Read an ordered list using one-based positions

A list stores entries in order, including repeated values. In this pseudocode, positions start at 1 and ← means assignment

What is \(L[2]\)?

Count positions from 1. Position 2 contains -2

Read a different position without removing repeats

A count and a selected-value sum use different updates

Keep entries at least four. The two occurrences of four and the seven all pass

To count passing entries, start total at zero and add one for each passing entry

To sum passing values, start total at zero and add the current value only when it passes

The count is three and the selected-value sum is fifteen. Neither task sorts the list or removes a repeat

Summing every entry would instead give thirteen because the negative two is then included

Count all entries that meet an inclusive threshold

A list stores entries in order, including repeated values. In this pseudocode, positions start at 1 and ← means assignment

1. total ← 0
2. FOR EACH x IN L: if x ≥ 4, set total ← total + 1
3. OUTPUT total

What is the final output?

The passing entries, in order, are [4, 4, 7]. The value 4 occurs 2 times and each occurrence is visited

There are 3 passing entries

Count repeated passing values separately

Add the passing values rather than adding one

A list stores entries in order, including repeated values. In this pseudocode, positions start at 1 and ← means assignment

1. total ← 0
2. FOR EACH x IN L: if x ≥ 4, set total ← total + x
3. OUTPUT total

What is the final output?

The passing entries, in order, are [4, 4, 7]. The value 4 occurs 2 times and each occurrence is visited

Trace a selected-value sum with three equal entries

Test the equality case that separates two conditions

The requirement is to count entries at least three, but the program increments its count only when the entry is greater than three

Only nine passes the faulty condition. Both threes should also pass the requirement

A one-entry list containing three is a smaller distinguishing test: the faulty program returns zero while the required count is one

Also test a value below the threshold and one above it. The repair must include equality without admitting smaller values

Record the faulty states, then repair the condition

A list stores integer entries in order, including repeats. Positions start at one and the arrow means assignment

Goal: Count all list entries greater than or equal to 3, including repeated entries

The intended algorithm must also return zero for an empty list

Trace this implementation exactly before deciding how to correct it

1. total ← 0
2. FOR EACH x IN L: if x > 3, set total ← total + 1
3. OUTPUT total

Calculate total immediately after each list entry has been processed by the supplied implementation

Start total at zero, exactly as the supplied program says

Entry 1 is 3

3 > 3 is false, so keep the total

Entry 2 is -2

-2 > 3 is false, so keep the total

Entry 3 is 3

3 > 3 is false, so keep the total

Entry 4 is 0

0 > 3 is false, so keep the total

Entry 5 is 9

9 > 3 is true, so add one

What output should a correct implementation produce for this list according to the stated goal?

Initialise total at zero once, before processing the entries

After entry 1, 3 meets the inclusive threshold, so total is 1

After entry 2, -2 does not meet the inclusive threshold, so total is 1

After entry 3, 3 meets the inclusive threshold, so total is 2

After entry 4, 0 does not meet the inclusive threshold, so total is 2

After entry 5, 9 meets the inclusive threshold, so total is 3

The supplied program and the stated goal give different final outputs, so this input exposes a fault

A value equal to the threshold must be counted, but a strict greater-than test misses it

Include equality in the threshold test

A distinguishing test is [3]

The stated goal gives 1, while the faulty program gives 0

After repairing the program, rerun this test and the earlier passing tests

State a correction that makes the program meet its goal for every allowed list

A value equal to the threshold must be counted, but a strict greater-than test misses it

Include equality in the threshold test

A distinguishing test is [3]

The stated goal gives 1, while the faulty program gives 0

After repairing the program, rerun this test and the earlier passing tests

Find the effect of missing equality in a different list

List and required condition

\(\displaystyle L=[4,-2,4,0,7],\quad x\ge4\)

Use all five entries, compare the two conditions, then reduce the number of entries to zero. The program starts its count at zero and adds one when an entry passes

Which result describes these tests?

Initialise once before an accumulation loop

To sum every entry, set total to zero before the loop, add the current entry on each iteration and output total after the loop

If total is reset to zero before every addition, each update discards the previous work

The faulty result is only the last entry, zero, instead of the required sum nine

Remove the reset inside the loop while keeping the single initialisation before it

After each corrected iteration, total is the sum of all entries visited so far. Starting at zero and adding the next entry preserves that statement

Locate where earlier contributions disappear

A list stores integer entries in order, including repeats. Positions start at one and the arrow means assignment

Goal: Find the sum of all list entries

The intended algorithm must also return zero for an empty list

Trace this implementation exactly before deciding how to correct it

1. total ← 0
2. FOR EACH x IN L: first set total ← 0; then set total ← total + x
3. OUTPUT total

Calculate total immediately after each list entry has been processed by the supplied implementation

Start total at zero, exactly as the supplied program says

Entry 1 is 8

Reset total to zero, discarding the previous value 0, then add 8

Entry 2 is 2

Reset total to zero, discarding the previous value 8, then add 2

Entry 3 is -3

Reset total to zero, discarding the previous value 2, then add -3

Entry 4 is 2

Reset total to zero, discarding the previous value -3, then add 2

Entry 5 is 0

Reset total to zero, discarding the previous value 2, then add 0

What output should a correct implementation produce for this list according to the stated goal?

Initialise total at zero once, before processing the entries

After entry 1, add 8 to the previous total 0 to obtain 8

After entry 2, add 2 to the previous total 8 to obtain 10

After entry 3, add -3 to the previous total 10 to obtain 7

After entry 4, add 2 to the previous total 7 to obtain 9

After entry 5, add 0 to the previous total 9 to obtain 9

The supplied program and the stated goal give different final outputs, so this input exposes a fault

Resetting inside the loop forgets all earlier contributions

Remove the reset inside the loop and initialise total once before it

A distinguishing test is [8, 8]

The stated goal gives 16, while the faulty program gives 8

After repairing the program, rerun this test and the earlier passing tests

State a correction that makes the program meet its goal for every allowed list

Resetting inside the loop forgets all earlier contributions

Remove the reset inside the loop and initialise total once before it

A distinguishing test is [8, 8]

The stated goal gives 16, while the faulty program gives 8

After repairing the program, rerun this test and the earlier passing tests

Repair a longer accumulation trace

Input list

\(\displaystyle L=[4,-2,4,0,7]\)

Both programs visit every list entry in order and add its value. One initialises total to zero only before the loop; the other also resets it to zero before every addition. What outputs do they give for the full list?

A faulty program can pass a particular test

The faulty reset-inside-loop program also returns eight because eight is the last entry

Its final answer happens to agree, but its earlier states are not the intended accumulated sums

This smaller test exposes the same bug. A passing example alone does not prove that the program works for every allowed input

Both programs initialise total to zero before the loop. The faulty program also resets total to zero before adding each entry, but is meant to sum the whole list. Which test distinguishes it from a correct sum?

Do not invent zero as the maximum of a negative list

The goal is the largest entry of a nonempty list. A faulty program starts best at zero, then replaces it only when a larger entry appears

The output zero is not even in the list. Every entry is negative, so none replaces zero

Start best at the first entry, then compare each remaining entry with the current best

After each comparison, best is the largest entry visited so far. The initial first entry establishes this before the remaining comparisons

If empty input is allowed, specify a separate response such as no maximum before attempting to read a first entry

Trace both faulty and repaired initialisation

A list stores integer entries in order, including repeats. Positions start at one and the arrow means assignment

Goal: Find the largest entry of a non-empty list

The maximum-finding task excludes empty lists

Trace this implementation exactly before deciding how to correct it

1. best ← 0
2. FOR EACH x IN L: if x > best, set best ← x
3. OUTPUT best

Calculate best immediately after each list entry has been processed by the supplied implementation

Start best at zero, exactly as the supplied program says

Entry 1 is -9

-9 is not greater than 0, so best remains unchanged

Entry 2 is -6

-6 is not greater than 0, so best remains unchanged

Entry 3 is -4

-4 is not greater than 0, so best remains unchanged

What output should a correct implementation produce for this list according to the stated goal?

For a non-empty list, initialise best using its first entry

After entry 1, the first entry initialises best to -9

After entry 2, compare -6 with the previous best -9, giving -6

After entry 3, compare -4 with the previous best -6, giving -4

The supplied program and the stated goal give different final outputs, so this input exposes a fault

Zero is not a valid starting maximum when every list entry is negative

Initialise the candidate maximum using the first list entry, then compare the remaining entries

A distinguishing test is [-9]

The stated goal gives -9, while the faulty program gives 0

After repairing the program, rerun this test and the earlier passing tests

State a correction that makes the program meet its goal for every allowed list

Zero is not a valid starting maximum when every list entry is negative

Initialise the candidate maximum using the first list entry, then compare the remaining entries

A distinguishing test is [-9]

The stated goal gives -9, while the faulty program gives 0

After repairing the program, rerun this test and the earlier passing tests

Find the maximum without assuming it is nonnegative

A maximum program is changed to accept empty lists as well as nonempty lists. What must its specification and implementation add?

Write expected results before running the tests

For a program that counts entries at least four, these tests target different risks

Record actual results alongside these expected results. When a test fails, trace the first point where the state disagrees with the intended meaning

After changing the code, rerun the failing test and the other tests. Keep the counterexample as a regression test for later changes

A count program is repaired by replacing greater than four with greater than or equal to four. Which next step best tests the repair?

Test whether a search reaches the last position

Search the list [6, 2, 9] for nine, returning its first position or zero if absent. Positions start at one

A faulty search starts i at one and repeats while i is less than the length. It compares L[i] with the target and increases i when they differ

It stops before checking the last entry and wrongly returns zero

Use i less than or equal to the length. Check the loop limit before accessing L[i], return i immediately on a match, otherwise increase i

Test a match at the first position, a match at the last position, an absent target, repeated targets and empty input. Return zero only after all permitted positions have been checked

Ordered input and target

\(\displaystyle L=[8,5,2,5],\quad t=5\)

The repaired search visits positions one through the list length in order and returns immediately on a match. Which position is returned for target five?

One adjacent-swap pass need not sort the whole list

The goal is ascending order while preserving every entry and repeat. A pass compares each adjacent pair from left to right and swaps the pair if the left value is greater

The largest entry reaches the last position, but the first two entries are still out of order

Repeat complete passes until a pass makes no swaps. Reset a swapped flag to false before each pass and set it to true whenever a swap occurs

A final no-swap pass checks that every adjacent pair is in order. Empty and one-entry lists need no comparisons

For a finite list, each out-of-order adjacent swap reduces the number of inverted pairs. This explains why repeated passes finish, rather than treating several passing examples as a proof

Starting list

\(\displaystyle L=[4,3,2,1]\)

Make exactly one left-to-right adjacent-swap pass on the given list. Swap a pair when its left entry is greater. What is the first entry after this pass?

Test divisibility with repeated subtraction

Let n be a nonnegative integer and d a positive integer. Start r at n, then subtract d while r is greater than or equal to d

When the loop stops, r is the remainder. The input n is divisible by d exactly when r is zero

A faulty strict condition r greater than d stops at four and incorrectly reports not divisible

Equality is essential because one final subtraction is needed when the current remainder equals the divisor

Here the remainder is two, so fourteen is not divisible by four

With n zero and positive d, no iterations are needed and the remainder is zero. Exclude divisor zero: subtracting zero would never decrease a nonnegative remainder

Input and divisor

\(\displaystyle n=18,\quad d=6\)

Start r at eighteen and subtract six while r is greater than or equal to six. What is the final remainder?

Input and divisor

\(\displaystyle n=20,\quad d=6\)

Start r at twenty and subtract six while r is greater than or equal to six. What is the final remainder?

A divisibility program starts r at n and subtracts positive d while r is greater than d, instead of greater than or equal to d. Which input directly isolates the missing equality case?

Implement, test and correct a list-processing program

Independent written and digital programming task, not automatically marked

Write pseudocode or a program that returns the first position of a target in a list, or zero when absent. State the position convention and allowed inputs

Create a test table with expected results before running it. Include first-position, last-position, absent, repeated-target and empty-list tests

Run or hand-trace the program. Record actual results and the first incorrect state for any failure. Correct the cause and rerun every test

Example tests using one-based positions: [6, 2, 9] with target nine returns three; [9, 2, 9] with target nine returns one; [6, 2] with target nine and an empty list both return zero

A model solution starts i at one, checks i is within the list, returns i when L[i] equals the target, and otherwise increases i. Return zero only after leaving the loop

Explain why all earlier positions have been checked before each next comparison and why i eventually exceeds the finite list length if no match is found

As a further task, implement the repeated-pass sorting or divisibility procedure from this lesson. State its allowed inputs and tests, and keep the actual program or trace for review

Use a specification, a trace and discriminating tests together

A specification defines required behaviour; an actual output records what the implementation did. Calculate expected results independently

Trace assignments in order, preserve repeated entries and distinguish positions from stored values

Test equality when strict and inclusive conditions differ. Visit every required list position without accessing a position outside the list

Initialise an accumulator once before its loop. For a nonempty maximum, initialise from an actual entry and handle empty input separately if it is allowed

A counterexample disproves a claim that every allowed case works. A passing example alone does not establish that claim

Repair the cause, rerun the failing example and earlier tests, then explain why the corrected steps preserve the intended meaning and finish