After completing this lesson you should be able to:
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
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.
Here is an example of an algorithm for making a pot of tea:
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:
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 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.
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:
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.
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.
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:
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.
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.
The data used in algorithms can be of different types. The simplest types of data that an algorithm might use are:
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
|
|
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.
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
Step 2: Preliminary algorithm step
Step 3: Refining the algorithm step
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.
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 David Beech and Learning Systems 1997-2002
and may not be reproduced by any means without the written permission of
David Beech.
9 Wyndella Street, Tasmania, Australia