Understanding and producing algorithms
Introduction
Programmers need to be able to describe problems accurately and precisely. They need to be able to plan programs or parts of programs before they actually write them. If they plan what they are going to do, then it becomes easier to discuss in teams how some code or a solution will work and it becomes easier to 'dry run' the proposed solution (this simply means working through the code on paper to check that it works in the way it was intended to work). Discussion of code before it is written and dry running code help ensure that any problems are discovered before the code is written - tracking down problems after the code has been written usually takes a great deal more time!
For programmers to accurately describe how some code will work or how a solution will work on paper, they need a set of tools they can use. They need to produce 'algorithms' using specialist diagrams or pseudo-code.
Algorithms
The first thing that needs to be done when solving a problem using a programming language is to describe how to solve it! This will then lead the programmer into producing efficient code that will perform the task. There are a number of ways to describe a problem that we wish to write a program for. However we decide to describe a problem, it is known as an ‘algorithm’. An algorithm is simply a list of instructions that describe how to do a particular task. All that needs to happen is that the programmer analyses a task and writes down (or draws) step-by-step how the solution is to solve the problem. A programmer may also decide to write algorithms to describe the problem in the first place, and then write algorithms to describe the solution. Whichever approach is taken, there is some good news when writing algorithms. There are no rules dictating what you have to do and how you have to do it!
-
- You can produce an algorithm by writing a list of sentences.
- You can produce an algorithm by drawing a diagram, for example, a flow chart.
- You can produce an algorithm by writing instructions using pseudo-code.
Describing a solution using algorithms
As has already been said, there are no rules to follow when writing algorithms. As long as your argument is structured and logical you can write or draw what you like. However, a popular way of representing algorithms is to use pseudo-code.
Pseudo-code
Pseudo-code is a cross between English and the keywords used in programming languages. It also makes use of the programming constructs found in programming languages (sequence, selection, iteration) but it has no strict rules that you have to follow. It is used to effectively describe solutions in a near-programming language type of way! This means that the pseudo-code can then be given to a programmer expert in any language and they should be able to quickly convert the pseudo-code into that language. This is the big advantage of pseudo-code. It is independent of any particular programming language. Pseudo-code can be quickly converted into any language!
An example of pseudo-code
Suppose you need to write an algorithm to find a record in a file. A first attempt at an algorithm in pseudo-code might look like this;
RecordFound=FALSE
EndOfFile=FALSE
READ Key field of record you want to find
READ First record in file
WHILE ((EndOFFile=FALSE) AND (RecordFound=FALSE)) DO
BEGIN
COMPARE record you are looking for with record from file
IF same THEN
RecordFound=TRUE
PRINT "Record found"
ELSE
IF EndOfFile Then
EndOfFile=TRUE
PRINT "End of file reached. Record not found."
ELSE
READ next record
ENDIF
ENDIF
END
ENDWHILE
Flowcharts
Another way of describing algorithms is to use a flowchart. This is a diagram that uses a set of symbols and lines of flow that link the symbols. If you have used popular control programs such as Logicator, for example, then you will be familiar with flow diagrams. The following symbols are the most common ones used in flowcharts, although there are others and if you read around this topic, you may find slight variations in their use.
An example of a flowchart
Here is an example of a flowchart that describes the discount given for buying products in a club’s shop. The discount given depends upon your membership type.
You begin and end the flowchart with a start / stop symbol. You then input your membership type.
-
- If it is gold, you get 25% discount and a message is displayed stating the discount given.
- If it is silver, you get 20% discount and a message is displayed stating the discount given.
- If it is bronze, you get 15% discount and a message is displayed stating the discount given.
- If you are not a member, you get 10% discount and a message is displayed stating the discount given.
An example of a FOR loop and using subroutines
Suppose you had to carry out a set of instructions a fixed number of times. In programming code, you would use a FOR loop for this. But stepping back for a moment, how might you represent this as a flowchart?
There are some useful tools for making flowcharts around. There is a drawing toolbar in both Word and OpenOffice that can be used for drawing neat flowcharts. Meesoft's 'Diagram Designer' is also excellent (and free). If your school has Logicator, that's also an excellent way of getting experience producing good flowcharts.