Testing and evaluating algorithms

Testing an algorithm

One way to test short is to do what is known as a using paper. A dry run involves creating a , containing all the variables a program contains. Whenever the value of a changes, the change is indicated in the trace table.

Consider this simple program:

1 total is integer
2 number is integer
3 set total = 0
4 for count = 1 to 3
5 input “Enter number”, number
6 total = total + number
7 next count
8 output total

Each instruction has been given a line number (1-8). The program has three variables - total, count and number. These variables will be put into a trace table.

Instruction	total	count	number

Instruction
total
count
number

Next, the program is tested using test data. If the numbers 5, 7 and 9 are input, the resulting total should be 21.

The instruction number is entered in the table. If a variable changes with that instruction, the new variable value is written in the appropriate box, as follows:

Instruction	total	count	number
1
2
3	0
4		1
5			5
6	5
7
4		2
5			7
6	12
7
4		3
5			9
6	21
7
8	21

Instruction	1
total
count
number

Instruction	2
total
count
number

Instruction	3
total	0
count
number

Instruction	4
total
count	1
number

Instruction	5
total
count
number	5

Instruction	6
total	5
count
number

Instruction	7
total
count
number

Instruction	4
total
count	2
number

Instruction	5
total
count
number	7

Instruction	6
total	12
count
number

Instruction	7
total
count
number

Instruction	4
total
count	3
number

Instruction	5
total
count
number	9

Instruction	6
total	21
count
number

Instruction	7
total
count
number

Instruction	8
total	21
count
number

At each step, the programmer is able to see if, and how, a variable is affected.

Trace tables are extremely useful because they enable a programmer to compare what the value of each variable should be against what a program actually produces. Where the two differ is the point in the program where a logic error has occurred.

Evaluating an algorithm

When developing an it is useful to formalise exactly what that algorithm is designed to do. This makes it possible to check whether it meets all of those requirements. In addition, there might be several possible algorithms for the same problem. A good algorithm will not only do what it is supposed to do but will also do it efficiently. Inefficient algorithms may slow down the speed of the program execution. For example, a is less efficient than a .

Ways that algorithms may be faulty

Algorithms may fail because:

the original problem may not be fully understood
the algorithm is incomplete
the algorithm is inefficient and may be too complicated or too long
the algorithm does not meet the original design criteria, so it is not fit for purpose

Algorithms - EduqasTesting and evaluating algorithms