Unit6
1
2
3
4
5
6

Lesson 2: Algorithm Efficiency

Overview

In this lesson students follow a demonstration of Linear Search before writing their own search algorithms. Following this, students are introduced to Binary Search after which they compare graphs of the search algorithms to determine which is most efficient.

Purpose

In the previous lesson students learned that there are many different ways to write an algorithm to solve a problem. However, not all solutions are good options, and some algorithms require many fewer steps to run than others. This lesson focuses on comparing Linear Search to Binary Search. The longer the length of the list being searched, the more efficient Binary Search is compared to Linear Search. That said, Binary Search has a constraint: the list must first be sorted. This lesson more broadly introduces students to thinking about the efficiency of an algorithm, an idea that will be explored more in future lessons.

Agenda

Lesson Modifications

Warm Up (5 mins)

Activity (30 mins)

Wrap Up (10 mins)

View on Code Studio

Objectives

Students will be able to:

  • Use Linear Search to determine if a number is in a list
  • Use Binary Search to determine if a number is in a list
  • Compare the efficiency of Linear Search and Binary Search

Preparation

  • Preview the slides and click through all animations
  • Practice running Binary Search yourself

Links

Heads Up! Please make a copy of any documents you plan to share with students.

For the Teachers

Support

Report a Bug

Forum

Teaching Guide

Lesson Modifications

Attention, teachers! If you are teaching virtually or in a socially-distanced classroom, please read the full lesson plan below, then click here to access the modifications.

Warm Up (5 mins)

Discussion Goal

Goal: Use this discussion to highlight the following points

  • Students may have as systematic approach (search through every pocket in order) or a random approach.
  • Some students may have a system where they place their books and materials in their backpack to be retrieved in the order of their class schedule. If they look in their bag at a certain spot and don't see the pencil, they have a pretty good idea where to search next.
  • There are no right answers here - the idea is to start thinking about the efficiency of different search methods.

Prompt: Have you ever lost a pencil in a backpack? What are the steps you take to find the pencil?

Discuss: Have students think about their answers on their own, then share with a partner, and then finally discuss responses with the entire room.

Remarks

There are many different ways to achieve the same goal for this problem: finding your pencil. Today we are going to explore different search methods that computers use.

Activity (30 mins)

Distribute: Students should have sticky notes and their journals

Do This: Call for three volunteers. These students use the Ticket Generator on Code Studio to produce raffle tickets numbers (one per volunteer). Students write the number on a sticky note and come to the front of the room.

Teaching Tip

Before class, choose your own winning number (a number between 0-999), or alternatively use the Ticket Generator yourself!

Remarks

Thank you, volunteers! Let's figure out if any of you have the winning number for this instance of the problem. I'm going to ask you one by one to show your number and we will compare it with the winning number.

Do This: Each volunteer reveals their number and compares it to the winning number.

Discussion Goal

Answer:

  • The greatest possible number of steps for this instance is 3.
  • With six volunteers, the greates number of steps is 6.
  • The patterns is a 1:1 relationship. The number of tickets in the raffle exactly equals the number of steps it would take to check for a number in the worst case.

Prompt: How many steps did it take to find out if anyone had the winning ticket? What is the greatest possible number of steps it could take for this instance?

Prompt: What if we had six volunteers? The whole class? The whole school? What is the pattern here?

Display: Look at the chart as a class and examine the graph. The graph visualizes the pattern the class discussed.

Remarks

Now let's try a different way to search.

Group: Place students in groups of two

Do This: With a partner, students navigate to Code Studio and use the Ticket Generator to create seven random numbers that are copied to sticky notes. Students organize these sticky notes in numerical order. Students choose one extra number as the "winning number" and write that number down on a separate sticky note.

Challenge: Students work with their partner to write an algorithm to search for their winning number. Make sure the rules are displayed.

  • The search can start at any of the sticky notes
  • You can "jump" over sticky notes. In other words, you don't need to search the stickies in order.
  • You can determine which sticky notes to search next based on the current sticky note you are checking.
  • The goal is to make the determination in the least steps possible, but don't forget your number could be anywhere in the list - what is the worst possible case? What is the greatest number of comparison steps it would take to find any number in your list using your current algorithm?

Teaching Tip

It's important for students to think about this problem as looking for the number in the worst possible situation. In other words, what is the least amount of steps it would take to definitevely cross off every option?

Discuss: Students share their algorithms with another group and determine which one runs faster, depending on the number of steps it takes to find a number in the list.

Do This: Students return to their partner and now run a given algorithm, displayed on the board, step by step (click through for animation). As they are doing this, they should think about whether or not this algorithm runs faster (has less steps) than their own algorithms.

Remarks

This search algorithm is known as Binary Search. Let's see it in action.

Do This: Click through the animations to see Binary Search in action on the activity slide. Discuss each step as it is happening.

  • Find the number in the middle and compare it with the given number. The given number is greater than the middle number, so remove the middle number and all to the left.
  • Find the number in the middle of the numbers left, and compare it with the given number. The given number is less than the middle number, so remove the middle number and all to the right.
  • Find the number in the middle of the numbers left (there is only one!), and compare it with the given number. The given number is equal to the middle number. We have found our number!

Remarks

Binary search only works with a sorted list of numbers. This allows us to remove options from the search after we've made a decision. In other words, if we know the number is greater than 410, we can remove all numbers less than or equal to 410 and we don't have to manually check those numbers one by one.

Teaching Tip

What if there is no middle number while performing a step in Binary Search? Students can come up with a protocol for this like: if there is no middle number, compare the number on the right.

Do This: Display the graph. Students copy the chart into their journals and fill out the missing parts. They can use their sticky note to try out each instance of the problem. When the class has mostly finished, click through the animations to see the answers.

Teaching Tip

This is a tricky concept! It's ok if students don't fully understand. What's most important is what is revealed next: Binary Search is more efficient than Linear Search.

Display: Display the chart on the next slide. Click through the animations. This slide shows another way to fill out the chart, that does not require multiple sticky notes. Instead, we can use the flippy do! For Binary Search, for each instance the number of steps it take to run is equal to the number of bits required to represent the input.

Display: Discuss the graph and click through the animation to see Binary Search graphed.

Remarks

Both Binary Search and Linear Search find the answer to our search problem. However, one option is much faster than the other: Binary Search, although it requires that the numbers are sorted first.

Wrap Up (10 mins)

Discussion Goal

Answers:

  • For one input, either Binary Search or Linear Search would be appropriate. Students may argue for Linear as it does not need to first be sorted.
  • For five inputs, it's clear that Binary Search is fastest, although it only saves two steps over Linear Search. This is all the more true with one hundred inputs, which only takes seven steps (Binary number: 1100100) compared to Linear Search's one hundred steps.

Prompt: If I had one input, which algorithm would I use to get my answer with the fewest amount of steps? What if I had five? What about one hundred?

Discuss: Have students think about their answers on their own, then share with a partner, and then finally discuss responses with the entire room.

Journal: Students add the following vocabulary words and definitions to their journals: efficiency, linear search, binary search.

Remarks

Well done! It's clear that there are many algorithms we can use to search for an item in a list. Some are faster, or more efficient, than others. In the case of Binary Search, the larger the list we are searching through, the greater the efficiency in using this algorithm instead of Linear Search.

Assessment: Check For Understanding

Check For Understanding Question(s) and solutions can be found in each lesson on Code Studio. These questions can be used for an exit ticket.

Question: What is the third step using Binary Search to look for the number 32 in this list?

Question: Which of the following is true of two algorithms designed to solve the same problem?

Standards Alignment

View full course alignment

CSTA K-12 Computer Science Standards (2017)

AP - Algorithms & Programming
  • 3B-AP-10 - Use and adapt classic algorithms to solve computational problems.
  • 3B-AP-11 - Evaluate algorithms in terms of their efficiency, correctness, and clarity.

CSP2021

AAP-2 - The way statements are sequenced and combined in a program determines the computed result
AAP-2.O - For algorithms involving elements of a list: a. Represent using iterative statements to traverse a list. b. Determine the result of an algorithm with list traversals.
  • AAP-2.O.5 - Linear search or sequential search algorithms check each element of a list, in order, until the desired value is found or all elements in the list have been checked.
AAP-2.P - For binary search algorithms: a. Determine the number of iterations required to find a value in a data set. b. Explain the requirements necessary to complete a binary search.
  • AAP-2.P.1 - The binary search algorithm starts at the middle of a sorted data set of numbers and eliminates half of the data; this process repeats until the desired value is found or all elements have been eliminated. EXCLUSION STATEMENT (EK: AAP-2.P.1): Specific imp
  • AAP-2.P.2 - Data must be in sorted order to use the binary search algorithm.
  • AAP-2.P.3 - Binary search is often more efficient than sequential/linear search when applied to sorted data.
AAP-4 - There exist problems that the computer cannot solve
AAP-4.A - For determining the efficiency of an algorithm: a. Explain the difference between algorithms that run in reasonable time and those that do not run in reasonable time. b. Identify situations where a heuristic solution may be more appropriate.
  • AAP-4.A.1 - A problem is a general description of a task that can (or cannot) be solved algorithmically. An instance of a problem also includes specific input. For example, sorting is a problem; sorting the list (2,3,1,7) is an instance of the problem.
  • AAP-4.A.2 - A decision problem is a problem with a yes/no answer (e.g., is there a path from A to B?). An optimization problem is a problem with the goal of finding the "best" solution among many (e.g., what is the shortest path from A to B?).
  • AAP-4.A.3 - Efficiency is an estimation of the amount of computational resources used by an algorithm. Efficiency is typically expressed as a function of the size of the input. EXCLUSION STATEMENT (EK AAP-4.A.3): Formal analysis of algorithms (Big-O) and formal reaso
  • AAP-4.A.4 - An algorithm’s efficiency is determined through formal or mathematical reasoning.
  • AAP-4.A.5 - An algorithm's efficiency can be informally measured by determining the number of times a statement or group of statements executes.
  • AAP-4.A.6 - Different correct algorithms for the same problem can have different efficiencies.