5.8. Analyzing Algorithms

This lesson has students compare the efficiencies of searching and sorting algorithms. Students need to reason about the algorithms and evaluate the experimental data to evaluate their efficiency.

CSP Framework
Big Idea 3: Algorithms and Programming (AAP)
Enduring Understanding 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.
Learning Objective AAP-2.B: Represent a step-by-step algorithmic process using sequential code statements.
Skill 2.B AAP-2.B.7 Essential Knowledge AAP-2.B.7: Clarity and readability are important considerations when expressing an algorithm in a programming language.
Enduring Understanding AAP-4: There exist problems that computers cannot solve, and even when a computer can solve a problem, it may not be able to do so in a reasonable amount of time.
Learning Objective AAP-4.A.a: For determining the efficiency of an algorithm: a. Explain the difference between algorithms that run in reasonable time and those that do not. Learning Objective AAP-4.A.b: For determining the efficiency of an algorithm: b. Identify situations where a heuristic solution may be more appropriate.
Skill 1.D AAP-4.A.1 AAP-4.A.2 AAP-4.A.3 AAP-4.A.4 AAP-4.A.5 AAP-4.A.6 AAP-4.A.7 AAP-4.A.8 AAP-4.A.9 Essential Knowledge 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. Essential Knowledge 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?). Essential Knowledge 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 reasoning using mathematical formulas are outside the scope of this course and the AP Exam. Essential Knowledge AAP-4.A.4: An algorithm’s efficiency is determined through formal or mathematical reasoning. Essential Knowledge 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. Essential Knowledge AAP-4.A.6: Different correct algorithms for the same problem can have different efficiencies. Essential Knowledge AAP-4.A.7: Algorithms with a polynomial efficiency or slower (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 time. Essential Knowledge 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. Essential Knowledge 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 heuristic solutions are outside the scope of this course and the AP Exam.

Professional Development

The Student Lesson: Complete the activities for Mobile CSP Unit 5: Lesson 5.7 Analyzing Algorithms.

Materials

• Slides for Analyzing Search Algorithms, Analyzing Sort Algorithms
• Graphing paper - You can print graph paper from www.printablepaper.net OR you can have students use this spreadsheet to enter the data and draw the graphs.

5.8.1. Learning Activities

Estimated Length: 90 minutes

• Hook/Motivation (5 minutes): Have students hypothesize about which sort and search algorithms are the fastest. Have them explain their reasoning. (They should identify radix/bucket sort and binary search of the ones covered.) Explanation: we reason about algorithms (formally/mathematically - analytically and experimenting - empirically) to determine their efficiences
• Experiences and Explorations (75 minutes):
  • Lecture - Analyzing Search: Give the presentation about analyzing search algorithms (or show the video).
  • Activity - Search Experiment: Have students complete the search experiment, recording results and then plotting them on graph paper or the given spreadsheet. Emphasize that this is a worst-case analysis.
  • Lecture - Analyzing Sort: Give the presentation about analyzing sort algorithms (or show the video).
  • Activity - Sort Experiment: Have students complete the sort experiment, recording results and then plotting them on graph paper or the given spreadsheet. Emphasize that this is a worst-case analysis.
• Rethink, Reflect and/or Revise (10 minutes): Have students share the results of their experiments and complete their portfolio reflections

AP Classroom

The College Board's AP Classroom provides a question bank and Topic Questions. You may create a formative assessment quiz in AP Classroom, assign the quiz (a set of questions), and then review the results in class to identify and address any student misunderstandings.The following are suggested topic questions that you could assign once students have completed this lesson.

Suggested Topic Questions:

• Topic 3.17 Algorithmic Efficiency

Assessment Opportunities and Solutions

Solutions Note: Solutions are only available to verified educators who have joined the Teaching Mobile CSP Google group/forum in Unit 1.

• Quizly Solutions
• Portfolio Reflection Questions Solutions

Assessment Opportunities

You can examine students’ work on the interactive exercise and their reflection portfolio entries to assess their progress on the following learning objectives. If students are able to do what is listed there, they are ready to move on to the next lesson.

• Interactive Exercises:
• Portfolio Reflections:
  LO X.X.X - Students should be able to ...

Answers to Student Reflection Questions

1. This algorithm is linear. In the worst case you need to check each number 1 to N to see if it is divisible by M.
2. Quick sort is an n log n algorithm. So most similar to merge sort. Which case is closer to worst? The few unique keys is the worst case. You can see this by observation.

Differentiation: More Practice

If students are struggling with lesson concepts, have them review the following resources:

Differentiation: Enrichment

Background Knowledge:

• The Sorting-Algorithms.com page provides a more visual comparison of the efficiencies of sorting algorithms

Teaching Tips:

5.8.2. Professional Development Reflection

Discuss the following questions with other teachers in your professional development program.

• How does this lesson encourage students to think analytically and empirically about algorithms?

I am confident I can teach this lesson to my students.
• 1. Strongly Agree
• 2. Agree
• 3. Neutral
• 4. Disagree
• 5. Strongly Disagree

Before you keep reading...

Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.

Support Runestone Academy Today

Before you keep reading...

Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.

Support Runestone Academy Today