In this part of the course, we're going to look at some common algorithms that are used throughout computing. We will do this not only to give you some examples of algorithms, but also, so, you can see how we analyze them. In order to understand how long they will take to execute, and how we can express them? So, that they can be ultimately coded. Recall from the working dog center case study, that we determined the similarity between the new dog and all the other dogs. Wanted to find the dogs that are most similar, or have the highest similarity. On this slide, you can see eight dogs, in the working dog center. A number representing their similarity to a new dog. Such as that. We want to find the most similar dog. So, the problem really is to find the maximum value, in this collection of numbers. Finding the maximum value, in a collection is a common problem, or component of a larger problem in computer science. So, let's look at these eight values. Which of these is the largest? The answer of course, is 90.4, right here. So, how did you do this? Well, your eyes have gotten pretty good at looking at lots of pieces of data and making quick subconscious decisions about them. You've probably had a lot of experience comparing numbers and recognizing them quickly by their shapes. You may have looked for the number that starts with the largest digit, which in this case, happens to be the largest number. Although, it wouldn't have been, if you had the number 100 as well. Unfortunately though, a computer can't do these types of things. As we'll see in the next part of the course, the computer can only perform binary operations. That is operations that take two operands, such as adding two numbers, or multiplying two numbers, or comparing two numbers. In that case, the computer can't just look at all eight numbers and find the largest. It can only inspect them one at a time. So, given the limitations of operations that only take two operands, what algorithm should we use? In particular, if we asked you to solve the problem of finding the maximum value by only comparing two numbers at a time, what would you do? Let's see, how it might work. You just remember the largest value you have seen so far, starting with the beginning of the list, and then consider each subsequent number. End of this figure, you'd update the largest value so far. For example, given the following list of numbers which are the similarities from the working dog center, you'd start by saying that the first, 52.3 is the largest seen so far, and remember it. We'll call this the variable max, for short. We're going to use the convention, the black numbers represent those that remain to be looked at and green represents the max. Comparing max in green, with the next number 81.2, shown in red, you'd update the max to 81.2. Since it is larger than the current largest of 52.3. Comparing with the next 33.6, you wouldn't update the max, you'll stay with the current value of 81. 2. Note that we're graying out the values that have already been compared, and keeping those that remained to be compared in black. The same would happen for the next two numbers on the list, 17.3 and 25.1, since, they are both smaller than the current max, shown in green, which is 81.2. However, the next number on the list, 90.4, is larger than 81.2. So, 90.4, would become the max. Comparing with the last two numbers 28.2 and 43.1, would not change the max, since, they are both smaller than 90.4. We're done with the list, there are no numbers remaining to be compared. So, the final result is 90.4, shown here in green. Now, that we figured out, how to find the max by comparing only two numbers, how would we communicate that algorithm to someone else? More specifically, how could we communicate it to a computer? We will answer the second question later in the course, but for now, let's just write it out in English. At first, the max is the first value on the list. Then we look at each value in the list. If it is greater than the current max, then that value becomes the max, otherwise, the max remains the same. After going through the entire list, the current max, is the maximum of the value in the list. We can express this, using the following flowchart. First, we get the input list. If it is empty, then there is no max value. So, we output N/A, for not appropriate, and we stop. Otherwise, we read the first item in the list, and store it as max. We now enter a repeated behavior, where we test an item against max, and update max, depending on whether or not it is larger. The first time the item is max, so, the test fails, and we just read the next item in the list. If a subsequent item is larger than the current max, then we would also update max. When there is no next item, we output the max, and stop. Otherwise, we continue through the list. Now let's say we want to find the minimum value in a collection. Well, the algorithm is almost the same. Here's the algorithm, again expressed as a flowchart for finding the minimum value. Note that the algorithm is almost the same, except that we will remember the minimum found so far. We will also check, if each successive element is smaller than the current minimum. Again, when we get to the end of the list, we're done and output min. In this lesson, we've looked at a common computational problem. Finding the maximum or minimum value, in a list or collection. This often arises as a component of the larger problem. Although, humans can look at a collection of numbers and somehow process them all at once. A computer can only perform operations that take two numbers at a time. These are called binary operations. So, we came up with a solution, that the computer could use. Remember the current largest value in the collection, we call this max, and compare against the next untested value. The result is the value in max, when all items in the collection have been tested. We showed how this algorithm could be represented as a flowchart and notice that a minor change to it, remembering the smallest value seen so far, instead of the largest, could be used as a solution for finding the minimum value in a collection. In the next lesson, we'll look at another closely related and common problem, searching a collection for a value. Previously, we talked about, how pattern recognition is one of the pillars of computational thinking. Finding the maximum value, has the same pattern as finding the minimum value, it is just slightly different. It doesn't matter, whether we're comparing numbers, or words, or even dogs, the algorithm to find the maximum element is the same. This is important in computational thinking, and in programming. You'll be able to solve lots of problems using similar algorithms, once you're able to recognize the patterns.
