When did women first contribute to the subject we now call Computer Science: developing useful algorithms, for example? Perhaps you would guess Ada Lovelace in the Victorian era so the mid 1800s? She corrected one of Charles Babbage’s algorithms for the computer he was trying to build. Think earlier. Two centuries or so earlier! Maria Cunitz improved an algorithm published by the astronomer Kepler and then applied it to create a work more accurate than his.
Very few women, until the 20th century were given the opportunities to take part in any kind of academic study. They did not get enough education, and even if they did were not generally welcome in the circles of mathematicians and natural philosophers. Maria, who was Polish from an educated family of doctors and scientists, was tutored and supported in becoming a polymath with an interest in lots of subjects from history to mathematics. Her husband was a doctor who also was interested in astronomy something that became a shared passion with him teaching her the extra maths she needed. They lived at the time of the 30 years war that was waged across most of Europe. It was a spat turned into a war about religion between catholic and protestant countries. In Poland, where they lived, it was not safe to be a protestant. The couple had a choice of convert or flee, so left their home taking sanctuary in a convent.
This actually gave Cunitz a chance to pursue an astronomical ambition based on the work of Johannes Kepler. Kepler was famous for his three Laws of Planetary Motion published in the early 1600s on how the planets orbit the sun. It was based on the new understanding from Copernicus that the planets rotated around the sun and so the Earth was not the centre of everything. Kepler’s work gave a new way to compute the positions of the planets,
Cunitz had a detailed understanding of Kepler’s work and of the mathematics behind it, She therefore spent her time in the convent computing tables that gave the positions of all the planets in the sky. This was based on a particular work of Kepler called the Rudolphine Tables. It was one of his great achievements stemming from his planetary laws. Such astronomical tables became vital for navigating ships at sea, as the planetary positions could be used to determine longitude. However, at the time, the main use was for astrology as casting someone’s horoscope required knowledge of the precise positions of the planets. In creating the tables, Cunitz was acting as an early human computer, following an algorithm to compute the table entries. It involved her doing a vast amount of detailed calculation.
Kepler himself spent years creating his version of the tables. When asked to hurry up and complete the work he said: “I beseech thee, my friends, do not sentence me entirely to the treadmill of mathematical computations…” He couldn’t face the role of being a human computer! And yet a whole series of women who came after him dedicated their lives to doing exactly that, each pushing forward astronomy as a result. Maria herself took on the specific task he had been reluctant to complete in working out tables of planetary positions.
Kepler had published his algorithm for computing the tables along with the tables. Following his algorithm though was time consuming and difficult, making errors likely. Maria realised it could be improved upon, making it simpler to do the calculations for the tables and making it more likely they were correct. In particular, Kepler was using logarithms for the calculations. but she realised that was not necessary. Sacrificing some accuracy in the results for the sake of the avoidance of larger errors, the version she followed was even simpler. By the use of algorithmic thinking she had avoided at least some of the chore that Kepler himself had dreaded. This is exactly the kind of thing good programmers do today, improving the algorithms behind their programs so the programs are more efficient. The result was that Maria produced a set of tables that was more accurate than Kepler’s, and in fact the most accurate set of planetary tables ever produced to that point in time. She published them privately as a book “Urania Propitia’ in 1650. Having a mastery of languages as well as maths and science, she, uniquely, wrote it in both German and Latin.
Women do not figure greatly in the early history of science and maths just because societal restrictions, prejudices and stereotypes meant few were given the chance. Those who were like Maria Cunitz, showed their contributions could be amazing. It just took the right education, opportunities, and a lot of dedication. That applies to modern computer science too, and as the modern computer scientist, Karen Spärck Jones, responsible for the algorithm behind search engines said: “Computing is too important to be left to men.”
By Przemysław Wałęga, Queen Mary University of London
Logical reasoning and proof, whether done using math notation or informally in your head, is an important tool of computer scientists. The idea of proving, however, is often daunting for beginners and it takes a lot of practice to master this skill. Here we look at a simple puzzle to get you started.
Computer Scientists use logical reasoning and proofs a lot. They can be used to ensure correctness of algorithms. Researchers doing theoretical computer science use proofs all the time, working out theories about computation.
Proving mathematical statements can be very challenging, though. Coming up with a proof often requires making observations about a problem and exploiting a variety of different proof methods. Making sure that the proof is correct, concise, and easy to follow matters too, but that in itself needs skill and a lot of practice. As a result, proving can be seen as a real art of mathematics.
Let’s think about a simple puzzle to show how logical thinking can be used when solving a problem. The puzzle can be solved without knowing any specific maths, so anyone can attempt it, but it will probably look very hard to start with.
Before you start working on it though, let me recommend that first you try to solve it entirely in your mind, that is, with no pen and paper (and definitely no computer!).
The Puzzle
Here is the puzzle, which I heard at a New Year’s party from a friend Marcin:
Mrs. and Mr. Taylor hosted a party and invited four other couples. After the party, everyone gathered in the hallway to say their goodbyes with handshakes. No one shook hands with themselves (of course!) or their partner, and no one shook hands with the same person more than once. Each person kept track of how many people they had shaken hands with. At one point, Mr. Taylor shouted “STOP” and asked everyone to say how many people they had shaken hands with. He received nine different answers.
How many people did Mrs Taylor shake hands with?
I will give you some hints to help solving the puzzle, but first try to solve it on you own, and see how far you get. Maybe you will be solve the puzzle on your own?
Why did I recommend solving the puzzle without pen and paper? Because, our goal is to use logical and critical thinking instead of finding a solution in a “brute force” manner, that is, blindly listing all the possibilities and checking each of them to find a solution to the puzzle. As an example of a brute force way of solving a problem, take a crossword puzzle where you have all but one of the letters of a word. You have no idea what the clue is about, so instead you just try the 26 possible letters for the missing one and see which make a word and then check which that do fit the clue!
Notice that the setting of our puzzle is finite: there are 10 people shaking hands, so the number of ways they shake hands is also finite if bigger than say checking 26 different letters of the crossword problem. That means you could potentially list all the possible ways people might shake hands to solve the puzzle. This is, however, not what we are aiming for. We would like to solve the puzzle by analysing the structure of the problem instead of performing brute force computation.
Also, it is important to realise that often mathematicians solve puzzles (or prove theorems) about situations in which the number of possibilities is infinite so the brute force approach of listing them all is not possible at all. There are also many situations where the brute force approach is applicable in theory, but in practice it would require considering too many cases: so many that even the most powerful computers would not be able to provide us with an answer in our lifetimes.
For our puzzle, you may be tempted to list all possible handshake situations between 10 people. Before you do start listing them, let’s check how much time you would need for that. You have to consider every pair that can be formed from 10 people. A mathematician refers to that as “10 choose 2”, the answer to which is that there are 45 possible pairs among 10 people (the first person pairs with 9 others, the next has 8 others to pair with having been paired with the first already, and so on and 9+8+….+1 = 45). However, 45 is not the number that we are looking for. Each of these pairs can either shake hands or not, and we need to consider all those different possibilities. There are 245 such handshake combinations. How big is this number? The number 210 is 1024, so it is approximately 1000. Hence 240=(210)4 (which is clearly smaller than our 245) is approximately 10004 = 1,000,000,000,000 that is, a trillion. Listing a trillion combinations should sound scary to you. Indeed, if you can be quick enough to write each of the trillion combinations in one second, you will spend 31 688 years. Let’s not try this!
Of course, we can look more closely at the description of the puzzle to decrease the number of combinations. For example, we know that nobody shakes hands with their partner, which will already massively reduce the number. However, let’s try to solve the puzzle without using any external memory aids or computational power. Only our minds.
Can you solve it? A key trick that mathematicians and computer scientists use is to break down problems into simpler problems first (decomposition). You may not be able to solve this puzzle straight away, so instead think about what facts you can deduce about the situation instead.
If you need help, start by considering Hint 1 below. If you are still stuck, maybe Hint 2 will help? Answer these questions and you will be a long way to solving the puzzle.
Hints
Mr. Taylor received nine different answers. What are these answers?
Knowing the numbers above, can you work out who is a partner of whom?
No luck in solving the puzzle? Try to spend some more time before giving up! Then read on. If you managed to solve it you can compare your way of thinking with the full solution below.
Solution
First we will answer Hint 1. We can show that the answers received by Mr. Taylor are 0, 1, 2, 3, 4, 5, 6, 7, and 8. There are 5 couples, meaning that there are 10 people at the party (Mr. and Mrs. Taylor + 4 other couples). Each person can shake hands with at least 0 people and at most 8 other people (since there are 10 people, and they cannot shake hands with themselves or their partner). Since Mr. Taylor received nine different answers from the other 9 people, they need to be 0, 1, 2, 3, 4, 5, 6, 7, and 8. This is an important observation which we will use in the second part of the solution.
Next, we will answer Hint 2. Let’s call P0 the person who answered 0, P1 the person who answered 1, …, P8 the person who answered 8. The person with the highest (or the lowest) number of handshakes is a good one to look at first.
Who is the partner of P8? P8 did not shake hands with themselves and with P0 (as P0 did not shake hands with anybody). So P8 had to shake hands with all the other 8 people. Since no one shakes hands with their partner, it follows that P0 is the partner of P8!
Who is the partner of P7? They did not shake hands with themselves, with P0 and with P1, because we already know that P1 shook hands with P8, and they shook hands with only one person. So the partner of P7 can be either P8, P0, or P1. Since P8 and P0 are partners, P7 needs to be the partner of P1.
Following through with this analysis for P6 and P5, we can show that the following are partners: P8 and P0, P7 and P1, P6 and P2, P5 and P3. The only person among P0, … , P8 who is left without a partner is P4. So P4 needs to be Mrs. Taylor, the partner of Mr. Taylor, the one person left who didn’t give a number.
Consequently, we have also showed that Mr Taylor shook hands with 4 people.
Observe that the analysis above does not only provide us an answer to the puzzle, but it also allows us to uniquely determine the handshake setting as presented in the picture below (called a graph by Computer Scientists). Here, people are nodes (circles) and handshakes are represented as edges (lines) in the graph. Red edges correspond to handshakes with P8, blue edges are handshakes with P7, green with P6 and yellow with P5. Partners are located next to each other, for example, Mr. Taylor is a partner with P4.
Image computer generated by Przemysław Wałęga
Large Language Models
Although this article is about logical thinking, and not about tools to solve logic puzzles, it is interesting to see if current AI models are capable of solving the puzzle. As puzzles go it is relatively easy and occurs on the Internet in different settings and languages, so large language models (LLMs) trained on the Internet should be good at solving it. Let’s test them!
I asked ChatGPT-4o and Gemini 1.5 Flash to solve the puzzle. To my surprise, both of them did struggle. They had problems with understanding some parts of the problem formulation and made mathematical mistakes.
ChatGPT seems to wrongly assume that Mr. Taylor answered his own question about the number of handshakes, and so, that each of 10 people announced a different number of handshakes. As follows from our solution of the puzzle, there exists exactly one graph representing the handshake situation. In this graph, the number of handshakes of Mr. and Mrs. Taylor is the same, namely 4. Hence, the additional assumption made by ChatGPT (that each of 10 people had a different number of handshakes) makes the situation described in the puzzle impossible. Interestingly, ChatGPT was able to solve such an impossible puzzle providing a correct answer… Does it mean that ChatGPT has solved the puzzle?
Gemini, in contrast, states that the puzzle cannot be solved without more information such as the order of arrivals. This is clearly wrong. We know how to solve the puzzle and the order of arrivals is actually completely irrelevant to the puzzle!
This small experiment uses basic LLMs and does not aim to draw any conclusions about their capabilities. I am quite certain that one can find an LLM that can solve this simple puzzle without mistakes. However, this experiment aims to emphasise the need for checking AI solutions yourself. To do that you need to gain the skills of doing proof yourself!
In what follows I provide answers obtained from AI models and highlight as bold parts which are wrong assumptions or reasoning.
Solution by ChatGPT:
Key Observations:
There are 10 people in total at the party (5 couples: Mr. and Mrs. Taylor and 4 other couples).
No one shakes hands with their own partner.
No one shakes hands with themselves or the same person more than once.
The handshake answers must be unique and range from 0 to 9 (since there are 10 people, including Mr. and Mrs. Taylor).
Solution:
Since there are 10 people total, the number of handshakes any one person could have ranges from 0 to 9.
If everyone gives a unique answer, it means:
One person shook hands with 0 people.
Another shook hands with 1 person.
Another with 2, and so on, up to 9.
Steps:
The person who shook hands with 9 people: This person shook hands with everyone else, meaning their partner (who doesn’t shake hands with them) must have shaken hands with 0 people.
The person who shook hands with 8 people: This person shook hands with everyone except their partner and the person who shook hands with 0.
By continuing this pattern, we see that for every unique count of handshakes k, the person with k handshakes corresponds to a partner with 9−k handshakes.
Mrs. Taylor’s Handshakes:
Mr. Taylor shouted “STOP” after collecting answers from all 10 people. Since there are 9 different handshake counts, one of those counts must belong to Mrs. Taylor.
Let’s assume Mr. Taylor is among the group and is the one with the maximum or minimum handshakes.
The pairing pattern ensures Mrs. Taylor’s number of handshakes must fall within the range, but based on symmetry of couples logic !
The key is to match couples symmetrically:
If Mr. Taylor gets answers (0, 1, 2,…
Let’s refine the solution:
The possible handshake counts are 0,1,2,…,9, ensuring each number is unique.
The pairing works such that if one person shakes k hands, their partner shakes 9-k hands.
This logic means:
The person who shook 9 hands paired with the person who shook 0.
The person who shook 8 hands paired with the person who shook 1, and so on.
Mrs. Taylor’s Count:
If there are nine unique handshake counts (from 0 to 9), Mrs. Taylor must have shaken 4 hands because her partner, Mr. Taylor, who controls the setup, must fall at the midpoint to allow symmetrical pairing logic.
Solution by Gemini:
Certainly, let’s solve the handshake puzzle!
Understanding the Problem:
We have 10 people at the party (Mr. and Mrs. Taylor, plus 4 other couples).
No one shakes hands with themselves or their partner.
No one shakes hands with the same person more than once.
Each person keeps track of how many handshakes they’ve done.
Mr. Taylor asks everyone how many handshakes they’ve done, and gets 9 different answers.
We need to figure out how many handshakes Mrs. Taylor did.
Let’s Analyze:
The key to solving this is to consider the possible range of handshakes each person could have.
Lowest Possible Handshakes: If someone is the first to arrive and doesn’t shake hands with anyone else, they’ll have 0 handshakes.
Highest Possible Handshakes: The maximum number of handshakes depends on the order of arrivals and who shakes hands with whom. In the most efficient scenario, everyone could shake hands with everyone else except their partner. This would lead to a maximum of 8 handshakes for each person.
Now, let’s consider the 9 different answers:
Since there are 9 different answers, and the minimum is 0, the maximum number of handshakes someone could have is 8.
Let’s think about Mrs. Taylor:
She can’t have 0 handshakes because she would have to shake hands with someone eventually.
She can’t have 8 handshakes because Mr. Taylor would have to have the same number (since they are the only couple).
Therefore, Mrs. Taylor must have shaken hands with a number between 1 and 7.
Unfortunately, without more information about the order of arrivals and who shook hands with whom, we can’t pinpoint the exact number of handshakes Mrs. Taylor did.
Let me know if you’d like to explore a specific scenario with a particular order of arrivals and handshakes to determine Mrs. Taylor’s exact number!
Mike Lynch was one of Britain’s most successful entrepreneurs. An electrical engineer, he built his businesses around machine learning long before it was a buzz phrase. He also drew heavily on a branch of maths called Bayesian statistics which is concerned with understanding how likely, even apparently unlikely, things are to actually happen. This was so central to his success that he named his super yacht, Bayesian, after it. Tragically, he died on the yacht, when Bayesian sank in a freak, extremely unlikely, accident. The gods of the sea are cruel.
Mike started his path to becoming an entrepreneur at school. He was interested in music, and especially the then new but increasingly exciting, digital synthesisers that were being used by pop bands, and were in the middle of revolutionising music. He couldn’t afford one of his own, though, as they cost thousands. He was sure he could design and build one to sell more cheaply. So he set about doing it.
He continued working on his synthesiser project as a hobby at Cambridge University, where he originally studied science, but changed to his by-then passion of electrical engineering. A risk of visiting his room was that you might painfully step on a resistor or capacitor, as they got everywhere. That was not surprising giving his living room was also his workshop. By this point he was also working more specifically on the idea of setting up a company to sell his synthesiser designs. He eventually got his first break in the business world when chatting to someone in a pub who was in the music industry. They were inspired enough to give him the few thousand pounds he needed to finance his first startup company, Lynett Systems.
By now he was doing a PhD in electrical engineering, funded by EPSRC, and went on to become a research fellow building both his research and innovation skills. His focus was on signal processing which was a natural research area given his work on synthesisers. They are essentially just computers that generate sounds. They create digital signals representing sounds and allow you to manipulate them to create new sounds. It is all just signal processing where the signals ultimately represent music.
However, Mike’s research and ideas were more general than just being applicable to audio. Ultimately, Mike moved away from music, and focussed on using his signal processing skills, and ideas around pattern matching to process images. Images are signals too (resulting from light rather than sound). Making a machine understand what is actually in a picture (really just lots of patches of coloured light) is a signal processing problem. To work out what an image shows, you need to turn those coloured blobs into lines, then into shapes, then into objects that you can identify. Our brains do this seamlessly so it seems easy to us, but actually it is a very hard problem, one that evolution has just found good solutions to. This is what happens whether the image is that captured by the camera of a robot “eye” trying to understand the world or a machine trying to work out what a medical scan shows.
This is where the need for maths comes in to work out probabilities, how likely different things are. Part of the task of recognising lines, shapes and objects is working out how likely one possibility is over another. How likely is it that that band of light is a line, how likely is it that that line is part of this shape rather than that, and so on. Bayesian statistics gives a way to compute probabilities based on the information you already know (or suspect). When the likelihood of events is seen through this lens, things that seem highly unlikely, can turn out to be highly probably (or vice versa), so it can give much more accurate predictions than traditional statistics. Mike’s PhD used this way of calculating probabilities even though some statisticians disdained it. Because of that it was shunned by some in the machine learning community too, but Mike embraced it and made it central to all his work, which gave his programs an edge.
While Lynett Systems didn’t itself make him a billionaire, the experience from setting up that first company became a launch pad for other innovations based on similar technology and ideas. It gave him the initial experience and skills, but also meant he had started to build the networks with potential investors. He did what great entrepreneurs do and didn’t rest on his laurels with just one idea and one company, but started to work on new ideas, and new companies arising from his PhD research.
He realised one important market for image pattern recognition, that was ripe for dominating, was fingerprint recognition. He therefore set about writing software that could match fingerprints far faster and more accurately than anyone else. His new company, Cambridge Neurodynamics, filled a gap, with his software being used by Police Forces nationwide. That then led to other spin-offs using similar technology
He was turning the computational thinking skills of abstraction and generalisation into a way to make money. By creating core general technology that solved the very general problems of signal processing and pattern matching, he could then relatively easily adapt and reuse it to apply to apparently different novel problems, and so markets, with one product leading to the next. By applying his image recognition solution to characters, for example, he created software (and a new company) that searched documents based on character recognition. That led on to a company searching databases, and finally to the company that made him famous, Autonomy.
One of his great loves was his dog, Toby, a friendly enthusiastic beast. Mike’s take on the idea of a search engine was fronted by Toby – in an early version, with his sights set on the nascent search engine market, his search engine user interface involved a lovable, cartoon dog who enthusiastically fetched the information you needed. However, in business finding your market and getting the right business model is everything. Rather than competing with the big US search engine companies that were emerging, he switched to focussing on in-house business applications. He realised businesses were becoming overwhelmed with the amount of information they held on their servers, whether in documents or emails, phone calls or videos. Filing cabinets were becoming history and being replaced by an anarchic mess of files holding different media, individually organised, if at all, and containing “unstructured data”. This kind of data contrasts with the then dominant idea that important data should be organised and stored in a database to make processing it easier. Mike realised that there was lots of data held by companies that mattered to them, but that just was not structured like that and never would be. There was a niche market there to provide a novel solution to a newly emerging business problem. Focussing on that, his search company, Autonomy, took off, gaining corporate giants as clients including the BBC. As a hands-on CEO, with both the technical skills to write the code himself and the business skills to turn it into products businesses needed, he ensured the company quickly grew. It was ultimately sold for $11 billion. (The sale led to an accusation of fraud in hte US, but, innocent, he was acquitted of all the charges).
Investing
From firsthand experience he knew that to turn an idea into reality you needed angel investors: people willing to take a chance on your ideas. With the money he made, he therefore started investing himself, pouring the money he was making from his companies into other people’s ideas. To be a successful investor you need to invest in companies likely to succeed while avoiding ones that will fail. This is also about understanding the likelihood of different things, obviously something he was good at. When he ultimately sold Autonomy, he used the money to create his own investment company, Invoke Capital. Through it he invested in a variety of tech startups across a wide range of areas, from cyber security, crime and law applications to medical and biomedical technologies, using his own technical skills and deep scientific knowledge to help make the right decisions. As a result, he contributed to the thriving Silicon Fen community of UK startup entrepreneurs, who were and continue to do exciting things in and around Cambridge, turning research and innovation into successful, innovative companies. He did this not only through his own ideas but by supporting the ideas of others.
Mike was successful because he combined business skills with a wide variety of technical skills including maths, electronic engineering and computer science, even bioengineering. He didn’t use his success to just build up a fortune but reinvested it in new ideas, new companies and new people. He has left a wonderful legacy as a result, all the more so if others follow his lead and invest their success in the success of others too.
Superheroes don’t just have physical powers. Often theycome out on top because of their mental abilities. Sherlockis a good example, catching villains through logicalthinking. Anyone can get better at thinking! Just practice.
It is important for everyone to be able to think clearly. It is especially true for programmers, detectives and lawyers as well as superheroes. You need to be able to work things out from the facts you know. The Ancient Greeks were very good at logic. They invented the idea of a ‘syllogism’. These are common patterns that combine facts where you figure out a conclusion only using the facts.
For example, if we know facts 1 and 2 below (where you can swap in anything for X, Y and Z) then we can create a new fact as shown.
Image by Paul Curzon
So let’s replace X with the word superheroes, Y with fight crime and Z with my favourite superhero, Ghost Girl. If we put them in to the picture above we get the new picture:
Image by Paul Curzon
In this case we can deduce the new fact that Ghost Girl fights crime. Notice how you use the plurals in Fact 1 and singular words in the other facts to make the English work.
Puzzles
Can you solve these Superhero Syllogism puzzles? Work out which conclusion is the one that follows from the given facts. Use our coloured template above to help.
Superhero syllogism puzzle 1
FACT 1: ALL superheroes do good. FACT 2: The Invisible Woman is a superhero.
Which statement below (a, b, c or d) can we say from these facts alone? Don’t use anything extra, just use fact 1 and fact 2. (ANSWERS at the bottom of the page).
a) The Invisible Woman has superpowers. b) The Invisible Woman does good. c) The Invisible Man does good. d) The Invisible Woman does not do good
Superhero syllogism puzzle 2
FACT 1: ALL superheroes sometimes accidentally do harm. FACT 2: Jamila is a superhero.
What can we say from these facts alone?
a) Jamila sometimes accidentally does harm. b) Jamila is not a superhero c) Those with superpowers only do good. d) Jamie is a superhero
Superhero syllogism puzzle 3
FACT 1: ALL supervillains laugh in an evil way. FACT 2: The Spider is a supervillain.
What can we say from these facts alone?
a) The Spider sometimes accidentally does harm. b) The Spider does not laugh in an evil way. c) Supervillains are evil. d) The Spider laughs in an evil way.
As long as the facts are true the conclusion follows, though if the facts are not true then nothing is really known.
Superhero syllogism puzzle 4
The following logic is good but something has gone wrong because the conclusion is not true. The superhero called the Angel does not actually have any superpowers! The Angel just wears a flying suit! Can you work out what has gone wrong with our logic?
1. ALL superheroes have superpowers. 2. The Angel is a superhero.
Therefore we can conclude from these facts alone that
3.The Angel has superpowers.
Answers are at the bottom of the page.
Fun to do
Take the pattern of the above syllogisms and invent your own. Just substitute your own words, but keep the pattern.See how silly the “facts” you can deduce are.
– Paul Curzon, Queen Mary University of London, first appeared in A BIT of CS4FN 2
Learn the basics of computer science through magic tricks
Subscribe to be notified whenever we publish a new post to the CS4FN blog.
This page is funded by EPSRC on research agreement EP/W033615/1.
Answers
Superhero syllogism puzzle 1
Answer: b. FACT 1: ALL superheroes … do good. FACT 2: The Invisible Woman is a superhero Therefore we can conclude from these facts alone that NEW FACT: The Invisible Woman … does good.
Superhero syllogism puzzle 2
Answer: a. FACT 1: ALL superheroes … sometimes accidentally do harm. FACT 2: Jamila is a superhero Therefore we can conclude from these facts alone that NEW FACT: Jamila … sometimes accidentally does harm.
Superhero syllogism puzzle 3
Answer: d. FACT 1: ALL supervillains … laugh in an evil way. FACT 2: The Spider is a supervillain. Therefore we can conclude from these facts alone that NEW FACT: The Spider … laughs in an evil way.
Superhero syllogism puzzle 4
Something has gone wrong. We are told that The Angel has no superpowers. They just wear a special flying suit. The new fact is therefore not true. This means that one of the original ‘facts’ was not actually true. If we start from things that are not true then the things we deduce will not be true either! In this case
Queens is a fairly simple kind of logic puzzle found for example on LinkedIn as a way to draw you back to the site. Doing daily logic puzzles is good both for mental health and to build logical thinking skills. As with programming, solving logic puzzles is mostly about pattern matching (also a useful skill to practice daily) rather than logic per se. The logic mainly comes in working out the patterns.
Let’s explore this with Queens. The puzzle has simple rules. The board is divided into coloured territories and you must place a Queen in each territory. However, no two Queens can be in the same row or column. Also no two Queens can be adjacent, horizontally, vertically or diagonally.
If we were just to use pure logic on these puzzles we would perhaps return to the rules themselves constantly to try and deduce where Queens go. That is perhaps how novices try to solve puzzles (and possibly get frustrated and give up). Instead, those who are good at puzzles create higher level rules that are derived from the basic rules. Then they apply (ie pattern match against) the new rules whenever the situation applies. As an aside this is exactly how I worked when using machine-assisted proof to prove that programs and hardware correctly met their specification, doing research into better ways to ensure the critical devices we create are correct.
Let’s look at an example from Queens. Here is a puzzle to work on. Can you place the 8 Queens?
mage by Paul Curzon
mage by Paul Curzon
Where to start? Well notice the grey territory near the bottom. It is a territory that lives totally in one column. If we go to the rules of Queens we know that there must be a Queen in this territory. That means that Queen must be in that column. We also know that only one Queen can be in a column. That means none of the other territories in that column can possibly hold a Queen there. We can cross them all out as shown.
In effect we have created a new derived inference rule.
IF a territory only has squares available in one column
THEN cross out all squares of other territories in that column
By similar logic we can create a similar rule for rows.
Now we can just pattern match against the situation described in that rule. If ever you see a territory contained completely in a row or column, you can cross out everything else in that row/column.
In our case in doing that it creates new situations that match the rule. You may also be able to work out other rules. One obvious new rule is the following:
IF a territory only has one free space left and no Queens
THEN put a Queen in that free space
mage by Paul Curzon
We can derive more complicated rules too. For example, we can generalise our first rule to two columns. Can you find a pair of territories that reside in the same two columns only? There is such a pair in the top right corner of our puzzle. If there is such a situation then as both must have a Queen, between them they must be the territories that provide the Queens for both those two columns. That means we can cross out all the squares from other territories in those two columns. We get the rule:
IF two territories only have squares available in two columns
THEN cross out all squares of other territories in both columns
Becoming good at Queens puzzles is all about creating more of these rules that quickly allow you to make progress in all situations. As you apply rules, new rules become applicable until the puzzle is solved.
Can you both apply these rules and if need be derive some more to pattern match your way to solving this puzzle?
It turns out that programming is a lot like this too. For a novice, writing code is a battle with the details of the semantics (the underlying logical meaning) of the language finding a construct that does what is needed. The more expert you become the more you see patterns where you have a rule you can apply to provide the code solution: IF I need to do this repeatedly counting from 1 to some number THEN I use a for loop like this… IF I have to process a 2 dimensional matrix of possibilities THEN I need a pair of nested for loops that traverse it by rows and columns… IF I need to do input validation THEN I need this particular structure involving a while loop… and so on.
Perhaps more surprisingly, research into expert behaviour suggests that is what all expert behaviour boils down to. Expert intuition is all about subconscious pattern matching for situations seen before turned into subconscious rules whether expert fire fighters or expert chess players. Now machine learning AIs are becoming experts at things we are good at. Not suprisingly, what machine learning algorithms are good at is spotting patterns to drive their behaviour.
Ariane 5 on the launch pad. Photo Credit: (NASA/Chris Gunn) Public Domain via Wikimedia Commons.
If you spent billions of dollars on a gadget you’d probably like it to last more than a minute before it blows up. That’s what happened to a European Space Agency rocket. How do you make sure the worst doesn’t happen to you? How do you make machines reliable?
A powerful way to improve reliability is to use redundancy: double things up. A plane with four engines can keep flying if one fails. Worried about a flat tyre? You carry a spare in the boot. These situations are about making physical parts reliable. Most machines are a combination of hardware and software though. What about software redundancy?
You can have spare copies of software too. Rather than a single version of a program you can have several copies running on different machines. If one program goes wrong another can take over. It would be nice if it was that simple, but software is different to hardware. Two identical programs will fail in the same way at the same time: they are both following the same instructions so if one goes wrong the other will too. That was vividly shown by the maiden flight of the Ariane 5 rocket. Less than 40 seconds from launch things went wrong. The problem was to do with a big number that needed 64 bits of storage space to hold it. The program’s instructions moved it to a storage place with only 16 bits. With not enough space, the number was mangled to fit. That led to calculations by its guidance system going wrong. The rocket veered off course and exploded. The program was duplicated, but both versions were the same so both agreed on the same wrong answers. Seven billion dollars went up in smoke.
Can you get round this? One solution is to get different teams to write programs to do the same thing. The separate teams may make mistakes but surely they won’t all get the same thing wrong! Run them on different machines and let them vote on what to do. Then as long as more than half agree on the right answer the system as a whole will do the right thing. That’s the theory anyway. Unfortunately in practice it doesn’t always work. Nancy Leveson, an expert in software safety from MIT, ran an experiment where different programmers were given programs to write. She found they wrote code that gave the same wrong answers. Even if it had used independently written redundant code it’s still possible Ariane 5 would have exploded.
Redundancy is a big help but it can’t guarantee software works correctly. When designing systems to be highly reliable you have to assume things will still go wrong. You must still have ways to check for problems and to deal with them so that a mistake (whether by human or machine) won’t turn into a disaster.
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.
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.
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
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.
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)
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.
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.
Computers get faster and faster every year. How come? Because computer scientists and electronic engineers keep thinking up new tricks, completely new ways to make them go faster. One way has been to shrink the components so signals don’t have as far to go. Another is to use the same trick they were using in a beach car park I came across on holiday.
Woolacombe Sands in Devon is one of the most popular beaches around. There is a great expanse of beautiful sand as well as rocks for kids to climb on and good surfing too. The weather is even good there – well most of the time. The car park, right on the edge of the beach fills in the morning. Since most people arrive early and stay all day it’s a standard price of £5.50 for the day. Entry and exit barriers control the numbers. The entry barrier only allows a car to go in if there is a space and another allows people out when they have paid.
That’s where there is a problem though. The vast majority of people leave around 5pm as the ice cream vans pack up and it’s time to look for dinner. The machine only takes coins, and you insert the money from your car at the barrier. Each driver has to fumble with 5 one-pound coins and a 50p and that takes time. Once the current car moves on out there is then another delay as the driver behind pulls forward to get into a position to put their money in. Without some thought it would lead to long queues behind. Not only that it wouldn’t be very green. Cars are at there worst pumping out pollution when in a jam.
The last thing you want to do to a family who’ve had a great day on your beach is then irritate them by clogging them up in a traffic jam when they try to leave. So what do you do? How can you speed things up (and make sure you aren’t just moving the queue to the morning or to some other ticket machine somewhere else)?
The problem is similar to one in designing a computer chip. Think of the cars as data waiting to be processed (perhaps as part of a calculation) and the barrier as a processing unit where some manipulation of that data is needed. Data waiting to be processed has to be fetched before it can be used, just as the cars have to move up to the barrier before the driver can pay. The fact that the problems are so similar suggests that a solution to one may also be a a solution to the other.
Speed it up
There are lots of ways you could change the system to improve the speed of cars being processed in the car park. This speed that data passes through a system is called the ‘throughput’ of the system. Woolacombe have thought of a simple way to improve their throughput. They put a person with a bit of change next to the barrier to help the drivers. This allows them to keep the relatively simple barrier system they have. It also has advantages in keeping the money in one place and being a foolproof way of ensuring there is a space for everyone who enters. It still maintains all the safeguards of the ticket barrier though. How can that one person speed things up?
What would you do?
So what would YOU do if you were that person? Would you speed things up? Or would you just stand there powerless watching the misery of all those families?
The first thing you could do is to stand by the machine and take the change off the driver and insert it yourself. That will speed things up a little bit because it takes longer for drivers to put the money in as they have to stretch out the window of a car. Also if the driver only has a five pound note you can take it and just insert coins from your change bag rather than wasting time passing it back to the driver to then insert. Similarly if the driver only has 50 pence pieces say, rather than wasting time inserting 10 of them you can take them and insert 5 one-pound coins.
You’ve done some good, and removed problems of the slow people inserting coins but you haven’t really solved the bad problems. Cars aren’t moving at all while you are inserting the 6 coins, and after each car moves through the barrier you are doing nothing but waiting for the next car to pull forward. In an ideal system, with the best throughput, the cars barely stop at all and you are constantly busy.
A Pipeline of Cars
It turns out you can do something about that. It’s called pipelining. There is a way you can be busy dealing with the next car even before it’s got to you. You just have to get ahead of yourself!
How? Before the first car arrives, insert 5 pound coins into the machine and wait. As the driver gets to you and gives you the money, insert his or her 50p, keeping the rest. The barrier opens immediately for the driver who barely has to stop. Better still you are now holding 5 pound coins that you can insert as the next car arrives, leaving you back in an identical situation. That means the next car can drive straight through too, and you are constantly busy as long as there are cars arriving.
Speedy data
So you’ve helped the families leaving the beach, but how might a similar trick speed up a computer? Well you can do a similar thing in the way you get a computer processor to execute the instructions from a program. Suppose your program requires the processor to get some numbers from storage, process them (perhaps multiplying the numbers together) and then store the result somewhere else for later use. Typically a program might do that over and over again, varying where the data comes from and how it is processed.
Early computers would do each instruction in turn – doing the fetching, processing and storing of one instruction before starting the next. But that is just like a car in our car park coming to the barrier, being processed and leaving before the next one moves. Can we pull off the same trick to speed things up? Well, yes of course.
All you need to do is overlap the separate parts. Just as at any time in the car park a car will be driving out, a second will be handing over money and a third pulling forward, the same can happen in the computer. As the first instruction’s result is being stored, the next instruction can already be being processed and the data from the one after that can be fetched from memory. Just by reorganising the way the work is done, we have roughly tripled the speed of our computer as now three things are happening at once.
What we have done is set up a ‘pipeline’ – with a series of instructions all flowing through it, being executed, at the same time. Woolacombe has a pipeline of cars, but in a computer we pipeline data. Either way things get done faster and people are happier.
Computer science happens in some unexpected places – even at the beach – but then perhaps that isn’t so surprising given computers are made of sand!
Other beach-themed articles on this blog include how the origins of how Paul learned to program while on holiday (“The beach, the missionary and my origin myth”) and messages hidden (steganography) within the stripes of deckchairs (“Encrypted deckchairs”).
The Formula 1 car screams to a stop in the pit-lane. Seven seconds later, it has roared away again, back into the race. In those few seconds it has been refuelled and all four wheels changed. Formula 1 pit-stops are the ultimate in high-tech team work. Now the Ferrari pit stop team have helped improve the hospital care of children after open-heart surgery!
Open-heart surgery is obviously a complicated business. It involves a big team of people working with a lot of technology to do a complicated operation. Both during and after the operation the patient is kept alive by computer: lots of computers, in fact. A ventilator is breathing for them, other computers are pumping drugs through their veins and yet more are monitoring them so the doctors know how their body is coping. Designing how this is done is not just about designing the machines and what they do. It is also about designing what the people do – how the system as a whole works is critical.
Pass it on
One of the critical times in open-heart surgery is actually after it is all over. The patient has to be moved from the operating theatre to the intensive care unit where a ‘handover’ happens. All the machines they were connected to have to be removed, moved with them or swapped for those in the intensive care unit. Not only that, a lot of information has to be passed from the operating team to the care team. The team taking over need to know the important details of what happened and especially any problems, if they are to give the best care possible.
A research team from the University of Oxford and Great Ormond Street Hospital in London wondered if hospital teams could learn anything from the way other critical teams work. This is an important part of computational thinking – the way computer scientists solve problems. Rather than starting from scratch, find a similar problem that has already been solved and adapt its solution for the new situation.
Rather than starting from scratch, find a similar problem that has already been solved
Just as the pit-stop team are under intense time pressure, the operating theatre team are under pressure to be back in the operating theatre for the next operation as soon as possible. In a handover from surgery there is lots of scope for small mistakes to be made that slow things down or cause problems that need to be fixed. In situations like this, it’s not just the technology that matters but the way everyone works together around it. The system as a whole needs to be well designed and pit stop teams are clearly in the lead.
Smooth moves
To find out more, the research team watched the Ferrari F1 team practice pit-stops as well as talking to the race director about how they worked. They then talked to operating theatre and intensive care unit teams to see how the ideas might work in a hospital handover. They came up with lots of changes to the way the hospital did the handover.
For example, in a pit-stop there is one person coordinating everything – the person with the ‘lollipop’ sign that reminds the driver to keep their brakes on. In the hospital handover there was no person with that job. In the new version the anaesthetist was given the overall job for coordinating the team. Once the handover was completed that responsibility was formally passed to the intensive care unit doctor. In Formula 1 each person has only one or two clear tasks to do. In the hospital people’s roles were less obvious. So each person was given a clear responsibility: the nurses were made responsible for issues with draining fluids from the patient, anaesthetist for ventilation issues, and so on. In Formula 1 checklists are used to avoid people missing steps. Nothing like that was used in the handover so a checklist was created, to be used by the team taking on the patient.
These and other changes led to what the researchers hoped would be a much improved way of doing handovers. But was it better?
Calm efficiency saves the day
To find out they studied 50 handovers – roughly half before the change was made and half after. That way they had a direct way of seeing the difference. They used a checklist of common problems noting both mistakes made and steps that proved unusually difficult. They also noted how well the teams worked together: whether they were calm and supported each other, planned what they did, whether equipment was available when needed, and so on.
They found that the changes led to clearly better handovers. Fewer errors were made both with the technology and in passing on information. Better still, while the best performance still happened when the teams worked well, the changes meant that teamwork problems became less critical. Pit-stops and open-heart surgery may be a world apart, with one being about getting every last millisecond of speed and the other about giving as good care as possible. But if you want to improve how well technology and people work together, you need to think about more than just the gadgets. It is worth looking for solutions anywhere: children can be helped to recover from heart surgery even by the high-octane glitz of Formula 1.
.jpg)
cs4fn 