Sunday 1 June 2014

Computational Thinking

There is more to computer science than programming

The new Computing At Schools (CAS) curriculum puts ‘Computational Thinking’ as a main feature of the program of study. At first, I didn’t pay special attention to the term; I thought as long as it’s something related to programmers and computer scientists, then I must have been doing it for years now anyway, so there’s no need for me to worry about what exactly it means.

With me now being a big supporter of CAS though, I thought I should get a proper understanding of what ‘Computational Thinking’ accurately refers to. After looking at quite a lot of definitions and explanations from different sources, I believe I now have a reasonable understanding of it, but I’ve also realized that this understanding wasn’t gained from one single source but actually by a combination of many.

The top five sources I found useful and that I’ve used in the description below (directly or indirectly), are:

I have two goals for writing this post:
1. To try and provide a simpler description of the term (ideally to spare you having to go through all the sources that I have)

2.  To almost test my own understanding of what information I’ve read, by writing a summary of it – one I can go back to if needed

The term ‘computational thinking’ was first coined by Jeannette M. Wing in 2006.  In a later article of hers (computational-thinking-what-and-why) she referred to the following definition:
Computation thinking is the thought processes involved in formulating problems and their solutions so that the solutions are represented in a form that can be effectively carried out by an information-processing agent1” (an information processing agent can be a human, a machine or a combination of both).

It is reworking what we see as a difficult problem into one we know how to solve. When faced with such a problem, computational thinking addresses the question ‘what is computable?"

From the sources above combined with my own experience, I’ve compiled a list of some of the actions used during computational thinking. The first, in many cases, is ‘decomposition’ which involves breaking up a big task into smaller sub-tasks to make it easier to understand and manage. The following activities are usually applied to these sub-tasks:

Pattern recognition: Using collected data to identify patterns or anomalies.
Being able to read others’ hand writing is done by identifying the general pattern of the letters and comparing them with the example patterns of each letter that we have in our head. Those that we can’t recognize are anomalies in this case. We also identify patterns in people’s behaviour depending on different stimulus and build our future interactions with them accordingly.

Abstraction and pattern generalization: Filtering out unnecessary information for a certain context and keeping only what is generalizable.

: ) is an ‘abstraction’ of a smiling face. Only the very general features of a smiling face are kept (a curved mouth and two eyes). Everything else about the face is left out, yet everybody knows that a colon and a right bracket is a smiley face.

In some cases, multiple layers of abstraction are used to bridge the gap between what is considered useable/understandable by humans and what a machine can use. All ‘easy-to-use’ computer programming languages  use it to turn the 1s and 0s that the hardware deals with into a human readable presentation.

Algorithm design:
developing a step-by-step strategy for solving a problem (one that others can follow without thinking). It’s particularly useful when a  task needs to be repeated multiple times or when a task needs to be carried out by others (including machines)

Preparing a cooking recipe for a friend

Prefetching and caching in anticipation of future use.


Putting things into a school bag or travel bag is ‘prefetching’ for future use. Keeping a tool next to you in case it is needed or to avoid fetching it again is ‘caching’ with the aim of saving time.

Making trade-offs between time, storage space, processing power and complexity.

Should you, very quickly, put the things you need for a trip in a big bag, or spend time to pack things very efficiently into a smaller bag (time vs storage)

Approximation: considering if approximating the current problem into a simpler one (either by simplifying the problem itself, or the information available) will still give us good enough results.
If I need to roughly estimate the cost of a shopping list in a shop, do I need to use the exact prices up to the penny when adding numbers, or can I just approximate to the nearest pound (or in the unlikely case of a very expensive shopping list, to the nearest ten or even a hundred pound!)

Performance modelling

Which line should you stand in at the supermarket, or which route should you choose when travelling to a certain destination?

Apart from the activities above, there are certain approaches to solving problems used quite often in programming that we benefit from in real life without knowing that these are well defined techniques with jargon names such as a ‘binary search tree’. You’ve probably used ‘binary search tree’ without knowing that it has a name and here's an example for it:

A computational thinking example: Guess a number

A few days ago, I was playing ‘guess the number’ with my 7 year old daughter. One of us thinks of a number between 1 and 100 and the other has to guess it. After a few tries, she noticed that I normally guess her ‘secret’ number faster than she guesses mine. So she asked me how I did this. What I was actually doing was using a ‘binary search tree’ technique to guess the number. I explained to her in the simplest way I could think of that she should always give a guess that is the number ‘roughly’ in the middle of the remaining range and she is guaranteed to guess the number in no more than 7 guesses (obviously without explaining why).
I compared this to her random guessing technique and told her that in this case, that may require many more attempts (100 in the very worst case). She obviously experimented with several examples before taking my word for it.

This is a very simple use of computational thinking to show off in front of a 7 year old: “I can guarantee you I’ll guess your secret number in no more than 7 attempts, or to make it more interesting, a number between 1 and a 1000, in no more than 10 guesses”.

Suppose the range is 1-100 and the selected number is 17 (the following scenario is a worst case scenario):

1- Is the number 50? (No - smaller)
2- Is the number 25? (No - smaller)
3- Is the number 12? (No - larger)
4- Is the number 18? (No - smaller)
5- Is the number 15? (No - larger)
6- Is the number 16? (No – larger)
7- The number is 17

Another practical example of computational thinking is using sorting to speed-up search. If you are the person in front of the CD player at a karaoke party with a 100 CDs, finding the required songs will be much faster if these CDs are sorted alphabetically than if they are in a random pile. When the CDs are sorted, your brain is doing some form of binary search to quickly find the right one without you even realizing it. Combining sorting and binary search is one of the most widely used searching techniques in computing.

Back to the term

According to Wing, Computational thinking is not an optional skill, but a fundamental one that everybody should learn, to function in our modern society. It complements and combines mathematical and engineering thinking.

Computational thinking is not just about computer software, but also the concepts we use to solve problems in our daily lives.

1- Jan Cuny, Larry Snyder and Jeannette M. Wing, "Demystifying Computational Thinking for Non-Computer Scientists," work in progress, 2010.