How would you find the a book on a bookshelf, when all the books aren’t in any particular order?
Are there any other methods you could use?
Potential answers
Guide students to discuss the algorithm or process that they would use to find a value in an unsorted list and how that would be harder than in a sorted list.
Help them to recognise that the only way to search the unsorted list is to go through every item (whether they choose randomly or look at the first, then second, then third…) because they are still just checking and eliminating one at a time.
Lesson starter
On each sheet are 31 number boxes with lots of money in them. All money has a serial number on it and in each of the number boxes all the notes start with the same serial number.
The only problem is there is only one number box that has the real money in it, the rest are fake.
You know what the serial number on the real money is, and your challenge is to find the number box with the real money in it, but you should "open" as few number boxes as possible.
Guide students through how the game will work by following the instructions on the Number Hunt.
Teaching observations
If students make the connection that the real money serial could have a check digit, they would be correct in that what they learnt in the error detection and correction unit would apply in knowing if the serial number represents real money or fake money.
Here’s a link to the Error Detection and Correction topic for more information.
However, this isn't the purpose of this exercise; the goal is to find a number in the number boxes.
Mathematical Links
This is a teachable moment for the class to discuss different strategies to ensure the least number of guesses are needed.
The only useful strategy in this case is to make sure that you don't ask for the same box twice i.e. record which ones you have looked at.
This will give a number of guesses between 1 and the total number of boxes.
Statistics: Gather the raw data of the number of guesses made by each student and graph it on a bar chart.
Repeat the game a number of times to see what the pattern of data is.
Number Knowledge: Read and say numbers between 100 and 9999.
Lesson activities
Organise your class into pairs.
They need a hard surface to write on and a pencil or pen (or whiteboard pen if you have laminated the sheets).
Go through the instructions and set up their games.
Play the game and have students add up how many guesses it took each of them to find the number box with the correct number in it.
Add this data to either a class sheet to graph on paper or add it to a spreadsheet that also displays the graph and what the graph grow as more data becomes available.
Teaching observations
It is recommended to have the activity from lesson one and lesson two set up for students to move on to when they have both finished guessing their numbers, or else new sheets with different numbers on for them to try again.
As the range of guesses could be the first guess through to 31 guesses, the time delay for everyone finishing means that some students will have nothing to do for 10 or 15 minutes.
Having the other searching algorithm games available helps with classroom management.
Applying what we have just learnt
The method you have been using is called sequential search - if the values are out of order then we just go through them one-by-one, in some sequence, until we find the one we want.
Some people probably found the number in one or two questions, while others may have "opened" most of the 31 boxes before they found it.
This algorithm is very variable in the time taken - sometimes it's instant, sometimes it's slow, and on average, you'll go halfway through the list of values.
Lesson reflection
Can you write down the algorithm for a sequential search for the Number Hunt game?
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
In this lesson we used the same algorithm and algorithmic thinking as we did in lesson 1, but applied it to number boxes instead of the numbers being guessed.
Just like in lesson 1, if we check in every number box then we are guaranteed to find the real money at some stage (unless all the money is fake!)
From lesson 1: 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:
Who are the students who not only can explain the exact process to find the real money, but are also the students who don’t deviate from that process?
Do they realise that if the value isn't there, then every box will have to be opened to find that out?
Abstraction
As in lesson 1, we can ignore many details about the items we are searching for.
For example it doesn’t matter if the money is in New Zealand dollars/$, Japanese yen/¥, or pounds/£.
You only need to focus on the serial numbers and remember that the boxes are in order, as this is all the information you need to solve the problem.
Examples of what you could look for:
What questions are students asking about the number boxes?
Organise them into useful questions and no as useful questions.
Which students can identify quickly what the relevant information is?
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:
Which students quickly understand that this is actually no different to playing the “how many guesses game” in lesson one?
Evaluation
Students will be evaluating sequential search when they collect and examine the statistics of how many boxes they had to check.
They can further evaluate it by collecting the number of guesses it takes to search through larger numbers of boxes and examining these statistics.
For example, what do students think will happen if there are twice as many boxes to search through? 10 times as many? 1,000,000 as many? Would this algorithm be efficient for this many boxes?
Examples of what you could look for:
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.
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 money if the boxes where in sorted order?
Ask the students if it would be worth sorting these boxes into order, and look for the students who can identify why this might not be worth it if you're only doing the search once (we only need to search through the boxes once because once we’ve found the money there is no point looking for it again! So sorting them wouldn’t be helpful, it would actually slow things down).
This definition is not available in English, sorry!