Representing Algorithms
Quick links 
Fundamentals of algorithms 
Representing algorithms 
Efficiency of algorithms 
Searching algorithms 
Sorting algorithms 
Syllabus content
Content  Additional Information  

Understand and explain the term algorithm.  An algorithm is a sequence of steps that can be followed to complete a task. Be aware that a computer program is an implementation of an algorithm and that an algorithm is not a computer program.  
Understand and explain the term decomposition.  Decomposition means breaking a problem into a number of subproblems, so that each subproblem accomplishes an identifiable task, which might itself be further subdivided.  
Understand and explain the term abstraction.  Abstraction is the process of removing unnecessary detail from a problem.  
Use a systematic approach to problem solving and algorithm creation representing those algorithms using pseudocode and flowcharts.  Any exam question where students are given pseudocode will use the AQA standard version. However, when students are writing their own pseudocode they may do so using any form as long as the meaning is clear and unambiguous. 
Example
Example
An algorithm is in essence a sequence of instructions.
Here are the instructions for making a cup of tea; they are not in the right order...
  Add milk if required.
  Place the cup and saucer on a flat surface
  Stir the brewed tea and milk
  Fill the kettle with sufficient water
  Add sufficient water to the cup
  Fetch the tea, milk and sugar from the cupboard and place near the cup and saucer
  Place sufficient tea into the cup
  Heat the kettle to boiling point
  Add sufficient sugar
  Wait for the tea to brew
  Serve
... so write the list in the right order.
An algorithm can either be expressed as a flowchart or in pseudo code. (Pseudo code does not lend itself to cups of tea.)
Here is part of the answer as a flowchart
You are going to use Visio to complete the flowchart.
Here is the complete answer.
Visio
Loading Visio
Click on "Start" "All programs" and then "Core Applications". Visio os the one above Word.
When Visio loads you should see this...
If you have not got the short cut you can find the basic flowchart in "Flowcharts"
Activity
Good Algorithms
For an algorithm to be good enough for a computer to follow it must be:
  Unambiguous – There must be only one way to interpret each instruction
  To the right level of detail – Not too vague, not too specific
  Correct – Free from errors
Here is the algorithm for sorting things
 1. Look at the first number in the list.
 2. Compare the current number with the next number.
 3. Is the next number smaller than the current number? If so, swap the two numbers around. If not, do not swap.
 4. Move to the next number along in the list and make this the current number.
 5. Repeat from step 2 until the last number in the list has been reached.
 6. If any numbers were swapped, repeat again from step 1.
 7. If the end of the list is reached without any swaps being made, then the list is ordered and the algorithm can stop.
Here is the algorithm as a flow chart.
The diagram shows the trace table of the first cycle through the following list of numbers 3, 2, 4, 1, 5. You will notice that only one pair of numbers (highlighted) is affected each iteration.
In the first iteration the 3 and 2 are compared and then swapped.
In the second iteration the 3 and 4 are compared and being in the right order are not swapped and so on.
Has the list been sorted into ascending order? No. If the routine is run until there are no exchanges then the list will be in ascending order, as shown below.
Exercises
Examples of Algorithms
Here are some numeric based algorithms for you to try. The examiner wants you to show that you can read and understand an algorithm, show what the algorithm can do and with suggested input data show what the algorithm actually does, probably using a trace table.
Exercise 1
Here is a flow chart for adding two numbers, write the algorithm in words.
Create the trace table to show adding 6 and 8. (I have begun the able already, all you have to do is complete it.)
Instruction  "Sum"  "A"  "B"  

Set "Sum"  0  
Input the first number, store as “A”  
Input the second number, store as “B”  
Sum = A + B  
Output “Sum” 
In a Word document show, the algorithm in words, as a flow chart and the trace table.
Exercise 2
Here is the algorithm in words for finding the area and perimeter of a square.
 1. The variable "Area" is set to 0
 2. The variable "Perimeter" is set to 0
 3. Ask the user for the length of a side and store the value in variable "Side"
 4. Calculate the area of the square ("Side" x "Side") and store the value in "Area"
 5. Calculate the perimeter of the square ("Side" x 4) and store the value in "Perimeter"
 6. Output the result, "Area".
 7. Output the result, "Perimeter".
In a word document show the algorithm in words, the flowchart and the trace table for finding the area of a square of side 6cm.
Exercise 3
In a word document write in words and as a flowchart the algorithm for finding the perimeter and area of a circle and show the trace table for finding the perimeter and area of a circle radius 5cm.
Exercise 4 (To make you think)
In a word document write in words and as a flowchart the algorithm for the change for a transaction in the minimum number of coins. At transaction amount must be less than £10 and the change will be calculated from £10.
Explanation of decomposition
Decomposition in Algorithms (Bringing Order to Chaos)
Certainly, there will always be geniuses among us, people of extraordinary skill who can do the work of a handful of mere mortal developers, the software engineering equivalents of Frank Lloyd Wright or Leonardo da Vinci. These are the people whom we seek to deploy as our system architects: the ones who devise innovative idioms, mechanisms, and frameworks that others can use as the architectural foundations of other applications or systems. However, "The world is only sparsely populated with geniuses. There is no reason to believe that the software engineering community has an inordinately large proportion of them" [2]. Although there is a touch of genius in all of us, in the realm of industrialstrength software we cannot always rely on divine inspiration to carry us through. Therefore, we must consider more disciplined ways to master complexity.
The Role of Decomposition
"The technique of mastering complexity has been known since ancient times: divide et impera (divide and rule)". When designing a complex software system, it is essential to decompose it into smaller and smaller parts, each of which we may then refine independently. In this manner, we satisfy the very real constraint that exists on the channel capacity of human cognition: To understand any given level of a system, we need only comprehend a few parts (rather than all parts) at once. Indeed, as Parnas observes, intelligent decomposition directly addresses the inherent complexity of software by forcing a division of a system's state space.
Algorithmic Decomposition
Most of us have been formally trained in the dogma of topdown structured design, and so we approach decomposition as a simple matter of algorithmic decomposition, wherein each module in the system denotes a major step in some overall process. Figure 1Â3 is an example of one of the products of structured design, a structure chart that shows the relationships among various functional elements of the solution. This particular structure chart illustrates part of the design of a program that updates the content of a master file. It was automatically generated from a data flow diagram by an expert system tool that embodies the rules of structured design.
The BBC Bitesize website has a better and more succinct description.
Decomposition is one of the four cornerstones of Computer Science. It involves breaking down a complex problem or system into smaller parts that are more manageable and easier to understand. The smaller parts can then be examined and solved, or designed individually, as they are simpler to work with.
Why is decomposition important?
If a problem is not decomposed, it is much harder to solve. Dealing with many different stages all at once is much more difficult than breaking a problem down into a number of smaller problems and solving each one, one at a time. Breaking the problem down into smaller parts means that each smaller problem can be examined in more detail.
Similarly, trying to understand how a complex system works is easier using decomposition. For example, understanding how a bicycle works is more straightforward if the whole bike is separated into smaller parts and each part is examined to see how it works in more detail.
Decomposition in practice
We do many tasks on a daily basis without even thinking about – or decomposing – them, such as brushing our teeth.
Example 1: Brushing our teeth
To decompose the problem of how to brush our teeth, we would need to consider:
  which toothbrush to use
  how long to brush for
  how hard to press on our teeth
  what toothpaste to use
Example 2: Solving a crime
It is only normally when we are asked to do a new or more complex task that we start to think about it in detail – to decompose the task. Imagine that a crime has been committed. Solving a crime can be a very complex problem as there are many things to consider.
For example, a police officer would need to know the answer to a series of smaller problems:
  what crime was committed
  when the crime was committed
  where the crime was committed
  what evidence there is
  if there were any witnesses
  if there have recently been any similar crimes
The complex problem of the committed crime has now been broken down into simpler problems that can be examined individually, in detail.
Explanation of abstraction in algorithms
Abstraction in Algorithms
Again the BBC helps with "Abstraction". Abstraction is one of the four cornerstones of Computer Science. It involves filtering out – essentially, ignoring  the characteristics that we don't need in order to concentrate on those that we do.
In computational thinking, when we decompose problems, we then look for patterns among and within the smaller problems that make up the complex problem.
Abstraction is the process of filtering out – ignoring  the characteristics of patterns that we don't need in order to concentrate on those that we do. It is also the filtering out of specific details. From this we create a representation (idea) of what we are trying to solve.
What are specific details or characteristics?
In pattern recognition we looked at the problem of having to draw a series of cats.
We noted that all cats have general characteristics, which are common to all cats, eg eyes, a tail, fur, a liking for fish and the ability to make meowing sounds. In addition, each cat has specific characteristics, such as black fur, a long tail, green eyes, a love of salmon, and a loud meow. These details are known as specifics.
In order to draw a basic cat, we do need to know that it has a tail, fur and eyes. These characteristics are relevant. We don't need to know what sound a cat makes or that it likes fish. These characteristics are irrelevant and can be filtered out. We do need to know that a cat has a tail, fur and eyes, but we don't need to know what size and colour these are. These specifics can be filtered out.
From the general characteristics we have (tail, fur, eyes) we can build a basic idea of a cat, ie what a cat basically looks like. Once we know what a cat looks like we can describe how to draw a basic cat.
A cat stamp is a general model of a cat without added specifics regarding the cats appearance.
Why is abstraction important?
Abstraction allows us to create a general idea of what the problem is and how to solve it. The process instructs us to remove all specific detail, and any patterns that will not help us solve our problem. This helps us form our idea of the problem. This idea is known as a ‘model’.
If we don’t abstract we may end up with the wrong solution to the problem we are trying to solve. With our cat example, if we didn’t abstract we might think that all cats have long tails and short fur. Having abstracted, we know that although cats have tails and fur, not all tails are long and not all fur is short. In this case, abstraction has helped us to form a clearer model of a cat.
How to abstract
Abstraction is the gathering of the general characteristics we need and the filtering out of the details and characteristics that we do not need.
When baking a cake, there are some general characteristics between cakes. For example:
  a cake needs ingredients
  each ingredient needs a specified quantity
  a cake needs timings
When abstracting, we remove specific details and keep the general relevant patterns.
General patterns  Specific details  

We need to know that a cake has ingredients  We don't need to know what those ingredients are  
We need to know that each ingredient has a specified quantity  We don’t need to know what that quantity is  
We need to know that each cake needs a specified time to bake  We don't need to know how long the time is 
Creating a model
A model is a general idea of the problem we are trying to solve.
For example, a model cat would be any cat. Not a specific cat with a long tail and short fur  the model represents all cats. From our model of cats, we can learn what any cat looks like, using the patterns all cats share.
Patterns and similarities can be found between different types of cat. All cats have tails, eyes and fur but the characteristics of each can vary from cat to cat.
Similarly, when baking a cake, a model cake wouldn’t be a specific cake, like a sponge cake or a fruit cake. Instead, the model would represent all cakes. From this model we can learn how to bake any cake, using the patterns that apply to all cakes.
Once we have a model of our problem, we can then design an algorithm to solve it.
Constructing Algorithms
Suppose there is a description of a process that is described in words such as this:
How can this be turned into an algorithm? Even more importatnly how can I get marks in the examination when I try to create an suitable algorithm?
First there are four statements in the description, each of which may or may not be a single pseudocode statement. The 5 marks being the giveaway that perhaps they are not all 1to1 matches between description and pseudocode.
Look at the first statement "get the user to enter a password". There is an AQA pseudocode phrase "USER INPUT" which is used to accept data from the keyboard (or INPUT from the USER). We know that < is used to assign a value to a variable and all we need to do is think of a suitable variable name "Password" seems suitable and put the statement together
Password < USER INPUT
The second statement is very similar. However we cannot use the same variable "Password" to store the user input so a different variable name is needed. "Password2" would seem to be suitable.
Password < USER INPUT
Password2 < USER INPUT
The third statement "repeat the two bullet points above until both passwords are identical is the tricky one that I will leave to the end.
THe fourth statement "Output "password created" when both entered passwords are identical" actually gives you the answer in the text. The keyword in AQA pseudocode to output a value to the user is "OUTPUT" amd the instructions want us to output "password created".
The pseudocode is now:
Password < USER INPUT
Password2 < USER INPUT
OUTPUT "password created"
This would give 3 out of 5: not bad for some common sense. Now for the tricky bit.
We need to test to see if the two passwords are the same "Password = Password2" would do. This would be an IF statement, IF Password = Password2 THEN ...
The first tricky part is to recognise that the program needs to loop when the test fails. If the test passes and the passwords are the same then we can OUTPUT "password created"; but what do we do if it fails  they have to try again.
Password < USER INPUT
Password2 < USER INPUT
IF Password = Password2 THEN OUTPUT "password created"
This would get 4 marks because you have included the comparison but would not satisfy the problem of what to do if the passwords don't match. We need to keep asking the user to input their passwords until they match, i.e. while the passwords dont match input a pair of passwords. This is the clue to the right answer, it is not an IF statement but a WHILE statement and the logical expression must be set to fail so that the loop is repteated.
Password < USER INPUT
Password2 < USER INPUT
WHILE Password != Password2 THEN
Password < USER INPUT
Password2 < USER INPUT
ENDWHILE
OUTPUT "password created"
So this reads as "as long as the passwords do not match keep asking for a pair of passwords; if they do match then say "password created"."
As a computer program it looks like this:
You can see the connection between the pseudocode and the actual Python.
More about Algorithms
The important aspect here is not the code (there is more of than to come) but the shapes of the various algorithms when drawn as flowcharts.
Algorithm constructs
Key algorithm constructs are:
  Sequence
  Selection
  Repetition
You also need to be able to identify
  Inputs and Outputs
  Variable declaration and initialisation
  Subprograms
  Data structures such as arrays (lists)
Sequence is simply the order that instructions follow on from each each.If instructions are out of sequence the result of the algorithm might not be what is intended.A trace table can be used to check that the sequence of instructions is correct.
Selection is the use of a decision within a program used to decide what to do next in a program. Selection uses IF statements.
Repetition is a block of code which is executed more than once – it is repeated. Also known as Iteration. Repetition uses FOR or WHILE loops.
Write the algorithm and draw the flowchart for this program.
Inputs allow data to be entered into an algorithm – either by a user to through some other kind of input device. Inputs use RECEIVE FROM commands in pseudocode
Outputs allow data to be sent from the algorithm. Outputs use SEND TO commands in pseudocode
Variables are named area of memory which hold data.

 Declaration creates the variable.
  Initialisation sets the first value in a variable
Subprograms break programs down into smaller blocks. Subprograms are FUNCTIONS or PROCEDURES in pseudocode.
Data Structures hold data in Arrays or Lists. These allow more than one data item to be held within a named area. To process Arrays or Lists you usually use a loop to work through the structure.
3.1 Fundamentals of algorithms
 3.1.1 Representing algorithms
 3.1.2 Efficiency of algorithms
 3.1.3 Searching algorithms
 3.1.4 Sorting algorithms
3.2 Programming
 3.2.1 Data types
 3.2.2 Programming concepts
 3.2.3 Arithmetic operations in a programming language
 3.2.4 Relational operations in a programming language
 3.2.5 Boolean operations in a programming language
 3.2.6 Data structures
 3.2.7 Input/output and file handling
 3.2.8 String handling operations in a programming language
 3.2.9 Random number generation in a programming language
 3.2.10 Subroutines (procedures and functions)
 3.2.11 Structured programming
 3.2.12 Robust and secure programming
 3.2.13 Classification of programming languages
3.3 Fundamentals of data representation
 3.3.1 Number bases
 3.3.2 Converting between number bases
 3.3.3 Units of information
 3.3.4 Binary arithmetic
 3.3.5 Character encoding
 3.3.6 Representing images
 3.3.7 Representing sound
 3.3.8 Data compression
3.4 Computer systems
 3.4.1 Hardware and software
 3.4.1 Operating systems
 3.4.2 Boolean logic
 3.4.3 Software classification
 3.4.4 Systems architecture
3.5 Fundamentals of computer networks
3.6 Fundamentals of cyber security
3.7 Ethical, legal and environmental impacts of digital technology on wider society, including issues of privacy
 3.7.1 Ethical impacts of digital technology on wider society
 3.7.2 Legal impacts of digital technology on wider society
 3.7.3 Environmental impacts of digital technology on wider society
 3.7.4 Issues of privacy