Starting with Algorithms

After completing this lesson you should be able to:

  1. define the term algorithm
  2. list the key features of an algorithm
  3. describe what is meant by sequence
  4. describe the if ... then and if ... then ... else constructs
  5. describe the repeat and while loop constructs
  6. list different ways of stating algorithms
  7. explain what is meant by the term "variable"
  8. explain what is meant by variable data types
  9. explain what is meant by variable naming conventions
  10. describe a strategy for designing algorithms

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


What is an algorithm?

The computer scientist Niklaus Wirth stated that:

Programs = Algorithms + Data

In the first lesson you were introduced to the notions of a computer program and data, what is an algorithm?

The algorithm is part of the blueprint or plan for the computer program, an algorithm is:

"An effective procedure for solving a problem in a finite number of steps."

It is effective, which means that an answer is found and it finishes, that is it has a finite number of steps. A well-designed algorithm will always provide an answer, it may not be the answer you want but there will be an answer. It may be that the answer is that there is no answer. A well-designed algorithm is also guaranteed to terminate.

The key features of an algorithm

Here is an example of an algorithm for making a pot of tea:

  1. If the kettle does not contain water then fill the kettle
  2. Plug the kettle into the power point and switch it on.
  3. If the teapot is not empty then empty the teapot.
  4. Place tea leaves in the teapot.
  5. If the water in the kettle is not boiling then go to step 5
  6. Switch the kettle off.
  7. Pour water from the kettle into the teapot.

You can see that the algorithm has a number of steps, that some steps (steps 1, 3 and 5) involve decision-making and one step (step 5) involves repetition, in this case the process of waiting for the kettle to boil.

Algorithms show these three features:

  1. Sequence (also known as Process)
  2. Decision (also known as Selection)
  3. Repetition (also known as Iteration or Looping)

In 1964 the mathematicians Corrado Bohm and Guiseppe Jacopini demonstrated that any algorithm can be stated using sequence, decision and repetition. The work of Bohm and Jacopini was of great importance since it eventually led to the disciplines of structured program design that are much used today and the work you are studying now is part of software engineering

Sequence

Sequence means that each step or process in the algorithm is executed in the specified order. In the example algorithm above each process must be in the correct place otherwise the algorithm will most probably fail.

The Decision constructs - If ... then, If ... then ... else ...

In algorithms the outcome of a decision is either true or false, there is no in between. The outcome of the decision is based on some condition that can only result in a true or false value, for example:

if today is Wednesday then collect pay

is a decision and the decision takes the form:

if proposition then process

A proposition in this sense is a statement which can only be true or false, it is either true that today is Wednesday or it is false that today is Wednesday. It can't be both true and false. If the proposition is true then the process which follows the then is executed.

The decision can also be stated as:

if proposition
then process1
else process2

this is the if ... then ... else ... form of the decision. This means that if the proposition is true then execute process1 else or otherwise execute process2.

The first form of the decision  if proposition then process  has a null else, that is, there is no else.

The Repetition constructs - Repeat and While

Repetition takes two forms, the Repeat loop and the While loop.

The repeat loop is used to iterate or repeat a process or sequence of processes until some condition becomes true. It has the general form:

    Repeat
     Process1
     Process2
     ProcessN
    Until proposition

Here is an example:

    Repeat
        Put water in kettle
    Until kettle is full

The process is Put water in kettle, the proposition is kettle is full.

The repeat loop does some processing before testing the state of the proposition, what happens though if in the example above the kettle is already full? If the kettle was already full at the start of the repeat loop then putting more water in will lead to an overflow.

In this case the While loop is more appropriate:

    While kettle is not full
        put water in kettle

Since the decision about the kettle being full or not is made before putting water in then the possibility of overflow is eliminated.

Different ways of stating algorithms

One way of stating an algorithm has already been shown above - I call this the Step-Form. In this course you will study four different ways of stating algorithms:

  1. Step-Form
  2. Pseudocode
  3. Flowchart
  4. Nassi-Schneiderman

The first two are written forms. The tea-making example is in Step-Form and as you saw with the Step-Form (SF) the written form is just normal language. A problem with human language is that it can seem to be imprecise. In terms of meaning, what I write may not be the same as what you read. Pseudocode is also human language but tends toward more precision by using a limited vocabulary.

The last two are graphically-oriented, that is they use symbols and language to represent sequence, decision and repetition.

In the next lesson we start studying the different ways of stating algorithms but first we need to cover two important topics.

What are Variables?

Since Programs = Algorithms + Data we should return to the topic of data. You know that data is a symbolic representation of value and that programs set the context which gives data meaning - in programs data is transformed into information. The question is: How is data represented in programs?

Just about every algorithm contains data and usually the data is "contained" in a thing called a variable. The variable is a container for a value which may vary during the execution of the program. For example, in our tea-making algorithm the level of water in the kettle is variable, the temperature of the water is variable, the quantity of tea leaves is also variable.

Each variable in a program is given a name, for example:

and at any given time the value which is represented by Water_Level for instance may be different to its value at some other time. The statement:

could also be written as:

or

At some point Water_Level will be the maximum value, whatever that is, and the kettle is full.

Variables and data types

The data used in algorithms can be of different types. The simplest types of data that an algorithm might use are:

Naming of variables

You should always try choose meaningful names for variables in algorithms to improve the readability of the algorithm or program. This is particularly important in large and complex programs.

In the tea-making algorithm I used plain English. I've shown here how you might use variable names for some of the algorithm variables. In the right-hand column I've chosen names that, although shorter than the original, don't hide the meaning of the original phrase. I've also used underscores to indicate the words belong together and represent a variable

  1. If the kettle does not contain water then fill the kettle
  2. Plug the kettle into the power point and switch it on.
  3. If the teapot is not empty then empty the teapot.
  4. Place tea leaves in the teapot.
  5. If the water in the kettle is not boiling then go to step 5
  6. Switch the kettle off.
  7. Pour water from the kettle into the teapot.
  1. If kettle_empty then fill the kettle
  2. Plug the kettle into the power point and switch it on.
  3. If teapot_not_empty then empty the teapot.
  4. Place tea leaves in the teapot.
  5. If water_not_boiling then go to step 5
  6. Switch the kettle off. 
  7. Pour water from the kettle into the teapot.

There are no hard and fast rules about how variables should be named but there are many conventions. It is a good idea to adopt a conventional way of naming variables.

By the way - your algorithms and programs can benefit from using naming conventions for processes too.

A strategy for designing algorithms

Now that we know something about algorithms and data we can devise a strategy for designing algorithms. Here is one strategy I have found useful:

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 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

I will use and refine this strategy during the rest of this module but for now we should just look at the steps.

The first step - Investigation - implies that you read through the statement of the problem to be solved and do some analysis of the terms used. In the tea-making example we can see that there are a number of processes, filling the kettle, plugging the kettle into the power point and so on. There are decisions, variables and loops.

The second step - Preliminary algorithm - is our first attempt at solving the problem. It can be quite crude but Step 2.2 will test it and bring out obvious errors.

The third step - Refining - is the most difficult step, this step needs practice and strictly speaking the learning of some of the skills implied in this step won't really occur until you have gained some programming experience. It won't hurt though to give the refining step some thought in this course.


Summary

In this lesson you learned about:

The algorithm is a statement about how a problem will be solved and almost every algorithm exhibits the same features. There are many ways of stating algorithms and some of them have been mentioned here. Every useful algorithm uses data which might vary during the course of the algorithm and, finally, to help in designing algorithms it is a good idea to develop and use a design strategy.

You should be just about ready to start designing programs now, there is just one short lesson which fits the program design activity in place amongst the bigger activity of designing software systems.


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


This publication is copyright Learning Systems 1997
and may not be reproduced by any means without the written
permission of Learning Systems.
P.O. Box 32, Mowbray, Tasmania, Australia