We've been looking at common algorithms and talking about their complexity. For instance, linear and logarithmic. Because creating algorithms is so important to the computational thinking process, in this part of the course, we'll introduce some general approaches to developing algorithms. Many problems that we encounter in computational thinking involve taking a list or a collection of things and organizing them in some optimal way or finding some optimal subset of things from the list. When it comes to these sorts of optimization problems, finding not just a valid solution but the best solution, one approach that will always work is to try all possible solutions and choose the one that's best. After all, if you consider all the possible solutions, then you know for certain that at least one of them will be the one you're looking for. This is known as a brute force approach. You might imagine though that if you're using a brute force approach, there may be lots of possible solutions. So, in this lesson, we'll talk about three types of problems and the number of possible solutions that each has when using a brute force approach. Let's take a look at the first example. I live in Philadelphia and it's a great city for museums and one of the most famous is the Philadelphia Museum of Art. My wife and I love to go there and always want to see as many exhibits and attend as many events as possible, but we can only make it one day a month, and sometimes exhibits and events are only held on different days of the week or in different months. So, figuring out which day we should go each month is an optimization problem. We want to figure out on which day we should go each month so that we can do as many different things as possible. We won't actually work all the way through this problem, but let's see how many possible solutions there would be using a brute force approach. Let's just look at the first four months of the year. Here are all the dates when I can go to the museum. Remember, I can only pick one date from each month. In January, I can go on the 21st or 22nd, as we see in the top row. In February, I can go on the 11th,18th, 25th, 26th, or 27th. In March, there are four days when I can go, the 3rd, 10th, 11th or 12th. There three days I can go on April, the 12th, 19th, or 26th. So, I can only go once each month and I want to see as many exhibits and attend as many events as possible. Using a brute force approach, I can choose one day from each of the four months and then figure out how many different exhibits I'll be able to see using that combination of visits. I can do that for all possible combinations of days. Once I've looked at all those possible solutions, I can choose the one that allows me to see and do the most things at the museum. For instance, a possible solution is January 22nd, February 18, March 11 and April 12th. At this point, I don't know how many exhibitions I'll get to see because I don't have that info here, but the point is that those four dates represent one possible solution to this problem. So, how many possible solutions are there? That is, how many ways are there to choose one day from each month? Let's just look at January and February. For each of January's two options, there are five for February. So, let's say I go on January 21, then I can also go on February 11 or February 18 or February 25 or February 26 or February 27. If instead of January 21, I go on January 22, then I can also go on February 11, February 18 and so on. So, just for January and February, there are two times five equals 10 different combinations. Because there are two options for January and for each of these, there are five different options for February. So, for these four months, how many combinations are there? As we just saw, for January and February, there are two times five equals 10 combinations. For each of those 10, there are four options for March. So, now, we have a total of 10 times 4 equals 40 combinations. For those 40, there are three options for April, which brings us to 40 times 3 equals 120. So, to determine the total number of combinations, we just multiply the number of individual options and that tells us how many solutions we need to consider if we use the a brute force approach. So, we see that when determining the number of possible solutions using a brute force, we just have to multiply the number of options together. In this case, I can look at all 120 combinations and find the one that allows me to see the most exhibits. That seems like a lot of combinations to consider, but I know it will work. Because if I consider all possible solutions, then one of them must be best. Here's another problem related to scheduling, and again, what we're interested in, is determining the number of possible solutions. A few years ago, I taught a class with eight teaching assistants and I wanted to meet all of them once a week. I know the students are busy and it would be hard to get all of us together in the same place at a reasonable time of day. So, I gave them five options for meeting times as you see here, and then I wanted to choose some combination of meeting times so that I could meet each TA at least once during the week, even if it meant having multiple meetings. So, an algorithm we could use here is to use brute force to find all possible combinations of the five meeting times and then identify those combinations where I can meet all TA's and then optimize it by finding the combination with the smallest number of meetings because I'm busy too. So, how many possible solutions are there? To determine the number of possible solutions using brute force, we can look at each potential meeting time and say that we either will or will not include it in the solution. For example, from Monday 4:00 PM, I either do or do not have a meeting at that time. So, there are two options for Monday 4:00 PM because I either do or do not include it in the solution. Likewise for Tuesday 6:00 PM, I either do or do not include it in the combination of meeting times. So, there are two options for it as well and so on. Now let's look at the combinations of options like we did for the museum example starting with just the first two times. One combination is to have meetings at both Monday 4:00 PM and Tuesday 6:00 PM. That is, I can include both in my solution. Another combination is to have a meeting on Monday at 4:00 PM but not Tuesday 6:00 PM, that's part of another solution. The third combination is to not meet on Monday at 4:00 PM, but to meet Tuesday at six, that's yet another solution. The fourth combination of these two times is to not have meetings at either time. So, you see again that we're just multiplying the number of options. For each of the five meeting times, we either do or do not include it. So, we get two times two times two times two times two, that's two times itself five times because there are five meeting times and that equals 32, which not coincidentally is two to the fifth. This makes sense because for each of the possible meeting times, there are two options and there are five possible meeting times. Whereas some of the algorithms we've seen previously have linear or logarithmic complexity, we say that the brute force approach to this problem exhibits exponential complexity. If we have five options, we have two to the fifth possible solutions. If we increase it by one to six options, now we would have two to the sixth possible solution, which is twice as many. Keep in mind that with logarithmic complexity which we saw for binary search, this meant if you double the input size, you only have one more step as shown by the graph here. But exponential is the opposite. If you add even one more thing to the input size, you double the number of things to consider. This may seem bad because it means that there are so many more possible solutions to investigate as the input size increases. But unfortunately, there are some problems for which this is the only way to get the best solution. Let's look at one last example. In this case, the number of possible solutions resulting from a brute force approach will grow even faster than exponentially. Earlier, Sue talked about mulching her yard and that one variant of that problem is that she wanted to visit all eight flower beds with as little walking between them as possible. So, we'll say that she starts at the mulch deposit, which is over here, fills up her wheelbarrow, visits the flower beds, and brings the wheelbarrow back to the deposit when she's done at the end. So, what's the best route for Sue to take? One way we can solve this problem is by looking at all the possible routes between the flower beds and then finding the one that's shortest. So, how many possible routes are there? Well, a route here is a sequence of the eight locations where the order matters. Each route is a possible solution to this problem. When the order matters, we say that this is a permutation. So, how many different permutations of those eight things exist? So, as I said, Sue has to start at the mulch deposit, and then from here, there are eight places where she can go. That is, each of the eight different flowerbeds. Let's say that from the deposit, she decides to go to the tree first. After the tree, now there are seven places where she could go for the second flower bed. Regardless of which one of the eight she picked as the first flowerbed, after that there are seven possible places to go for the second, because she can't go back to the mulch deposit yet and she can't stay where she is. So, now let's say that after the deposit and then the tree, she'd goes to the patio next. After that, now she has six different flower beds to choose from since she can't go back to one of the two she's already done and she's not finished yet. So, regardless of which of the seven, she picked for the second flowerbed, there are six possible flower beds for the third and so on. So, how many possible solutions are there? Well, for the first flowerbed, there are eight possible options. For the second choice, there are seven. For the third, there are six and so on. This gives us a total of 40,320 different possible routes through the eight flower beds. That's 40,320 different permutations and this is eight factorial. You may recall the factorial means you take the product of an integer number and all the integers less than that number down to one. So, let's say that Sue adds another flowerbed to her garden and now instead we have nine options. How many permutations would there be now? Well, if we increase it by one to nine options, then we'd have nine factorial possible solutions or permutations. That's nine times eight times seven times six and so on, and this is over 360,000 possible paths through the garden. So, we say that this approach to solving this problem exhibits factorial complexity. Remember, with exponential complexity as we see here, if we add one more thing, we get two times as many possible solutions. But in this case with factorial complexity, if we go from eight to nine, we're not getting twice as many solutions, we're getting nine times as many. If we added another, we'd have 10 times more than that. Although you can't see it in this graph, if we had exponential complexity and 10 options, we have two to the tenth, which is 1,024. But, if we have factorial complexity, 10 factorial is greater than three million, and the numbers keep growing faster and faster after that. Like exponential complexity, this is bad in terms of the growth of the number of possible solutions but unfortunately, there are some problems for which this is the only way to get the best solution. In this lesson, we've looked at brute force algorithms as an approach to solving optimization problems. These are approaches in which we consider all possible solutions, identify the ones that at least give us a valid solution, and then choose the one that's best. This is always guaranteed to work because if we consider all possibilities, then one of them must be the best one. But in many cases, this can result in a huge number of possible solutions, which may be exponential or factorial with respect to the number of options. Since it may take a very long time to solve problems using brute force algorithms, in the next lesson, we'll see another approach that will be faster. Though it may not always produce the best solution, it can quickly find one that maybe close enough.