 ## 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