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

5.9. Limits of Algorithms

Time Estimate: 45 minutes

5.9.1. 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.

Learning Objectives: I will learn to

• 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

Language Objectives: I will be able to

• 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

5.9.2. Learning Activities

• slides
• |
• YouTube video Part I
• |
• YouTube video Part II
• |
• POGIL Worksheet

There are two categories of problems that an algorithm cannot solve.

1. 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!
2. 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.)

Role	Responsibility
Facilitator	The facilitator records the details of the team's optimal password scheme.
Spokesperson	Reports the team's results.
Quality Control	Uses the online calculator to test the team's ideas for creating secure passwords.
Process Analyst	Assesses the team's performance and records on the Portfolio the team's answers to the following guided inquiry questions.

Questions

1. (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.
2. (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?
3. (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.

Questions

1. Starting and ending at Trinity College, what route would the nearest neighbor heuristic produce for the proposed visits?
2. 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.)
3. (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?

5.9.3. Summary

In this lesson, you learned how to:

5.9.4. Still Curious?

• 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.

5.9.5. Self-Check

Here is a table of some of the technical terms discussed in this lesson. Hover over the terms to review the definitions.

brute force decidable problems undecidable problems intractable problems reasonable Time unreasonable Time

The Halting Problem The Traveling Salesman Problem heuristic algorithm decision problem optimization problem

Q-3: Is the following problem tractable (solvable in a reasonable amount of time) or intractable (cannot be solved in a reasonable amount of time)? For any length string of letters using any combination of the letters ‘a’ through ‘z’, write down all possible strings.

• Tractable
• Let me add new information to help you solve this question. There are 26 possible 1-letter words, 26 × 26 2 letter words, 26 × 26 × 26 3-letter words, and so on. So there would be 26^N N-letter words. This is exponential.
• Intractable
• Yes. If the string has N letters 'a' to 'z', then there are 26^N possible strings, which is exponential. This is similar to trying to crack a long password made up of lowercase letters. In this case, each letter in the password can be one of 26 possible letters. If you made such a password long enough (e.g., more than 15 letters), it would be fairly secure from brute force attack.

Q-4: True or False: An algorithm can be found for any computational problem whatsoever.

• True
• This is challenging, but rewarding! The Halting Problem is an example of an unsolvable problem.
• False
• Yes. The Halting Problem is an example of an undecidable problem, as Turing proved.

Q-5: The Halting Problemis an example of

• an intractable problem.
• This is challenging, but rewarding! Intractable problems are those for which there are known algorithms but the algorithms are exponential and therefore too inefficient to solve the problem for large N.
• an exponential problem.
• This is challenging, but rewarding! Exponential problems are those for which there are only exponential algorithms available. But the Halting Problem is not such a problem.
• an undecidable problem.
• Yes. As Turing proved, it is impossible to solve the Halting Problem.
• a difficult problem.
• This is challenging, but rewarding! The Halting Problem is an undecidable problem.

Q-6: True or false: All intractable problems (that cannot be solved in a reasonable time) are bad.

• True
• Let me add new information to help you solve this...Some intractable problems, such as the problem of breaking cryptographic keys, are helpful. In that case the intractability of the problem protects the security of our networks. There are many similar uses of such intractable problems in computing, many of which are used to make the Internet more secure.
• False
• Some intractable problems, such as the problem of breaking cryptographic keys, are helpful. In that case the intractability of the problem protects the security of our networks. There are many similar uses of such intractable problems in computing, many of which are used to make the Internet more secure.

5.9.6. Sample AP CSP Exam Question

Q-7: Under which of the following conditions is it most beneficial to use a heuristic approach to solve a problem?

• When the problem can be solved in a reasonable time and an approximate solution is acceptable.
• When the problem can be solved in a reasonable time and an exact solution is needed.
• When the problem cannot be solved in a reasonable time and an approximate solution is acceptable.
• When the problem cannot be solved in a reasonable time and an exact solution is needed.

5.9.7. 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.

You have attempted of activities on this page