Even the dolphins use pocket switched networks!

(from the archive)

Dolphin leaping in waves off Panama City
Image by Heather Williams from Pixabay

Email, texting, Instant Messaging, Instant response…one of the things about modern telecoms is that they fuel our desire to “talk” to people anytime, anywhere, instantly. The old kind of mail is dismissed as “snail mail”. A slow network is a frustrating network. So why would anyone be remotely interested in doing research into slow networks? Surprisingly, slow networks deserve study. Professor Jon Crowcroft of the University of Cambridge and his team were early researchers of this area, and this kind of network could be the network of the future. The idea is already being used by the dolphins (not so surprising I suppose given according to Douglas Adams’ “The HitchHiker’s Guide to the Galaxy” they are the second most intelligent species on Earth…after the mice).

From node to node

Traditional networks rely on having lots of fixed network “nodes” with lots of fast links between them. These network nodes are just the computers that pass on the messages from one to the other until the messages reach their destinations. If one computer in the network fails, it doesn’t matter too much because there are enough connections for the messages to be sent a different way.

There are some situations where it is impractical to set up a network like this though: in outer space for example. The distances are so far that messages will take a long time – even light can only go so fast! Places like the Arctic Circle are another problem: vast areas with few people. Similarly, it’s a problem under the sea. Signals don’t carry very well through water so messages, if they arrive at all, can be muddled. After major disasters like Hurricane Katrina or a Tsunami there are also likely to be problems.

It is because of situations like these that computer scientists started thinking about “DNTs”. The acronym can mean several similar things: Delay Tolerant Networks (like in space the network needs to cope with everything being slow), Disruption Tolerant Networks (like in the deep sea where the links may come and go) or Disaster tolerant networks (like a Tsunami where lots of the network goes down at once). To design networks that work well in these situations you need to think in a different way. When you also take into account that computers have gone mobile – they no longer just sit on desks but are in our pockets or handbags, this leads to the idea of a “ferrying network” or as Jon Crowcroft calls them: “Pocket Switched Network”. The idea is to use the moving pocket computers to make up a completely new kind of network, where some of the time messages move around because the computers carrying them are moving themselves, not because the message itself is moving. As they move around they pass near other computers and can exchange messages, carrying a message on for someone else until it is near another computer it can jump to.

From Skidoo to you

A skiddo with driver standing next to it
Image by raul olave from Pixabay

How might such networks be useful in reality? Well one was set up for the reindeer farmers in the Arctic Circle. They roam vast icy wastelands on skidoos, following their reindeer. They are very isolated. There are no cell phone masts or internet nodes and for long periods they do not meet other people at all. The area is also too large to set up a traditional network cheaply. How could they communicate with others?

They set up a form of pocket switched network. Each carried a laptop on their skidoo. A series of computers were also set up sitting in tarns spread around the icy landscape. When the reindeer farmers using the network want a service, like delivering a message, the laptop stores the request until they pass within range of one of the other computers perhaps on someone else’s skidoo. The computer then automatically passes the message on. The new laptop takes the message with it and might later pass a tarn, where the message hops again then waits till someone else passes by heading in the right direction. Eventually it makes a hop to a computer that passes within range of a network point connected to the Internet. It may take a while but the mail eventually gets through – and much faster than waiting for the farmer to be back in net contact directly.

Chatting with Dolphins

Even the dolphins got in on the act. US scientists wanted to monitor coastal water quality. They hit on the idea of strapping sensors onto dolphins that measure the quality wherever they go. Only problem is dolphins spend a lot of time in deep ocean where the results can’t easily be sent back. The solution? Give them a normal (well dolphin adapted) cell phone. Their phone stores the results until it is in range of their service provider off the coast. By putting a receiver in the bays the dolphins return to most frequently, they can call home to pass on the data whenever there.

The researchers encountered an unexpected problem though. The dolphin’s memory cards kept inexplicably filling up. Eventually they realised this was because the dolphins kept taking trips across the Atlantic where they came in range of the European cell networks. The European telecom companies, being a friendly bunch, sent lots of text messages welcoming these newly appeared phones to their network. The memory cards were being clogged up with “Hellos”!

The Cambridge team investigated how similar networks might best be set up and used for people on the move, even in busy urban environments. To this end they designed a pocket switched network called Haggle. Using networks like Haggle, it is possible to have peer-to-peer style networks that side-step the commercial networks. If enough people join in then messages can just hop from phone to phone, using bluetooth links say, as they passed near each other. They might eventually get to the destination without using any long distance carriers at all.

The more the merrier

With a normal network, as more people join the network it clogs up as they all try to use the same links to send messages at the same time. Some fundamental theoretical results have shown that with a pocket switched network, the capacity of the network can actually go up as more people join – because of the way the movement of the people constantly make new links.

Pocket switched networks are a bit like gases – the nodes of the network are like gas molecules constantly moving around. A traditional network is like a solid – all the molecules, and so nodes, are stationary. As more people join a gaseous network it becomes more like a liquid, with nodes still moving but bumping into other nodes more often. The Cambridge team explored the benefits of networks that can automatically adapt in this way to fit the circumstances: making phase transitions just like water boiling or freezing.

One of the important things to understand to design such a network is how people pass others during a typical day. Are all people the same when it comes to how many people they meet in a day? Or are there some people that are much more valuable as carriers of messages. If so those are the people the messages need to get to to get to the destination the fastest!

To get some hard data Jon and his students handed out phones. In one study a student handed out adapted phones at random on a Hong Kong street, asking that they be returned a fixed time later. The phones recorded how often they “met” each other before being returned. In another similar experiment the phones were given out to a large number of Cambridge students to track their interactions. This and other research shows that to make a pocket switched network work well, there are some special people you need to get the messages to! Some people meet the same people over and over, and very few others. They are “cliquey” people. Other more “special” people regularly cross between cliques – the ideal people to take messages across groups. Social Anthropology results suggest there are also some unusual people who rather than just networking with a few people, have thousands of contacts. Again those people would become important message carriers.

So the dolphins may have been the “early adopters” of pocket switched networks but humans may follow. If we were to fully adopt them it could completely change the way the telecom industry works…and if we (or the dolphins) ever do decide to head en-mass for the far reaches of the solar system, pocket switched networks like Haggle will really come into their own.

– Paul Curzon, QMUL, based on a talk given by Jon Crowcroft at Queen Mary in Jan 2007.

More on …

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

This blog is funded through EPSRC grant EP/W033615/1.

NASA’s interstellar probe Voyager 1 went silent until computer scientists transmitted a fix that had to travel 15 billion miles!

by Jo Brodie, Queen Mary University of London

In 1977 NASA scientists at the Jet Propulsion Laboratory launched the interstellar probe Voyager 1 into space – and it just keeps going. It has now travelled 15 BILLION miles (24 billion kilometres), which is the furthest any human-made thing has ever travelled from Earth. It communicates with us here on Earth via radiowaves which can easily cross that massive distance between us. But even travelling at the speed* of light (all radiowaves travel at that speed) each radio transmission takes 22.5 hours, so if NASA scientists send a command they have to wait nearly two days for a response. (The Sun is ‘only’ 93 million miles away from Earth and its light takes about 8 minutes to reach us.)

FDS – The Flight Data System

The Voyager 1 probe has sensors to detect things like temperature or changes in magnetic fields, a camera to take pictures and a transmitter to send all this data back to the scientists on Earth. One of its three onboard computers (the Flight Data System, or FDS) takes that data, packages it up and transmits it as a stream of 1s and 0s to the waiting scientists back home who decode it. Voyager 1 is where it is because NASA wanted to send a probe out beyond the limits of our Solar System, into ‘interstellar space’ far away from the influence of our Sun to see what the environment is like there. It regularly sends back data updates which include information about its own health (how well its batteries are doing etc) along with the scientific data, packaged together into that radio transmission. NASA can also send up commands to its onboard computers too. Computers that were built in 1977!

The pale blue dot

‘The Pale Blue Dot’. In the thicker apricot-coloured band on the right you might be able to see
a tiny dot about halfway down. That’s the Earth! Full details of this famous 1990 photo here.

Although its camera is no longer working its most famous photograph is this one, the Pale Blue Dot, a snapshot of every single person alive on the 14th of February 1990. However as Voyager 1 was 6 billion miles from home by then when it looked back at the Earth to take that photograph you might have some difficulty in spotting anyone! But they’re somewhere in there, inside that single pixel (actually less than a pixel!) which is our home.

As Voyager 1 moved further and further away from our own planet, visiting Jupiter and Saturn before travelling to our outer Solar System and then beyond, the probe continued to send data and receive commands from Earth. 

The messages stopped making sense

All was going well, with the scientists and Voyager 1 ‘talking’ to one another, until November 2023 when the binary 1s and 0s it normally transmitted no longer had any meaningful pattern to them, it was gibberish. The scientists knew Voyager 1 was still ‘alive’ as it was able to send that signal but they didn’t know why its signal no longer made any sense. Given that the probe is nearly 50 years old and operating in a pretty harsh environment people wondered if that was the natural end of the project, but they were determined to try and re-establish normal contact with the probe if they could. 

Searching for a solution

They pored over almost-50 year old paper instruction manuals and blueprints to try and work out what was wrong and it seemed that the problem lay in the FDS. Any scientific data being collected was not being correctly stored in the ‘parcel’ that was transmitted back to Earth, and so was lost – Voyager 1 was sending empty boxes. At that distance it’s too far to send an engineer up to switch it off and on again so instead they sent a command to try and restart things. The next message from Voyager 1 was a different string of 1s and 0s. Not quite the normal data they were hoping for, but also not entirely gibberish. A NASA scientist decoded it and found that Voyager 1 had sent a readout of the FDS’ memory. That told them where the problem was and that a damaged chip meant that part of its memory couldn’t be properly accessed. They had to move the memory from the damaged chip.

That’s easier said than done. There’s not much available space as the computers can only store 68 kilobytes of data in total (absolutely tiny compared to today’s computers and devices). There wasn’t one single place where NASA scientists could move the memory as a single block, instead they had to break it up into pieces and store it in different places. In order to do that they had to rewrite some of the code so that each separated piece contained information about how to find the next piece. Imagine if a library didn’t keep a record of where each book was, it would make it very hard to find and read the sequel! 

Earlier this year NASA sent up a new command to Voyager 1, giving it instructions on how to move a portion of its memory from the damaged area to its new home(s) and waited to hear back. Two days later they got a response. It had worked! They were now receiving sensible data from the probe.  

Voyager team celebrates engineering data return, 20 April 2024 (NASA/JPL-Caltech). “Shown are Voyager team members Kareem Badaruddin, Joey Jefferson, Jeff Mellstrom, Nshan Kazaryan, Todd Barber, Dave Cummings, Jennifer Herman, Suzanne Dodd, Armen Arslanian, Lu Yang, Linda Spilker, Bruce Waggoner, Sun Matsumoto, and Jim Donaldson.”

For a while they it was just basic ‘engineering data’ (about the probe’s status) but they knew their method worked and didn’t harm the distant traveller. They also knew they’d need to do a bit more work to get Voyager 1 to move more memory around in order for the probe to start sending back useful scientific data, and…

Success!

… …in May, NASA announced that scientific data from two of Voyager 1’s instruments was finally being sent back to Earth and in June the probe was fully operational. You can follow Voyager 1’s updates on Twitter / X via @NASAVoyager.

Did you know?

Both Voyager 1 and Voyager 2 carry with them a gold-plated record called ‘The Sounds of Earth‘ containing “sounds and images selected to portray the diversity of life and culture on Earth”. Hopefully any aliens encountering it will have a record player (but the Voyager craft do carry a spare needle!) Credit: NASA/JPL

References

Lots of articles helped in the writing of this one and you can download a PDF of them here. Featured image credit showing the Voyager spacecraft: NASA/JPL.

*radiowaves and light are part of the electromagnetic or ‘EM’ spectrum along with microwaves, gamma rays, X-rays, ultraviolet and infra red. All these waves travel at the same speed in a vacuum, the speed of light (300,000,000 metres per second, sometimes written as 3 x 108 m/s or (m s-1)), but the waves differ by their frequency and wavelength.

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

EPSRC supports this blog through research grant EP/W033615/1.

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

Mary Ann Horton and the invention of email attachments

A glowing envelope flying over a grid of envelopes
Image by Divya Gupta from Pixabay

Mary Ann Horton was transitioning to female at the time that she made one of her biggest contributions to our lives with a simple computer science idea with a big impact: a program that allowed binary email attachments.

Now we take the idea of sending each other multimedia files – images, video, sound clips, programs, etc for granted, whether by email or social networks, Back in the 1970s, before even the web had been invented, people were able to communicate by email, but it was all text. Email programs worked on the basis that people were just sending words, or more specifically streams of characters, to each other. An email message was just a long sequence of characters sent over the Internet. Everything in computers is coded as binary: 1s and 0s, but text has a special representation. Each character has its own code of 1s and 0s, that can also be thought of as a binary number, but that can be displayed as the character by programs that process it. Today, computers use a universally accepted code called Unicode, but originally most adopted a standard code called ASCII. All these codes are just allocations of patterns of 1s and 0s to each character. In ASCII, ‘a’ is represented by 1100001 or the number 97, whereas A is 1000001 or number 65, for example. These are only 7 bits long and as computers store data in bytes of 8 bits at a time this means that not all patterns of binary (so representable numbers) correspond to one of the displayable characters that email messages were expected to contain by the programs that processed them.

That is fine if all you have done is used programs like text editors, that output characters so you are guaranteed to be sending printable characters. The problem was other kinds of data whether images or runnable programs, are not stored as sequences of characters. They are more general binary files, meaning the data is long sequences of byte-sized patterns of 1s and 0s and what those 1s and 0s meant depended on the kind of data and representation used. If email programs were given such data to send, pass on or receive, they would reject or more likely mangle it as not corresponding to characters they could display. The files didn’t even have to be non-character formats, as at the time some computer systems used a completely different code for characters. This meant text emails could also be mangled just because they passed through a computer using a different format of character.

Mary Ann realised that this was all too restrictive for what people would be needing computers to do. Email needed to be more flexible. However, she saw that there was a really easy solution. She wrote a program, called uuencode that could take any binary file and convert it to one that was slightly longer but contained only characters. A second program she wrote, called uudecode converted these files of characters back to the original binary file to be saved by the receiving email program exactly it was originally on the source program.

All the uuencode program did was take 3 bytes (24 bits) of the binary file at a time, split them into groups of 6 bits so effectively representing a number from 0 to 63, add 32 to this number so the numbers are now in the range 32 to 95 and those are the numbers so binary patterns of the printable characters that the email programs expected. Each three bytes were now 4 printable characters. These could be added to the text of an email, though with a special start and end sequence included to identify it as something to decode. uudecode just did this conversion backwards, turning each group of 4 characters back into the orginal three bytes of binary.

Email attachments had been born, and ever since communication programs, whether email, chat or social media, have allowed binary files, so multimedia, to be shared in similar ways. By seeing a coming problem, inventing a simple way to solve it and then writing the programs, Mary Ann Horton had made computers far more flexible and useful.

Paul Curzon, Queen Mary University of London

More on …

Related Magazines …

cs4fn issue 14 cover

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

Pac-Man and Games for Girls

In the beginning video games were designed for boys…and then came Pac-Man.

Pac-man eating dots
Image by OpenClipart-Vectors from Pixabay

Before mobile games, game consoles and PC based games, video games first took off in arcades. Arcade games were very big earning 39 billion dollars at their peak in the 1980s. Games were loaded into bespoke coin-operated arcade machines. For a game to do well someone had to buy the machines, whether actual gaming arcades or bars, cafes, colleges, shopping malls, … Then someone had to play them. Originally boys played arcade games the most and so games were targeted at them. Most games had a focus on shooting things: games like asteroids and space invaders or had some link to sports based on the original arcade game Pong. Girls were largely ignored by the designers… But then came Pac-Man. 

Pac-Man, created by a team led by Toru Iwatani,  is a maze game where the player controls the Pac-Man character as it moves around a maze, eating dots while being chased by the ghosts: Blinky, Pinky, Inky, and Clyde. Special power pellets around the maze, when eaten, allow Pac-Man to chase the ghosts for a while instead of being chased.

Pac-Man ultimately made around $19 million dollars in today’s money making it the biggest money making video arcade game of all time. How did it do it? It was the first game that was played by more females than males. It showed that girls would enjoy playing games if only the right kind of games were developed. Suddenly, and rather ironically given its name, there was a reason for the manufacturers to take notice of girls, not just boys.

A Pac-man like ghost
Image by OpenClipart-Vectors from Pixabay

It revolutionised games in many ways, showing the potential of different kinds of features to give it this much broader appeal. Most obviously Pac-Man did this by turning the tide away from shoot-em up space games and sports games to action games where characters were the star of the game, and that was one of its inventor Toru Iwatani’s key aims. To play you control Pac-Man rather than just a gun, blaster, tennis racket or golf club. It paved the way for Donkey Kong, Super Mario, and the rest (so if you love Mario and all his friends, then thank Pac-Man). Ultimately, it forged the path for the whole idea of avatars in games too. 

It was the first game to use power ups where, by collecting certain objects, the character gains extra powers for a short time. The ghosts were also characters controlled by simple AI – they didn’t just behave randomly or follow some fixed algorithm controlling their path, but reacted to what the player does, and each had their own personality in the way they behaved.

Because of its success, maze and character-based adventure games became popular among manufacturers, but more importantly designers became more adventurous and creative about what a video game could be. It was also the first big step towards the long road to women being fully accepted to work in the games industry. Not bad for a character based on a combination of a pizza and the Japanese symbol for “mouth”.

– 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 blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

The invisible dice mystery – a magic trick underpinned by computing and maths

Red dice image by Deniz Avsar from Pixabay

The Ancient Egyptians, Romans and Greeks used dice with various shapes and markings; some even believed they could be used to predict the future. Using just a few invisible dice, which you can easily make at home, you can amaze your friends with a transparent feat of magical prediction.

The presentation

You can’t really predict the future with dice, but you can do some clever magic tricks with them. For this trick first you need some invisible dice, they are easy to make, it’s all in the imagination. You take your empty hand and state to your friend that it contains two invisible dice. Of course it doesn’t, but that’s where the performance come in. You set up the story of ancient ways to predict the future. You can have lots of fun as you hand the ‘dice’ over and get your friend to do some test rolls to check the dice aren’t loaded. On the test rolls ask them what numbers the dice are showing (remember a dice can only show numbers 1 through 6), this gets them used to things. Then on the final throw, tell them to decide what numbers are showing, but not to tell you! You are going to play a game where you use these numbers to create a large ‘mystical’ number.

To start, they choose one of the dice and move it closer to them, remembering the number on this die. You may want to have them whisper the numbers to another friend in case they forget, as that sort of ruins the trick ending!

Next you take two more ‘invisible dice’ from your pocket; these will be your dice. You roll them a bit, giving random answers and then finally say that they have come up as a 5 and a 5. Push one of the 5s next to the dice your friend selected, and tell them to secretly add these numbers together, i.e. their number plus 5. Then push your second 5 over and suggest, to make it even harder, to multiply their current number by 5+5 (i.e. 10 – that’s a nice easy multiplication to do) and remember that new number. Then finally turn attention to your friend’s remaining unused die, and get them to add that last number to give a grand total. Ask them now to tell you that grand total. Almost instantly you can predict exactly the unspoken numbers on each of their two invisible dice. If they ask how it you did it, say it was easy – they left the dice in plain sight on the table. You just needed to look at them.

The computing behind

This trick works by hiding some simple algebra in the presentation. You have no idea what two numbers your friend has chosen, but let’s call the number on the die they select A and the other number B. If we call the running total X then as the trick progresses the following happens: to begin with X=0, but then we add 5 to their secret number A, so X= A+5. We then get the volunteer to multiply this total by 5+5 (i.e. 10) so now X=10*(A+5). Then we finally add the second secret number B to give X=10(A+5)+B. If we expand this out, X= 10A+50+B. We know that A and B will be in the range 1-6 so this means that when your friend announces the grand total all you need to do is subtract 50 from that number. The number left (10*A+B) means that the value in the 10s column is the number A and the units column is B, and we can announce these out loud. For example if A=2 and B=4, we have the grand total as 10(2+5)+4 = 74, and 74 – 50= is 24, so A is 2, and B is 4.

In what are called procedural computer languages this idea of having a running total that changes as we go through well-defined steps in a computer program is a key element. The running total X is called a variable, to start in the trick, as in a program, we need to initialise this variable, that is we need to know what it is right at the start, in this case X=0. At each stage of the trick (program) we do something to change the ‘state’ of this variable X, ie there are rules to decide what it changes to and when, like adding 5 to the first secret number changes X from 0 to X=(A+5). A here isn’t a variable because your friend knows exactly what it is, A is 2 in the example above, and it won’t change at any time during the trick so it’s called a constant (even if we as the magician don’t know what that constant is). When the final value of the variable X is announced, we can use the algebra of the trick to recover the two constants A and B.

Other ways to do the trick

Of course there are other ways you could perform the trick using different ways to combine the numbers, as long as you end up with A being multiplied by 10 and B just being added. But you want to hide that fact as much as possible. For example you could use three ‘invisible dice’ yourself showing 5, 2 and 5 and go for 5*(A*2+5) + B if you feel confident your friend can quickly multiply by 5. Then you just need to subtract 25 from their grand total (10A+25+B), and you have their numbers. The secret here is to play with the presentation to get one that suits you and your audience, while not putting too much of a mental strain on you or your friend to have to do difficult maths in their head as they calculate the state changes of that ever-growing variable X.

Paul Curzon, Queen Mary University of London

More on …

Related Magazine …

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

T. V. Raman and his virtual guide dogs

Guide dog silhouette with binary superimposed
Image by PC modifying dog from Clker-Free-Vector-Images from Pixabay

It’s 1989, a year with lots of milestones in Computer Science. In March, Tim Berners-Lee puts down in writing the idea of an “information management system”, later to become the world wide web. In July, Nintendo releases the Game Boy in North America selling 118 million units worldwide over its 14-year production.

Come autumn, a 24-year-old arrives in Ithaca, US, home of Cornell University. He would be able to feel the cool September air as it blows off Cayuga Lake, smell the aromas from Ithaca’s 190 species of trees, and listen to a range of genres in the city’s live music scene. However,, he couldn’t take in the natural beauty of the city in its entirety as he started his PhD … because he was blind. That did not stop him going on to have a gigantic impact on  the lives of blind and partially sighted people worldwide.

T. V. Raman was born in Pune, India, in 1965. He had been partially sighted from birth, but at the age of 14 he became blind due to a disease called glaucoma. Throughout his life, however, he has not let this stop him.

While he was partially sighted, he was able to read and write – but as his sight worsened, and with the help of his brother, mentors, and aides, he was still able to continue learning from textbooks, and solve problems which were read to him. At the height of its popularity, in the early 1980s, he also learned how to solve a specially customised Rubik’s cube, and could do so in about 30 seconds.

Raman soon developed an interest in mathematics, and around 1983 started studying for a Maths degree at the University of Pune. On finishing in 1987, he studied for a Masters degree at the Indian Institute of Technology Bombay, this time in Computer Science and Maths. It was with the help of student volunteers he was able to learn from textbooks and assistance with programming was provided by an able volunteer. 

Today people with no vision often use a screen reader to hear what is on a screen. It not everyone is lucky enough to have so much help as Raman and screen readers play the part of all those human volunteers who helped him. Raman himself played a big part in their development.

Modern screen readers allow you to navigate the screen part-by-part, with important information and content read to you. Many of these systems are built into operating systems, such as the Narrator in Windows (which uses a huge number of keyboard shortcuts), and Google TalkBack for Android devices (where rubbing the screen, vibration, and audio hints are used). These simpler screen readers might already be installed on your system – if so have a go with them!

While Raman was learning programming, such screen readers were still in their infancy. It was only in the 1980s that a team at IBM developed a screen reader for the command-line interface of the IBM DOS (which Raman would later use), and it would be many years before screen readers were available for the much more challenging graphical user interfaces we’re so accustomed to today.

It was at Cornell University where Raman settled on his career-long research interest: accessibility. He originally intended to do an Applied Mathematics PhD, but then discovered the need for ways to use speech technology to read complicated documents, especially those with embedded mathematics. For his dissertation, he therefore developed the Audio System for Technical Readings (ASTER) to solve the problem.

What he realised was that when looking at information visually our eyes are active taking in information from different places but the display is passive. With an audio interface this is reversed with the ear passive and the display actively choosing the order of information presented. This makes it impossible to get a high level view first and then dive into particular detail. This is a big problem when ‘reading’ maths by listening to it. His system solved the problem using audio formatting which allows the listener to browse the structure of information first.

He named this program after his first guide dog, Aster, which he obtained, alongside a talking computer, in early 1990. Both supported him throughout his PhD. For this work, he received the ACM Doctoral Dissertation Award, a prestigious yearly worldwide celebrating the best PhD dissertation in computer science and related fields.

Following on from this work, he developed a program called Emacspeak, an audio desktop, which, unlike a screen reader, takes existing programs and makes them work with audio outputs. It makes use of Emacs, a family of text editors (think notepad, but with lots more features), as well as a programming language called Lisp. Raman has continued to develop Emacspeak ever since and the program is often bundled within Linux operating system installations. Like ASTER, versions of this program are dedicated to his guide dogs.

Following his PhD, Raman worked briefly with Adobe Systems and IBM, but, since 2005, has worked with Google on auditory user interfaces, accessibility, and usability. In 2014, alongside Google colleagues, he published a paper on a new application called JustSpeak, a system for navigating the Android operating system with voice commands. He has also gone back to his roots, integrating mathematical speech into the ChromeVox, the screen reader built into Chromebook devices.

Despite growing up in a time of limited access to computers for blind and visually impaired people, Raman was able, with the help of his brother and student volunteers, to learn how to program, solve a Rubik’s cube, and solve complex maths problems. With early screen readers he was also able to build tools for fellow blind and visually impaired people, and then benefit himself from his own tools to achieve even more.

Guide dogs can transform the lives of blind and partially sighted people by allowing them to do things in the physical world that they otherwise could not do. T. V. Raman’s tools provide a similar transformation in the digital world, changing lives for the better.

– Daniel Gill, 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 blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Designing for autistic people

by Daniel Gill and Paul Curzon, Queen Mary University of London

What should you be thinking about when designing for a specific group with specific needs, such as autistic people? Queen Mary students were set this task and on the whole did well. The lessons though are useful when designing any technology, whether apps or gadgets.

A futuristic but complicated interface
A futuristic but complicated interface with lots of features: feature bloat?
Image by Tung Lam from Pixabay

The Interactive Systems Design module at QMUL includes a term-long realistic team interaction design project with the teaching team acting as clients. The topic changes each year but is always open-ended and aimed at helping some specific group of people. The idea is to give experience designing for a clear user group not just for anyone. A key requirement is always that the design, above all, must be very easy to use, without help. It should be intuitively obvious how to use it. At the end of the module, each team pitches their design in a short presentation as well as a client report.

This year the aim was to create something to support autistic people. What their design does, and how, was left to the teams to decide from their early research and prototyping. They had to identify a need themselves. As a consequence, the teams came up with a wide range of applications and tools to support autistic people in very different ways.

How do you come up with an idea for a design? It should be based on research. The teams had to follow a specific (if simplified) process. The first step was to find out as much as they could about the user group and other stakeholders being designed for: here autistic people and, if appropriate, their carers. The key thing is to identify their unmet goals and needs. There are lots of ways to do this: from book research (charities, for example, often provide good background information) and informally talking to people from the stakeholder group, to more rigorous methods of formal interviews, focus groups and even ethnography (where you embed yourself in a community).

Many of the QMUL teams came up with designs that clearly supported autistic people, but some projects were only quite loosely linked with autism. While the needs of autistic people were considered in the concept and design, they did not fully focus on supporting autistic people. More feedback directly from autistic people, both at the start and throughout the process, would have likely made the applications much more suitable. (That of course is quite hard in this kind of student role-playing scenario, though some groups were able to do so.) That though is key idea the module is aiming to teach – how important it is to involve users and their concerns closely throughout the design process, both in coming up with designs and evaluating them. Old fashioned waterfall models from software engineering, where designs are only tested with users at the end, are just not good enough.

From the research, the teams were then required to create design personas. These are detailed, realistic but fictional people with names, families, and lives. The more realistic the character the better (computer scientists need to be good at fiction too!) Personas are intended to represent the people being designed for in a concrete and tangible way throughout the design process. They help to ensure the designers do design for real people not some abstract tangible person that shape shifts to the needs of their ideas. Doing the latter can lead to concepts being pushed forward just because the designer is excited by their ideas rather than because they are actually useful. Throughout the design the team refer back to them – does this idea work for Mo and the things he is trying to do? 

An important part of good persona design lies around stereotypes. The QMUL groups avoided stereotypes of autistic people. One group went further, though: they included the positive traits that their autistic persona had, not just negative ones. They didn’t see their users in a simplistic way. Thinking about positive attributes is really, really important if designing for neurodivergent people, but also for those with physical disabilities too, to help make them a realistic person. That group’s persona was therefore outstanding. Alan Cooper, who came up with the idea of design personas, argued that stereotypes (such as a nurse persona being female) were good in that they could give people a quick and solid idea of the person. However, this is a very debatable view. It seems to go against the whole idea of personas. Most likely you miss the richness of real people and end up designing for a fictional person that doesn’t represent that group of people at all. The aim of personas is to help the designers see the world from the perspective of their users, so here of autistic people. A stereotype can only diminish that.

Multicolour jigsaw ribbon
Image by Oberholster Venita from Pixabay

Another core lesson of the module is the importance of avoiding feature bloat. Lots of software and gadgets are far harder to use than need be because they are packed with features: features that are hardly ever, possibly never, used. What could have been simple to use apps, focusing on some key tasks, instead are turned into ‘do everything’ apps. A really good video call app instead becomes a file store, a messaging place, chat rooms, a phone booth, a calendar, a movie player, and more. Suddenly it’s much harder to make video calls. Because there are so many features and so many modes all needing their own controls the important things the design was supposed to help you do become hard to do (think of a TV remote control – the more features the more buttons until important ones are lost). That undermines the aim that good design should make key tasks intuitively easy. The difficulty when designing such systems is balancing the desire to put as many helpful features as possible into a single application, and the complexity that this adds. That can be bad for neurotypical people, who may find it hard to use. For neurodivergent people it can be much worse – they can find themselves overwhelmed. When presented with such a system, if they can use it at all, they might have to develop their own strategies to overcome the information overload caused. For example, they might need to learn the interface bit-by-bit. For something being designed specifically for neurodiverse people, that should never happen. Some of the applications of the QMUL teams were too complicated like this. This seems to be one of the hardest things for designers to learn, as adding ideas, adding features seems to be a good thing, it is certainly vitally important not to make this mistake if designing for autistic people. 

Perhaps one of the most important points that arose from the designs was that many of the applications presented were designed to help autistic people change to fit into the world. While this would certainly be beneficial, it is important to realise that such systems are only necessary because the world is generally not welcoming for autistic people. It is much better if technology is designed to change the world instead. 

More on …

Magazines …

Front cover of CS4FN issue 29 - Diversity in Computing

EPSRC supports this blog through research grant EP/W033615/1,

Can you trust a smile?

Yellow smiles image by Alexa from Pixabay

How can you tell if someone looks trustworthy? Could it have anything to do with their facial expression? Some new research suggests that people are less likely to trust someone if their smile looks fake. Of course, that seems like common sense – you’d never think to yourself ‘wow, what a phoney’ and then decide to trust someone anyway. But we’re talking about very subtle clues here. The kind of thing that might only produce a bit of a gut feeling, or you might never be conscious of at all.

To do this experiment, researchers at Cardiff University told volunteers to pick someone to play a trust game with. The scientists told the volunteers to make their choice based on a short video of each person smiling – but they didn’t know the scientists could control certain aspects of each smile, and could make some smiles look more genuine than others.

Continue reading “Can you trust a smile?” →