Step-Form algorithms - the simplest form of algorithm, and Pseudocode (2024)

Step-Form algorithms - the simplest form of algorithmand: How to use Trace Tables

After completing this lesson you should be able to:

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

This is quite a large lesson since we get down to some of the details ofalgorithm design and introduce the trace table. You should pay close attentionto this lesson since some key topics are revealed by 'discovery', especiallyin 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 detaileddesign exercise
Exercise 3 - building a trace table

When you have finished the lesson you might like to attempt these questionsto 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 numberedsteps or points. It is the easiest to learn at first since it is ratherlike a "to-do" list however once you have mastered other ways of statingalgorithms you are unlikely to continue using this form.

You have already used this form in a previous lesson - the tea-makingalgorithm. 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 designingalgorithms 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 tostart identifying processes but a useful starting point is to rememberthat processes do work, in other words a process is an action that is carriedout. Another problem for beginners is determining just how "big" a processshould be. An example here may be a good way to explain this. In this caseof 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 vowelscan be recognised and counted. Since a vowel is a letter then one processwe require is the process of reading a letter in the text. A vowel is oneof the set A,E,I,O or U so another process needs to determine if the letterwe have read is in this set. A third process is conditional on the letterwhich 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 thevowel 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 alsoidentified some decisions, I've shown these in bold text, and some variableswhich I've shown in italic text. The only thing in our strategy step 1which seems not to have been done is to identify the loops. But wait, there'smore. 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 twoprocesses. We have even found a loop and we are ready for strategy step2, 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 algorithmand see if it works. Later when we look at trace tables I will show youa more formal way to test the algorithm. Assume we have a sample page whichcontains the text:

This is a page of text

We read a letter, the first letter 'T', we test it and find it isn't vowelso the vowel counter is not incremented. We also (somehow) determine thatthis is not the end of the page so we go back to step 1 and read the nextletter '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 thevowel counter start with? and how do we know when we have reached the endof the page? These problems aren't really an issue for human readers sincewe have conventions which govern how text is read - for English text youstart at the top left and finish at the bottom right. And we assume thevowel counter is zero at the start. However we are not designing an algorithmfor a human we are designing an algorithm for a 3GL, for a computer andthe machine will require all the conditions of the algorithm to be preciselyspecified. To help us out assume we have two numeric variables current_letter_positionand last_letter_position. Assume also that we can determine or we knowhow 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 likethis:

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 step4

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

This apparently simple example has turned out to be quite an exerciseand it has also enabled us to use the algorithm-designing strategy we meta couple of lessons ago. It is not far from being a complete design fora 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 resistthe 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 whichdisplays a count of vowels on each page and finally a total of the numberof vowels in the book.

You can see that it is a combination of the first example and the firstexercise. Try it yourself before viewing my sampleanswer.

Trace tables

Since an algorithm is a sequence or series of steps which seek to solvea problem you can expect that if you "freeze" the algorithm at any pointthen you have a snapshot of the state of all the variables. The trace tableis a very useful tool which allows you to see the state of your algorithmwith as much detail as you wish. It consists of a table in which each rowshows the state of step in the algorithm and each column shows the valueof a variable at that step. The trace table allows you to check the algorithmfor 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 cankeep the columns in the trace table to a reasonable width. Each variableis 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 valuesletter is vowel and curr <= last so the tablewill need at least six columns. Sometimes there is also a column whichindicates a step number or which contains the statement being executed.