yego.me
💡 Stop wasting time. Read Youtube instead of watch. Download Chrome Extension

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


4m read
·Nov 10, 2024

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.

More Articles

View All
The Most Likely End to The Universe
Imagine living a life filled with happiness and pain, love and grief, ambition and despair. A life with parents, kids, grandkids, and ultimately the death of everyone, including yourself. And then it all happens again in the same way. You make the same ch…
Hindu scripture overview | World History | Khan Academy
As we’ve mentioned in previous videos, Hinduism is a very diverse religion with many different practices and even different beliefs. But there is a core centered around scripture, and the most important of these texts are the Vedas. Now, the word Veda lit…
Functions with same limit at infinity | Limits and continuity | AP Calculus AB | Khan Academy
The goal of this video is to get an appreciation that you could have many, in fact, you could have an infinite number of functions that have the same limit as X approaches infinity. So, if we were to make the general statement that the limit of some funct…
Peter Lynch: The Secret to “Buying the Dip"
Anyone that’s been following this channel knows that I’m a huge fan of Peter Lynch. Lynch rose to prominence running the legendary Fidelity Magellan Fund and writing books such as “One Up on Wall Street,” one of my top five favorite investment books of al…
What Is Video ??
Hey, Vsauce. Michael here, and I just got back from VidCon. The entire convention was incredible, but the whole time I was there I thought a lot about video. We all watch video and many of us work with video, but what is it? I mean, what really is video? …
Our Bank Went Bankrupt
So our bank went bankrupt last Friday, but it’s not just us. In fact, most tech startups in Silicon Valley and over 2,500 Venture Capital firms held their funds with the 16th largest bank in the United States. Of course, we’re talking about the Silicon Va…