1. apply a strategy to the process of designing a step-form algorithm
2. construct a trace table

This is quite a large lesson since we get down to some of the details of algorithm design and introduce the trace table. You should pay close attention to this lesson since some key topics are revealed by 'discovery', especially in the trace table topic.

There are some exercises for you to do, each exercise has a sample answer:

Exercise 1 - a first design exercise
Exercise 2 - a second and more detailed design exercise
Exercise 3 - building a trace table

When you have finished the lesson you might like to attempt these questions to assess how much you have learned.

Return to the index
Go to the next lesson
Return to the previous lesson

Step-form algorithms

This form of algorithm is the simplest and consists of a sequence of numbered steps or points. It is the easiest to learn at first since it is rather like a "to-do" list however once you have mastered other ways of stating algorithms you are unlikely to continue using this form.

You have already used this form in a previous lesson - the tea-making algorithm. Here is another example:

First of all the problem to solve is:

Design a program which counts all the vowels on a given page of text.

Remember in the second lesson we came up with a strategy for designing algorithms so use this as a starting point:

Step 1: Investigation step

1. Identify the processes
2. Identify the major decisions
3. Identify the loops
4. Identify the variables

Step 2: Preliminary algorithm step

1. Devise a "high level" algorithm
2. Step through the algorithm. Does this "walk-through" reveal any major problems? If it does then correct the problems.

Step 3: Refining the algorithm step

1. Incorporate any refinements indicated in step 2.
2. Group together processes where appropriate
3. Group together variables where appropriate
4. Test the algorithm again by stepping through it

1.1 Identify the processes

Beginners in algorithm design are often a bit uncertain about how to start identifying processes but a useful starting point is to remember that processes do work, in other words a process is an action that is carried out. Another problem for beginners is determining just how "big" a process should be. An example here may be a good way to explain this. In this case of the vowel-counting problem we could be bold and state it like this:

The implication here is that some processes do a great deal work hence "big" processes. This process is the heart of the problem - counting vowels - but it gives no clue as to how the vowel-counting will be done. We need to analyse the process further so that we can specify how vowels can be recognised and counted. Since a vowel is a letter then one process we require is the process of reading a letter in the text. A vowel is one of the set A,E,I,O or U so another process needs to determine if the letter we have read is in this set. A third process is conditional on the letter which was read and tested being a vowel, if it is we need to count it. Lastly we need to determine if we have reached the end of the page.

So far we have the following processes:

1. Read a letter from the text
2. If the letter is a vowel then increment the vowel counter
3. Determine if the end of the page has been reached

You can see that in the process of identifying the processes we have also identified some decisions, I've shown these in bold text, and some variables which I've shown in italic text. The only thing in our strategy step 1 which seems not to have been done is to identify the loops. But wait, there's more. What happens in process 3 if we haven't reached the end of the page? We continue with the next letter, which will mean repeating the first two processes. We have even found a loop and we are ready for strategy step 2, devising and testing the high level algorithm. Here is my first attempt:

1. Read a letter from the text
2. If the letter is a vowel then increment the vowel counter
3. If the letter is not the last letter then got to step 1

Now do a "walk-through", that is go through each step of the algorithm and see if it works. Later when we look at trace tables I will show you a more formal way to test the algorithm. Assume we have a sample page which contains the text:

This is a page of text

We read a letter, the first letter 'T', we test it and find it isn't vowel so the vowel counter is not incremented. We also (somehow) determine that this is not the end of the page so we go back to step 1 and read the next letter 'h', and so on. That seems fine but there are still some problems. For instance: how do we start at the first letter? what value does the vowel counter start with? and how do we know when we have reached the end of the page? These problems aren't really an issue for human readers since we have conventions which govern how text is read - for English text you start at the top left and finish at the bottom right. And we assume the vowel counter is zero at the start. However we are not designing an algorithm for a human we are designing an algorithm for a 3GL, for a computer and the machine will require all the conditions of the algorithm to be precisely specified. To help us out assume we have two numeric variables current_letter_position and last_letter_position. Assume also that we can determine or we know how many letters are on the page which will be the value of last_letter_position. Later I will show you how we would do this in practice using sentinel values.

Given these variations we can now write an algorithm which looks like this:

1. Set current_letter_position to 1
2. Set last_letter_position to number of letters on the page
3. Set vowel_counter to 0
4. Read letter at current_letter_position
5. If letter is a vowel then increment vowel_counter
6. Increment current_letter_position
7. If current_letter_position <=  last_letter_position go to step 4

The symbol <=  in line 7 means less than or equal to.

This apparently simple example has turned out to be quite an exercise and it has also enabled us to use the algorithm-designing strategy we met a couple of lessons ago. It is not far from being a complete design for a 3GL program.

By the way I haven't tested the algorithm. Will it work?

Exercise 1:

Here is an exercise for you to complete:

Design a step-form algorithm to count the pages in a book.

My sample answer is here but resist the attempt to look at it first.

Exercise 2

If you have completed exercise 1 then here is another:

Design a program which reads all the vowels in a book and which displays a count of vowels on each page and finally a total of the number of vowels in the book.

You can see that it is a combination of the first example and the first exercise. Try it yourself before viewing my sample answer.

Trace tables

Since an algorithm is a sequence or series of steps which seek to solve a problem you can expect that if you "freeze" the algorithm at any point then you have a snapshot of the state of all the variables. The trace table is a very useful tool which allows you to see the state of your algorithm with as much detail as you wish. It consists of a table in which each row shows the state of step in the algorithm and each column shows the value of a variable at that step. The trace table allows you to check the algorithm for errors.

Here is a trace table which shows the states of our vowel counting algorithm, first the algorithm again:

1. Set curr to 1
2. Set last to number of letters on the page
3. Set count to 0
4. Read letter at curr
5. If letter is vowel then increment count
6. Increment curr
7. If curr <=  last go to step 4

Note that I have abbreviated the variable names, this is so that I can keep the columns in the trace table to a reasonable width. Each variable is shown in italic in the algorithm.

Next the data: A page

The algorithm has six variables - the numeric variables curr, last, count, the character variable letter and the logical values letter is vowel and curr <=  last so the table will need at least six columns. Sometimes there is also a column which indicates a step number or which contains the statement being executed.

The trace table reveals some interesting things about algorithms. For instance it stresses that a variable doesn't change value until it is re-evaluated by a statement which operates on the variable. You can see in line two that the variable letter contains 'A' but the state of the condition letteris vowel is unknown (?). Line three in the trace table shows the execution of statement five of the algorithm - If letter is vowel then increment count - and now the variable letter is vowel in the trace table takes on a value. Another thing shown by the trace table is the amount of work done by algorithms which use repetition. Large repetitious algorithms with large amounts of data will lead to enormous trace tables. The size of the table can be minimised by only showing the start and stop states of a loop and then showing one iteration of the loop in a separate table. Yet another thing revealed by the trace table is the initialisation of variables - setting variables to a known state. Initialising variables is a good defensive algorithm design technique and is strongly recommended. Remember that your algorithm will end up as a computer program and you should not assume that the particular programming language will take care of the initialisation of variables. It is good practice to assume that it will not.

Exercise 3:

Build trace tables for exercises 1 and 2. I have completed sample answers and you can see them here but try for yourself first.

Summary

In this lesson you learned about:

• Step-Form algorithms
• Using a strategy to design an algorithm
• Refining an algorithm
• Building a trace table
• The initialisation of variables

The Step-Form algorithm is the simplest way of stating algorithms and is a useful starting point for the other more formal methods of algorithm design. Whatever method is used it is always advisable to use a strategy to design the algorithm. As algorithms are designed you discover that some refinements are required, the first attempt at an algorithm is rarely the

The trace table is a tool which aids in testing and verifying algorithms. It contains rows to show the state of variables (the columns) at each step in the algorithm. You will find some additional notes on trace tables in Exercise 3.

Return to the index
Go to the next lesson
Return to the previous lesson