2.1 - Computational Thinking
In this section (click to jump)
In the world of Stock Photography, when you learn computing, a cardboard cloud shall be your only friend.
Ah, algorithms. What does it even mean? Say it enough times and even the word begins to stop making any sense whatsoever. But..! It underpins everything we're about to do, so it's probably a good idea to understand them.
We are going to go on a journey, a journey of much beard:
1. Decomposition
2. Abstraction
3. Writing algorithms and drawing flow charts
4. Refining algorithms and spotting errors
5. Writing pseudo code.
Only when you have mastered these 5 dark arts, shall you graduate from the academy of computational beardery with first class honours (you'll pass the exam).
We are going to go on a journey, a journey of much beard:
1. Decomposition
2. Abstraction
3. Writing algorithms and drawing flow charts
4. Refining algorithms and spotting errors
5. Writing pseudo code.
Only when you have mastered these 5 dark arts, shall you graduate from the academy of computational beardery with first class honours (you'll pass the exam).
Decomposition
When you become an intelligent, debonair master of algorithms, you too can invest in your own butler.
The problem with you is you're intelligent.
Just stop it.
No, really. Your intelligence is going to get in the way of this section.
We're dealing with computers, and one thing you need to know about computers is they are thick. Incredibly thick. But boy are they obedient. Imagine a crazy dog that literally does anything you say and that's what a computer is like. Throw a stick off a cliff and shout fetch and it'll happily jump off the cliff.
If it had legs.
and was a dog.
What's the point here? The point is that because we have intelligence we don't see things as they really are. We are capable of doing so much without thinking about it. When you add up two numbers, you just do it. Ride a bike? Just get on and go. Cold hands? Just stick them in the toaster for 5 minutes until golden brown, smear with Nutella and enjoy a light snack.
But have you ever stopped to think about how you do things?
Probably not, but when you do, you realise it's not actually that easy to describe exactly how or why you do things. This, to a computer, is a nightmare.
Computers are black and white devices. They don't do maybe, they don't do might, they don't do could/should/would... They do "yes" and they do "no" and if you can't put something in those terms then it can't do it.
The problem gets worse, because we need to be able to tell computers exactly how to do every... last... thing.
Just stop it.
No, really. Your intelligence is going to get in the way of this section.
We're dealing with computers, and one thing you need to know about computers is they are thick. Incredibly thick. But boy are they obedient. Imagine a crazy dog that literally does anything you say and that's what a computer is like. Throw a stick off a cliff and shout fetch and it'll happily jump off the cliff.
If it had legs.
and was a dog.
What's the point here? The point is that because we have intelligence we don't see things as they really are. We are capable of doing so much without thinking about it. When you add up two numbers, you just do it. Ride a bike? Just get on and go. Cold hands? Just stick them in the toaster for 5 minutes until golden brown, smear with Nutella and enjoy a light snack.
But have you ever stopped to think about how you do things?
Probably not, but when you do, you realise it's not actually that easy to describe exactly how or why you do things. This, to a computer, is a nightmare.
Computers are black and white devices. They don't do maybe, they don't do might, they don't do could/should/would... They do "yes" and they do "no" and if you can't put something in those terms then it can't do it.
The problem gets worse, because we need to be able to tell computers exactly how to do every... last... thing.
Computer says "no."
Let's take an example.
"Explain to your computer how to tie shoelaces."
Your first try might go something like this:
"Just tie them up in a knot like this..."
But the computer can't see. Worse, it has no idea what you're on about.
"Explain to your computer how to tie shoelaces."
Your first try might go something like this:
"Just tie them up in a knot like this..."
But the computer can't see. Worse, it has no idea what you're on about.
The exact expression your computer will have. Now you know how your teachers feel when you get stuck in a boot loop and keep saying "don't get it!"
What do you do in this situation?
The same as in any situation when someone you're talking to doesn't understand - break it down in to steps.
So lets really think about it. We all know how to tie our laces (well... most of you) but what are we actually doing, whats the processes we go through?
Well...
Better, right?
The same as in any situation when someone you're talking to doesn't understand - break it down in to steps.
So lets really think about it. We all know how to tie our laces (well... most of you) but what are we actually doing, whats the processes we go through?
Well...
- First tie a simple knot
- Then make a bow
- pull until tight
Better, right?
Not good enough!
Why? Because we haven't explained how we do these things. Try again...
1. Get a lace in each hand
2. Cross one over the other
3. Pull
4. Make a loop with one lace
5. wrap the other lace around the loop
6. Push the remaining lace through the loop you've just created
7. Pull both loops tight.
We could go into even more detail but this will do us for now.
Seems really complicated, doesn't it? But actually the complexity is in the simplicity! What on earth am I talking about?
It can be a complex task to an intelligent person to break down something seemingly simple into individual, specific steps.
This is exactly what decomposition is:
Decomposition - Breaking problems down in to their component parts
Therefore, the first part of designing any algorithm is to decompose the problem. Ask yourself:
The good part about decomposition is we can identify steps that need to be taken even if we have no idea how we will do them!
What do I mean? One more example:
Why? Because we haven't explained how we do these things. Try again...
1. Get a lace in each hand
2. Cross one over the other
3. Pull
4. Make a loop with one lace
5. wrap the other lace around the loop
6. Push the remaining lace through the loop you've just created
7. Pull both loops tight.
We could go into even more detail but this will do us for now.
Seems really complicated, doesn't it? But actually the complexity is in the simplicity! What on earth am I talking about?
It can be a complex task to an intelligent person to break down something seemingly simple into individual, specific steps.
This is exactly what decomposition is:
Decomposition - Breaking problems down in to their component parts
Therefore, the first part of designing any algorithm is to decompose the problem. Ask yourself:
- What is the problem?
- What are the main components of this problem?
- What steps would take me to the desired outcome?
The good part about decomposition is we can identify steps that need to be taken even if we have no idea how we will do them!
What do I mean? One more example:
Problem: Work out how to live forever
Decomposition:
It is obvious that there are some problems there that no one has solved yet, but it didn't stop us decomposing the problem! We are now one step closer to an algorithm.
Decomposition is not only useful in Computer Science, but is a genuinely useful life skill. Too often we will only look at the problem and will fail to decompose it, to break it down and work out what really we need to worry about. Without decomposition, everything looks big and scary.
But this is exactly what we need to learn to do, and it's a fine art because you can go too far...
Decomposition:
- Identify factors which affect aging in the human body
- Identify ways in which people die
- Work out how not to get killed in an accident
- Find a method of turning off genes/DNA/cells which cause ageing
- Work out what to do with never ending life.
It is obvious that there are some problems there that no one has solved yet, but it didn't stop us decomposing the problem! We are now one step closer to an algorithm.
Decomposition is not only useful in Computer Science, but is a genuinely useful life skill. Too often we will only look at the problem and will fail to decompose it, to break it down and work out what really we need to worry about. Without decomposition, everything looks big and scary.
But this is exactly what we need to learn to do, and it's a fine art because you can go too far...
Abstraction
What on earth is even happening here? I Googled "talking." The internet is a truly terrifying place.
Abstraction is awesome.
Have you ever had a conversation with someone where they just rattle on and on for what seems like an eternity, telling you every last detail about a story, who said what, who did what, what people were wearing, where they stood, what colour their shoes were, who had halitosis, which person hand a limp and smelled faintly of over ripe bananas and the direction the carpet pile went in.
You can feel yourself slowly dying in side, lights go out one by one and your last thought as you drift out of consciousness is "just get to the point!"
This is where abstraction comes in.
The term abstract basically means to summarise. In computer science, abstraction is:
Focusing on only the necessary, relevant information/detail
KEY EXAM POINT ALERT!!
In the exam you would want to say:
Abstraction is simple:
Example: Lord of the rings. 3x 3 hour films, full of much drama and peril for small furry footed creatures.
Abstract: Some small people and a wizard go for a very long walk. (and why didn't they just get the eagles to fly them there?)
As you can see, using abstraction we can condense huge amounts of detail and information down in to virtually nothing. This is a good thing.
When creating a computer program or algorithm, we need to be highly focused. We must concentrate only on what actually needs to be done in order to solve a problem.
To do this, you need to ask yourself "What is the goal?" Once you have identified your outcomes, work backwards through your decomposed problem and identify the information, processes and data you might need to get to your goal. Everything else is irrelevant.
Example:
Make a program to monitor traffic on a motorway and find the average speed of cars between speed cameras.
There is a wealth of information we could include in this scenario which might appear to be useful during decomposition:
and so on....
However, most of this is utterly pointless.
What is the goal here?! To find the average speed of each car!
Nothing else matters (which happens to be a song by Metallica, who are utterly terrible). Nothing.
We have abstracted the problem - "find the average speed." Now we've done that, actually it turns out all we need to know to solve this problem is:
Speed = distance/time, so we need no more information.
Software and big projects especially, go very wrong when people become eager to dump in endless amounts of data because we can, because it seems like a good idea, or might be useful. The art of achieving programming zen is to be able to focus solely on what the abstracted problem is and nothing else. Only then will you become one with the code.
Have you ever had a conversation with someone where they just rattle on and on for what seems like an eternity, telling you every last detail about a story, who said what, who did what, what people were wearing, where they stood, what colour their shoes were, who had halitosis, which person hand a limp and smelled faintly of over ripe bananas and the direction the carpet pile went in.
You can feel yourself slowly dying in side, lights go out one by one and your last thought as you drift out of consciousness is "just get to the point!"
This is where abstraction comes in.
The term abstract basically means to summarise. In computer science, abstraction is:
Focusing on only the necessary, relevant information/detail
KEY EXAM POINT ALERT!!
In the exam you would want to say:
- Abstraction removes or obscures unnecessary detail (notice you MUST use the word unnecessary in your answer)
- The reasons we do this are:
- Enable us to focus on the main processes in a problem
- Enable us to more easily understand a problem
- To reduce the complexity of a computer representation of something
Abstraction is simple:
Example: Lord of the rings. 3x 3 hour films, full of much drama and peril for small furry footed creatures.
Abstract: Some small people and a wizard go for a very long walk. (and why didn't they just get the eagles to fly them there?)
As you can see, using abstraction we can condense huge amounts of detail and information down in to virtually nothing. This is a good thing.
When creating a computer program or algorithm, we need to be highly focused. We must concentrate only on what actually needs to be done in order to solve a problem.
To do this, you need to ask yourself "What is the goal?" Once you have identified your outcomes, work backwards through your decomposed problem and identify the information, processes and data you might need to get to your goal. Everything else is irrelevant.
Example:
Make a program to monitor traffic on a motorway and find the average speed of cars between speed cameras.
There is a wealth of information we could include in this scenario which might appear to be useful during decomposition:
- The type of car
- The registration of each car
- The colour of the car
- The number of cars
- The make/model
- Which lane the car is travelling in
- The direction of travel
- The distance between each camera
- The date and time of each journey
and so on....
However, most of this is utterly pointless.
What is the goal here?! To find the average speed of each car!
Nothing else matters (which happens to be a song by Metallica, who are utterly terrible). Nothing.
We have abstracted the problem - "find the average speed." Now we've done that, actually it turns out all we need to know to solve this problem is:
- The registration of each car
- The time it passed camera 1
- The time it passed camera 2
- The distance between them.
Speed = distance/time, so we need no more information.
Software and big projects especially, go very wrong when people become eager to dump in endless amounts of data because we can, because it seems like a good idea, or might be useful. The art of achieving programming zen is to be able to focus solely on what the abstracted problem is and nothing else. Only then will you become one with the code.
Writing Algorithms
"I shall take both tests at once..."
What is an algorithm?
A set of steps that, when followed, will solve a problem.
We can do better than that:
A set of steps, which provides a solution to a problem and should work for all reasonable input or data.
So far, we have:
Now we're ready to do the scary bit - actually solve the problem.
By the time you come to actually write an algorithm, you should have already broken your problem down into manageable chunks. Lets look at an example:
Problem: Make a program which performs simple calculations for the user, e.g. "47 x 35" or "17 - 10"
Decomposition/Abstraction:
We will need a program which:
This list is clearly abstracted - we haven't worried about what the program looks like, how it does those things or how we may add features beyond the scope of the question. Basically put, we have done only what is necessary.
Now, the beauty of decomposition is that we could simply put lists like that together and then leave it there - we've suggested sensible steps towards providing a solution to the problem, but that is no longer good enough!
The next step to an algorithm is to take each of those steps (or in the case of big programs, just the complex ones) and working out how we'll actually do it!
So, let's take the first three bullet points, they're simple enough:
That's not so bad is it? We've just used sequencing and broken the problems down in to a set of steps. Nice. Let's move on.
A set of steps that, when followed, will solve a problem.
We can do better than that:
A set of steps, which provides a solution to a problem and should work for all reasonable input or data.
So far, we have:
- Been given a problem
- Broken it down (decomposition)
- Identified only the relevant information needed to solve the problem (abstraction)
Now we're ready to do the scary bit - actually solve the problem.
By the time you come to actually write an algorithm, you should have already broken your problem down into manageable chunks. Lets look at an example:
Problem: Make a program which performs simple calculations for the user, e.g. "47 x 35" or "17 - 10"
Decomposition/Abstraction:
We will need a program which:
- asks the user for a number
- asks for an operator (+, -, *, /)
- asks for another number
- checks what the operator is
- performs the calculation
- Outputs the answer
This list is clearly abstracted - we haven't worried about what the program looks like, how it does those things or how we may add features beyond the scope of the question. Basically put, we have done only what is necessary.
Now, the beauty of decomposition is that we could simply put lists like that together and then leave it there - we've suggested sensible steps towards providing a solution to the problem, but that is no longer good enough!
The next step to an algorithm is to take each of those steps (or in the case of big programs, just the complex ones) and working out how we'll actually do it!
So, let's take the first three bullet points, they're simple enough:
- Ask the user for number 1
- store the answer in a variable called "num1"
- ask the user for number 2
- store the answer in a variable called "num2"
- ask the user which type of calculation they would like to do
- store the answer in a variable called "operator"
That's not so bad is it? We've just used sequencing and broken the problems down in to a set of steps. Nice. Let's move on.
Niiiice.
What about the rest of the program?
Slightly more difficult, but with practise you'll recognise that problems like this require a sprinkling of "selection." Lets see what that breaks down in to:
You should be realising by now that algorithm writing is about these key things:
Stick to these rules and you shouldn't go far wrong.
- checks what the operator is
- performs the calculation
- Outputs the answer
Slightly more difficult, but with practise you'll recognise that problems like this require a sprinkling of "selection." Lets see what that breaks down in to:
- if the operator is "+" then
- add num1 and num2 together, store the answer in a variable called "answer"
- Output answer
- if the operator is "-" then
- take num2 away from num1, store the answer in a variable called "answer"
- Output answer
You should be realising by now that algorithm writing is about these key things:
- Saying exactly what you will do
- Stating exactly how you will do each step
- Not leaving anything to guess work - look what you've written, have you explained the steps to achieve every last part?
- Using very short, simple steps that cannot be broken down any further.
Stick to these rules and you shouldn't go far wrong.
Flow Charts
"Your time will come to work things out, let it flow" sang bearded musicians from Somerset. What more do you need?
Once we're confident with breaking problems down we need to start formalising our ideas. There are two main methods - Flow Charts and Pseudo code, both of which you'll need for both exams and your coursework. The whole course, in other words. No pressure, just saying.
A computer program/algorithm is actually made up of some very simple building blocks and we make virtually everything by just combining them using our dark, mystical programming mindset.
What are these building blocks called?
•Sequence or sequencing:
–Placing instructions in the correct order
•Selection
–Making a decision and allowing different actions to be taken depending on the outcome
•Iteration
–Doing things repeatedly, or going back to a certain point in an algorithm/program
That's easy enough, right?
Let's get this clear - if you tell the computer to do things in the right order (sequence), make the right decisions (selection) and occasionally go round in circles (iteration) you'll be fine.
Actually, re-reading that it sounds like an abstraction of some peoples lives.
A computer program/algorithm is actually made up of some very simple building blocks and we make virtually everything by just combining them using our dark, mystical programming mindset.
What are these building blocks called?
•Sequence or sequencing:
–Placing instructions in the correct order
•Selection
–Making a decision and allowing different actions to be taken depending on the outcome
•Iteration
–Doing things repeatedly, or going back to a certain point in an algorithm/program
That's easy enough, right?
Let's get this clear - if you tell the computer to do things in the right order (sequence), make the right decisions (selection) and occasionally go round in circles (iteration) you'll be fine.
Actually, re-reading that it sounds like an abstraction of some peoples lives.
"Zoom!"
What was that?
That was your life, mate!
Do I get another one?
Nah, sorry.
What was that?
That was your life, mate!
Do I get another one?
Nah, sorry.
Flow charts are incredibly useful things but sometimes can be hard for people to learn. They let us:
The idea is brilliant. You can easily follow the program (just follow the lines and do as you're told!) and if we spend time here, we should save loads of time later when we don't have to debug our code in the programming editor/language of our choice.
In a magical land, far, far away where it's always sunny, everyone is happy and living bacon (pigs) soar high in the sky, this actually happens.
So lets look at the symbols and rules we should use when drawing flow charts:
- Visualise our programs
- Follow our algorithms and check they work
- Debug our algorithms and find errors in our logic
The idea is brilliant. You can easily follow the program (just follow the lines and do as you're told!) and if we spend time here, we should save loads of time later when we don't have to debug our code in the programming editor/language of our choice.
In a magical land, far, far away where it's always sunny, everyone is happy and living bacon (pigs) soar high in the sky, this actually happens.
So lets look at the symbols and rules we should use when drawing flow charts:
Summary: put one at the start and if you don't have at least one stop something has gone very wrong.
Summary: This is the symbol to use when your program is "doing" something - maths, changing a variable value...
Summary: Need to ask the user a question or show something on the screen? Use this symbol.
Summary: Any time you need to implement a rule in your program, use this symbol.
One of the biggest problems with flow charts is that they rapidly become really, really long and can spill over many pages for programs that aren't actually that complicated. One way to combat this is to use one final symbol called a "sub routine."
Sub routines are little blocks of code that do a specific task - for example working out the date, displaying or updating the score in a game or sorting a list of data in to order.
To make a sub routine in your flow charts, simply put the sub routine symbol and then go and draw a new flow chart (complete with start and stop symbols) for that individual task. With practice, these are easy to understand and follow too.
Sub routines are little blocks of code that do a specific task - for example working out the date, displaying or updating the score in a game or sorting a list of data in to order.
To make a sub routine in your flow charts, simply put the sub routine symbol and then go and draw a new flow chart (complete with start and stop symbols) for that individual task. With practice, these are easy to understand and follow too.
Summary: Use this symbol to indicate that there is a separate flow chart for this particular task.
Once you've got the hang of using the various symbols, all you need to be able to do for the exam is follow them through and state what the outputs would be for a given input.
You were all amazing at that in lessons so all that you need is practice - grab the questions from the shared area and try them out. Failing that, draw your own and practise putting different inputs in.
You were all amazing at that in lessons so all that you need is practice - grab the questions from the shared area and try them out. Failing that, draw your own and practise putting different inputs in.
Drawing a Flowchart - An Example Question
ke an example question: A program asks the user to enter a number. The program then outputs the 12 times table for that number, e.g. if they enter 5 it displays 5, 10, 15 etc.
The first thing to do is to work out what inputs we will need - what information do you need to go away and do this task?
We don't need any more input. What else do we know? Well, a little bit of thinking should tell you that you are going to have to do something over and over again. What's that?
What is this called when we do something over and over again? Repetition or... Iteration. Whenever we have iteration we know there is a loop in our program. This means our flow chart will need a decision symbol, some kind of counter and a line that goes back on itself.
So far, then, what do we know?
Lets turn that in to a flow chart.
The first thing to do is to work out what inputs we will need - what information do you need to go away and do this task?
- Times_Table - this will be a variable that holds the number of the times table we are going to output (1, 2, 3, 4 ... 11, 12)
We don't need any more input. What else do we know? Well, a little bit of thinking should tell you that you are going to have to do something over and over again. What's that?
- Multiply the Times_Table number by 1, then 2, then 3, then, 4.... all the way to 12.
What is this called when we do something over and over again? Repetition or... Iteration. Whenever we have iteration we know there is a loop in our program. This means our flow chart will need a decision symbol, some kind of counter and a line that goes back on itself.
So far, then, what do we know?
- We will ask for input and store it as Times_Table
- We will then need to go round 12 times and work out 1xTimes_Table, 2xTimes_Table, 3xTimes_table etc
- We will need to output the answer.
Lets turn that in to a flow chart.
If you didn't know yet, you can really easily draw out flowcharts online by visiting www.draw.io
This example is a perfect illustration of how to do iteration (a loop) using a counter variable. To make it work, all we had to do was create a variable called Counter and set the value to 1. Then, in the decision symbol, we check if we have gone round the loop 12 times. If not, we drop down and do our calculations. Notice the really important bit at the bottom - "Counter = Counter + 1" this is the bit that makes our counter go up by 1 each time we go round the loop and if we miss it out... the loop goes round forever!
Notice the other clever advantage of using the loop counter? No?
"Answer = Counter * Times_Table"
We can use it as part of our program - think about it, it makes sense to use our loop counter in this situation.
Anyway, we're getting on to stuff that we need to learn in pseudo code, so look over this flow chart, practise yourselves and then move on to the next section.
This example is a perfect illustration of how to do iteration (a loop) using a counter variable. To make it work, all we had to do was create a variable called Counter and set the value to 1. Then, in the decision symbol, we check if we have gone round the loop 12 times. If not, we drop down and do our calculations. Notice the really important bit at the bottom - "Counter = Counter + 1" this is the bit that makes our counter go up by 1 each time we go round the loop and if we miss it out... the loop goes round forever!
Notice the other clever advantage of using the loop counter? No?
"Answer = Counter * Times_Table"
We can use it as part of our program - think about it, it makes sense to use our loop counter in this situation.
Anyway, we're getting on to stuff that we need to learn in pseudo code, so look over this flow chart, practise yourselves and then move on to the next section.
