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