What's an algorithm? - David J. Malan

2,582,025 views ・ 2013-05-20

TED-Ed


Please double-click on the English subtitles below to play the video.

00:00
Translator: Andrea McDonough Reviewer: Jessica Ruby
0
0
7000
Translator: Andrea McDonough Reviewer: Daban Q. Jaff
00:15
What's an algorithm?
1
15483
1348
00:16
In computer science,
2
16831
831
00:17
an algorithm is a set of instructions
3
17662
1754
00:19
for solving some problem, step-by-step.
4
19416
2689
00:22
Typically, algorithms are executed by computers,
5
22105
2272
00:24
but we humans have algorithms as well.
6
24377
2167
00:26
For instance, how would you go about counting
7
26544
1853
00:28
the number of people in a room?
8
28397
1820
00:30
Well, if you're like me,
9
30217
1215
00:31
you probably point at each person,
10
31432
1496
00:32
one at a time,
11
32928
960
00:33
and count up from 0:
12
33888
1837
00:35
1, 2, 3, 4 and so forth.
13
35725
2873
00:38
Well, that's an algorithm.
14
38598
1113
00:39
In fact, let's try to express it
15
39711
1134
00:40
a bit more formally in pseudocode,
16
40845
2229
00:43
English-like syntax
17
43074
831
00:43
that resembles a programming language.
18
43905
2124
00:46
Let n equal 0.
19
46029
1767
00:47
For each person in room, set n = n + 1.
20
47796
4792
00:52
How to interpret this pseudocode?
21
52588
1497
00:54
Well, line 1 declares, so to speak,
22
54085
1836
00:55
a variable called n
23
55921
1416
00:57
and initializes its value to zero.
24
57337
2379
00:59
This just means that at the beginning of our algorithm,
25
59716
2335
01:02
the thing with which we're counting
26
62051
1584
01:03
has a value of zero.
27
63635
1668
01:05
After all, before we start counting,
28
65303
1336
01:06
we haven't counted anything yet.
29
66639
1669
01:08
Calling this variable n is just a convention.
30
68308
2248
01:10
I could have called it almost anything.
31
70556
2005
01:12
Now, line 2 demarks the start of loop,
32
72561
2086
01:14
a sequence of steps that will repeat some number of times.
33
74647
3044
01:17
So, in our example, the step we're taking
34
77691
1794
01:19
is counting people in the room.
35
79485
1734
01:21
Beneath line 2 is line 3,
36
81219
1763
01:22
which describes exactly how we'll go about counting.
37
82982
2511
01:25
The indentation implies that it's line 3
38
85493
2250
01:27
that will repeat.
39
87743
1222
01:28
So, what the pseudocode is saying
40
88965
1219
01:30
is that after starting at zero,
41
90184
2066
01:32
for each person in the room,
42
92250
1710
01:33
we'll increase n by 1.
43
93960
2218
01:36
Now, is this algorithm correct?
44
96178
2329
01:38
Well, let's bang on it a bit.
45
98507
1608
01:40
Does it work if there are 2 people in the room?
46
100115
2826
01:42
Let's see.
47
102941
780
01:43
In line 1, we initialize n to zero.
48
103721
2085
01:45
For each of these two people,
49
105806
1302
01:47
we then increment n by 1.
50
107108
2168
01:49
So, in the first trip through the loop,
51
109276
1582
01:50
we update n from zero to 1,
52
110858
2005
01:52
on the second trip through that same loop,
53
112863
1655
01:54
we update n from 1 to 2.
54
114518
2249
01:56
And so, by this algorithm's end, n is 2,
55
116767
3341
02:00
which indeed matches the number of people in the room.
56
120108
2113
02:02
So far, so good.
57
122221
1223
02:03
How about a corner case, though?
58
123444
1752
02:05
Suppose that there are zero people in the room,
59
125196
1964
02:07
besides me, who's doing the counting.
60
127160
2347
02:09
In line 1, we again initialize n to zero.
61
129507
3010
02:12
This time, though, line 3 doesn't execute at all
62
132517
2522
02:15
since there isn't a person in the room,
63
135039
1880
02:16
and so, n remains zero,
64
136919
1624
02:18
which indeed matches the number of people in the room.
65
138543
2359
02:20
Pretty simple, right?
66
140902
906
02:21
But counting people one a time is pretty inefficient, too, no?
67
141808
3216
02:25
Surely, we can do better!
68
145024
1568
02:26
Why not count two people at a time?
69
146592
1866
02:28
Instead of counting 1, 2, 3, 4, 5, 6, 7, 8, and so forth,
70
148458
5099
02:33
why not count
71
153557
918
02:34
2, 4, 6, 8, and so on?
72
154475
2127
02:36
It even sounds faster, and it surely is.
73
156602
2418
02:39
Let's express this optimization in pseudocode.
74
159020
2835
02:41
Let n equal zero.
75
161855
1462
02:43
For each pair of people in room,
76
163317
1997
02:45
set n = n + 2.
77
165314
2588
02:47
Pretty simple change, right?
78
167902
1673
02:49
Rather than count people one at a time,
79
169575
1791
02:51
we instead count them two at a time.
80
171366
2343
02:53
This algorithm's thus twice as fast as the last.
81
173709
2815
02:56
But is it correct?
82
176524
1346
02:57
Let's see.
83
177870
794
02:58
Does it work if there are 2 people in the room?
84
178664
2125
03:00
In line 1, we initialize n to zero.
85
180789
2342
03:03
For that one pair of people, we then increment n by 2.
86
183131
3268
03:06
And so, by this algorithm's end, n is 2,
87
186399
2522
03:08
which indeed matches the number of people in the room.
88
188921
2382
03:11
Suppose next that there are zero people in the room.
89
191303
2412
03:13
In line 1, we initialize n to zero.
90
193715
2587
03:16
As before, line 3 doesn't execute at all
91
196302
2080
03:18
since there aren't any pairs of people in the room,
92
198382
2342
03:20
and so, n remains zero,
93
200724
1686
03:22
which indeed matches the number of people in the room.
94
202410
2773
03:25
But what if there are 3 people in the room?
95
205183
2372
03:27
How does this algorithm fair?
96
207555
1937
03:29
Let's see.
97
209492
829
03:30
In line 1, we initialize n to zero.
98
210321
2670
03:32
For a pair of those people,
99
212991
1290
03:34
we then increment n by 2,
100
214281
1916
03:36
but then what?
101
216197
992
03:37
There isn't another full pair of people in the room,
102
217189
2262
03:39
so line 2 no longer applies.
103
219451
2210
03:41
And so, by this algorithm's end,
104
221661
1669
03:43
n is still 2, which isn't correct.
105
223330
2596
03:45
Indeed this algorithm is said to be buggy
106
225926
2332
03:48
because it has a mistake.
107
228258
1148
03:49
Let's redress with some new pseudocode.
108
229406
1896
03:51
Let n equal zero.
109
231302
1793
03:53
For each pair of people in room,
110
233095
2123
03:55
set n = n + 2.
111
235218
2422
03:57
If 1 person remains unpaired,
112
237640
2459
04:00
set n = n + 1.
113
240099
2376
04:02
To solve this particular problem,
114
242475
1507
04:03
we've introduced in line 4 a condition,
115
243982
2249
04:06
otherwise known as a branch,
116
246231
1835
04:08
that only executes if there is one person
117
248066
2253
04:10
we could not pair with another.
118
250319
1876
04:12
So now, whether there's 1 or 3
119
252195
2065
04:14
or any odd number of people in the room,
120
254260
2273
04:16
this algorithm will now count them.
121
256533
2288
04:18
Can we do even better?
122
258821
1345
04:20
Well, we could count in 3's or 4's or even 5's and 10's,
123
260166
3294
04:23
but beyond that it's going to get
124
263460
1300
04:24
a little bit difficult to point.
125
264760
1870
04:26
At the end of the day,
126
266630
937
04:27
whether executed by computers or humans,
127
267567
2264
04:29
algorithms are just a set of instructions
128
269831
1960
04:31
with which to solve problems.
129
271791
1838
04:33
These were just three.
130
273629
1743
04:35
What problem would you solve with an algorithm?
131
275372
2982
About this website

This site will introduce you to YouTube videos that are useful for learning English. You will see English lessons taught by top-notch teachers from around the world. Double-click on the English subtitles displayed on each video page to play the video from there. The subtitles scroll in sync with the video playback. If you have any comments or requests, please contact us using this contact form.

https://forms.gle/WvT1wiN1qDtmnspy7