What’s an algorithm? – David J. Malan By TED-Ed

What’s an algorithm in computer science? An algorithm is a set of instructions for solving. Some problem. Step by step. Typically algorithms are executed by computers. But we humans have algorithms as well. For instance. How would you go about counting the number of people in a room? Well, if you’re like me, you probably pointed each person one at a time and count up from 0 1, 2 3 4.

So forth. Well, that’s an algorithm. In fact, let’s try to express it a bit more formally in pseudocode english-like syntax that resembles a programming language let N equal 0 for each person in room set, n equal to n plus 1, how to interpret the pseudocode. Well line, one declares. So to speak a variable called n in initialize, has its value to 0. This just means that at the beginning of our algorithm, the thing with which we’re counting has a value of 0. After all, before we start counting, we have encountered.

Did anything yet calling this variable? N is just a convention. I could have called it most. Anything now line to De marks the start of a loop, a sequence of steps that will repeat some number of times. So in our example, the step we’re taking is counting people in the room beneath line. 2 is line 3, which describes exactly how we’ll go about counting the indentation implies that it’s lined 3 that will repeat. So what the pseudocode is saying, is that after starting at zero for each person in the room will increase n by 1. Now is this

Correct. Well, let’s bang on it a bit. Does it work? If there are two people in the room? Let’s see in line one. We initialize n to 0 for each of these two people. We then increment n by 1. So, on the first trip through the loop. We update n from 0 to 1 on the second trip, through that same Loop. We update n from 1 to 2. And so by this algorithms end, n is 2 which indeed matches the number of people in the room so far. So good. How about a corner case though? Suppose that there are zero people in the room.

Umm, besides me, who’s doing the counting in line one. We again initialize n to 0 this time though. Line 3 doesn’t execute at all since there isn’t a person in the room and so and remain zero, which indeed matches the number of people in the room, pretty simple, right. But counting people wanted a time is pretty inefficient to know surely we can do better. Why not count two people at a time instead of counting 1 2 3 4 5 6 7 8 and so forth. Why not count 2 4 6 8 and so on it even sounds

It’s faster, and it surely is, let’s Express this optimization and pseudocode, let N equal 0 for each pair of people in room set. N equal to n plus 2, pretty simple change, right? Rather than count people. Wanted a time. We instead count them two at a time. This algorithms does twice as fast as the last but is it correct? Let’s see. Does it work? If there are two people in the room in line one, we initialize n to 0 for that one pair of people. We then increment n by 2. And so by this

Algorithms end and is to which indeed matches, the number of people in the room suppose next, that there are zero people in the room in line one. We initialize n to 0 as before line 3, doesn’t execute it. All since there aren’t any pairs of people in the room and so and remain zero which indeed matches the number of people in the room, but what if there are three people in the room? How does this algorithm Fair? Let’s see in line one. We initialize n to 0 for a pair of those people. We then increment n by 2, but then what?

There isn’t another full pair of people in the room so blind to no longer applies. And so by this algorithms end, n is still too, which isn’t correct, indeed? This algorithm said to be buggy because it has a mistake. Let’s redress with some new pseudocode. Let N equal 0 for each pair of people in room set, n equal to n plus 2, if one person remains unpaired Set, n equal to n plus 1, to solve this particular problem. We’ve introduced in line for a condition. Otherwise,

Known as a branch that only executes, if there’s one person we could not pair with another. And so now whether there’s one or three, or any odd, number of people in the room, this algorithm will now count them. Can we do even better? Well, we could count in threes or fours or you can fives and tens, but beyond that it’s going to get a little bit difficult to point at the end of the day whether executed by computers or humans, algorithms are just a set of instructions with which to solve problems. These were just three what problem with you solved with a