Category: Algorithmic thinking

The complexity of searching to speak

A close up of a blue eye
Image by Melanie from Pixabay

Locked-in to the Game of 20-Questions

One of the worst medical conditions I can imagine is locked-in syndrome. It leaves you with all your mental abilities intact, but totally paralysed except perhaps for the blink of an eye. A perfectly working mind is locked inside a useless body, able to sense all around but unable to communicate. Despite this, one of the most uplifting books I have read is “The Diving Bell and the Butterfly”. It’s the autobiography of Jean-Dominique Bauby, written after he woke up in a hospital bed with locked-in syndrome. In the book, he describes a life with locked-in syndrome, including how he communicated not only with medical staff, friends and family but also to write the book itself. He did so without any technological help.

The book was written via human-human interaction of a heroic form. Put yourself in his position, waking up in a hospital bed totally paralysed. All you can do is blink one eyelid. What would be the best way for you to communicate so that you could write a whole book? You have only a helper with a pen and paper to write down your “words”?

How did Bauby do it?

The system Bauby used involved the helper reading the alphabet aloud “A…B…C …” When the letter he was thinking of was spoken he blinked. The helper would write that letter down and then start again, letter after letter. Try it with a friend: communicate your initials to them that way…now think about that being the only way you have to talk to anyone. I hope your name isn’t Zebedee Zacharius Zog or Zara Zootle!

Bauby realized that the ABC algorithm could be improved upon. He had been the Editor-in-chief of the French women’s magazine Elle before that hospital bed so knew about language. He knew that some letters are more common than others in natural language, so got the helper to read out the letters in order of frequency in French “E…S…A…R…” That way the helper got to the common letters more quickly. A similar trick has been used through the ages to crack secret codes (see our Beheading story elsewhere).

Now as a computer scientist I immediately start thinking I could have made his life so much better (even before the step replacing the human helper with blink detection gadgets and the like). It is a problem about the “complexity”, the efficiency, of algorithms.

In the worst case, perhaps dictating a story where someone does nothing but snore for the whole book, “Zzzzz”, it takes 26 questions per letter. On average over the whole book roughly 13 letters will be said per letter dictated. Bauby’s modification improves things down to about 10 questions per letter, but the worst case is still 26. Thinking as a computer scientist the problem is a search problem (searching for one letter in 26) and the solution he used is known as linear search.

Linear search is a “linear” algorithm with “linear” complexity meaning the time it takes to give an answer is proportionate to the amount of date. Double the data and the algorithm takes twice as long to find the answer. Computer Scientists write this as O(n) as short hand for saying it is linear.

Do it in 5

Other search algorithms are far faster than linear search. From some simple computer science I learnt as an undergraduate, I know that a search through 26 things only needs at most 5 true/false or blink/no blink questions at worst, not 26!

How do we do it? By using the same strategy as is used in the children’s game of 20 questions. It is a search problem too: a search to find the name of a famous person out of thousands, possibly millions of people. And yet it does not take thousands or millions of questions to win. It is all in the questions that you ask.

Played well you do not ask as the first question “Is it Einstein?”, the equivalent to “Is it E?” Rather you first ask: “Are they female?”. Why is that a better question? It is because it rules out half the possibilities whatever the answer. Start with a million possibilities and always ask a halving question and you Try it – start with 1 million and see how many times you have to halve it before you get down to 1:

1 000 000  people are possible to start with
   500 000  people left after 1 question  
   250 000  people left after 2 questions 
   125 000  people left after 3 questions
     64 000  people left after 4 questions, approximately its actually a bit better than this
     32 000  people left after 5 questions
     16 000  people left after 6 questions
       8 000  people left after 7 questions
       4 000  people left after 8 questions
       2 000  people left after 9 questions
       1 000  people left after 10 questions
          500  people left after 11 questions
          250  people left after 12 questions
          125  people left after 13 questions
            64  people left after 14 questions, approximately
            32  people left after 15 questions
            16  people left after 16 questions
              8  people left after 17 questions
              4  people left after 18 questions
              2  people left after 19 questions
              1  person left after 20 questions

So starting with a million people, if you always ask halving questions, it only takes 20 questions (in the worst case) to have found the person, they were thinking of.

The equivalent halving question for the alphabet is “Is it before N?” Keep asking questions like that about letters in the remaining portion of the alphabet, rather than asking if it was a specific famous person, and you get down to a single letter in no more than 5 questions. 


            26  letters are possible to start with
            13  letter left after 1 questions
              7  letter left after 2 questions
              4  letter left after 3 questions
              2  letter left after 4 questions
              1  letter left after 5 questions

Tweak it based on letter frequencies and you can do even better for some letters.

Algorithms that halve the size of the problem at each step like this are called logarithmic algorithms. The number of steps it takes no longer increases proportionately with the amount of data, but with the logarithm of the amount of data. If we have n pieces of data to search it takes log (n) steps to find it. This is because the logarithm (to base 2) of a number is just the number of times you can halve the number before you get to 1. The notation log(n) is just a maths way of counting the number of times we halve. As we saw logarithmic algorithms like this are massively more efficient. When you double the amount of data (say from half a million pieces of data to search to a million pieces of data to search, you only need one extra step to find the answer (rather than half a million more). Our new halving algorithm has logarithmic efficiency, which we write O(log n). O(log n) algorithms are massively faster in general than O(n) algorithms.

Bauby should have got the helper to ask such halving questions. Think about it. 5 questions at worst rather than 26, multiplied up by all the letters in his book. If only he had known some computer science, how much easier his life would have been. How much easier it would be to write the book. Now we have worked out a method we can think how we could automate it with suitable technology. How wonderfully computer science can improve lives.

But wait a minute. Perhaps the computer scientist would have ensured his book was never completed and his life was even more a hell. We did not start with technology but we did start with computer science. Perhaps we should have started with the person. We have been counting questions asked and that is the job of the helper for which it may be tedious but it’s not difficult. What if blinking is a great effort for him. His solution involved him blinking only once per letter. Ours requires him to blink 5 times. Multiply that by a whole book and it is 5 times harder for him if blinking is hard. Furthermore, his solution is easy for anyone to walk in and understand. Ours is complex and might need some explaining before the visitor understands and Bauby is not going to be the one to do the explaining.

It worked for him

One thing is certain about Bauby’s solution – it worked for him. He wrote a whole book that way after all. Perhaps the helper did more than just write down his words. Perhaps they opened the curtains, talked to him about the outside world or just provided some daily human warmth. Perhaps the whole point of writing the book was that it gave him an excuse to have a person there to communicate with all the time. The communication method would not then be facilitating the needs of the book, but the book facilitating a deep need for direct communication with a person. Replace the human and perhaps you have replaced the thing that was actually keeping him alive. In extreme usability situation such as this the important thing is that the user really is involved throughout. It is they who ultimately have to adapt the available resources to something that works for them, not only technically but also emotionally and socially. Otherwise we may devise a “solution” that is in theory wonderful and in practice hell on earth. Complexity of algorithms is important but Computer Scientists have to think about much more than just maths and efficient solutions.

Paul Curzon, Queen Mary University of London (updated from the archive)

Further Reading

Find out about what life is like with locked in syndrome by reading: The Diving Bell and the Butterfly by J-D Bauby. Fourth Estate.

More on …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

Lego Computer Science: Programming Creativity

White lego buildings rising from rubble
Image by Paul Curzon taken at Tate Modern London at Olafur Eliasson’s “The cubic structural evolution project” exhibition, 2019.

My absolute favourite example of interactive art is Olafur Eliasson‘s “The cubic structural evolution project” back in 2019 at Tate Modern. It was “just” two piles of standard white Lego bricks piled on two tables (but a tonne of Lego between the two …so a LOT of Lego). Anyone visiting the exhibit was invited to sit down and help create a city by building a building … and it was joyfully creative. Kids and adults mixed together building great architectural wonders, big and small, out of the bricks. Sometimes intentionally, but often accidentally, an existing building was demolished, but that was just an opportunity for new amazing buildings to emerge from the rubble. We visited twice that summer, and each time a totally different city was there that had emerged from this constant evolution of building. On each visit we built something new ourselves to add to the ever changing city.

The exhibit took Lego back to its roots – no instructions, no specific creation to reproduce, just the bare building blocks of creativity. You can still buy generic lego sets of course (if not with the same scope as a tonne of bricks). However, the high profile modern Lego sets are now used to build a specific thing designed by someone else, like a Star Wars Tie fighter, a Death Star, a Ferrari, a parrot or perhaps Notre Dame. This is one form of creativity – you are definitely creating something, and doing so gives you an amazing feeling of accomplishment and well-being. I strongly recommend it and of doing similar activities whether doing a tapestry, or building a jigsaw, or … It is good for your happiness and mental health more generally. But you are creating just by following instructions. In computer science terms, you are acting as a computational agent, following an algorithm that if followed precisely guarantees the same result every time (an exact copy of the lighthouse on the box perhaps…). A computer (with a suitably good robotic arm and vision system) could do it. That is the point of algorithms! They take no thought just an ability to follow instructions precisely: the thing computers are good at.

There is another sense we mean when we talk about creativity though and that was the original Lego idea. You have the bricks. You can build anything. It is down to you. Create something new! According to an exhibition on the history of play I went to early construction kits like the original Lego inspired a whole generation of architects to do completely new things with buildings (if you know your architecture think especially Frank Lloyd Wright whose mother bought him educational blocks called the Froebel Gifts, or perhaps Denys Lasdun – I lived in one of his “Lasdun building” block like buildings for a year in my younger days).

This kind of pure creativity is what being a programmer is about. Not just following instructions to create someone else’s creation, but creating your own totally novel, wondrous things from simple building blocks (and you don’t have to be part of the Lego design team to do it either). That is the lesson that collaboratively emerged in Olafur Eliasson’s exhibit over and over again. Just as the inventor of Lego, Ole Kirk Christiansen, in creating the toy went to yet another level of creativity in doing so, Olafur Eliasson did so to in creating the exhibition. They both created the opportunities for others to be creative.

Programming languages are very much like Lego in this sense. They just provide the building blocks to create any program you want. Learn how to use them and you you can do anything if you have the imagination as well as having built the skill. The different constructs are like different kinds of Lego bricks. Put them together in different ways and you create different things. You can stick with the basics and still build amazing creations even without learning about all the libraries methods that act like specialist bricks designed for specialist purposes. And of course the early Computer Scientists who invented the idea of programming languages were being creative in the way Ole Kirk Christiansen and Olafur Eliasson were, creating the possibility for others. Creating possibilities for you.

The Arts are about pure creativity but so is Computer Science…(and when they are brought together by creative people even more amazing things can be created (by everyone).

Paul Curzon, Queen Mary University of London

More on …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

DoodleDraw a snowflake

A single snowflake
Image by Cheryl Johnson from Pixabay

Following algorithms to draw nature can lead to natural looking pictures of all all sorts of things: from trees to snowflakes. It is one way computer generated imagery (CGI) scenery is created for films and games. You can write computer programs to do it if you have programming skill, but it can be just as fun (and more stress-relieving) to just doodle algorithmic pictures by hand – you act as what computer scientists call a ‘computational agent’ just following the algorithm. Here is an example Doodle Algorithm to draw a snowflake.

The DoodleDraw Algorithm

1. Draw a Black rectangle
2. Draw a SnowflakeHex in the middle of the black rectangle.
3. DoodleDraw a.Hexagon Snowflake

To Draw a SnowflakeHex:
    1. Draw a white hexagon with white lines sticking out from each corner (as shown).

To DoodleDraw a Hexagon Snowflake:
    1. IF happy with the picture THEN STOP
        ELSE
            1. Pick an existing SnowflakeHex and pick a line on it.
            2. Draw a new smaller SnowflakeHex on that line.
            3. DoodleDraw a Hexagon Snowflake.
A hexagon with lines from each corner
Image by CS4FN

The doodle this led to for me is given below… does it look snowflake-ish? Now follow the algorithm and draw your own, just like snowflakes every drawing should be different even if following the same algorithm as we include random steps in the algorithm.

A snowflake drawn from hexagons with lines from each corner
Image by CS4FN


Different algorithms with different starting shapes give different looking trees, grasses, ferns, snowflakes, crystals,… Often nature is following a very similar recursive creation process, which is why the results can be realistic.

Try inventing your own doodle art algorithm and see how realistic the drawings you end up with are. First try using a slightly different starting picture to ours above (eg a hollow hexagon instead of a filled in one, or skip the lines, or have more lines, or have a different central image to the one that is then replicated…and see what you end up with. Find lots more ideas for doodle draw algorithms on our DoodleDraw page.

Next time you find yourself doodling in a meeting or lecture, invent your own doodle draw algorithm, draw an algorithmic doodle, develop your algorithmic thinking skills and at the same time explore algorithms for drawing nature.

More on …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

Hear and … their magic square

A magic three by three square with the numbers 2, 9 and 4 in the top row, 7, 5 and 3 in the middle row and 6, 1 and 8 in the bottom row. Each row, column and the two diagnonals add up to 15.
Image by CS4FN

Victorian Computer Scientists, Ada Lovelace and Charles Babbage were interested in Magic Squares. We know this because a scrap of paper with mathematical doodles and scribbles on it in their handwriting has been discovered, and one of the doodles is a magic square like this one. In a magic square all the rows, columns and diagonals magically add to the same number. At some point, Ada and Charles were playing with magic squares together. Creating magic squares sounds hard, but perhaps not with a bit of algorithmic magic.

The magical effect

For this trick you ask a volunteer to pick a number. Instantly, on hearing it, you write out a personal four by four magic square for them based on that number. When finished the square contents adds to their chosen number in all the usual ways magic squares do. An impressive feat of superhuman mathematical skills that you can learn to do most instantly.

Making the magic

To perform this trick, first get your audience member to select a large two digit number. It helps if it is a reasonably large number, greater than 20, as you’re going to need to subtract 20 from it in a moment. Once you have the number you need to do a bit of mental arithmetic. You need an algorithm – a sequence of steps – to follow that given that number guarantees that you will get a correct magic square.

For our example, we will suppose the number you are given is 45, though it works with any number.

Let’s call the chosen number N (in our example: N is 45). You are going to calculate the following four numbers from it: N-21, N-20, N-19 and N-18, then put them in to a special, precomputed magic square pattern.

The magic algorithm

Sums like that aren’t too hard, but as you’ve got to do all this in your head, you need a special algorithm that makes it really easy. So here is an easy algorithm for working out those numbers.

This four by four magic square contains the calculations needed to install the numbers in the correct positions so that the magic square will work with any large two digit number
Image by CS4FN.
  1. Start by working out N – 20. Subtracting 20 is quite easy. For our example number of 45, that is 25. This is our ‘ROOT’ value that we will build the rest from.
  2. N-19. Just add 1 to the root value (ROOT + 1). So 25 + 1 gives 26 for our example.
  3. N-18. Add 2 to the root value (ROOT + 2). So 25 + 2 gives 27.
  4. N-21. Subtract 1 from the root value (ROOT – 1). So 25 – 1 gives 24.
  5. Having worked out the 4 numbers created form the original chosen number, N, you need to stick them in the right place in a blank magic square, along with some other numbers you need to remember. It is the pattern you use to build your magic square from. It looks like the one to the right. To make this step easy, write this pattern on the piece of paper you write the final square on. Write the numbers in light pencil, over-writing the pencil as you do the trick so no-one knows at the end what you were doing.

A square grid of numbers like this is an example of what computer scientists call a data structure: a way to store data elements that makes it easy to do something useful: in this case making your friends think you are a maths superhero.

When you perform this trick, fill in the numbers in the 4 by 4 grid in a random, haphazard way, making it look like you are doing lots of complicated calculations quickly in your head.

Finally, to prove to everyone it is a magic square with the right properties, go through each row, column and diagonal, adding them up and writing in the answers around the edge of the square, so that everyone can see it works.

The final magic square for chosen number 45

So, for our example, we would get the following square, where all the rows, columns and diagonals add to our audience selected number of 45.

This four by four magic square is the result of taking the chosen number 45 and performing the sequence of calculations (the algorithm) using it as 'N'.
Image by CS4FN.

Why does it work?

If you look at the preset numbers in each row, column and diagonal of the pattern, they have been carefully chosen in advance to add up to the number being subtracted from N on those lines. Try it! Along the top row 1 + 12 + 7 = 20. Down the right side 11 + 5 + 4 = 20.

Do it again?

Of course you shouldn’t do it twice with the same people as they might spot the pattern of all the common numbers…unless, now you know the secret, perhaps you can work out your own versions each with a slightly different root number, calculated first and so a different template written lightly on different pieces of paper.

Peter McOwan and Paul Curzon, Queen Mary University of London

More on …

Debugging your sandwich maker

A peanut butter and jelly sandwich, made with Skippy peanut butter and Welch’s grape jelly on white bread by Evan-Amos, under a CC0 licence via Wikimedia

Do you know how to make a sandwich? More importantly do you know how to write down a set of precise, detailed instructions that could tell someone else how to make a sandwich? I’m sure you think you could, but after watching this video below you might feel less sure.

This video has been used in some classrooms as a fun way of talking about how precise and correct an algorithm needs to be in order to run a program correctly. Josh, the dad in the video, asks his children (Johnna and Evan) to write out some instructions to make a peanut butter and jelly (jam) sandwich. They all speak the same language (English) so the instructions don’t have to be converted into machine language for the computer (dad) to run the program and make the sandwich, but as you’ll soon see, it’s harder than his children think. They do get there in the end though… kind of.

See if you can write your own set of instructions and then get someone to follow them exactly.

Incidentally, the image used to illustrate this article has been “…assessed under the valued image criteria and is considered the most valued image on Commons within the scope: peanut butter and jelly sandwiches. You can see its nomination here.” Only the best peanut pics on this site! You can see all the images that didn’t win here.

Watch …

Part of a series of ‘whimsical fun in computing’ to celebrate April Fool’s (all month long!).

Find out about some of the rather surprising things computer scientists have got up to when they're in a playful mood.

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Maria Cunitz: astronomer and algorithmic thinker

When did women first contribute to the subject we now call Computer Science: developing useful algorithms, for example? Perhaps you would guess Ada Lovelace in the Victorian era so the mid 1800s? She corrected one of Charles Babbage’s algorithms for the computer he was trying to build. Think earlier. Two centuries or so earlier! Maria Cunitz improved an algorithm published by the astronomer Kepler and then applied it to create a work more accurate than his.

A stary sky with the milky way
Image by Rene Tittmann from Pixabay

Very few women, until the 20th century were given the opportunities to take part in any kind of academic study. They did not get enough education, and even if they did were not generally welcome in the circles of mathematicians and natural philosophers. Maria, who was Polish from an educated family of doctors and scientists, was tutored and supported in becoming a polymath with an interest in lots of subjects from history to mathematics. Her husband was a doctor who also was interested in astronomy something that became a shared passion with him teaching her the extra maths she needed. They lived at the time of the 30 years war that was waged across most of Europe. It was a spat turned into a war about religion between catholic and protestant countries. In Poland, where they lived, it was not safe to be a protestant. The couple had a choice of convert or flee, so left their home taking sanctuary in a convent.

This actually gave Cunitz a chance to pursue an astronomical ambition based on the work of Johannes Kepler. Kepler was famous for his three Laws of Planetary Motion published in the early 1600s on how the planets orbit the sun. It was based on the new understanding from Copernicus that the planets rotated around the sun and so the Earth was not the centre of everything. Kepler’s work gave a new way to compute the positions of the planets,

Cunitz had a detailed understanding of Kepler’s work and of the mathematics behind it, She therefore spent her time in the convent computing tables that gave the positions of all the planets in the sky. This was based on a particular work of Kepler called the Rudolphine Tables. It was one of his great achievements stemming from his planetary laws. Such astronomical tables became vital for navigating ships at sea, as the planetary positions could be used to determine longitude. However, at the time, the main use was for astrology as casting someone’s horoscope required knowledge of the precise positions of the planets. In creating the tables, Cunitz was acting as an early human computer, following an algorithm to compute the table entries. It involved her doing a vast amount of detailed calculation.

Kepler himself spent years creating his version of the tables. When asked to hurry up and complete the work he said: “I beseech thee, my friends, do not sentence me entirely to the treadmill of mathematical computations…” He couldn’t face the role of being a human computer! And yet a whole series of women who came after him dedicated their lives to doing exactly that, each pushing forward astronomy as a result. Maria herself took on the specific task he had been reluctant to complete in working out tables of planetary positions.

Kepler had published his algorithm for computing the tables along with the tables. Following his algorithm though was time consuming and difficult, making errors likely. Maria realised it could be improved upon, making it simpler to do the calculations for the tables and making it more likely they were correct. In particular, Kepler was using logarithms for the calculations. but she realised that was not necessary. Sacrificing some accuracy in the results for the sake of the avoidance of larger errors, the version she followed was even simpler. By the use of algorithmic thinking she had avoided at least some of the chore that Kepler himself had dreaded. This is exactly the kind of thing good programmers do today, improving the algorithms behind their programs so the programs are more efficient. The result was that Maria produced a set of tables that was more accurate than Kepler’s, and in fact the most accurate set of planetary tables ever produced to that point in time. She published them privately as a book “Urania Propitia’ in 1650. Having a mastery of languages as well as maths and science, she, uniquely, wrote it in both German and Latin.

Women do not figure greatly in the early history of science and maths just because societal restrictions, prejudices and stereotypes meant few were given the chance. Those who were like Maria Cunitz, showed their contributions could be amazing. It just took the right education, opportunities, and a lot of dedication. That applies to modern computer science too, and as the modern computer scientist, Karen Spärck Jones, responsible for the algorithm behind search engines said: “Computing is too important to be left to men.”

– Paul Curzon, Queen Mary University of London

More on …

Magazines …

Front cover of CS4FN issue 29 - Diversity in Computing

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page and talk are funded by EPSRC on research agreement EP/W033615/1.

Cooking up computer style

Spaghetti in a jar looking down from above so looks like a ball of spikes surrounded by ingredients below
Pasta image by Gentina Bintang Danurendra from Pixabay

Using clever computer vision techniques it’s now possible for your ingredients to tell you how they should be cooked in a kitchen. The system uses cameras and projectors to first recognise the ingredients on the chopping board, for example the size, shape and species of fish you are using. Then the system projects a cutting line on the fish to show you how to prepare it, and a speech bubble telling you how long it should be cooked for and suggesting ways it can be served. In the future these cooking support systems could take some of the strain from mealtimes. At least it will help to make us all better cooks, and perhaps with an added pinch of artificial intelligence we can all become more like Jamie Oliver.

Jo Brodie, Queen Mary University of London

More on …

  • A recipe for programming
    • Learn the recipe for Hummus and Tomato Pasta, and find out about program structure, commenting, variable storage and assignments. A bit of ‘back to school’ around the dinner table (or perhaps combine Computer Science classes with Food and Nutrition!).

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Coordinate conundrum puzzles and vector graphics

A computer with arms doing a coordinate conundrum on a pad of paper

Image by Samson Vlad from Pixabay modified by CS4FN

One way computers store images is as a set of points (as coordinates) that make up lines and shapes. This is the basis for the kind of computer graphics called Vector Graphics. You can explore the idea by doing coordinate conundrum puzzles. A coordinate conundrum is just a Vector Graphics Image to be drawn on paper.They are join-the-dot puzzles based on the idea. Can you recreate the original drawing?

Recreate a drawing from coordinates

Points on a grid can be represented by pairs of numbers called coordinates. The first, x coordinate, says how far to go along horizontally. The second, y coordinate, says how far to go up, vertically. The numbers along the axes (along the bottom and up the side) of the grid give the distance in that direction. Draw the point at the place you end up at! So for example the coordinate (4,5) means go right from the origin 4 and up 5 and plot the point there.

Grid showing point (4,5) as 4 right and 5 up.
Image by CS4FN

You can join any two coordinates with lines. If a series of lines join back to the original one then it make a shape (a polygon), which can be coloured in. For example, if we plot the points (4,5), (7,7 and (8,4) drawing lines between them and back to (4,5) we make a triangle.

A triangle marked out in coordinates
Image by CS4FN

From 4 points we could define a square, rectangle or more general quadrilateral shape and so on.

So from a set of instructions telling you where to plot points, you can create a picture out of all the shapes and lines that make up the picture, giving colours for the lines or shapes.

This (and so these puzzles) is the basis of how programs in the language SVG (Scalable Vector Graphics) work to store a drawing as the instructions needed to recreate it. Drawing programs often store illustrations that the artists using them draw as an SVG program.

How to solve them

Each picture is made of shapes, each given by a colour and a list of the coordinates of its vertices (corners). For each shape: 

1. Plot the list of (x,y) coordinates on the grid as dots. 

2. Join the dots (which start and end at the same place) to make the shape. 

3. Colour the shape you have made with the colour at the start of the list. 

So, for example, if the first instruction starts: red (5,24) … that means plot the point 5 along and 24 up. It starts a new shape, coloured red, that ends at the same point.

If the series of points do not join back to the start then they represent coloured lines rather than a coloured shape,

Example: Semaphore flag

Blank 10x10 grid
Image by CS4FN

Here is a simple example to draw a red and yellow semaphore flag, given the shapes:

  • red (0,10) (10,10) (10,0) and back to (0,10)
  • yellow (0,10) (10,0) (0,0) and back to (0,10)

From this we can draw the picture.

Top right triangle now coloured red with (0,10), (10,10) and (10,0) plotted, joined by lines and the shape coloured.
Image by CS4FN

First we plot the points given for the red shape (a triangle), join the dots and colour it in.

  • red (0,10) (10,10) (10,0) and back to (0,10)
Bottom rightt triangle now coloured yellow with (0,10), (10,0) and (0,0) plotted, joined by lines and the shape coloured.
Image by CS4FN

Then we plot the points given for the yellow shape (another triangle), join the dots and colour it in.

  • yellow (0,10) (10,0) (0,0) and back to (0,10)

Do some puzzles yourself

Try the coordinate conundrum puzzles on our puzzle page either by printing off the puzzle sheet or drawing on squared paper. Then read on to find out a little more the advantages of vector graphics.

From straight lines to curves

In these puzzles we have only used straight lines between points, but we could also include commands to create circles and curved lines between points based on the mathematical equation for the curve. SVG, the vector graphic programming language, has instructions for a variety of more complex kinds of lines and shapes like that.

Advantages and disadvantages of Vector Graphics

Recording images in this way as points, lines and shapes has several advantages over storing images as pixels:

  • we generally need far less space to store the image as we do not need to store a colour for thousands or even millions of pixels;
  • the images are mathematically accurate – a line is represented as a perfect straight line not a pixelated (staircase-like) line;
  • the images are scalable, meaning you can increase the size of an image, zooming in just by multiplying all the numbers involved by a scale factor (which is just a number giving the magnification you want). The resulting image is still mathematically perfect with straight lines still straight lines, for example, just bigger. For example, suppose we want to make a semaphore flag twice the size of our original. We just multiply all points by 2, for example giving red (0,20) (20,20) (20,0) and back to (0,20); yellow (0,20) (20,0) (0,0) and back to (0,20) and it gives an identical picture, just bigger. (Try plotting it and see!)

Disadvantages are:

  • Vector graphics are not a good way to represent photographs – digital cameras record the light at lots of points corresponding to pixels so naturally are stored as pixels (numbers that give the colour in that small square of the image). Trying to convert a photo to a vector image would be hard (needing algorithms to recognise shapes, for example). It would be a less natural and less accurate way of doing so.
  • With computer memory cheap, the advantages of using less storage are less important than they once were.

SVG: a graphics programming language

The programming language SVG records drawings in this way as instructions to draw shapes and lines based on points. It has some difference to our instructions though. For example the y-axis coordinates start at the top and work down. The principles are the same though, it is only the detail that differs.

Paul Curzon, Queen Mary University of London

More on …

Magazines …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

From Egyptian Survey puzzles to computational thinking

One way to use logical thinking is to deduce new facts but then turn them into IF-THEN rules. They tell us an action to do IF something is true. For example:  IF both cards are the same THEN shout SNAP! Once we have IF-THEN rules we can use them as the basis of a program. We can see how this works, and how it involves various computational thinking skills with a simple logical thinking puzzle.

An Egyptian Survey puzzle 

Image by CS4FN

Old records show that this area of the desert contains the tombs of 3 scribes (a large tomb covering 3 squares), 1 artisan (medium, 2 squares) and 1 merchant (small, 1 square).

A survey has gathered information of where the tombs could be. Each number tells you how many squares are part of a tomb in that row or column. 

Tombs are not adjacent (horizontally, vertically or diagonally).

Can you work out where all the tombs are without further digging?

Solving Egyptian Survey puzzles

The instructions of the puzzle give us some simple facts such as that the number at the end of the row tells us the number of squares in that row holding tombs.  On its own that does not tell us how to solve the puzzle. However, thinking logically about it we can draw simple logical conclusions so deduce new facts. For example, it is fairly simple to deduce the fact:

the number for a row being 0 IMPLIES there are no tombs in that row.

If we know there are no tombs in a row then we can mark each square of the row as empty. If we use X to mean nothing is in that square, then we can turn that deduced fact into an action. It means that we can do the following when trying to solve the puzzle:

IF the number on a row is 0 
THEN put an X in all the squares of that row.

With that rule we can start to solve the puzzle just by following the rule. Find a row numbered 0 and put Xs there. We can create a similar rule for columns. Applying both these rules to our puzzle we get:

Image by CS4FN

Can you work out more rules before reading on?

Rules, rules, rules

What happens if the number of a row is more than 0? Knowing the number alone doesn’t help us much. We need to combine it with other information. The top row of the puzzle has the number 4, for example, but one of the squares already has a cross in it. That means the remaining 4 squares all must have tombs, which we will mark T. We can turn that into a rule:

IF the number for a row is 4 AND there are 4 empty squares in that row and an X
THEN put a T in all the empty squares of that row.

We can make similar rules for each number 1 to 4. We can then create similar rules for columns. Applying them once each to our puzzle gives us:

Image by CS4FN

We could also make a more general version of this rule 

IF the number for a row is <n> AND there are only <n> empty squares in that row 
THEN put a T in all the empty squares of that row.

This is what computer scientists call generalisation: a part of computational thinking. Instead of having lots of rules (or lines of code) for lots of similar situations, we create one simple but general one that covers all the cases. We can of course apply rules more than once, so as you probably noticed we can apply our row rule once more. In effect our rules live inside a loop and we keep trying them in sequence for as long as we find a rule that makes a difference.

Image by CS4FN

Now one of the rows has the number 1, but we have already marked a tomb in a square of that row. That gives us another rule.

IF the number for a row is 1 AND there is already 1 tomb marked in that row
THEN put an X in all the empty squares of that row.

This gives us:

Image by CS4FN

Similar rules apply for other numbers so we could also make a general version of this rule too.

IF the number for a row is <n> AND there are already <n> tombs marked in that row
THEN put an X in all the empty squares of that row.

Now, applying a column version of the last general rule and we can mark an X in the last square for column with 2 tomb squares.

Image by CS4FN

We need one last rule for this puzzle:

IF the number for a row is <n> AND the number of spaces + the number of 0s is <n>
THEN put a T in all the empty squares of that row.

This is actually an even more general version of our second rule (it is the case where the number of Ts is 0, so could replace that rule with this new one.

 Applying it finally solves the puzzle:

Image by CS4FN

If we put our rules together then they become the basis of an algorithm (so program) for solving the puzzles and in creating them from deduced facts we are doing algorithmic thinking. IF-THEN instructions along with sequencing and loops are the basis of all programs. Here we create a sequence of the rules to try in order and put them inside a loop so that we keep trying them until none apply or we have solved the puzzle. There is a style of programming where all a program is is a series of IF-THEN rules – with looping happening implicitly.

Algorithms are just rules to follow that guarantee a result (here solving the puzzle). It is only an algorithm if it guarantees to always work. To solve any (solvable) Egyptian Survey puzzle like this we would need yet more rules: we would need more more rules for it to be an algorithm for solving all puzzles. Making sure algorithms cover all possibilities is one of the harder parts of algorithmic thinking – bugs in programs are often there because the programmer didn’t manage to cover every possibility. In our case we could write a program based on our limited rules. We would just need to include an extra rule that quits (admitting defeat and saying that the program cannot solve the puzzle) if no rule applies.

Perhaps you can work out all the rules (so an algorithm) needed to solve any of these puzzles! All you need are the instructions for the game, some logical thinking to deduce new facts, some algorithmic thinking to turn them into rules, and an ability to generalise so you have a small number of rules … computational thinking skills in fact.

– Paul Curzon, Queen Mary University of London

More on …

Magazines …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Exploring mazes, inventing algorithms (part I) 

by Paul Curzon, Queen Mary University of London

A maze with mouse searching for cheese.
Image by CS4FN

Computer science research in part involves inventing new algorithms or improving new ones. But what does that mean. Let’s explore some mazes to explore algorithms.

What does computer science research involve? It is very varied: from interviewing people to find out what the real problems that need solving in their lives or jobs are; to running experiments to find out what works and what doesn’t; to writing programs to solve problems.

Improving algorithms

A core part of much research is coming up with new and better algorithms that solve particular problems. The kind of algorithm could be anything from a new more secure cryptographic protocol, or a better way to rank the results of a search engine, to a new more effective machine learning algorithm that is less likely to make things up, or perhaps can better explain how it came to its conclusions.

What does it mean to come up with a better algorithm though? Once a problem is solved, isn’t it solved? Let’s explore a simple problem to see. Let’s explore mazes. Solve the simple maze puzzle above before you go on. Find a route that gets the mouse to the cheese.

Wandering around mazes, finding algorithms

If you’ve ever been in a hedge maze in the garden of some stately home, or a corn field maze, the chances are you just dived in and wandered rather aimlessly. Perhaps you tried to remember which way you went at each junction, to avoid going down the same dead-ends more than once. How about solving the paper version of a maze puzzle like the one above? Now perhaps you looked ahead to spot dead-ends to avoid tracing wrong paths with your pencil.

Probably what you are doing is at least a little random. You could, in theory at least, end up going back over the same paths, never taking the right one and and never getting to the middle. Could we come up with an algorithm that guarantees to solve mazes? To be an algorithm it would need to guarantee you ended up finding a path to the centre of the maze if you followed the steps of the algorithm precisely. It should also work for any maze, or at least all mazes of a particular kind. Ideally, the algorithm gives you a path that can then be followed by anyone without them having to run the algorithm themselves. They can just follow the path generated by the algorithm for that maze.

Wall-following

In fact lots of maze algorithms have been invented. Perhaps the one most people have heard of, if they know of any maze algorithm, is called Wall-following. It is very simple to do, You just pick a wall at the entrance either to the left or right and then follow it, If in a garden maze, keep your hand on the hedge as you walk round. If doing a paper puzzle, draw the path sticking to the chosen wall. Try it on the following simple maze.

A simple maze with mouse and cheese.
Image by CS4FN

Simply connected

The wall-following algorithm will guarantee to get you to the centre of the maze, and back out again too, but only as long as the maze is what is called simply connected. That just means the maze is constructed from a single hedge (or one unbroken drawn line) not a series of unconnected hedges. If you look at both examples above you will see I created them by just drawing a single wiggly line.

If a maze is simply connected then it cannot have looping paths, so no going round in circles for ever. It will also only have one entrance/exit. That shows the first aspect of inventing algorithms that is important. They often only work for some situations, not all. You must be sure you know what situations they do and don’t work.

Often the earliest algorithms invented to solve a problem are like wall-following: they only work for simple situations. Other people then come along and find new algorithms that can cover more problems (here more mazes). Can you tweak the wall-following maze algorithm to work even if there are multiple exits from the maze, for example? As it stands our algorithm could just take you from the entrance straight out of another exit without exploring much of the maze at all! See the end for one simple way to tweak the algorithm. What if there are paths that take you round in circles? Can you come up with an algorithm to deal with that?

Some times the improvements invented just involve tweaking an existing algorithm as with dealing with multiple exits in a maze. Some times a whole new algorithm is needed.

Faster, higher, stronger?

Even for a simple constrained version of the problem, like simply connected mazes, people can invent better algorithms. What does better mean for a maze? Well one way you might have a better algorithm is if it is faster in coming up with a solution. Another is that the solution it comes up with is faster. For a maze that means a shorter (ideally the shortest) path to the centre. Wall following may get you in to the centre (and out again) but you probably will have discovered a very long path that takes you in and out of lots of dead-ends needlessly. You do find a path to the centre, but it may be a very long path. Can you come up with an algorithm that finds shorter paths?

We will explore an algorithm that does next.

More to come…

Some solutions

The result of wall following on our simple maze

A route for the mouse to follow that takes it to the cheese.
Image by CS4FN

One way to deal with multiple exits

To deal with a maze that has multiple exits, so multiple breaks in the outer wall, tweak the wall-following algorithm as follows. First mark the exit you use to enter the maze, so you know when you return to it. If you come to any other exit then pretend there is a gate there and keep following the wall as though it were unbroken and there were no exit.

More on …

Magazines …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos