5.8. 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.8.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 thinkpairshare 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.
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
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.8.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