1
00:00:09,000 --> 00:00:15,800
Hi. I'm Doug Baldwin, and I'd like to welcome you to this mini-lecture on the meaning of the word "algorithm."
2
00:00:15,800 --> 00:00:22,733
This lecture is intended to introduce the term to viewers with no previous experience with algorithms or programming.
3
00:00:22,733 --> 00:00:24,733
I hope you'll like it.
4
00:00:24,733 --> 00:00:32,733
The broadest definition of the word "algorithm" is that an algorithm is simply a procedure for solving some problem.
5
00:00:32,733 --> 00:00:38,366
So if you know an algorithm, you can feed the problem into it, and get a solution out.
6
00:00:38,366 --> 00:00:44,566
It's certainly useful to have ways of solving problems, but what makes algorithms really important today
7
00:00:44,566 --> 00:00:51,433
is that every computer program is an algorithm, or a set of algorithms, expressed in a form that a computer can follow.
8
00:00:51,433 --> 00:00:59,033
Algorithms are thus key to understanding what computers can do, and to writing or understanding programs.
9
00:00:59,033 --> 00:01:03,033
There are lots of fine points to this definition that need to be fleshed out.
10
00:01:03,033 --> 00:01:06,466
First, I should say exactly what a "procedure" is:
11
00:01:06,466 --> 00:01:13,166
when I talk about an algorithm as a procedure for solving a problem, I mean that an algorithm is a set of instructions,
12
00:01:13,166 --> 00:01:18,533
a set of steps that someone or something can follow in order to find a solution to the problem.
13
00:01:18,533 --> 00:01:26,233
The steps have to be what are called "effective" ones, meaning that whatever is following the instructions really can carry them out.
14
00:01:26,233 --> 00:01:31,200
For example, "add 1 and 3" would generally be considered an effective step,
15
00:01:31,200 --> 00:01:35,733
because anyone can be expected to be able to do it, or at least be trained to do it.
16
00:01:35,733 --> 00:01:40,000
On the other hand, "win the lottery" is not an effective step,
17
00:01:40,000 --> 00:01:44,933
because no-one has a sure-fire way of doing it, so it can't be carried out on demand.
18
00:01:44,933 --> 00:01:51,966
The steps in an algorithm also have to be what is called "definite," meaning that there is no uncertainty about what they mean.
19
00:01:51,966 --> 00:01:56,133
The previous "add 1 and 3" example is pretty definite,
20
00:01:56,133 --> 00:02:00,166
whereas the famous direction "go west, young man" is not,
21
00:02:00,166 --> 00:02:06,433
because it is unclear how far west one should go and whether one is
supposed to stay in the west after getting there.
22
00:02:06,433 --> 00:02:10,566
I also need to say a little more about problems.
23
00:02:10,566 --> 00:02:16,500
Non-trivial problems have inputs that indicate exactly what instance of the problem is to be solved.
24
00:02:16,500 --> 00:02:24,266
For example, a problem might be to add two numbers, in which case the inputs would be the actual values of the numbers to add.
25
00:02:24,266 --> 00:02:31,600
Then adding 3 and 12 would be one instance of the problem, adding 18 and 6 would be another, and so forth.
26
00:02:31,600 --> 00:02:38,933
An algorithm that solves a problem thus also needs inputs, so that it knows what instance of the problem to work on.
27
00:02:38,933 --> 00:02:46,566
Finally, algorithms produce solutions to problems in the form of outputs, i.e., numbers, pieces of text, pictures,
28
00:02:46,566 --> 00:02:51,800
or other information that describes the solution to the problem instance that the algorithm was working on.
29
00:02:51,800 --> 00:02:56,966
Having outputs imposes two more restrictions on what procedures count as algorithms.
30
00:02:56,966 --> 00:03:05,166
First, an algorithm has to be a finite procedure, i.e., it has to produce its output and stop after a finite amount of time.
31
00:03:05,166 --> 00:03:11,333
This means, for example, that procedures that involve blindly guessing solutions aren't algorithms,
32
00:03:11,333 --> 00:03:15,666
because one could keep making the same wrong guesses forever.
33
00:03:15,666 --> 00:03:23,366
The second output-related requirement is that the output produced by an algorithm always has to be a correct solution to the problem.
34
00:03:23,366 --> 00:03:30,133
This requirement seems almost too obvious to mention, but in fact lots of useful procedures don't meet it.
35
00:03:30,133 --> 00:03:36,366
For example, "if a word is in the dictionary, then, and only then, it is spelled correctly"
36
00:03:36,366 --> 00:03:41,966
is a useful enough way to check spelling that it is the essence of just about every computer spelling checker.
37
00:03:41,966 --> 00:03:50,000
But it doesn't pass the "always correct" test for being an algorithm to solve the problem of making sure that a document has no misspellings,
38
00:03:50,000 --> 00:03:57,933
because no dictionary contains every technical or slang term, nor can a dictionary catch misspellings of one word that turn it into another.
39
00:03:57,933 --> 00:04:04,966
This is why your spelling checker sometimes rejects words that are OK in a particular context, or accepts ones that aren't.
40
00:04:04,966 --> 00:04:17,866
Procedures that are useful but don't meet all the requirements for being algorithms are called "heuristics."
41
00:04:17,866 --> 00:04:25,666
As an example of a problem and an algorithm, suppose you can measure the diameter of a circle, and you want to know its area.
42
00:04:25,666 --> 00:04:29,866
So the problem is to find the area of a circle given its diameter.
43
00:04:29,866 --> 00:04:36,400
Parts of problem descriptions that use such words as "given" or "if you know" or similar phrases
44
00:04:36,400 --> 00:04:41,233
usually identify the problem's inputs, and this example is no exception.
45
00:04:41,233 --> 00:04:48,500
So the input to this problem is the circle's diameter. Next we need some steps that calculate area from diameter.
46
00:04:48,500 --> 00:04:54,933
There is a formula from geometry that says the area of a circle equals pi times its radius squared.
47
00:04:54,933 --> 00:05:01,366
In this problem we have the diameter, not the radius, but we can calculate the radius as half the diameter.
48
00:05:01,366 --> 00:05:05,400
These ideas provide a complete set of steps for the algorithm:
49
00:05:05,400 --> 00:05:09,866
First, calculate the radius as the diameter divided by 2.
50
00:05:09,866 --> 00:05:14,333
Then, calculate the area as pi times the radius squared.
51
00:05:14,333 --> 00:05:18,633
This algorithm's output is the area from the second step.
52
00:05:18,633 --> 00:05:24,033
Notice something interesting about the steps in this algorithm. I wrote them as if there were two,
53
00:05:24,033 --> 00:05:28,433
namely divide the diameter by 2, and then calculate pi r squared.
54
00:05:28,433 --> 00:05:32,400
But you could just as well see this algorithm as having three steps:
55
00:05:32,400 --> 00:05:38,433
one to divide the diameter by 2, one to square the radius, and one to multiply by pi.
56
00:05:38,433 --> 00:05:45,533
And, in fact, if someone wasn't sure how to do this arithmetic, even it
could be broken down into simpler steps.
57
00:05:45,533 --> 00:05:49,866
This is really another way to look at the requirement that steps be effective--
58
00:05:49,866 --> 00:05:57,566
they can always be described in more and more detail until reaching a level that the person or machine performing the algorithm can do.
59
00:05:57,566 --> 00:06:05,400
Programmers find this tremendously valuable, because they can
start by describing an algorithm at a level appropriate for themselves,
60
00:06:05,400 --> 00:06:10,066
and only when they understand the algorithm at that level and believe that it solves their problem
61
00:06:10,066 --> 00:06:16,266
do they need to worry about expressing the steps in the greater
level of detail that a computer needs.
62
00:06:16,266 --> 00:06:22,833
This idea that programs are just algorithms expressed in a particular way has come up a couple of times,
63
00:06:22,833 --> 00:06:26,833
so let's look at what the area algorithm would look like as a program.
64
00:06:26,833 --> 00:06:34,133
I can write it as a so-called function in Matlab, a language often used for mathematical problem solving, like so.
65
00:06:34,133 --> 00:06:42,566
I don't expect that this program makes complete sense to you, but hopefully you can see some connections between it and the algorithm.
66
00:06:42,566 --> 00:06:47,566
That, in fact, is the point: even without knowing the programming language,
67
00:06:47,566 --> 00:06:54,266
the fact that you understand the algorithm, which is independent of language, allows you to get some meaning from the program.
68
00:06:54,266 --> 00:06:57,800
Furthermore, because you know what steps are in the algorithm,
69
00:06:57,800 --> 00:07:03,633
you might even be able to learn something about the programming
language from seeing how it expresses the algorithm.
70
00:07:03,633 --> 00:07:11,000
For instance you might guess that the name spelled "p-i" stands for the constant 3.1415 et cetera,
71
00:07:11,000 --> 00:07:15,433
or that the caret character means to raise a number to a power.
72
00:07:15,433 --> 00:07:18,866
This ends this introduction to the word "algorithm."
73
00:07:18,866 --> 00:07:24,466
You have seen that an algorithm is a series of doable and unambiguous steps for solving a problem.
74
00:07:24,466 --> 00:07:31,400
Given inputs that identify the specific instance of the problem to solve, following the algorithm's steps will,
75
00:07:31,400 --> 00:07:36,533
in a finite amount of time, produce outputs that provide a correct solution to the problem.
76
00:07:36,533 --> 00:07:40,100
Algorithms are important in computer programming, because
77
00:07:40,100 --> 00:07:45,000
every program is really just an algorithm written in a form that a computer can understand,
78
00:07:45,000 --> 00:07:51,966
but developing the algorithm in a form that people understand first, and only then translating it into computer form,
79
00:07:51,966 --> 00:07:56,533
is usually much easier than writing the computer form from scratch.
80
00:07:56,533 --> 00:08:01,399
Thank you for watching this lecture. I hope you've found it useful.