Representing Algorithms

Quick links

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

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 sub-problems, 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 pseudo-code and flowcharts.   Any exam question where students are given pseudo-code will use the AQA standard version. However, when students are writing their own pseudo-code 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. 1. The variable "Area" is set to 0
  2. 2. The variable "Perimeter" is set to 0
  3. 3. Ask the user for the length of a side and store the value in variable "Side"
  4. 4. Calculate the area of the square ("Side" x "Side") and store the value in "Area"
  5. 5. Calculate the perimeter of the square ("Side" x 4) and store the value in "Perimeter"
  6. 6. Output the result, "Area".
  7. 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 industrial-strength 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 top-down 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 1-to-1 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.2 Programming

3.3 Fundamentals of data representation

3.4 Computer systems

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.8 Aspects of software development

Glossary and other links

Glossary of computing terms.

AQA 8520: The 2016 syllabus

AQA pseudocode guide