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.

CSP Framework
Big Idea 3: Algorithms and Programming (AAP)
Enduring Understanding AAP-4: There exist problems that computers cannot solve, and even when a computer can solve a problem, it may not be able to do so in a reasonable amount of time.
Learning Objective AAP-4.A.a: For determining the efficiency of an algorithm: a. Explain the difference between algorithms that run in reasonable time and those that do not. Learning Objective AAP-4.A.b: For determining the efficiency of an algorithm: b. Identify situations where a heuristic solution may be more appropriate.
Skill 1.D AAP-4.A.2 AAP-4.A.7 AAP-4.A.8 AAP-4.A.9 Essential Knowledge AAP-4.A.2: A decision problem is a problem with a yes/no answer (e.g., is there a path from A to B?). An optimization problem is a problem with the goal of finding the 'best' solution among many (e.g., what is the shortest path from A to B?). Essential Knowledge AAP-4.A.7: Algorithms with a polynomial efficiency or slower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time. Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time. Essential Knowledge AAP-4.A.8: Some problems cannot be solved in a reasonable amount of time because there is no efficient algorithm for solving them. In these cases, approximate solutions are sought. Essential Knowledge AAP-4.A.9: A heuristic is an approach to a problem that produces a solution that is not guaranteed to be optimal but may be used when techniques that are guaranteed to always find an optimal solution are impractical. EXCLUSION STATEMENT (AAP-4.A.9): Specific heuristic solutions are outside the scope of this course and the AP Exam.
Learning Objective AAP-4.B: Explain the existence of undecidable problems in computer science.
Skill 1.A AAP-4.B.1 AAP-4.B.2 AAP-4.B.3 Essential Knowledge AAP-4.B.1: A decidable problem is a decision problem for which an algorithm can be written to produce a correct output for all inputs (e.g., Is the number even?). Essential Knowledge AAP-4.B.2: An undecidable problem is one for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer. EXCLUSION STATEMENT (EK AAP-4.B.2): Determining whether a given problem is undecidable is outside the scope of this course and the AP Exam. Essential Knowledge AAP-4.B.3: An undecidable problem may have some instances that have an algorithmic solution, but there is no algorithmic solution that could solve all instances of the 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

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.

Support Runestone Academy Today

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.

Support Runestone Academy Today