Algorithms and selection | Intro to CS - Python | Khan Academy

Imagine you're playing a word game where you need to guess only three words. What strategy might you use to solve for all the words in this game? One approach might be to just guess all of the letters in alphabetical order. So you start by guessing A, then you guess B, then you guess C, and so on until you get the full word.

We think we can be a bit more clever than that. So what if instead we guess the letters in order of how frequently they occur in the English language? Both of these processes will get to the correct solution eventually, but neither is particularly clever or efficient. These solutions do the same exact thing every single time. They don't take new information into account to inform what they do next. For example, that there is an E and it's the last letter of the word.

To do this, we need a new type of control flow called selection. We've seen control flow in our programs that use a sequence where one step comes after the other. Selection allows our control flow to branch. We ask a yes or no question, and then based on the answer to that question, we select which branch to continue down, skipping the other branch entirely.

With our word game, we might still start with the step that guesses the letter E. But then we might pause here to consider the information we have available and then decide what to do next based off of it. We'll use a control flow diagram to model all the different paths that are available.

Here we ask: Is there an E? If the answer is no, we want to keep trying to find the vowel, so we'll guess A. If the answer is yes, then the best letter to guess depends on whether that E is the first, second, or third letter of the word. So we make another selection. If the answer to your question is E, the last letter of the word is yes, then we're likely to have an OE or an IE ending, since those are pretty common. So our next step in this process on this branch will be to guess I.

We can continue on in this way until we have a complete process. It's a lot more complex than our first two processes, but we can easily see how this process is more likely to get the correct word in fewer guesses.

Now for the terminology, all these things I've just been calling processes in computer science. These are called algorithms. An algorithm is just a repeatable process to accomplish a task. Like we saw, algorithms are programming language independent. We express them in English or any other natural language you may speak.

As programmers, we want to think about how we're going to go about solving a problem before we start writing code. So we often spend the majority of our time designing, evaluating, and iterating on our algorithms. Only at the very end do we work on translating our algorithm into code.

In programming, there are always many solutions to a problem. To evaluate which algorithm is best for a specific use case, we look at three characteristics: correctness, does the algorithm accomplish the task; efficiency, how long does it take to accomplish the task; and readability, how complex is the process and how hard is it for somebody to understand?

There's often not an objective best solution. It's all in how you evaluate the trade-offs. If I design a search algorithm and when someone searches for "study music," I return playlists of like really intense German bass, then the correctness of my algorithm is probably a bit off.

If someone searches for a really generic word like "the," and I have 100 million songs in my database, it might take a really long time for me to find all of the songs that have the word "the" in them, which makes my algorithm not super efficient. In this case, I might choose to sacrifice some of the correctness in order to get efficiency. So instead of looking for all of the songs that have the word "the," I might choose the 20 most common and say that's good enough.

If I design a route finding algorithm and maybe technically the quickest way to get from point A to point B is to take a route with like 20 different turns and change my mind on which way to go depending on if the stoplight is green or red, well, it's certainly efficient and it's correct. It reaches the destination, but it's not so readable.

Try giving these directions to your friend and see if they can figure it out. Maybe there's also an option here to take a back road with no turns and a slightly lower speed limit that's a lot more readable. So if the efficiency trade-off is minimal—like this takes 10 minutes and the other way takes 8 minutes—then maybe this is the better route.

As we design our own algorithms with sequence and selection, we should always keep these trade-offs in mind, which brings us to our next step: translating our algorithms with selection into code.