Before you keep reading...
Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.
Before you keep reading...
Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.
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.
The Student Lesson: Complete the activities for Mobile CSP Unit 5: Lesson 5.8 Limits of Algorithms.
- 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 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.
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.
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
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