ALGORITHMS
Game (High Stakes!)
On the board there are 13 blank circles and 1 shaded circle.
We’ll take turns removing blank circles until only the shaded circle is left. We can remove 1, 2 or 3 blank circles at a time.
If I end up with the shaded circle, you get….
If you end up with the shaded circle, I get….
[Students can choose whatever they want; just follow the algorithm a few slides down and you’ll win every time. Just be careful!]
So You Need to Tile a Floor…
Suppose you want to cover a rectangular surface with square tiles, and you want these tiles to be as large as possible. The dimensions of the surface are 1456 x 398cm. What size tiles should you use?
1456cm
398cm
So You Need to Tile a Floor…
Notice that this is a question of finding the greatest common factor between the length and width of the rectangle.
1456cm
398cm
So how do we do that?
“Euclid’s Algorithm” (Used in Proofs VII.1, VII.2, X.3)
Step 1: Subtract the smaller number from the larger number as many times as possible (i.e. until you get a remainder less than the smaller number).
Step 2: Subtract the remainder from Step 1 from the smaller number in Step 1 as many times as possible.
Step 3: Subtract the remainder from Step 2 from the smaller number in Step 2 as many times as possible.
�
Repeat this procedure until there is no remainder. The GCF of the original two numbers is the number which leaves no remainder when subtracted.
1456 – 398 – 398 – 398 = 262
398 – 262 = 136
262 – 136 = 126
136 – 126 = 10
126 – 10 (12) = 6
10 – 6 = 4
6 – 4 = 2
4 – 2 – 2 = 0
So the GCF is 2!
Algorithms
An algorithm is a precise set of instructions for carrying out a procedure or solving a problem in a finite series of steps.
The word "algorithm" comes from a Latin distortion of “al-Khwarizmi,” (man of Khwarizm), referring to an important 9th c. Persian mathematician named Abu Jafar Muhammad ibn Musa.
(“al-Khwarizmi” became “Algorithmi”.)
https://en.wikipedia.org/wiki/Muhammad_ibn_Musa_al-Khwarizmi
al-Khwarizmi, 780-850
The Algorithm Behind Our Game Earlier
Step 1: Make the first move by removing one blank circle, leaving 12.
Step 2: In the next move, remove 4 – n blank circles, where n is how many circles the other person took. (In this way the other person is always left with a multiple of 4.)
Repeat until there are 3 or fewer blank circles left. Then take the remaining blank circles, leaving the shaded one to the other person.
Key Features of Algorithms
Algorithms have an input (the information in the problem) and an output (the result or solution the algorithm generates).
In order to work, algorithms need to be unambiguous. All terms must be precisely defined in order for each step to yield a definite result.
Algorithms take time.
�
For successful algorithms, it can be proven that they work in all cases.
Another Problem
Given a list of positive numbers, identify the largest number on the list.
So the input for the algorithm is a list of positive numbers, and the output is a single number, the largest in the list.
Create an algorithm to perform this task.
Solution 1
Input: 56, 32, 67, 2, 30, 95, 28, 57, 3, 1, 98
1. Set MAX to 0.
2. Compare n1 to MAX. If n1 > MAX, set MAX to n1.
�
3. Repeat for each subsequent number.
4. MAX is now set to the largest number on the list.
Solution 2
Input: 56, 32, 67, 2, 30, 95, 28, 57, 3, 1, 98
1. Compare n1 and n2. If n1 > n2, reverse their order.
2. Repeat for each subsequent pair.�
3. Return to the first pair and repeat the whole process until no pairs are reversed.
4. The largest number is now the last one in the list.
Comparison
Which of these two algorithms is better?
Usually this comes down to a question of efficiency: Which one is faster? Which one has fewer steps?
Solution 1 is better, since this algorithm will only go through the list of numbers once. In Solution 2, the algorithm will go through the list repeatedly, until the numbers are in ascending order.
Sorting Algorithms
The second solution is an example of a sorting algorithm, i.e. an algorithm that sort inputs into a desired order.
The Secret Rules of Modern Living: Algorithms
https://www.youtube.com/watch?v=kiFfp-HAu64
(13:45-22:00)
The Google Search Engine
The Secret Rules of Modern Living: Algorithms
https://www.youtube.com/watch?v=kiFfp-HAu64
(8:25-13:42)
(2) Do you think this makes a Google search objective, or is it
biased in some way?
Matching Algorithms
The Secret Rules of Modern Living: Algorithms
https://www.youtube.com/watch?v=kiFfp-HAu64
(22:00-32:15)
(2) What are some examples of problems that matching
algorithms solve?
ALGORITHMS 2
The Limits of Algorithms
There are problems for which it’s been proven that no efficient algorithm is possible. (An efficient algorithm is one that can be run in a reasonable amount of time.)
For other problems, no efficient algorithm has been found, but it’s unknown whether or not one is possible.
The Secret Rules of Modern Living: Algorithms
https://www.youtube.com/watch?v=kiFfp-HAu64
(32:23-42:40)
Algorithms and Time
Computer scientists call the number of elements inputted into an algorithm N.
What is the relation between N and the time it takes the algorithm to solve the problem?
Clearly, as N increases, the time increases as well, since more input means there is more for the algorithm to work through, and hence more steps it has to take.�
Two Sets of Problems: P and NP
For one set or group of problems, as N increases, the time required increases at a manageable rate. This set of problems is called P.
For another set of problems, as N increases, the time required increases at an unmanageable rate—with even a modest amount of input the algorithm would take thousands or even millions of years. This set of problems is called NP.
Problems in the P Set
A polynomial (“many-termed”) expression consists of numbers (constants) and/or variables and involves only the operations of addition, subtraction, multiplication and non-negative integer exponents. E.g. 2x + 3x3 or 23x2 -17 + x6
For some algorithms, the time required can be expressed as a polynomial involving N (the number of elements inputted); for example, the time might be 2N, 3N + 2, N2, N3, etc.
In this case, as the number of elements inputted increases, the time required increases in a manageable way. The algorithm remains efficient.
�
The set (group) of problems that can be solved by algorithms like this is called P (for “polynomial time”).
Examples of Problems in P
Problems in the NP Set
For other algorithms, the number of elements inputted (N) is an exponent in the expression of the time required. For example, the time required might be 2N, 3N, 4N, and so on. (These expressions are not polynomials since the exponent is a variable, not an integer.)
In this case, as the number of elements inputted increases, the time required increases astronomically. The algorithm is not efficient; in some cases it would take millions of years for it to solve the problem.
�
The set (group) of problems that seem to require algorithms like this is called NP (for “non-deterministic polynomial” or “exponential” time).
Yet even though the algorithm takes impractically long to yield a solution, any proposed solution can be checked or tested in a reasonable amount of time.
Examples of Problems in NP
� Million-Dollar Question: Does P = NP? �http://www.claymath.org/millennium- �problems/p-vs-np-problem
Does P = NP?
Two sets or groups are equal iff everything in one is also in the other.
So if P = NP, then all the problems currently in NP (all the problems we have no efficient algorithm for, but whose solutions we can check efficiently) are actually in P (they do have efficient algorithms; we just have to figure out what they are).
If P does not equal NP, then the NP problems really are impossible.
�
Create an algorithm to factor any number into its prime components.
Prime Factorization: A Very Significant NP Problem
Problem: Given any composite number, find its prime factors. (Recall the FTA: Every natural number is either prime or the product of exactly one set of primes.)
An algorithm for factoring:
�
Example: Factor 2574 into its prime components.
2574
Try 2 again; doesn’t work. So try 3.
Try 3 again.
�
Try 3 again; doesn’t work. So try 5; doesn’t work. So try 7; doesn’t work. So try 11.
2 1287
3 429
3 143
11 13
11 is greater than √13, so stop.
So the prime factors of 2574 are 2, 3, 3, 11, 13.
Try 2.
Why Prime Factorization is an NP Problem
This was quick, but how much longer would it take to factor much larger numbers? (How drastically does the time required increase as the input increases?)
It turns out that as the number to be factored gets bigger, the time required to factor it increases astronomically. For example, suppose you’re given the number 1 459 160 519 and told that it is the product of two prime integers. To solve this problem, a computer has to check most of the possible combinations. For any size number, the number of combinations the computer has to check is approximately the square-root of the number to be factored. So to find which two numbers multiplied together produce 1 459 160 519, the computer must check roughly 38 000 combinations.
�
This won’t take the computer very long, but what if the number to
be factored is not ten digits, but 400 digits? The square-root of a number with 400 digits is a number with 200 digits. The lifetime of the universe is approximately 1018 seconds—an 18 digit number. Assuming a computer could test one million factorizations per second, in the lifetime of the universe it could check 1024 possibilities. But for a 400 digit product, there are 10200 possibilities. This means the computer would have to run for 10176 times the life of the universe to factor it! (From Kathryn Mann, “The Science of Encryption”)
Yet, like other NP problems, even though an algorithm takes impractically long to yield a solution, any proposed solution can be checked or tested quite easily (you just multiply the possible factors together to see if they yield your number).
More on recent advances in factoring very large numbers: https://aiimpacts.org/progress-in-general-purpose-factoring/
Prime Factorization and Internet Security
As an NP problem, prime factorization is at the heart of encryption on the Internet.
Reading: https://math.berkeley.edu/~kpmann/encryption.pdf�