Day 21: Algorithm Efficiency

Learning Objectives

• AAP-2.D: Compare multiple algorithms to determine if they yield the same side effect or result.
• AAP-2.Q: For algorithms: a. Create algorithms. b. Combine and modify existing algorithms.

Essential Questions

• How do we measure and compare the efficiency of algorithms?
• Why does algorithm efficiency matter in real-world applications?

Materials Needed

• Presentation slides on algorithm efficiency
• Programming environment
• Algorithm comparison worksheet
• Timing tools for measuring execution
• Exit ticket templates

Vocabulary

• Algorithm efficiency
• Time complexity
• Space complexity
• Execution time
• Resource usage
• Scalability
• Performance
• Optimization
• Benchmark

Procedure (50 minutes)

Opening (8 minutes)

1. Review and Week 5 Introduction (3 minutes)

   • Review collection types from previous lesson
   • Introduce Week 5 focus on algorithm analysis and final project
   • Connect to today's focus on algorithm efficiency

2. Warm-up Activity (5 minutes)

   • Present two algorithms that solve the same problem (e.g., two ways to find the maximum value in a list)
   • Ask students which they think would be faster and why
   • Introduce the concept of comparing algorithms beyond correctness

Main Activities (32 minutes)

3. Lecture: Introduction to Algorithm Efficiency (12 minutes)

   • Define algorithm efficiency as an estimation of computational resources used
   • Explain why efficiency matters:
     • Programs with large data sets
     • Applications with time constraints
     • Systems with limited resources
     • User experience considerations
   • Discuss ways to measure efficiency:
     • Execution time
     • Number of operations
     • Memory usage
   • Explain that efficiency is typically expressed relative to input size
   • Introduce informal efficiency analysis:
     • Counting operations or iterations
     • Identifying dominant operations
     • Comparing algorithms based on operation counts
   • Discuss common efficiency patterns:
     • Constant time operations
     • Linear time algorithms (proportional to input size)
     • Quadratic time algorithms (proportional to square of input size)
   • Explain the concept of scalability and how efficiency affects it

4. Demo: Comparing Algorithms with Different Efficiencies (8 minutes)

   • Walk through examples of algorithms with different efficiencies:
     • Linear search vs. binary search
     • Different sorting algorithms
     • Different ways to compute the same result
   • Demonstrate measuring execution time for different algorithms
   • Show how efficiency differences become more apparent with larger inputs
   • Illustrate how to count operations to compare algorithms
   • Highlight the trade-offs between efficiency and other factors:
     • Code simplicity
     • Memory usage
     • Implementation difficulty

5. Hands-on: Analyzing Simple Algorithms (12 minutes)

   • Students work in the programming environment
   • Provide students with pairs of algorithms that solve the same problem
   • Have students:
     • Analyze the algorithms by counting operations
     • Implement the algorithms
     • Measure execution time with different input sizes
     • Create graphs showing how performance scales with input size
     • Determine which algorithm is more efficient and why
   • Example algorithm pairs:
     • Two ways to find duplicates in a list
     • Two ways to compute a sum
     • Two ways to check if a list is sorted

Closing (10 minutes)

6. Activity: Measuring Execution Time of Different Approaches (5 minutes)

   • Students select a problem with multiple solution approaches
   • Implement and time the different approaches
   • Compare results and discuss efficiency differences
   • Consider how the efficiency would change with larger inputs
   • Share findings with the class

7. Exit Ticket and Preview (5 minutes)

   • Students analyze and compare the efficiency of different algorithms
   • Preview that next class will focus on Big O notation

Assessment

• Formative: Quality of algorithm analysis during hands-on activities
• Exit Ticket: Accuracy of algorithm efficiency comparison

Differentiation

For Advanced Students

• Challenge them to analyze more complex algorithms
• Introduce the concept of space-time trade-offs
• Have them optimize an inefficient algorithm

For Struggling Students

• Focus on simpler algorithm comparisons
• Provide more structured analysis templates
• Use visual aids to illustrate efficiency differences

Homework/Extension

• Complete a worksheet on algorithm efficiency analysis
• Research a real-world scenario where algorithm efficiency made a significant difference
• Implement and compare the efficiency of different algorithms for a specific problem

Teacher Notes

• Emphasize that efficiency is a critical consideration in real-world programming
• Watch for confusion between algorithm correctness and efficiency
• Make connections to real-world scenarios where efficiency matters
• Consider using animations or visualizations to show algorithm performance
• Remind students that understanding efficiency is important for the AP exam