Students are shown the idea of binary search. The idea is based on human robots -exercise.
| Creator | Mikko Muilu |
| Subject | Math, ICT |
| Length | 45 minutes |
| Pedagogical Approach | Phenomenon-based learning |
| Competences | Students learn what an algorithm means Students learn that there are different ways to retrieve certain numbers and some ways are considerably faster than others Students learn simple algorithm principles Students learn how to use the programming-related if statement in practice |
| Grades | Students aged 9-12. |
| Technologies | Pen and paper |
Description
The activity needs an even number of students. They are divided into pairs. The other person in a pair comes up with a number from the agreed range. The other person tries to guess the number by asking questions. Th person who decided the number can answer these questions only with ‘yes’ or ‘no’. What is the quickest way to find the desired number?
Introduction
The principle of algorithms is explained to the students (attachment 1) and how the algorithms follow certain instructions to always provide a solution regardless of the data that is given to them. The students can be reminded of the human robot exercise and they are advised to closely follow the provided instructions.
Assignment 1
The teacher assigns the students into pairs. First one is the searcher and the other one is the answerer. The answerer picks a number between 1 and 50 and writes the number on paper. When they are done, the searcher starts to ask questions and the answerer can only answer ‘yes’ or ‘no’. In the beginning, someone may be inquiring about individual numbers (‘Is it two?’, ‘Is it three?’). If they do not come up with the possibility to narrow the set down by asking questions such as ‘Is it bigger than 10, they can be guided to the right direction. The idea of the exercise is explained in the video below.
Discussion: How many guesses did it take to find the right number? What kind of tactics did the students have? How the number of guesses with the different tactics would change, if the number was between 1 and 1 000?
The teacher explains the principle of binary search: If the search range is between 1 and 1 000, it is first important to inquire is the number greater than 500 (middle of the search). After that, the remaining set is divided to half with a similar question and this is continued until the desired number can be reached.
https://youtu.be/vV7TR6_moug
Assignment 2
Let’s start with the range from 1 to 1 000. The student practice the binary search and if they desire, they can try out another way of finding the number. The students count how many guesses are needed to find the right number. What happens, if the range is from 1 to 10 000? What about one to million, or one to billion?
Discussion:
What did the students notice about the number of guesses? Why didn’t the number of guesses grow very rapidly? How many guesses were needed to find a number between one and one million?
You can tell the older students about the power of two and how quickly it grows. Each search cuts the number set to half, making it easier to find the desired number. In other words, when the number set doubles, you only need one more question. The picture below explains the power of two. The number two is multiplied with itself as many times as is stated in the exponent. The picture also explains the number of guesses needed for successful binary search. If the number range is 128, you need up to seven questions to find the right number (2 multiplied by itself seven times equals 128). The power of two tells the maximum amount of questions needed to find the desired number.
Assignment 3
If there is time, the students can also try in practice whether or not the previously made statement actually makes sense.
Attachment 1
Algorithms are sets of instructions that enable achieving a desired outcome. Basically, these instructions can be any kind of instructions, for example the ones that we can see in cook books. However, usually when algorithms are discussed, we often refer to mathematical instructions or instructions that are meant for a computer to understand. The binary search that we practice here is a search algorithm. Many search and ordering algorithms are used in information technology, but also for example in targeting commercials to people using the Internet.