There are undecidable problems – cannot be solved by an algorithm.

There are intractable problems – problems for which we only have inefficient algorithms.


  • example – decidable, ie. is a given #M
  • cannot answer yes or no to a question


  • heuristic algorithms – algorithms that usually work
  • take expenential – Y=2 to the N

Dictionary attack – looks for every word in the dictionary. That is why you don’t use a single work for a password.

Brute force attack – tries every possible combination.

  • for M number of possible letters, number, symbols – and N is the number of characters in the password, it would take M to the N possible guesses to guarantee finding the password

9 character passwords with a mix of upper case, lower case, numbers, and special characters is the strongest.



  1. (POGIL) 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.
    1. 9 character password using lower case letters, numbers, and special characters would take 12.8 years to crack.
  2. (POGIL) According to this 2012 article, a password-cracking computer can try 350 billion passwords per second. How would you have to modify your scheme to withstand a 10-year attack by this specially designed computer?
    1. I would say you would have to increase the number of characters to at least 11.
  3. (POGIL) That article was written in 2012, almost 5 years ago. Password cracking technology has probably gotten a lot better. Suppose the number of passwords that can be checked per second doubles every year, use the Password Strength Calculator to determine an optimal password scheme for the year 2020?
    1. You would have to have at least 12 characters and introduce upper case letters as well.
  4. (POGIL) For routes starting and ending at Trinity College, identify the nearest neighbor route and the optimal route. What does this show you about the nearest neighbor heuristic?
    1. It gets you there but is not always the most efficient result.