Verifying Algorithms

Imagine a banking software that does not work correctly — say the online money-transfer module is programmed wrongly and credits only half the transacted amount into the account, or worse, debits the account instead of crediting it. Such faulty software would mess up the working of the whole system and cause havoc. And software today runs even more critical services — in the medical field, in space shuttles — where it must work correctly in every situation. The software designer therefore has to make sure the functioning of every component is defined correctly, checked and verified in every possible way.

How we verify a formula — the same idea

Recall being told that the sum of the first N natural numbers is given by the formula:

sum = N * (N + 1) / 2

How did we convince ourselves? By checking it on small numbers where the sum can be computed by hand. Take N = 6:

Manual:   1 + 2 + 3 + 4 + 5 + 6 = 21
Formula:  6 * (6 + 1) / 2       = 21

Trying a few more values the same way builds confidence that the formula works correctly.

The dry run

Verifying an algorithm follows the same principle. Having written an algorithm, we take different input values and walk through all the steps of the algorithm by hand, checking that each input yields the desired output — modifying or improving the algorithm as needed. This method of taking an input and running through the steps is called a dry run. A dry run helps us to:

1. identify any incorrect steps in the algorithm, and
2. figure out missing details or specifics in the algorithm.

Choosing the type of input values for the simulation matters greatly: if all possible kinds of input are not tested, the program will fail on the untested case. Always ask — what if there is some other case for which it does not work?

Worked example: adding two time durations

Task: calculate the total time taken to go from place A to place C via B (call it T_total), given the time from A to B (T1) and from B to C (T2), where each time is given in hours and minutes.

A first attempt at the algorithm:

PRINT value for T1
INPUT hh1
INPUT mm1
PRINT value for T2
INPUT hh2
INPUT mm2
hh_total = hh1 + hh2     (add hours)
mm_total = mm1 + mm2     (add minutes)
PRINT T_total as hh_total, mm_total

Dry run 1. T1 = 5 hrs 20 mins, T2 = 7 hrs 30 mins → result 12 hrs 50 mins. Looks fine.

Dry run 2. T1 = 4 hrs 50 mins, T2 = 2 hrs 20 mins → result 6 hrs 70 mins — which is not how time is measured. The correct answer is 7 hrs 10 mins.

The second example exposes the flaw: the algorithm only works while mm1 + mm2 (that is, mm_total) is less than 60. Whenever mm_total reaches 60 or more, the algorithm must carry: increase the hour total by 1 and reduce the minutes by 60.

The corrected algorithm:

PRINT value for T1
INPUT hh1
INPUT mm1
PRINT value for T2
INPUT hh2
INPUT mm2
hh_total = hh1 + hh2     (add hours)
mm_total = mm1 + mm2     (add minutes)
IF (mm_total >= 60) THEN
    hh_total = hh_total + 1
    mm_total = mm_total - 60
PRINT T_total as hh_total, mm_total

Re-running the failing case — T1 = 4 hrs 50 mins, T2 = 2 hrs 20 mins — now gives T_total = 7 hrs 10 mins: the algorithm works correctly.

Why verify at the algorithm stage …