Placeholder Image

Subtitles section Play video

  • 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 point at each person,

  • one at a time,

  • and count up from 0:

  • 1, 2, 3, 4 and 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 = n + 1.

  • How to interpret this pseudocode?

  • Well, line 1 declares, so to speak,

  • a variable called n

  • and initializes its value to zero.

  • This just means that at the beginning of our algorithm,

  • the thing with which we're counting

  • has a value of zero.

  • After all, before we start counting,

  • we haven't counted anything yet.

  • Calling this variable n is just a convention.

  • I could have called it almost anything.

  • Now, line 2 demarks the start of 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 line 3

  • that will repeat.

  • So, what the pseudocode is saying

  • is that after starting at zero,

  • for each person in the room,

  • we'll increase n by 1.

  • Now, is this algorithm correct?

  • Well, let's bang on it a bit.

  • Does it work if there are 2 people in the room?

  • Let's see.

  • In line 1, we initialize n to zero.

  • For each of these two people,

  • we then increment n by 1.

  • So, in the first trip through the loop,

  • we update n from zero to 1,

  • on the second trip through that same loop,

  • we update n from 1 to 2.

  • And so, by this algorithm's 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,

  • besides me, who's doing the counting.

  • In line 1, we again initialize n to zero.

  • This time, though, line 3 doesn't execute at all

  • since there isn't a person in the room,

  • and so, n remains zero,

  • which indeed matches the number of people in the room.

  • Pretty simple, right?

  • But counting people one a time is pretty inefficient, too, no?

  • 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 faster, and it surely is.

  • Let's express this optimization in pseudocode.

  • Let n equal zero.

  • For each pair of people in room,

  • set n = n + 2.

  • Pretty simple change, right?

  • Rather than count people one at a time,

  • we instead count them two at a time.

  • This algorithm's thus twice as fast as the last.

  • But is it correct?

  • Let's see.

  • Does it work if there are 2 people in the room?

  • In line 1, we initialize n to zero.

  • For that one pair of people, we then increment n by 2.

  • And so, by this algorithm's end, n is 2,

  • which indeed matches the number of people in the room.

  • Suppose next that there are zero people in the room.

  • In line 1, we initialize n to zero.

  • As before, line 3 doesn't execute at all

  • since there aren't any pairs of people in the room,

  • and so, n remains zero,

  • which indeed matches the number of people in the room.

  • But what if there are 3 people in the room?

  • How does this algorithm fair?

  • Let's see.

  • In line 1, we initialize n to zero.

  • 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 line 2 no longer applies.

  • And so, by this algorithm's end,

  • n is still 2, which isn't correct.

  • Indeed this algorithm is said to be buggy

  • because it has a mistake.

  • Let's redress with some new pseudocode.

  • Let n equal zero.

  • For each pair of people in room,

  • set n = n + 2.

  • If 1 person remains unpaired,

  • set n = n + 1.

  • To solve this particular problem,

  • we've introduced in line 4 a condition,

  • otherwise known as a branch,

  • that only executes if there is one person

  • we could not pair with another.

  • So now, whether there's 1 or 3

  • 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 3's or 4's or even 5's and 10's,

  • 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 would you solve with an algorithm?

What's an algorithm?

Subtitles and vocabulary

Operation of videos Adjust the video here to display the subtitles

B1 TED-Ed algorithm room counting line people

【TED-Ed】What's an algorithm? - David J. Malan

  • 2082 280
    VoiceTube posted on 2013/10/19
Video vocabulary