Download as CSV
Unit 6 - Algorithms
Lesson 1: Algorithms Solve Problems
Standards Alignment
CSP2021
AAP-2 - The way statements are sequenced and combined in a program determines the computed result
AAP-2.A - Express an algorithm that uses sequencing without using a programming language.
- AAP-2.A.1 - An algorithm is a finite set of instructions that accomplish a specific task.
- AAP-2.A.2 - Beyond visual and textual programming languages, algorithms can be expressed in a variety of ways, such as natural language, diagrams, and pseudocode.
- AAP-2.A.3 - Algorithms executed by programs are implemented using programming languages.
- AAP-2.A.4 - Every algorithm can be constructed using combinations of sequencing, selection, and iteration.
AAP-2.B - Represent a step-by-step algorithmic process using sequential code statements.
- AAP-2.B.1 - Sequencing is the application of each step of an algorithm in the order in which the code statements are given.
AAP-2.G - Express an algorithm that uses selection without using a programming language.
- AAP-2.G.1 - Selection determines which parts of an algorithm are executed based on a condition being true or false.
AAP-2.I - For nested selection: a. Represent using nested conditional statements. b. Determine the result of nested conditional statements.
- AAP-2.J.1 - Iteration is a repeating portion of an algorithm. Iteration repeats a specified number of times or until a given condition is met.
AAP-2.L - Compare multiple algorithms to determine if they yield the same side effect or result.
- AAP-2.L.1 - Algorithms can be written in different ways and still accomplish the same tasks.
- AAP-2.L.2 - Algorithms that appear similar can yield different side effects or results.
- AAP-2.L.5 - Different algorithms can be developed or used to solve the same problem.
Lesson 2: Algorithm Efficiency
Standards 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.
Lesson 3: Unreasonable Time
Standards Alignment
CSTA K-12 Computer Science Standards (2017)
AP - Algorithms & Programming
- 3B-AP-11 - Evaluate algorithms in terms of their efficiency, correctness, and clarity.
CSP2021
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.4 - An algorithm’s efficiency is determined through formal or mathematical reasoning.
- AAP-4.A.7 - Algorithms with a polynomial efficiency or lower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time. Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of
Lesson 4: The Limits of Algorithms
Standards Alignment
CSTA K-12 Computer Science Standards (2017)
AP - Algorithms & Programming
- 3B-AP-11 - Evaluate algorithms in terms of their efficiency, correctness, and clarity.
CSP2021
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.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.8 - Some problems cannot be solved in a reasonable amount of time because there is no efficient algorithm for solving them. In these cases, approximate solutions are sought.
- AAP-4.A.9 - A heuristic is an approach to a problem that produces a solution that is not guaranteed to be optimal but may be used when techniques that are guaranteed to always find an optimal solution are impractical. EXCLUSION STATEMENT (AAP-4.A.9): Specific heurist
AAP-4.B - Explain the existence of undecidable problems in computer science.
- AAP-4.B.1 - A decidable problem is a decision problem for which an algorithm can be written to produce a correct output for all inputs (e.g., “Is the number even?”).
- AAP-4.B.2 - An undecidable problem is one for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer. EXCLUSION STATEMENT (EK AAP-4.B.2): Determining whether a given problem is undecidable is outside the scope of this co
- AAP-4.B.3 - An undecidable problem may have some instances that have an algorithmic solution, but there is no algorithmic solution that could solve all instances of the problem.
Lesson 5: Parallel and Distributed Algorithms
Standards Alignment
CSTA K-12 Computer Science Standards (2017)
AP - Algorithms & Programming
- 3B-AP-11 - Evaluate algorithms in terms of their efficiency, correctness, and clarity.
CSP2021
CSN-2 - Parallel and distributed computing leverages multiple computers to more quickly solve complex problems or process large data sets
CSN-2.A - Compare problem solutions that use sequential, parallel, and distributed computing.
- CSN-2.A.1 - Sequential computing is a computational model in which operations are performed in order one at a time.
- CSN-2.A.2 - Parallel computing is a computational model where the program is broken into multiple smaller sequential computing operations, some of which are performed simultaneously.
- CSN-2.A.3 - Distributed computing is a computational model in which multiple devices are used to run a program.
- CSN-2.A.4 - Comparing efficiency of solutions can be done by comparing the time it takes them to perform the same task.
- CSN-2.A.5 - A sequential solution takes as long as the sum of all of its steps.
- CSN-2.A.6 - A parallel computing solution takes as long as its sequential tasks plus the longest of its parallel tasks.
- CSN-2.A.7 - The “speedup” of a parallel solution is measured in the time it took to complete the task sequentially divided by the time it took to complete the task when done in parallel.
CSN-2.B - Determine the efficiency of sequential and parallel solutions.
- CSN-2.B.1 - Parallel computing consists of a parallel portion and a sequential portion.
- CSN-2.B.2 - Solutions that use parallel computing can scale more effectively than solutions that use sequential computing.
- CSN-2.B.3 - Distributed computing allows problems to be solved that could not be solved on a single computer because of either the processing time or storage needs involved.
- CSN-2.B.4 - Distributed computing allows much larger problems to be solved quicker than they could be solved using a single computer.
- CSN-2.B.5 - When increasing the use of parallel computing in a solution, the efficiency of the solution is still limited by the sequential portion. This means that at some point, adding parallel portions will no longer meaningfully increase efficiency.