Lesson 4: The Limits of Algorithms
Widget
Overview
Students explore the limits of what algorithms are able to compute. First they use a widget that exposes students to the Traveling Salesman Problem. After recognizing this problem can only be solved using an unreasonable time algorithm the develop their own good enough solutions that run more efficiently. Later in the lesson students watch a video about undecidable problems for which no algorithm can ever be developed to solve them.
Purpose
Prior to this lesson students have learned about the efficiencies of different algorithms and have considered the difference between reasonable and unreasonable algorithms. In this lesson they explore what happens when you reach that limit. In one instance the response is to accept good enough solutions that run more reasonably. In the other case the problem simply can't be solved at all.
Agenda
Lesson Modifications
Warm Up (5 mins)
Activity (30 mins)
Wrap Up (10 mins)
View on Code Studio
Objectives
Students will be able to:
- Determine if an algorithm runs in unreasonable time.
- Develop a heuristic to solve a problem.
- Distinguish between decision problems and optimization problems.
- Explain the existence of undecidable problems
Preparation
- Read through the slides
- Preview the Traveling Salesman widgets
Links
Heads Up! Please make a copy of any documents you plan to share with students.
For the Teachers
- CSP Unit 6 - Algorithms - Presentation
Teaching Guide
Lesson Modifications
Attention, teachers! If you are teaching virtually or in a socially-distanced classroom, please read the full lesson plan below, then click here to access the modifications.
Warm Up (5 mins)
Discussion Goal
Goal: Use this discussion to quickly review topics brought up in the previous lesson.
- Reasonable algorithms grow at a polynomial rate or slower. Unreasonable algorithms grow exponentially.
- The time to solve an unreasonable algorithm grows very quickly even for relatively small problem sizes.
Prompt: What is the difference between a reasonable and unreasonable time algorithm?
Discuss: Have students think about their answers on their own, then share with a partner, and then finally discuss responses with the entire room.
Remarks
This was a good reminder of what we learned last time. Unreasonable time algorithms just don't make sense to run. Today we're going to be thinking more about what happens when we reach the limits of algorithms, and how sometimes we can make compromises.
Activity (30 mins)
Traveling Salesman
Set Up: Each student needs to have their journals and a pen or pencil.
Display: Use the activity slides for this lesson to guide the activity on the limits of algorithms.
| Slides | Speaker Notes |
|---|---|
 |
Say: Today we are going to explore the Traveling Salesman Problem. |
 |
Prompt: How many different paths can you find to visit all of your friends' houses? Do This: Students should sketch out different paths in their journals. Read through the rules together as a class. Rules:
Discuss: Students share their paths with a partner before discussing as a class. |
 |
Say: Take a look at some of these paths on the screen. You may have similar ones in your journal. Prompt: What do you need to know to determine the best path? |
 |
Say: Distance! If we know the distance between each house, we can make a better decision about which path to take. In this example, the first option is shortest, so that's the path we would choose. |
 |
Prompt: What if we had a lot more places to visit? How would we determine the best path? Discussion Goal: The goal here is for students to come to the realization that they would need to explore all possible paths in order to determine which one is the best. |
 |
Say: This is known as the Traveling Salesman Problem. For each new place to visit, the number of options for possible paths increases factorialy. |
 |
Say: A factorial function is written with the letter "n" followed by an explanation point. Here's how n! works: Multiply all whole numbers from the given number down to the number 1. Note: Talk through the examples and the table. The goal here isn't for students to memorize the math, but to understand that with each new house added, the number of potential paths that have to be checked expands very quickly. |
 |
Say: The Traveling Salesman is an Optimization Problem. It's not a Decision Problem. We know there is a path. Now we must determine which is the shortest or most efficient path. |
 |
Say: The Traveling Salesman Problem can be solved with an algorithm, which checks each possible option. BUT, it would take massive amounts of computing power to compare every single option, especially as the number of homes to visit (otherwise known as nodes) increases. Therefore, it would take an unreasonable amount of time for the solution to be calculated for most instances of the problem. |
 |
Say: Welcome to heuristics! Heuristics provide a good enough solution to a problem when an actual solution is impractical or impossible. |
Do This: Students now navigate to Level 2 on Code Studio where they will use the Traveling Salesman Widget to find the "best" path to visit all nodes.
- In their journal, students should write down a plan or heuristic for choosing a good path.
Discuss: In pairs, students should share their heuristics and make adjustments to their own as needed.
Do This: Now students navigate to Level 3 and use the Widget: Traveling Salesman with Random Nodes. Students test their heuristic on this widget, keeping a log in their journal of the distance for the path their heuristic finds and the best distance the student finds not using the stated heuristic (i.e. clicking around, or "brute force").
- Note: Click reset to try different paths on the same level. Click "New Level" to generate at new random assortment of nodes.
Discussion Goal
Goal: Tease out what factors students used to create their heuristics.
Prompt: How did you create your heuristic? Did you change your heuristic after testing it out?
Discuss: Call on several students to share their heuristics. As a class, discuss which heuristic we think is best, and will give us a "good enough" result for most cases.
Discussion Goal
Goal: There are times when the Next-Closest heuristic will not provide the best option, but on average it's a good option.
- Students can reflect back on the paper route problem from earlier in the class. This may have been the option they first suggested.
Display: Show the sample heuristic. This may be one that students already came up with. Discuss whether or not this heuristic is "good enough".
Remarks
The Traveling Salesman Problem is an optimization problem. We are attempting to find the best path.
It's also unreasonable because there is not an algorithm that can solve the problem in a reasonable amount of time.
We need to use a heuristic to come up wtih a solution that is "good enough" for most instances of the problem.
Undecidable Problems
Teaching Tip
Do I Need to Understand the Halting Problem?: Students don't actually need to understand the Halting Problem or the proof in this video. The main ideas are covered in the takeaways and are fairly simple. There are a few problems, most notably "will this code run?" that we've proven there is no algorithm that will ever be able to determine the correct answer in every case. The proof is interesting but if you are short on time you may opt to skip the video.
Remarks
We've learned how we address unreasonable problems. Before we finish our study of problems let's learn about one more type, problems that no algorithm will ever be able to solve. This video is a little tricky, but it gives you a good sense for the way this problem shows up.
Video: Show the video on the halting problem, located on the slide
Display: Review the main takeaways about undecidable problems.
Wrap Up (10 mins)
Discussion Goal
Answer: A heuristic is used when it's impossible or impractical to use an algorithm to solve a problem. Therefore, we need something that is good enough on average for most instances. This is where a heuristic shines.
Prompt: Why is a heuristic acceptable when it doesn't always produce the "best" result?
Discuss: Have students think about their answers on their own, then share with a partner, and then finally discuss responses with the entire room.
Remarks
Great! Heuristics are handy in every day life. Think about using mapping software to find the best route to a destination!
Assessment: Check For Understanding
Check For Understanding Question(s) and solutions can be found in each lesson on Code Studio. These questions can be used for an exit ticket.
Question: In which of the following situations is it most appropriate to use a heuristic solution?
Question: In your own words, explain the difference between undecidable problems and unreasonable time algorithms.
Standards Alignment
View full course alignment
CSTA K-12 Computer Science Standards (2017)
AP - Algorithms & Programming
- 3B-AP-11 - Evaluate algorithms in terms of their efficiency, correctness, and clarity.
CSP2021
AAP-4 - There exist problems that the computer cannot solve
AAP-4.A - For determining the efficiency of an algorithm: a. Explain the difference between algorithms that run in reasonable time and those that do not run in reasonable time. b. Identify situations where a heuristic solution may be more appropriate.
- 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?).
- 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.
- 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 heurist
AAP-4.B - Explain the existence of undecidable problems in computer science.
- 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?”).
- 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 co
- 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.