Suppose you lent a friend your favourite book to read and can’t remember who you lent it to.
Imagine these 6 houses represent where they live.
You need it back urgently because you are going on holiday tomorrow, so you start visiting each house to see if they have your book.
How many houses do you predict you will need to visit to find the one where your book is?
Write the number of guesses you think and your initials on a post-it note.
Place your post-it on a continuum like the one below.
What do you notice about our predictions?
Potential answers could include:
That we had different numbers of guesses, because you might get lucky and find your book at the first house, but you might also could be unlucky and find your book at the last house.
Three and four guesses are likely to be popular because that’s approximately half way (this is indeed close to the average that could be expected).
Some students might choose 6 guesses; that is the most that would ever be needed.
Teaching observations
Students might expect that they could be 'lucky' and find the book early, or they might pessimistically go for the worst case, where it's in the last few houses that they visit.
The activity below will illustrate that both of these cases could happen, but the actual number will be randomly distributed, so there's no simple answer to the question.
Lesson starter
Place the 15 searching squares on a table.
Explain that we have 15 different numbers, one on each card.
Show that one side has an animal on it and the other a number.
Under each of these cards is a number that you can’t see, and they aren’t in order.
The numbers range from 1 to 15.
Can you find the card with the number 12?
Teaching observations
You can adapt the range to suit what your students are working on in their mathematics lessons.
This lesson focuses on unsorted lists so it doesn’t matter if the numbers are all from a sequential range (for example: all the numbers in the range from 1 - 15), as long as the cards are placed in a random order.
When you’re using a sorted list in future exercises though it works better to not have all the numbers from a certain range, otherwise students can just count to figure out where the number is!
You can generate different sets of cards with various ranges of numbers here.
Lesson activities
Set up a line of 15 cards, with the animal facing upwards.
Have a payment system ready such as tokens for your classroom, counters, sweets, or marbles.
The game could be set to have some real stakes - for example: I have 10 marbles, and each is worth 2 minutes of free time.
For every guess you make you have to pay me one marble.
Say to the students: let’s see how many guesses it takes to find the number 4.
Who would like the first guess? (Choose a student).
Which animal should I turn over?
Tell us why you chose that guess.
(There's no particular logic for which card to choose, but students might choose to be methodical and go from left to right, or simply choose cards at random.)
Turn over the chosen card to show the number under it.
If it's the correct one, you can stop, otherwise remove it from the row and put it aside and have the student pay you with one marble (or with whatever you are using as tokens).
Repeat this process until a student chooses the card with your number on it (you should carry on even if they have lost all their tokens).
If at the end of the game the student has no tokens left then you have one, and if they found it before using all their marbles then they win the game.
If you find they guessed the number quickly, then shuffle the cards and repeat the game to demonstrate that they might guess on the first guess, but likewise it could be the very last guess as well.
At the beginning of a new game the student starts with all their tokens again.
How many guesses did it take to find the number this time?
With each guess, how many cards were eliminated from being a possibility? (Answer one - each question can only get rid of one option).
Did the students win because they guessed within 10 guesses or did you win because it took them longer and they lost all their tokens?
Repeat this game until the students have won 3 times or you have won 3 times.
You should shuffle the cards each time, and introduce new cards or different sets if necessary to avoid students memorising what is on each card.
Teaching observations
The number of guesses required can be anything from 1 (if you are lucky and find the number on the first guess), to 15 (if you’re very unlucky and have to turn over every card).
The number of guesses should be evenly distributed between 1 and 15 - each number is equally likely.
Students could also work out the average (which should be close to 7 if enough games are played).
This also means that most of the time students won't have any tokens left if you start with 5 for each search.
You can repeat this game using the 0 - 100 searching cards, or you can use the blank searching cards to create your own numbers.
You can also use the blank searching cards to make a game which uses letters, words etc. instead of numbers.
Applying what we have just learnt
This algorithm is a practical one that is sometimes used for searching for data on a computer.
It's very useful to be able to predict how long an algorithm will take.
In this lesson, it might seem unpredictable, but there are some definite conclusions that can be drawn.
For example, if there are 15 cards, you never need to look at more than 15 items, and it's a matter of luck whether you find it very quickly or if it's the last one you look at.
A worse algorithm would be to pick a card at random, check it, put it back, and repeat this until you find what you're looking for; this could theoretically go on forever!
Lesson reflection
The method you have been using is called sequential search - if the values are out of order then we just go through them in some sequence until we find the one we want.
What is the algorithm for a sequential search?
Repeat until the number is found.
Remove one item from the payment system
Turn over a card.
If it isn’t the card you are searching for then remove that card (or leave the card turned over to show the number).
How much longer will this take if we give the algorithm twice as many cards to search? (It will take twice as long, on average.)
We will explore more accurate statistics to measure this at older ages.
Seeing the Computational Thinking connections
Throughout the lessons there are links to computational thinking. Below we've noted some general links that apply to this content.
Teaching computational thinking through CSUnplugged activities supports students to learn how to describe a problem, identify what are the important details they need to solve this problem, break it down into small logical steps so that they can then create a process which solves the problem, and then evaluate this process. These skills are transferable to any other curriculum area, but are particularly relevant to developing digital systems and solving problems using the capabilities of computers.
These Computational Thinking concepts are all connected to each other and support each other, but it’s important to note that not all aspects of Computational Thinking happen in every unit or lesson. We’ve highlighted the important connections for you to observe your students in action. For more background information on what our definition of Computational Thinking is see our notes about computational thinking.
Algorithmic thinking
We used an algorithm in this lesson to find the number we were searching for.
This is an algorithm because it is a step-by-step process that will always give the right solution for any input you give it as long as the process is followed exactly; if we check every card in the list we are guaranteed to find the right number (as long as it is in the list!)
Examples of what you could look for:
Can students work out how many guesses it could take if you mentioned that there are now 100 cards on the table instead of 31?
What would be the smallest number of guesses?
What would be the greatest number of guesses?
What about if you were looking for one number out of a thousand?
If students can answer this question with one being the least amount of guesses or the maximum number of cards being the maximum number of guesses then they are showing a thorough understanding of sequential search.
Abstraction
In this activity there are many details which are irrelevant to the task of finding the right number, and these can be ignored.
For example, it matters that the numbers are all hidden but it doesn’t matter what they are hidden by.
They could be hidden under cups, or rocks, or the students could be blindfolded!
It wouldn’t change the task or the algorithm.
Examples of what you could look for:
If you repeat this exercise but with the numbers underneath different objects, or maybe use different letters of the alphabet or different coloured discs to search for, who are the students that can see that these differences don’t actually matter and they are still solving the same problem?
Which students immediately apply the same searching strategy?
Decomposition
The larger task of “find my number” is broken down into a series of small steps, each of which is simply “check one of the cards to see if your number is there" and eliminate that card if it isn’t the correct one.
This is important because when a computer searches through data this is the most basic step it performs, it can only compare two things at a time so our algorithm must only compare two things at a time.
Examples of what you could look for:
Who are the students who are able to break the problem down into steps and then explain why each step is important?
Which students can articulate that the computer is only checking one number at a time, and so can only eliminate one number at a time.
Generalising and patterns
The generalised idea of this activity is that any searching problem where the data being searched is not organised into some structure or order can only be approached using sequential search.
Recognising this pattern can save students, and programmers, time because when they encounter this problem in the future they are aware that they do not need to spend their time trying to come up with an especially clever solution.
This situation can be generalised to apply to any type of data.
Examples of what you could look for:
Just like with abstraction, if you repeat this exercise but with the numbers underneath different objects, or use different letters of the alphabet, who are the students that can see that these differences don’t actually matter and they are still solving the same problem?
Evaluation
How much longer would this take if there were twice as many cards? 10 times as many cards?
Search engines routinely search through billions of web pages to find the term you're looking for, would this algorithm be efficient for this application?
Discuss other ideas on how you could find a number more effectively.
Examples of what you could look for:
Who are the students who can explain the strengths and potential problems of using a sequential search to find the number?
Logic
Let's think about the problem logically: The cards have been placed in a random order, therefore all we learn when we look at a card is what is on that card, we don’t learn anything at all about what is on the other cards.
Since all we can learn from checking a card is whether or not that card is the one we are searching for, it doesn’t matter what order we check the cards in because it won’t change the fact that we have to check each card, one-by-one, until we find the correct one.
Examples of what you could look for:
Which students can explain why it would be easier to find the number if they were in sorted order?
This definition is not available in English, sorry!