Category Archives: Algorithms

Should We Mind the ‘Reality Gap’?

It’s generally accepted that making education ‘relevant’ is a good thing for the classroom.  Usually, this means finding practical applications for theory.  But how much of a problem is it when our ‘real world’ examples aren’t as ‘real’ as they might appear?  How important is the ‘Reality Gap’?

A universal complaint of students, whether at school, college or university, is that they often don’t see the relevance of some of the material they study.  “When am I going to be doing this in a real job?” is a typical question.  There are three broad categories of response from the teacher; bluntly and clumsily characterised as follows:

  1. “You’re getting an education that shows your capability at this level.  The content doesn’t matter.  You’ll be trained to do a particular job when you’ve got one.”
  2. “You might only use about 10% of what you’re learning now in the real world but you don’t know which 10% it’s going to be and your 10% will be different to everyone else’s 10% so we have to do all this stuff.”
  3. “Well, here’s an example of how this might be used in the real world.”

(A good teacher would add a considerable degree of finesse to these answers, of course.)  Ignoring the merits and demerits of 1 and 2 entirely, how best to achieve 3 presents some interesting challenges because, much as we might like to pretend otherwise, the real world is a terribly complicated place, in which the textbook usually only gets us so far … Continue reading


A Christmas Cracker Algorithm!

T’is the season to be jolly … and silly.  So here’s a seasonal and jolly silly example of why it’s hard to implement high-level languages efficiently.  Liberties are taken with the hardware/software relationship in some parts of the analogy but, hey, it’s Christmas!

Let’s write an algorithm for pulling a Christmas cracker …

  • Buy a box of crackers and bring home
  • Take a cracker out of the box
  • Get two people to hold an end each
  • Pull in opposite directions
  • Have fun with what’s inside
  • Clear up the mess

That’s probably going to be enough detail for most people (and more than enough for some).  However, if you’re the one that’s been entrusted with the initial purchase or the child told to do the clearing up, you might want a bit more to go on; what’s actually involved in that bit?  And who are the ‘two people’ anyway?  OK then, if needed, we can easily expand this a touch …

Continue reading


An Alternative to “Hello world!”

There’s an appreciable risk that this post may be considered sacrilegious within the programming world.  If there’s one thing, even  just one tiny, single thing, that every programmer knows about teaching programming, it’s that the first lesson should be how to output the string, “Hello world!”  (There’s some dispute as to whether the ‘w’ should be capitalised but the ‘!’ is entirely necessary.)  How heretical would it be to suggest that, not only is this probably not the best place to start, but that a better alternative can be found by turning around a bottle of shampoo?

ShampooBottle Continue reading


Maths and Programming Working Together

When the Four Colour Theorem (FCT) was finally ‘proved’ in 1976, it upset a lot of mathematicians.  It was the first significant mathematical concept to be proved with a good deal of help from a computer and, for many, that didn’t make it a real proof.  Although we’re largely (maybe not entirely) OK with it now, the objections at the time weren’t just theorists’ snobbery.  At the heart of it all were some fundamental questions about the role a computer could or should play in formal logic.

Essentially, the FCT says that the maximum number of different colours needed to colour a map, so that no bordering countries are the same colour, is four.  (Colours can touch at a point but not at an edge.)  It’s easy to show that five will always do the trick and, in fact, most normal maps only need three.  However, certain types of map certainly seemed to need four so was four always enough? Continue reading