Limits of Algorithms¶
Time Estimate: 45 minutes
Introduction and Goals¶
We've been using algorithms to build our apps and we've learned about algorithms for solving certain types of problems, such as searching and sorting problems.
It may seem that no matter what the problem, we can find an algorithm to solve it. But that is not true. And in this lesson we want to look at some problems that algorithms cannot solve or cannot solve efficiently.
- differentiate between problems that have reasonable solutions and those that do not
- discuss heuristic solutions when an optimal solution is not possible
- explain how intractability can be used to solve problems such as password security
- use target vocabulary, such as reasonable time, unreasonable time, decidable problems, intractable problems and intractable problem while discussing algorithms, with the support of concept definitions and vocabulary notes from this lesson
There are two categories of problems that an algorithm cannot solve.
- Undecidable Problems. These problems are the theoretically impossible to solve — by any algorithm. The halting problem is a decision problem (with a yes or no answer) that is undecidable. A computer cannot tell if it is in an infinite loop or it will at some point stop!
- Intractable Problems. These problems are theoretically impossible to solve in a reasonable time — i.e., there are known algorithmic solutions, but the algorithms are too inefficient/slow to solve the problem when the number of inputs grows large.
The following video will give us an overview of these types of limits to algorithms and will illustrate how we can use the fact that certain problems are intractable to protect our passwords and other information.
POGIL Activity for the Classroom: Creating a Strong Password (15 minutes)
To give us a better sense of what it takes to create a strong password -- i.e., one that can withstand a brute force attack -- we're going to use the Password Strength Calculator to test the strength of various password schemes. (Open widget in a separate window)
According to Wikipedia, an ordinary desktop computer equipped with special password cracking software can test more than 100 million passwords per second. The goal of this activity is to come up with the optimal password scheme that would take an ordinary PC, equipped with password-cracking software, more than 10 years to crack.
Break into 4-person POGIL teams. Record your answers using this worksheet. (File-Make a Copy to have a version you can edit.)
|The facilitator records the details of the team's optimal password scheme.
|Reports the team's results.
|Uses the online calculator to test the team's ideas for creating secure passwords.
|Assesses the team's performance and records on the Portfolio the team's answers to the following guided inquiry questions.
- (Portfolio) A password scheme consists of a minimum password length and the different types of symbols (i.e., letters, numbers, specials) that can be used in the password. Using the Password Strength Calculator, determine the optimal scheme for withstanding a brute force attack of at least 10 years by an ordinary PC performing 100 million tests per second.
- (Portfolio) According to this 2020 article, a password-cracking computer can try 669 billion passwords per second. How would you have to modify your scheme to withstand a 10-year attack by this specially designed computer?
- (Portfolio) After you’ve calculated the estimated number of passwords that can be checked per second for the next year, use the Password Strength Calculator to determine an optimal password scheme.
a. How long should the password be?
b. What combination of characters should it include?
Heuristic Solutions to Intractable Problems
For some intractable problems, we need to have practical solutions. One such example is the Traveling Salesman Problem (TSP): Construct the most efficient route, the optimal route, that visits N cities. This is an optimization problem where the goal is to find the "best" (most optimal) solution among many.
This is a problem we would like to be able to solve. Variations of this problem are the kinds of problems that Google maps and other apps solve for us when we ask for driving directions.
Fortunately, there are so-called heuristic algorithms that computer scientists use to solve such problems. A heuristic algorithm is one that provides a solution to a problem, although in many cases the solution may not be the best possible solution -- i.e., it may not be an optimal solution.
The following video will give us an overview of the Traveling Salesman Problem.
POGIL Activity for the Classroom: Traveling Salesman Problem (15 minutes)
Using the same POGIL teams as above, let's give the nearest neighbor heuristic a try on this problem.
A Trinity College student needs to visit some of the Mobile CSP Schools in Hartford, Connecticut. The following map shows the schools that need to be visited and gives the distances between each pair of schools. The student needs a good route, starting and ending at Trinity College, that will visit all of the schools.
Use the map to answer the following questions.
- Starting and ending at Trinity College, what route would the nearest neighbor heuristic produce for the proposed visits?
- Starting and ending at Trinity College, find the optimal route that visits all schools. (HINT: To prove that your route is optimal, you'll have to compare it to all possible routes starting and ending at Trinity.)
- (Portfolio) For routes starting and ending at Trinity College, you have identified the nearest neighbor route and the optimal route. What does this show you about the nearest neighbor heuristic?
In this lesson, you learned how to:
- Try the How secure is my password site.
- Check out the article Why So Many People Make Dragon Their Password from Wired magazine.
- Check out the article Estimating Password Cracking Times from Better Buys.
- Do some online research to explore alternatives to passwords schemes -- for example, two-factor authentication, biometrics, virtual tokens. What are their relative advantages and disadvantages?
- Here's an interactive shortest TSP tour to visit the top 647 colleges in the U.S..
- Here's a neat TSP Game that uses maps in Europe and Africa. You can use it to test the nearest neighbor heuristic, or to try to come up with your own heuristic for finding good routes through the cities.
- One field of computer science that makes extensive use of heuristics is Artificial Intelligence (AI). You've probably heard of it. The field of AI traditionally tackles problems that humans are good at but computers are not (yet) good at -- for example, vision, speech recognition, natural language understanding, planning, driving, and so on. However, great progress is being made in these various areas -- just think for a moment about how well Siri and similar intelligent digital assistants work today. In fact, try asking Siri "Hey Siri, how do you solve the traveling salesman problem?". AI is a vast field. And, as for many topics, a good way to start learning more about Heuristics and AI would be to start with Wikipedia.
Here is a table of some of the technical terms discussed in this lesson. Hover over the terms to review the definitions.
The Halting Problem
The Traveling Salesman Problem
Sample AP CSP Exam Question¶
Reflection: For Your Portfolio¶
Answer the following portfolio reflection questions as directed by your instructor. Questions are also available in this Google Doc where you may use File/Make a Copy to make your own editable copy.