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.
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 worstcase 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 worstcase 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.
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
 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.
 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
Differentiation: Enrichment
Background Knowledge:
 The SortingAlgorithms.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