Algorithms and selection

0:00- [Instructor] Imagine you're playing a word game where you need to guess only three-letter 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.

0:17We 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.

0:31These 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.

0:45We've seen control flow in our programs that uses 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.

1:00With our word game, we might still start with a 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.

1:13Here we ask, is there an E? If the answer is no, we wanna 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.

1:27If the answer to our question, is E the last letter of the word, is yes, then we're likely to have an O-E or an I-E 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.

1:42It'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.

1:57An 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 wanna think about how we're going to go about solving a problem before we start writing code.

2:13So 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.

2:32Correctness, 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.

2:50If 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.

3:12In 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.

3:41Try giving those 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 eight minutes, then maybe this is the better route.

3:57As 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.