6.1 Algorithms solve Problems & 6.2 Algorithm Efficiency

CSP Conceptual Framework

AAP-2 - The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.

• AAP-2.A - Express an algorithm that uses sequencing without using a programming language.

• AAP-2.B - Represent a step-by-step algorithmic process using sequential code statements.

• AAP-2.G - Express an algorithm that uses selection without using a programming language.

• AAP-2.I - For nested selection: a. Represent using nested conditional statements. b. Determine the result of nested conditional statements.

• AAP-2.L - Compare multiple algorithms to determine if they yield the same side effect or result.

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.

6.1 Overview

Students will complete two exploratory activities that introduce the concept of a problem and an algorithm. In the first students answer a series of questions about the birthdates and names of their classmates. They then discuss the similarities and differences between the problems. In the second activity, students are given six different algorithms and must analyze them to determine which they think are the same or different. At the end of the lesson, they are introduced to the formal definitions of a problem and an algorithm.

6.1 Purpose

This lesson is an approachable and interactive introduction to the main concepts of this short unit. Students have been writing a lot of code, and now they are ready to think on a high level about the patterns that make two different problems, or two different algorithms, similar or different. This mindset will be important as they tackle the more challenging material later in the unit where students will learn to compare different algorithms that address the same problem.

_______________________________________________________________________

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

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