Author: Paul Curzon

Accessible Technology in the Voting Booth

CS4FN Banner

by Daniel Gill, Queen Mary University of London

Voting at an election: people deposting their voting slip
Image AI generated by Vilius Kukanauskas from Pixabay

On Thursday 4th July 2024, millions of adults around the UK went to their local polling station to vote for their representative in the House of Commons. However, for the 18% of adults who have a disability, this can be considerably more challenging. While the right of voters to vote independently and secretly is so important, many blind and partially sighted people cannot do so without assistance. Thankfully this is changing, and this election was hailed as the most accessible yet. So how does technology enable blind and partially sighted people to vote independently?

 There are two main challenges when it comes to voting for blind and partially sighted people. The names of candidates are listed down the left-hand side, so firstly, a voter needs to find the row of the person who they want to vote for. They then, secondly, need to put a cross in the box to the right. The image below gives an example of what the ballot paper looks like:

A mock up of a "CS4FN" voting slip with candidates HOPPER, Grace TURING, Alan Mathison BENIOFF, Paul Anthony Lovelace, Ada

To solve the first problem, we can turn to audio. An audio device can be used to play a recording of the candidates as the appear on the ballot paper. Some charities also provide a phone number to call before the election, with a person who can read this list out. This is great, of course, but it does rely on the voter remembering the position of the person that they want to vote for. A blind or partially sighted voted is also allowed to use a text reader device, or perhaps a smart phone with a special app, to read out what is on the ballot paper in the booth.

Lots of blind and partially impaired people are able to read braille: a way of representing English words using bumps on the paper (read more about braille in this CS4FN article). One might think that this would solve all the problems, but, in fact, there is a requirement that all the ballot papers for each constituency have a standard design to ensure they can be counted efficiently and without error.

The solution to the second problem is far more practical: the excitingly named tactile voting device. This is a simple plastic device which is placed on top of the ballot paper. Each of the boxes on the ballot paper (as shown to the right of the image above), has a flap above it with its position number embossed on it. When the voter finds the number of the person they want to vote for, they simply turn over the flap, and are guided by a perfectly aligned square guide to where the box is. The voter can then use that guide to draw the cross in the box.

This whole process is considerably more complicated than it is for those without disabilities – and you might be thinking, “there must be an easier way!” Introducing the McGonagle Reader (MGR)! This device combines both solutions into one device that can be used in the voting booth. Like the tactile voting device, it has flaps which cover each of the boxes for drawing the cross. But, next to those, buttons, which, when pressed, read out the information of the candidate for that row. This can save lots of time, removing the need to remember the position of each candidate – a voter can simply go down the page and find who they want to vote for and turn over the correct flap.

When people have the right to vote, it is especially important to ensure that they have the ability to use that right. This means that no matter the cost or the logistics, everyone should have access to the tools they need to vote for their representative. Progress is now being made but a lot more work still needs to be done.

To help ensure this happens in future, the RNIB want to know the experiences of those who voted or didn’t vote in the UK 2024 general election – see the survey linked from the RNIB page here.

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 through EPSRC grant EP/W033615/1.

The basics of Quantum Computing: Qubits

An eye looking at two blue spheres
Image by Gerd Altmann from Pixabay

Reality is weird, very weird. The first thing you have to do to understand the reality of reality is to drop your common sense. Only then can you start to understand it especially when it comes to the quantum world of the very small. Our brains evolved to naturally make sense of human scale things, rather than the very large or very small. Accept the weirdness, though, and there are lots of opportunities, especially for computer scientists. That is why it is now an exciting area of research with theoretical physicists, engineers and computer scientists working together to make progress.

Not common sense

Imagine you are a person trying to understand the world a thousand years ago. Clearly the world MUST be flat. It looks flat and suggesting you are standing on a sphere is just ridiculous. People living on the other side would obviously fall off if it was a sphere! Except the world is a sphere and people in Australia (or Europe if you are Australian) don’t fall off. Common sense doesn’t work (until you understand how gravity works). That’s why science is so powerful. Common Sense also doesn’t work for understanding the reality of the very small. This branch of physics, quantum physics, is very important for computer scientists not only because the building blocks of our computers are becoming ever smaller, but because when you get so small that the laws of quantum physics matter, computers can work in new, exciting ways, ways that are far better than our current computers.

Bits and qubits

Let’s start with binary, the fundamental way we represent information in a computer. The basic building block of information is the bit. A bit is something that can have one of two states. It can be a 1 or a 0. That means a bit can store some information. These two states of 1 and 0 might be physically represented in lots of ways, such as a high voltage stored versus a low voltage stored, or a pulse of light versus no pulse of light, or someone’s hand up versus their hand down. If you have two bits then you can store one of 4 pieces of information in them because of the possible combinations (00, 01, 10 and 11), with three bits and you can store 8 different things. Those collections of bits can then stand for different numbers (that is all binary is), and by building big circuits from simple basic circuits that do simple manipulations on bits (i.e., logic gates) we can do ever more complex calculations with them and ultimately everything our current computers are capable of.

The spin of an electron

A pedestrian light showing green/walk
Image by Hans from Pixabay

Bits can be represented by anything that has 2 states. So suppose you want to represent your bits using something really small like electrons. Electrons have a property called spin. You can imaging them as spinning balls of charge (though they are not exactly spinning like a spinning ball … electrons aren’t balls and they aren’t actually rotating in the normal sense – remember reality is weird so these analogies are just there to help give an idea, but it is never as simple as that). Now, electrons can “spin” in exactly one of two ways called spin up and spin down. There are only two possible kinds of spin because in the quantum world things come in discrete amounts, not continuous ones. They jump from one state to another, like a pedestrian (walk/don’t walk) traffic light going from red to green instantly) rather than gradually changing between them (such as the way a car gradually speeds up to the speed limit). An electron is either spin up or spin down, like the pedestrian lights, never something in between.

Now, it is possible to set the spin of an electron and to measure whether it has spin that is spin up or spin down, so an electron can, in principle, be used to store a binary bit given it has two states (spin up for 1 and spin down for 0, say). However, this is where weirdness really comes in. It turns out that it is possible for an electron to be both spin up and spin down at once as long as the spin is not measured, due to the way the quantum world works. A quantum pedestrian light doing a similar thing would have only one light that could be red or green. However, it would be both red and green at the same time UNTIL someone looked at it to see which state it was in (so measured the state). At that point they would become, and the person would only see, one colour or the other. This is called quantum superposition. To understand this it is better to think about reality being about probabilities not certainties. Imagine that the electron is like a tossed coin that is still in the air. It has a probability of being Heads and of being Tails. Only when it lands (so is measured) is it actually one or the other. An electron is combining both possibilities until the spin is measured.

The quantum tortoise and the hare

You may have the quaint idea that reality is made of sub-atomic particles (like electrons or protons) that are solid little bits of matter that are very ball like and exist in one place at any given time. Actually they aren’t like that at all. It is better to think of particles as just having probabilities of being at one place or another – they are kind of smeared across space, everywhere at once, like a ripple pattern across a pond, just with different probabilities of actually being in any place when their position is measured. When you do measure their position you find they definitely are in one place or another, appearing to be a particle again, not a wave.

It may help to think of this in terms of watching slow moving tortoises and fast moving hares passing you as they race. The position of a slow moving tortoise you see wander by is easy to call: it has a very high probability to be in a particular place. The position of a fast moving hare that whizzes past is much harder to call: it has a far lower probability to be in a given place at any time. However, without looking you can’t tell. You just know the probabilities. Of course with particles it isn’t exactly like that just as an electron’s spin isn’t exactly like a ball spinning. It is only when a particle’s position is actually checked (i.e. measured) that it is definitely at a known place and that smeared probability collapses to certainty. A quantum tortoise and hare racing past would be in all possible positions round the race track just with different probabilities. Suppose you only checked (so measured their position) at the finish line. It is only because of that measurement that the probabilities of where they were through the race turn into specific measured so known positions with a quantum hare or a quantum tortoise having actually won.

This weirdness is linked to the fact that the fundamental components that reality is made up of are both particles in given places (think of an electron or a proton) and waves passing through space (think of light or ripples in a pond) at the same time. So light behaves like a particle and like a wave. Similarly, an electron does too. 

Electron spin as Qubits

Other properties of sub-atomic particles act in the same way as a particle’s position being smeared across lots of possibilities at once. This includes the spin of an electron. Until it is measured, an electron is superposed in both a spin up and spin down state at the same time (spinning both ways at once!): there is just a probability that the electron is in each state, it isn’t actually definitely in either. That means as long as you do not measure its spin, the electron as a device storing a piece of information is storing both 1 and 0 at the same time, each with a given probability. As such it behaves differently to an actual bit which must be either 1 or 0. We therefore call such an electron-based storage a qubit rather than a bit. 

In theory, we can do computations on qubits manipulating and combining them in simple ways using the quantum equivalent of logic gates. Once we have created quantum logic gates to do simple manipulations, we can combine those gates into bigger and bigger circuits that do more complicated quantum calculations. As long as the states of the qubits are not measured all the states through the circuit are superposed in both states with particular probabilities. Unlike a normal circuit which does one series of computations based on its inputs, these quantum circuits are in effect doing all possible computations of that circuit at once. It is only when we measure the answer at the output, say, that the qubits in the circuit are fixed at either 1 or 0 and an actual result is delivered. This is like the tortoise and hare being everywhere (whatever racing strategy they followed) with some probability until we measure the result at the finish line (the output of the race). Because all states existed at once, lots of computation exists simultaneously, this means that such a circuit can, in theory, and with the right algorithms, deliver answers far, far faster than a conventional circuit could possibly do, given the latter can only do one computation at a time,

From theory to practice

That is the theory, and it is gradually being realised in practice. Qubits can be created and their values changed. Various quantum logic gates have also now been invented and so small quantum computers do now exist. Quantum algorithms to do certain tasks quickly have been invented. Since the original ideas were mooted, progress has been relatively slow, but now that the ideas have been shown to work in practice, more and more is being achieved, making it an exciting time to be doing quantum computing research.

Paul Curzon, Queen Mary University of London

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.

Gutta-Percha: how a tree launched a global telecom revolution

CS4FN Banner

by Paul Curzon, Queen Mary University of London

(from the archive)

Rubber tree being tapped
Image  from Pixabay

Obscure plants and animals can turn out to be surprisingly useful. The current mass extinction of animal and plant species needs to be stopped for lots of reasons but an obvious one is that we risk losing forever materials that could transform our lives. Gutta-percha is a good example from the 19th century. It provided a new material with uses ranging from electronic engineering to bioengineering. It even transformed the game of golf. Perhaps its greatest claim to fame though is that it kick-started the worldwide telecoms boom of the 19th century that ultimately led to the creation of global networks including the Internet.

Gutta-percha trees are native to South East Asia and Australia. Their sap is similar to rubber. It’s actually a natural polymer: a kind of material made of gigantic molecules built up of smaller structures that are repeated over and over again. Plastics, amber, silk, rubber and wool are all made of polymers. Though very similar to it, unlike rubber, Gutta-percha is biologically inert – it doesn’t react with biological materials – and that was the key to its usefulness. It was discovered by Western explorers in the middle of the 17th century, though local Malay people already knew about it and used it.

Chomping wires

So how did it play a part in creating the first global telecom network? Back in the 19th century, the telegraph was revolutionising the way people communicated. It meant messages could be sent across the country in minutes. The trouble was when the messages got to the coast they ground to a halt. Messages could only travel across an ocean as fast as a boat could take them. They could whiz from one end of America to the other in minutes but would then take several weeks to make it to Europe. The solution was to lay down undersea telegraph cables. However, to carry electricity an undersea cable needs to be protected and no one had succeeded in doing that. Rubber had been tried as an insulating layer for the cables but marine animals and plants just attacked it, and once the cable was open to the sea it became useless for sending signals. Gutta-percha on the other hand is a great insulator too but it doesn’t degrade in sea-water.

As it was the only known material that worked, soon all marine cable used Gutta-percha and as a result the British businessmen who controlled its supply became very rich. Soon telegraph cables were being laid everywhere – the original global telecoms network. To start with the network carried telegraph signals then was upgraded to voice and now is based on fibre-optics – the backbone of the Internet.

Rotting teeth

Gutta-percha has also been used by dentists – just as marine animals don’t attack it, it doesn’t degrade inside the human body either. That together with it being easy to shape makes it perfect for dental work. For example, it is used in root canal operations. The pulp and other tissue deep inside a rotting tooth are removed by the dentist leaving an empty chamber. Gutta-percha turns out to be an ideal material to fill the space, though medical engineers and materials scientists are trying to develop synthetic materials like Gutta-percha, but that have even better properties for use in medicine and dentistry.

Dimpled balls

That just leaves golf! Early golf balls were filled with feathers. In 1848 Robert Adams Paterson came up with the idea of making them out of Gutta-percha since it was much easier to make than the laborious process of sewing balls of feathers. It was quickly realised, if by accident, that after they had been used a few times they would fly further. It turned out this was due to the dimples that were made in the balls each time they were hit. The dimples improved the aerodynamics of the ball. That’s why modern golf balls are intentionally covered in dimples.

So gutta-percha has revolutionised global communications, changed the game of golf and even helped people with rotting teeth. Not bad for a tree.

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.

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.

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

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,