Lesson Summary

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 demonstrate how combining data sources and classifying data are part processing data
  • Students will describe challenges to structuring large data sets for analysis
  • Students will identify how the order of data influences which methods are appropriate for searching the data.
  • Students will describe standard search algorithms in pseudocode and in Python.
  • Students will Compare different algorithms for efficiency when searching for an item.

Overview

Session 1

  1. Getting Started (5 min) - Journal
  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

 

Learning Objectives

CSP Objectives

Big Idea - Creativity
  • EU 1.2 - Computing enables people to use creative development processes to create computational artifacts for creative expression or to solve a problem.
    • LO 1.2.4 - Collaborate in the creation of computational artifacts. [P6]
      • EK 1.2.4A - A collaboratively created computational artifact reflects effort by more than one person.
      • EK 1.2.4D - Effective collaboration strategies enhance performance.
    • LO 1.2.5 - Analyze the correctness, usability, functionality, and suitability of computational artifacts. [P4]
      • EK 1.2.5A - The context in which an artifact is used determines the correctness, usability, functionality, and suitability of the artifact.
Big Idea - Data
  • EU 3.1 - People use computer programs to process information to gain insight and knowledge.
    • LO 3.1.1 - Find patterns and test hypotheses about digitally processed information to gain insight and knowledge. [P4]
      • EK 3.1.1C - Combining data sources, clustering data, and data classification are part of the process of using computers to process information.
  • EU 3.2 - Computing facilitates exploration and the discovery of connections in information.
    • LO 3.2.2 - . Determine how large data sets impact the use of computational processes to discover information and knowledge. [P3]
      • EK 3.2.2C - Structuring large data sets for analysis can be challenging.
Big Idea - Algorithms
  • EU 4.1 - Algorithms are precise sequences of instructions for processes that can be executed by a computer and are implemented using programming languages.
    • LO 4.1.1 - Develop an algorithm for implementation in a program. [P2]
      • EK 4.1.1A - Sequencing, selection, and iteration are building blocks of algorithms.
      • EK 4.1.1B - Sequencing is the application of each step of an algorithm in the order in which the statements are given.
      • EK 4.1.1C - Selection uses a Boolean condition to determine which of two parts of an algorithm is used.
      • EK 4.1.1D - Iteration is the repetition of part of an algorithm until a condition is met or for a specified number of times.
      • EK 4.1.1E - Algorithms can be combined to make new algorithms.
      • EK 4.1.1F - Using existing correct algorithms as building blocks for constructing a new algorithm helps ensure the new algorithm is correct.
      • EK 4.1.1G - Knowledge of standard algorithms can help in constructing new algorithms.
      • EK 4.1.1H - Different algorithms can be developed to solve the same problem.
      • EK 4.1.1I - Developing a new algorithm to solve a problem can yield insight into the problem.
    • LO 4.1.2 - Express an algorithm in a language. [P5]
      • EK 4.1.2A - Languages for algorithms include natural language, pseudocode, and visual and textual programming languages.
      • EK 4.1.2B - Natural language and pseudocode describe algorithms so that humans can understand them.
      • EK 4.1.2C - Algorithms described in programming languages can be executed on a computer.
      • EK 4.1.2G - Every algorithm can be constructed using only sequencing, selection, and iteration.
  • EU 4.2 - Algorithms can solve many, but not all, computational problems.
    • LO 4.2.1 - Explain the difference between algorithms that run in a reasonable time and those that do not run in a reasonable time. [P1]
      • EK 4.2.1A - Many problems can be solved in a reasonable time.
      • EK 4.2.1B - Reasonable time means that the number of steps the algorithm takes is less than or equal to a polynomial function (constant, linear, square, cube, etc.) of the size of the input.
      • EK 4.2.1C - Some problems cannot be solved in a reasonable time, even for small input sizes.
    • LO 4.2.4 - Evaluate algorithms analytically and empirically for efficiency, correctness, and clarity. [P4]
      • EK 4.2.4A - Determining an algorithm's efficiency is done by reasoning formally or mathematically about the algorithm.
      • EK 4.2.4B - Empirical analysis of an algorithm is done by implementing the algorithm and running it on different inputs.
      • EK 4.2.4C - The correctness of an algorithm is determined by reasoning formally or mathematically about the algorithm, not by testing an implementation of the algorithm.
      • EK 4.2.4D - Different correct algorithms for the same problem can have different efficiencies.
      • EK 4.2.4E - Sometimes, more efficient algorithms are more complex.
      • EK 4.2.4F - Finding an efficient algorithm for a problem can help solve larger instances of the problem.
      • EK 4.2.4H - Linear search can be used when searching for an item in any list; binary search can be used only when the list is sorted.
Big Idea - Programming
  • EU 5.1 - Programs can be developed for creative expression, to satisfy personal curiosity, to create new knowledge, or to solve problems (to help people, organizations, or society).
    • LO 5.1.2 - Develop a correct program to solve problems. [P2]
      • EK 5.1.2A - An iterative process of program development helps in developing a correct program to solve problems.
      • EK 5.1.2B - Developing correct program components and then combining them helps in creating correct programs.
      • EK 5.1.2C - Incrementally adding tested program segments to correct working programs helps create large correct programs.
      • EK 5.1.2D - Program documentation helps programmers develop and maintain correct programs to efficiently solve problems.
      • EK 5.1.2E - Documentation about program components, such as code segments and procedures, helps in developing and maintaining programs.
      • EK 5.1.2F - Documentation helps in developing and maintaining programs when working individually or in collaborative programming environments.
      • EK 5.1.2G - Program development includes identifying programmer and user concerns that affect the solution to problems.
    • LO 5.1.3 - Collaborate to develop a program. [P6]
      • EK 5.1.3B - Collaboration facilitates multiple perspectives in developing ideas for solving problems by programming.
      • EK 5.1.3C - Collaboration in the iterative development of a program requires different skills than developing a program alone.
      • EK 5.1.3F - Effective communication between participants is required for successful collaboration when developing programs.
  • EU 5.3 - Programming is facilitated by appropriate abstractions.
    • LO 5.3.1 - Use abstraction to manage complexity in programs. [P3]
      • EK 5.3.1A - Procedures are reusable programming abstractions.
      • EK 5.3.1B - A procedure is a named grouping of programming instructions.
      • EK 5.3.1C - Procedures reduce the complexity of writing and maintaining programs.
      • EK 5.3.1D - Procedures have names and may have parameters and return values.
      • EK 5.3.1E - Parameterization can generalize a specific solution.
      • EK 5.3.1F - Parameters generalize a solution by allowing a procedure to be used instead of duplicated code.
      • EK 5.3.1G - Parameters provide different values as input to procedures when they are called in a program.
      • EK 5.3.1L - Using lists and procedures as abstractions in programming can result in programs that are easier to develop and maintain.
  • EU 5.5 - Programming uses mathematical and logical concepts.
    • LO 5.5.1 - Employ appropriate mathematical and logical concepts in programming. [P1]
      • EK 5.5.1A - Numbers and numerical concepts are fundamental to programming.
      • EK 5.5.1D - Mathematical expressions using arithmetic operators are part of most programming languages.
      • EK 5.5.1E - Logical concepts and Boolean algebra are fundamental to programming.
      • EK 5.5.1F - Compound expressions using and, or, and not are part of most programming languages.
      • EK 5.5.1H - Computational methods may use lists and collections to solve problems.
      • EK 5.5.1J - Basic operations on collections include adding elements, removing elements, iterating over all elements, and determining whether an element is in a collection.

Math Common Core Practice:

  • 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.

Common Core Math:

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

Common Core ELA:

  • RST 12.3 - Precisely follow a complex multistep procedure

NGSS Practices:

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

Key Concepts

Students will:

  • Demonstrate how combining data sources and classifying data are part processing data
  • Describe challenges to structuring large data sets for analysis
  • Be able to identify how the order of data influences which methods are appropriate for searching the data.
  • Be able to describe standard search algorithms in pseudocode and in Python.
  • Compare different algorithms for efficiency when searching for an item.

Essential Questions

  • 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 are algorithms implemented and executed on computers and computational devices?
  • What kinds of problems are easy, what kinds are difficult, and what kinds are impossible to solve algorithmically?
  • How are algorithms evaluated?
  • How do computer programs implement algorithms?
  • How does abstraction make the development of computer programs possible?
  • Which mathematical and logical concepts are fundamental to computer programming?

Teacher Resources

Student computer usage for this lesson is: required

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
  • Binary Search in LISP example to show on the screens.

Lesson Plan

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? 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)

  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?
  • Is there always a "correct" solution when sorting 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 to implement binary search.
  3. When finished, display binary search code in other languages. (Scratch https://scratch.mit.edu/projects/23163175/; javascript https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/implementing-binary-search-of-an-array ; LISP (see handout)

Part 2 Coding (20 min)

  1. 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.

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.

Options for Differentiated Instruction

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'.


Evidence of Learning

Formative Assessment

Correctness of Python functions for linear search and binary search


Summative Assessment

"Searching Assessment Items.docx" in lesson folder

"Search Comparison Worksheet" in the lesson folder