What is an Algorithm?

What is an algorithm?

It’s a reasonably straightforward question isn’t it? But one that yields quite a few debates. I’ve written the following answer to ‘what is an algorithm?’ question based around the STEM computing classes with children.

First it helps I find it helps if you pretend you’re asking one of these to solve a problem; if you don’t tell them everything they get into a real mess!

Robot algorithm

 

An Algorithm is a precise set of instructions to solve a  problem*

For me, that gets to the heart of the definition: solving a problem in a precise manner.

The problem being solved could be as simple as calculating the number of times ‘as’ appears in this sentence or as complicated as finding the quickest route for a journey across rush hour London.

What’s interesting about algorithms and not obvious from their definition is that once created, executed and observed they can often be refactored/reused to solve other problems that require the same generic process to solve.

For example, I’ve lost count of the times I’ve written a function to solve a specific problem then subsequently refined and abstracted it slightly to solve a much broader range of problems, often implemented using polymorphism. This elasticity, once you recognise it, is for me, the root of writing maintainable code. e.g. In the example above, rather than searching for a specific word, you would refine the algorithm to search for any word. This is obviously beyond the stated curriculum but a nice example of a way to illustrate a seemingly abstract part of the curriculum.

I’ve been asked about efficacy a few times as part of the definition and my view is that its not part of the definition. Efficacy is important for Computing Science but it’s not part of the definition.

* As some children are pretty young, under 7,  we don’t talk about Turing machines. But I know a few people favour this addition to the definition and describe it as something that could be simulated by a Turing complete machine. Although I do wonder if we could somehow simplify and adapt this into the design and discussion of Turing machines…

Hover Bovver Bot GameCity.org – A Programmable HTML5 Version For Teaching Children Algorithms

Hover Bovver was a Jeff Minter* game for the Commodore 64 published by his studio Llamasoft. 30 years later, I can still recall the day I first saw it on my neighbours 64. And hearing it, to a Spectrum owner it sounded incredible:

I had a ZX Spectrum so my games sounded like a bunch of wasps in a tin can

Like most of Jeff’s games, he takes a classic game mechanic and adds his own uniquely brilliant take on it. In this case, he takes Pac-man’s famous ‘visit all the locations” mechanic, changes the ghosts for a gardener and dots for grass.

I’ve always had a soft spot for it, so I’ve decided to remake it for my Craft Computer workshop at the forthcoming GameCity**. I was looking for something simple and cute and for some reason the theme tune to English Country Garden popped into my head 😉

Here’s how the prototype looks after Day 1:

The game itself will be mechanically the same as the original but there won’t be any keyboard or joystick inputs…

Instead the children will have to program the “mowbot” via an iconified programming language – a bit like punch cards!  Rather than the procedural “route finding” approach we’re going to use an event driven language.

If nothing else it should result in the kids having lots of garden based floral carnage!

*Jeff and Llamasoft are still making games and are due to release TXK on the PS Vita shortly. He’s like the Game Industry’s Willy Wonka and if you’ve not played his games, you should go check them out – here’s his Llamasoft site.

**GameCity: I’m going to be there from Weds 23rd to the end on Sat 26th, I’ll be at Waterstone’s running Craft Computer workshops.

Computational Thinking

Computational Thinking. It’s the current buzz phrase of the moment with regard education news. It’s the ‘thing’ we must teach our children.

So what is Computational Thinking?

Although it sounds like it, we don’t want you to think like a computer. It’s really set of ways to think that help you solve problems in a systematic and logical way. More importantly, they are methods that can be ‘abstracted’ and applied to more than one problem.

For example, knowing how to use flour, water and yeast to make dough means you can make breads, pizzas, pasta, cakes.

Computational Thinking will also help you to describe a solution that can be easily translated into a computer program. i.e. Programming

But the real value here extends beyond just programming as they are ways to think about solving problems. Ways that will serve you well solving real-world problems such as: finding the fastest route somewhere, finding a different route if there’s an unforeseen problem, ordering large groups of information, building things, etc

Common types of Computational Thinking are:

Problem Decomposition:

This is the art of taking a hammer to big overwhelming problem and smashing it up into small bite size pieces. Our brains get very tired thinking about solving a big problem in one go.

Think of a child eating solid food. We wouldn’t just give them a whole chicken and a giant potato. We’d help them by cutting it up into ‘bite sized pieces.’

That’s what Problem Decomposition helps us to do, mentally. For example, asking someone to build the Great Wall of China is a Herculean task, and one you’d rightly decline, but at its most fundamental it’s just putting one stone on top of the other. And doing it over and over again. The repetition of an algorithm is an important concept too. We call it a loop.

Problem Decomposition allows you turn an insurmountable problem into something manageable.

Google famously asks questions of its software engineering candidates such as:

How many golf balls can fit into a School Bus?

This is designed to test your problem decomposition skills along with some basic maths. What they are really checking is that you can see beyond the irrelevant parts of the description to the real problem. That you can break it down to a simple volume problem. A rectangular solid’s volume minus the volume of the spheres calculation. A good computational thinker would ignore the colourful but meaningless description of the bus and visualise something like a fish tank filled with ping pong balls.

Pattern Recognition

Being able to see patterns in collections of data such as strings of letters, numbers, objects, graphs is pretty much a fundamental part of Computational Thinking. The good news here is that our brains are pretty much Pattern recognition machines! The Rorschach test is this principle in action.

Pattern Recognition is really powerful as it lets us see beyond the noise of data to the repeating structure behind it. In our previous example of the bus filled with golf balls, pattern recognition lets us zoom through past the windows, wheels and doors and see a familiar maths problem.

Pattern Recognition allows you to see sequences like 1,2,3,5,8,13,21 and see beyond the string of numbers to a simple function that can generate it. It’s a great skill to acquire and leads onto the next part of Computational Thinking, Abstraction.

Abstraction

Abstraction allows you to develop a solution for a single problem and make it generic so it can be used to solve other problems.

i.e. It gives you mindset to look for what’s ‘variable‘, the parts that can be taken out and replaced with an ‘x’

For example, we use time in the short-term in minutes and hours, but we’ve abstracted this into decades and centuries when we’re describing events far in the past or future.

Abstraction is being able to take that seemingly random string of numbers we just saw and, if not immediately see it’s a Fibonacci sequence, know that there is a functional abstraction, i.e. a formula, an algorithm, that can describe the sequence: F_n = F_{n-1} + F_{n-2},\!\,

Algorithms

As we’ve just seen, we can decompose a problem into a pattern or series of patterns that can be abstracted and then turned into an algorithm.

An algorithm is a precise set of instructions to achieve some desired outcome

It could be you want to count the number of words in an article, or find the most common colour in Monet’s Lilies or work out how high a Wimbledon tennis ball bounces when dropped of a 10 foot wall. You’ll probably notice that these problems are really maths problems and you can solve them without a computer but it’s MUCH quicker to use a computer. For example, an average computer can count to a billion in about 4 seconds, how long would it take you?

This is why computational thinking is important, it allows us to solve problems that are either too large for our brains to solve manually or to solve them in a fraction of the time.  Humans are tool users and the computer is our best tool yet.

Whatever the ‘thing’ is you are trying to do, being able to solve your problem by articulating as a set of instructions, such as a computer program, is a very powerful way of thinking and one that lets you know quickly whether you actually understand the problem properly.

Computational Thinking is centered around these four concepts and while programming is the most common form of expressing a solution, it’s reach extends far beyond the computer.

What is Computer Programming?

Computer Programming is simply the act of instructing a computer’s processor (CPU) to perform a task.

6502 CPU
What is Programming? The famous 6502 CPU

In effect, the Computer is your servant, it will do exactly what you tell it to. If something goes wrong it’s your fault!

So What is Computer Programming? Computer Programming is just you telling the machine what to do. Simple eh!?

Sort of.

At a very low, machine level, Computers largely perform binary arithmetic which is pretty much the opposite to how us humans work.

To overcome this problem we have developed ‘Programming languages’ which are attempts to abstract all those numbers with words, grammars and syntax that we can understand.

So instead of us having to write long lists of 1’s and 0’s, programming languages let us write statements like this:


10 PRINT "BARRY IS ACE!"
20 GOTO 10
RUN.

Which if you grew up in the 80’s should be very familiar, if not, it’s a BASIC program that prints “BARRY IS ACE!” to the screen. Forever as dictated by the line “20 GOTO 10” i.e. when you get to line 20 go to line 10 and start again, which is what we call a loop. Actually it’s an infinite loop but that’s for another day.

To recap ‘What is Computer Programming’ is the act of giving a computer a list of things to do. The list usually solves a specific problem or task we’re trying to achieve.

Arguably, modern programming is now largely about interacting with other files and programs (such as databases, libraries, APIs, web services, etc) more than with the low level machine.

This is why most modern development, particularly application development, doesn’t really require strong maths skills.

Computer Programming is about understanding time, resources, networking all tied to strong logical thinking. Sometimes these things follow on from being good at mathematics, but not always.

If you can think laterally about problems and enjoy solving them, chances are you’ll make a good programmer.

Give it a go.

 

 

 

Teaching Children Algorithms : Starting With A Four Year Old

Teaching Children Algorithms

In two months my daughter will be five. This weekend I wanted to teach her two things. The first was to start riding her bike without stabilisers. The second was the word Algorithm, what it means and what one is.

Algorithms - just like riding a bike, sort of.
Algorithms – just like riding a bike, sort of.

The first lesson, riding her bike, is going to take longer than this weekend but she gave it a good crack.

The second, learning about Algorithms was much easier and she got it straight away. I was astonished at how easily she picked up the word and handled it. She can now tell anyone who asks (pretty much me) that Algorithm means ‘instructions to do something’. She even offered her own example Algorithm as I was stuttering around for a suitable one.

Children continue to prove they are mentally as quick if not quicker than I am most of the time. She asked if an algorithm could “paint a square” so we wrote a square algorithm, verbally, during a car journey: draw across, draw down, draw back across then draw up. Granted, it needs some additional accuracy but considering all that was learned and practised in the space of five minutes is incredible.

Her ability to grasp the word, understand it and furnish the word with her own examples gives great credibility to the idea that children at this age can learn to solve problems programmatically. In fact, the hardest part was pronouncing it!

The reason I wanted to start with the word Algorithm was simple. For me, Algorithm is the most powerful word in our Computer Science lexicon. It is the single most important foundation upon which the discipline sits and can build on. That single word can solve millions of problems larger than the mind can often comprehend. It’s a mathematically beautiful concept. The fact a Turing complete machine can run all algorithms is poetry.

Algorithm sounds a bit lofty, a classical sounding word that appears much more complicated that it is. It’s not. Like most mathematics, it’s a simple, economic and elegant idea.

For me it’s the heart of computer science and the part to focus on with children because once they grasp it, everything else is easy.

Sort of.