5.9. Limits of Algorithms

This lesson focuses on the limits of computing - are there problems that computers cannot solve? Are there problems that they cannot solve in a reasonable time? Students explore these concepts through short lectures and POGIL activities that look at classic problems, such as the traveling salesman problem.

Professional Development

The Student Lesson: Complete the activities for Mobile CSP Unit 5: Lesson 5.8 Limits of Algorithms.

Materials

• Presentation system (LCD projector/Interactive whiteboard)
• Access to computer, laptop, or Chromebook 
• Slides: Limits of Algorithms
  
• POGIL Roles
• POGIL Worksheet
• Password Widget

5.9.1. Learning Activities

Estimated Length: 45 minutes

• Hook/Motivation (10 minutes): Ask students if they think computers can solve any problem. Have them discuss it using the think-pair-share method. Another possible hook is to start talking about password schemes and looking at the site howsecureismypassword.net.
• Experiences and Explorations (45 minutes):
  • Lecture: Limits of Algorithms (10 minutes)
  • (Possible hook: howsecureismypassword.net
  • POGIL Activity: Creating a Strong Password (15 minutes):
  • Lecture: Heuristic Algorithms (5 minutes)
  • (Possible Hook: Traveling Salesperson Problem - College Tour)
  • POGIL Activity: Traveling Salesman Problem (15 minutes):
• Rethink, Reflect and/or Revise (5 minutes): Have students complete the interactive exercises and 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
• Topic 3.18 Undecidable Problems

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

Differentiation: More Practice

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

Differentiation: Enrichment

Background Knowledge

Teaching Tips: Graphing by Hand

If students are struggling with the differences between the growth functions, try having them graph the data for the experiment by hand. This will also reinforce their graphing skills and ability to read graphs.

5.9.2. Professional Development Reflection

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

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