Part of Unit: AP Concepts Using BYOB/SCRATCH
Lesson Plan Overview / Details
The goal of this lesson is to use a number guessing game as a scaffolding tool for teaching the concept of binary searching. The game is created in BYOB/Scratch. AP Computer Science teachers may use this lesson to scaffold the search algorithm before implementing the Java code version.
- 1 Class Period
California's 2008 CTE Standards
- IT.D.D2.1 Know the fundamentals of programming languages and concepts.
- IT.D.D2.2 Compare programs by using control structures, procedures, functions, parameters,...
California Academic Content Standards (Reinforced)
- ELA.9-10.R.CAGT.2.6 Demonstrate use of sophisticated learning tools by following technical direction...2
Objectives and Goals
- Understand the binary search algorithm
- Understand program interface design as it pertains to user interaction
Activities in this Lesson
- Hook Hooks / Set
Students observe an animated sprite of Albert Einstein saying "Think of a number between 1 and 1000. I can find it in 10 or fewer guesses: " This is displayed on the overhead projector as they walk in the classroom.
A student volunteer plays the game indicating after each response by "Albert Einstein" whether the guess is too high, too low, or correct. Students are asked if they can explain the logic behind the program.
Students are asked if they can explain why 10 would be the maximum number of guesses for a number in the range of 1 to 1000.
The concept of binary searches is covered in the Lecturing Activity.
The completed game is downloadable from this website. Make sure you use the version of BYOB/Scratch available from http://byob.berkeley.edu
- Lecture Lecture
Binary search algorithms typically halve the number of items to check with each successive iteration.
Essentially, they are used to find an item in a list that is already sorted. It is important to stress that this kind of search does not apply to unsorted lists.
The simple guessing game demonstrated in the hook activity works by repeatedly dividing the possible choice of numbers in half until the correct number is reached.
A useful website for in depth discussion of the issue:
- Demo/Modeling Demo / Modeling
Demonstrate on the board the workings of the binary guessing game with a much smaller range: 1 to 10l
Write the list of numbers on the board
1 2 3 4 5 6 7 8 9 10
A student volunteer says he has thought of a number between 1 and 10 inclusive.
Have the student write the number on a piece of paper that he/she keeps folded.
Let's pretend the number is 7.
Say, "Is the number 5?" (You arrive at this number by dividing (1 + 10)/2 = 5.5. The integer portion is 5.
The student should say, "too low."
You cross out the numbers from 1 to 5. The remaining list is now
6 7 8 9 10
Say, "Is the number 8?" (You arrive at this number by dividing (6 + 10)/2 = 8.
The student should say, "too high."
You cross out the numbers from 8 to 10. The remaining list is
Say, "Is the number 6?" (You arrive at this number by dividing (6 + 7)/2 = 6.5. The integer portion is 6.
The student should say, "too low."
You cross out the 6. The remaining number is 7.
Say, "Is the number 7?"
The student should say, "correct."
There are at most log 2N questions required.
A simple way to say this is that four maximum questions are required for 10 numbers because 2 raised to the power of 4 is 16. 2 raised to the power of 3 is not enough to cover 10 possibilities because it is only 8.
- Check Understanding Check Understanding
Have students model the guessing game as you just did for another range of anothers, for example 40 to 50.
Ask students how many possible guesses it would take to guess a number in the 1 to 100 range. (Answer 7)
Ask students how many possible guesses it would take to guess a number in the 1 to 100 range. (Answer 10)
- Guided Practice Guided Practice
At this point students should develop an algorithm for carrying out the binary search number guessing game.
Note that we also need to find a means to round numbers down in order to carry out the solution as noted in the Modeling Activity.
Here is what such a block might like.
- Independent Practice Independent Practice
The goal of this exercise is for students to replicate the number guessing game on their own using BYOB/Scratch. There may be variety in the look and feel of the program, but the main functioning of the guessing game should work correctly and demonstrate knowledge of the binary search approach.
Here is the basic approach needed.
- Closure Closure
For a closing activity, have students play their binary guessing game in pairs.
You may want to give the students the rubric and have them self-evaluate or evaluate their partner's game.
Check for knowledge of all programming algorithms as well as the use of the BYOB/Scratch algorithm.
Also check for the students' ability to verbally explain the logic behind the algorithm.
BYOB/Scratch has a section called Project Notes located under the File menu where students can write descriptions of their programs.
The rubric contained in the following section is for a game based on a fixed range such as 1 to 1000.
You may wish to have students extend the game by having the option to set the range at the beginning of the game.
- Assessment Types:
- Rubrics, Projects, Demonstrations, Observations,
100 point scale
50 pts. Correctly re-adjust each succeeding guess using the binary search algorithm.
30 pts. User interface is complete. All necessary buttons present and functioning correctly.
10 pts. Game resets itself when play button is pressed.
10 pts. Keep track of the number of guesses.