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? Would you need a different method for a radio station with thousands of DVDs? Discuss.
Class Discussion and Activities (25 min)
Linear Search Discussion (5 min)
As a class, discuss the following questions:
What if you are looking for a specific song. What is the most effective way to look for something if it is in an unordered, unsorted collection?
What are some challenges to organizing large sets of information so they can be processed?
Why does it help to classify data when you are trying to sort it or search through it?
Possible Answers and suggestions for discussion:
- You can search Randomly (How do you stop yourself from repeating yourself?)
- You can search One-by-one, marking off which ones have already been checked.
- You can divide up the problem and each search a pile (multiprocessing)
- Challenges: data entry is time consuming. Large sets of data are more important to keep organized but if you combine information from multiple places they might be organized differently so you have to come up with a single system.
- If you don’t classify the information you’re sorting or searching such as the album title, song title or other searchable information, it would be very confusing to try to find what you are looking for, especially if you don’t know exactly what you are trying to find.
- Having things grouped by artist, genre, or other categories makes it easier to narrow down what you're looking for.
Linear Search Activity (5 min)
- 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.
- 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?
- 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:
- Flip to the middle and pick a word in the middle of the page
- 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.)
- Repeat steps 1 and 2 until you find the word.
Why would this not work for an unordered list?
Binary Search Activity (5 min)
- 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.
- Try with a number not in the list. How can you tell when it doesn’t exist?
Coding Linear Search (20 min)
- Have students work in pairs to write a code for linear search. The code should:
- Read in a csv file that has a list of unordered numbers. (They should input the file name from the user.)
- Ask the user what number they want to find and validate that number.
- Tell the user whether the number was found. If it was, it should output the number of items it had to look at.
- Students should save their code for the next day.
Note: Skeleton code (SearchCode.py) is provided in the Lesson Resources Folder.
Getting Started (5 min)
- 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?
- Is there always a "correct" solution when sorting data?
Coding Activity (30 min)
Part 1 Pseudocode (10 min)
- As a class, write the major steps for Binary Search on the board.
- Identify algorithms that could be combine to make a binary search algorithm.
- In pairs, have the students pseudocode a binary search algorithm.
- Discuss the advantages of using established algorithms.
Part 2 Coding (20 min)
- Students should use their pseudocode to write a program for binary search. (It would be useful to build on 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.
Guidance for Practice Questions - Question Set 20
Questions in the AP Classroom Question Bank may be used for summative purposes.
Sixty of the 80 questions are restricted to teacher access. The remaining 20 questions are from public resources.
Questions are identified by their initial phrases.
A code segment will be used to swap the values of
A programmer is deciding between using a linear...
A programmer wrote the code segment below to di...
An algorithm will be used to identify the maximum
In the procedure Mystery below, the parameter n...
The program segment below is intended to move a...
The question below uses a robot in a grid of sq...
There are 32 students standing in a classroom. ...
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'.