5.7. 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.
The Student Lesson: Complete the activities for Mobile CSP Unit 5: Lesson 5.7 Analyzing Algorithms.
- 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.7.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
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
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
- The Sorting-Algorithms.com page provides a more visual comparison of the efficiencies of sorting algorithms
5.7.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