Last time, we talked about what an algorithm is, and as a reminder, an algorithm is a step-by-step plan for solving a problem or detailed set of steps that we follow to solve a particular problem. In this lecture, our problem is, we need to find the Queen of Hearts in the deck of cards. There's actually a constraint that I'm putting on your solution, your algorithm needs to be detailed enough that you could give it to an information processing agent, and that information processing agent could follow your set of steps and actually solve the problem. So if your information processing agent were a computer, you would express the algorithm in some programming language. It would need to be detailed enough that when you run the program on your computer, that it finds the Queen of Hearts. If you were to give it to a robot, the sequence of steps that you expressed for the robot to accomplish would have to find the Queen of Hearts in the deck. If you were going to give it to a sibling because you're trying to punish them for something, then you would need to give them sufficiently detailed steps. That last information processing agent, is the one that we're going to use as we try to come up with an algorithm. So at this point, you should pause the video and try to come up with a set of steps that you would follow to find the Queen of Hearts in a deck of cards. Once you have done so, unpause the video and we'll talk about some possible algorithms you might have come up with. Okay. So you may have come up with a perfect algorithm right out of the gate, and if you did that, great. But if you didn't, there are a number of reasonable possibilities you might have come up with that we should discuss. So here's the first one. We could just say, look through the deck for the Queen of Hearts and if you find it say so. There's a problem with this algorithm, and the problem is that it's not detailed enough. We are assuming that our information processing agent knows how to look through the deck, and also knows how to find the Queen of Hearts. Now, your sibling might be able to do that, but let's work a little harder at getting better detail in a better algorithm. So here is a slightly better algorithm, that says, if the top card is the Queen of Hearts say so, otherwise if the second card is the Queen of Hearts say so, and so on. This would work except, there are some problems here too. One of the problems, is that we're assuming we know how many cars are in the deck. Now, you could typically assume there are 52 cards in a deck unless you're not playing with a full deck. But making that assumption, makes our algorithm brittle against changes in the size of the deck of cards. We can come up with a more general algorithm that will work no matter how many cards are in the deck. Because if we ran an algorithm that was written for 52 cards and we had 53 cards in the deck, and the Queen of Hearts was the 53rd card, our algorithm wouldn't work The other problem is of course, that our algorithm gets very long and we're doing the same stuff. Time and time again we're checking a card, whether it's the first card, the second card, and so on. So our algorithm gets really long as we try to solve this problem. Let's take a look at one possible solution to this problem. So here's an algorithm that we could use, while there are more cards in the deck. If the top card is the Queen, then say so and discard the Queen. Otherwise, discard the top card. So what's wrong with this algorithm? Well, I'll claim nothing. There were probably some things wrong with it, but for this particular lecture, this is a good algorithm. It's sufficiently detailed. We do have to be able to tell if a particular card is a Queen and that's a pure comparison. We can easily write comparisons, encode, and we can tell our sibling how you can tell if a card is the Queen of Hearts and this is robust against. However many cards are in the deck, we will keep looking at all of them, looking for the Queen and either will find the Queen discard it and keep looking. Or will exhaust the deck of cards and we'll stop without breaking the algorithm. The other thing is, this algorithm actually will find multiple Queens of Hearts in the deck. So if you in fact find one and discard it, then you'll keep looking through the rest of the deck because you discarded that Queen of Hearts. Now, that was not a requirement of this particular problem. So you could argue that who cares? If in fact you wanted to exactly meet the requirements of the problem, then you could in fact just stop the algorithm when you found the first Queen of hearts. So let's talk about the fact that we're actually using three standard control structures in our solution to this particular problem. The first control structure is called sequence. We do something one after the other, we do them in sequence. So this step in our algorithm that says say so and discard the queen, is actually a set of two steps that we do one after the other. The second control structure that we've included, is something called selection. We use that control structure to make decisions in our algorithm. In our particular algorithm, we're saying if the top card is the Queen. So we're actually using that condition to say if it is the Queen do this, and if it's not the Queen do this other thing, and that's called the selection control structure. The final control structure that we've included in our algorithm, is called iteration or looping. We use it to do something repetitively, and that is the while there are more cards in the deck. While there are more cards in the deck, we do that stuff checking to see if the top card is the Queen and taking action based on whether that's true or not. So why do we care about these control structures when we're building algorithms? Well, when we're building algorithms, we can think of these control structures as building blocks that help us build the set of steps we need to solve a particular problem. If you are in fact going to express your algorithm in a programming language, you'll discover that most modern programming languages support these three different control structures that we again use as building blocks to solve a particular problem. So there you have it. Your first practice, developing a detailed algorithm to solve a particular problem.