Now let's finish this part of the course by looking at the pseudocode for our two case studies. Keep in mind that the goal of pseudocode is to communicate an algorithm in a fairly structured way based on the operations of a computer. This will later allow us to more easily convert this into a program using a language that the computer can understand. Let's start with Erin from the LGBT Center. Remember that Erin was trying to figure out how to schedule meetings with the 27 groups that the center supports. Using computational thinking, Erin was able to use decomposition to break this problem into smaller sub-problems. One problem was determining which group to meet. The other was removing any meeting requests that overlapped with that one. She use pattern recognition to realize that there's a repeated process of deciding which group to schedule by looking at all the requests and choosing the best one. She used data representation and abstraction to represent the meeting requests as two numbers; the start time and the end time. Finally, she could use computational thinking to develop an algorithm for solving this problem. This is the flowchart we saw for that algorithm in the last part of the course. It's definitely more structured than the plain text description, but we can't ask the computer to execute this algorithm in this form. We might be able to write our program just using this diagram, but writing the algorithm in pseudocode is an intermediate step that will make writing the program easier. So, for this algorithm, we'll say that the input is a collection that will call requests. Any elements represent each meeting request. Remember using computational thinking in the pillar of data representation and abstraction, we said that Erin can represent a request using just its start and end times. The output will be a collection called scheduled requests that contains the maximum number of meeting requests such that none overlap. Here's a slightly different way of expressing the algorithm, but the main idea is the same. We have two steps and keep repeating them as long as there are more meeting requests. First, we find a meeting request that we want to schedule, then we remove all the meeting requests that overlap with it, and we continue. Now, here's the pseudocode for the first step, which is finding a request to schedule. We'll use the greedy approach that we saw earlier in which we choose the meeting request with the earliest ending time. This syntax may seem a little bit scary, but it's all things we've seen before. We're just going to look through the collection and requests and find the minimum value, which we've seen a few times now. So, we have a variable called earliest request, and initially set that to the first request in the collection. We'll use the subscript notation here and say this is index zero, the first request in the collection. We'll also set the earliest end time to be the end time of that first request. Now we have this loop, and we're going to do this for each request in the collection. If the end time is less than the earliest end time we've seen so far, then we'll update earliest request and also the earliest end time. This is exactly like we saw earlier in the course with finding the smallest value in a collection. When we're done looping, we know that earliest request represents the request with the earliest ending time, and we add it to our collection which we'll use for holding the output. So, that's the first part, finding a request to schedule. Now let's look at the pseudocode for the second part of the algorithm, which is removing any requests that cannot be scheduled. Keep in mind that this is still part of our loop that keeps repeating while the collection of requests is not empty. A request overlaps with the one we've just scheduled if its start time is before the earliest requests ending time. So, we'll loop over all the requests, compare the start time to the ending time of the one we just scheduled. If it starts before the scheduled one ends, then we'll remove it from the collection. Let's finish with our other case study from the Working Dog Center. Remember that Cindy was trying to predict whether a dog would be suitable for disaster search and rescue based on whether the three most similar dogs were also suitable. We saw on the first part of the course that Cindy can solve this problem using computational thinking. She could use decomposition to break this problem into three smaller problems: first, determining the similarity between the new dog and the other dogs; second, finding the three most similar dogs; and third, doing a vote based on whether those three dogs were suitable for search and rescue. Using pattern recognition, Cindy discovered that there are repeated processes of calculating the similarity for each dog in the same manner, but also in using the individual test results in the same manner to perform that calculation. In solving this problem, Cindy can represent each dog as a collection of values which are their individual test results and whether they are suitable for disaster search and rescue. Then, she could develop an algorithm that, as we saw previously, is actually a well-known machine learning algorithm called K-nearest neighbors. Let's take a quick look at the flowchart for the prediction algorithm which involves lots of if-then else statements and loops, but consists of the three main parts that we saw from the decomposition pillar of computational thinking. Now we'll look at the pseudocode for this algorithm. The input will be a collection that we'll call dogs. Using the computational thinking pillar of data representation and abstraction, we'll say that dog can be represented as the results of its three tests that I'm highlighting here. It will also include whether or not it's suitable for search and rescue and how similar it is to the new dog. The other part of the input is information about the new dog itself, which we'll represent just as the results of the three tests. The output is the prediction of whether the new dog will be suitable for search and rescue. We'll take the three dogs that have the highest similarity values and then take the majority value for their suitable values. Recall that using the computational thinking pillar of decomposition, Cindy broke this problem into three sub-problems, and we can look at the pseudocode for each individually since they comprise the overall solution. First, let's look at calculating the similarity for each dog. Using the computational thinking pillar of pattern recognition, Cindy saw that we do the same steps for each dog, which here we will represent using this loop. For each dog in the collection, we initialize its similarity value to zero. Then we'll compare the results of the three tests between this dog and a new dog. Each time the results of the test is the same, we'll add one to the similarity, so that at the end, the similarity value holds the number of tests for which this dog and a new dog had the same results. Now let's look at the second step, which is finding the three most similar dogs. That is, the three dogs with the highest similarity values. This is very similar to the algorithm we saw on previous part of the course in which we look for the largest value in a collection, and it's also similar to the scheduling algorithm we just saw, except that that one was looking for the smallest value. Because we're looking for the three highest values, we'll repeat these steps three times. We'll say that the most similar dog is the first one in the collection, and the highest similarity so far is that dogs similarity. Then for each dog in the collection, if it's similarity is greater than the highest one we've seen so far, then we'll update the highest similarity score and say that this dog is the most similar. When we're done looking, we can add that most similar dog to a collection called similar dogs and remove it from the collection of all the other dogs. Now we're almost done. We know the three most similar dogs. So, let's do a vote based on whether they were suitable for disaster search and rescue. We'll initialize the vote to zero and then iterate over the three dogs in the similar dogs collection. If the dog in the collection was suitable for search and rescue, we'll increment the value of the vote. Since there are three dogs, a majority would be two or more. So, if the total vote is greater than or equal to two, then we output true, meaning that we predict that the new dog will be suitable for disaster search and rescue based on whether the majority of the three most similar dogs were suitable. But if the vote is less than two, then we'll output false, which means that we predict that this dog will not be suitable for search and rescue since the majority of the most similar dogs were not suitable. Using computational thinking, Erin from the LGBT Center and Cindy from the Working Dog Center were able to identify systematic ways to approach their problems and develop algorithms for solving them. In this lesson, we've seen how we can structure those algorithms based on the fundamental operations of a modern computer. We'll revisit the pseudocode definitions when we wrap up these case studies and look at how we express these algorithms to a computer in the next part of the course. As we move through this course, you'll notice that we started out a bit abstract, and are now getting more concrete. When it comes to computational thinking and algorithms, there may be many options for how you will apply the pillars or which algorithms you choose. But when you're expressing that algorithm to a computer, there's not a lot of room for ambiguity. Just about every modern computer is an instance of the von Neumann architecture, and there are certain things it can do in certain ways in which it works. That's why we spent this part of the course talking about how it stores and organizes data and how it executes instructions. No matter what programming language you use, whether it's Java, or C, or Python, you're still pretty much telling it to do the same things. You're just using a different language or syntax for that. So. Now that you have a good understanding of algorithms and what a computer is capable of, your ready to conclude your journey from computational thinking to code. In the next part of the course, we'll start looking at the Python programming language.
