What is an Algorithm?
Resources
Video Script
So what is an algorithm in computer science? A good definition for an algorithm is a finite list of specific instructions for carrying out a procedure or solving a problem. If you think about it, every computer program we write consists of many different algorithms. Because as we’ve learned, writing a computer program is exactly that. It’s giving the computer a list of very specific instructions that we’d like it to carry out so that it can perform a task or solve a problem for us. So let’s look at an example of what an algorithm looks like. One of the most common algorithms used today is Euclid’s algorithm. Euclid was a Greek mathematician from 300 B.C, and his algorithm was developed to find the greatest common divisor of two numbers. That greatest common divisor if you studied algebra is used to reduce fractions. And even today in our computers and calculators. We use a modified version of this algorithm to do exactly this task. It really is one of the most efficient ways to To do this, so let’s explore what Euclid’s algorithm looks like and take a look at an example.
So Euclid’s algorithm consists of four simple steps. The first step is you start with two numbers labeled A and B. In the second step, if either of those numbers is zero, the answer is obviously the other number. However, if neither of those numbers is zero, we’ll take the smaller number, and we’ll subtract it from the larger number. Then we’ll repeat those steps two through four until an answer is found. So what we will repeatedly do is take the larger number, subtract the smaller number from it, which will make the larger number smaller. And we repeat that process over and over and over again until we find an answer. So let’s take a look at an example and see how this works. So let’s look at an example of finding the greatest common divisor of 1071 and 462. So we’ll start with our two numbers 1071 and 462. Now, we know that we need to label these numbers A and B. So I’m going to label 1071 as A, and I’m going to label 462. as B. In the algorithm, we see the first step is to see if either of these numbers are zero. So looking at these numbers, 1071 and 462, neither of them zero, so we can move on to Step three, which is subtracting the smaller number from the larger one. So we’ll replace a with 1071. And we’ll subtract 462 from that. And that will give us the result 609. So now our numbers are 609 and 462. Once again, we start over at step two, we see that neither of these numbers are zero. So we do the same thing again, A is still our larger number. So we’ll do 609 minus 462 and we will get 147 and B will still be 462.
So we can keep repeating this process. Now B is the smallest number, so we’ll do 462 minus 147 and we will get 315. Now we have 315, 315 is again, let the larger number, so we’ll subtract 147 again, and this time we will get 168. And 168 is greater than 147 again, so we will subtract 147. And we will get, I’ll go over here to a second column, we will get 21. So now our numbers are 147 and 21. So once again, we need to subtract 21 from 147. And I’ll just kind of do this quickly. We’ll get 126 then we’ll get 105. Then we’ll get 84, 63, 42. then we will get 21. And we’ll notice that here, they’re both the same number. So if we subtract that again, we’ll get zero. And so now that we have zero as one of our numbers, we know that the greatest common divisor of 1071 and 462 is 21. This slide shows that example worked out a little bit clearer so you can follow it. If you’re interested in the greatest common divisor algorithm written by Euclid, I encourage you to pick just two random numbers and see if you can perform this same process. It should work on any two random numbers you pick, but we were very careful in picking 1071 and 462. So we got a larger number as the greatest common divisor. Don’t be surprised if you find out the answer is something small like two or three. That is pretty common as well.