Pre-Lesson Preparation

• Teachers will need to have a piece of paper with a unique number on it for all but one student in the class.
• Students will need access to the datasets and Python skeleton code in the Lesson Resources folder.
• Teachers will need to print out the "Search Comparison Worksheet" for each student.

Summary

Students investigate data organization, simulate linear and binary searches, and write pseudocode and Python for linear and binary search methods.

Outcomes

• Students will recognize the differences between linear search and binary search and will be able to recognize which method is suitable for a given problem.
• Students will be able to code both binary and linear searches.

Overview

Session 1

1. Getting Started (5 min)- Journaling
2. Class Discussion and Activities (25 min) - Introduction to linear and binary search algorithms
3. Coding Linear Search (20 min)

Session 2

1. Getting Started (5 min) - Think-Pair-Share 
2. Coding Activity (30 min) - Write pseudocode and implement binary search
3. Compare Searches (15 min) - Fill out worksheet to compare search algorithms

Source

Phone book presentation adapted from a lesson taught by Dr. Rheingans in CMSC 201 at the University of Maryland, Baltimore County

• MP1: Make sense of problems and persevere in solving them.
• MP2: Reason abstractly and quantitatively.
• MP6: Attend to precision.
• MP7: Look for and make use of structure.

• F-BF.1-2: Build a function that models a relationship between two quantities

• RST 12.3 - Precisely follow a complex multistep procedure

• 2. Developing and using models
• 3. Planning and carrying out investigations
• 5. Using mathematics and computational thinking

Students will:

• Understand the definition of a search.
• Be able to identify how the order of data influences which methods are appropriate for searching the data.
• Be able to describe linear and binary search algorithms in pseudocode and in Python.
• Understand the concept of efficiency when searching for an item.

• How does abstraction help us in writing programs, creating computational artifacts and solving problems?
• How can computational models and simulations help generate new understanding and knowledge?
• How can computation be employed to help people process data and information to gain insight and knowledge?
• What considerations and trade-offs arise in the computational manipulation of data?
• What opportunities do large data sets provide for solving problems and creating knowledge?
• How do computer programs implement algorithms?
• How does abstraction make the development of computer programs possible?

In Lesson Resources Folder:

• Search Comparison Worksheet to use at the end of Session 2
• DataSets folder that contains the six datasets for the Search Comparison Worksheet
• SearchCode.py contains skeleton code for a numeric search program

Session 1

Getting Started (5 min)

Journal: What would be the best way to organize a collection of DVDs so that you could find the one you want very quickly? Discuss.

Class Discussion and Activities (25 min)

Linear Search Discussion (5 min)

As a class, discuss the following question: What is the most effective way to look for an item in an unordered set of values?

Possible Answers:

• Randomly (How do you stop yourself from repeating yourself?)
• One-by-one

Linear Search Activity (5 min)

1. Pass out pieces of paper with numbers on them to everyone in the class except one person. Students should not share their numbers with anyone.
2. Have everyone stand at the front of the room in a line. The person without a number stands in front and is assigned a number to look for. The class should keep track of how many people they have to ask before they get the number (students that have been checked should sit down).
   • Do this activity a few times. In between, each student should switch with another student a couple of times without showing their paper. (Note: A fun way to do this might be a snowball fight if you can)
   • Ask for a number that does not exist in the set at least once. What happens? How many people does it take before they figure out the number is not in the set?
3. Have everyone sit down but keep their papers.

Binary Search Discussion and Presentation (10 min)

Take out a dictionary (or phone book). Ask the class, how would you search for a particular word/name?

Steps for Binary Search in a book of items to demonstrate to the class:

1. Flip to the middle and pick a word in the middle of the page
2. Is your word higher or lower than this word? If it is higher, “throw out” the lower half of the book. If it is lower, “throw out” the top half. (Not literally unless it is a very old phonebook. Students do love it when you tear up the phonebook, though, and it makes for a very effective demonstration.)
3. Repeat steps 1 and 2 until you find the word.

Why would this not work for an unordered list?

Binary Search Activity (5 min)

1. Have everyone go to the front of the room and get in numerical order by paper. Repeat the search activity using the binary search algorithm.
2. Try with a number not in the list. How can you tell when it doesn’t exist?

Coding Linear Search (20 min)

1. Have students work in pairs to write a code for linear search. The code should:
   1. Read in a csv file that has a list of unordered numbers. (They should input the file name from the user.)
   2. Ask the user what number they want to find and validate that number.
   3. Tell the user whether the number was found. If it was, it should output the number of items it had to look at.
2. Students should save their code for the next day.

Note: Skeleton code (SearchCode.py) is provided in the Lesson Resources Folder.

Session 2

Getting Started (5 min) 

Think-Pair-Share

• Ask students to list non-numbered, real-world things that they search for or sort/order in their daily lives.
• Can all data be sorted, or do types of data exist that cannot be sorted? How would you organize and search these types of data?

Coding Activity (30 min)

Part 1 Pseudocode (10 min)

1. As a class, write down the steps for Binary Search on the board.
2. In pairs, have the students write pseudocode for how they would implement binary search.

Part 2 Coding (20 min)

1. Students should use their pseudocode to write a program for binary search. (They can also make use of the skeleton code provided for linear search.) The code should accomplish the same things as linear search: read in a file, get a number, and output if the number is found and how many items were checked.

Comparing Searches (15 min) – (May also be Homework if programs are not finished)

• Pass out the worksheet "Search Comparison Worksheet" from the lesson resources folder.
• Students should run both their linear and binary search programs with the six provided datasets of increasing sizes, (also in the lesson resources folder.)
• As they go through, students should record their results in the worksheet and answer the questions at the bottom.
• Discuss the results as a class.

For students that have difficulty understanding the concepts of searching for items in a set of data, pair those students with a student who has a firm grasp of the concept for the activities. Have the pair work together for 1A and then have them keep their own paper secure using the extra game sheet (1A').  Simiilarly for 1B - 1B' and 1C - 1C'.

Correctness of Python functions for linear search and binary search

"Searching Assessment Items.docx" in lesson folder

"Search Comparison Worksheet" in the lesson folder