1
00:00:00,000 --> 00:00:03,740
So what might an algorithm be for a
problem that we might want to solve?

2
00:00:03,740 --> 00:00:04,710
Well, consider this.

3
00:00:04,710 --> 00:00:06,590
This is an old school
problem where you might

4
00:00:06,590 --> 00:00:09,320
have lots and lots of names
and lots of lots of numbers,

5
00:00:09,320 --> 00:00:12,800
and those names are hopefully sorted
alphabetically from A through Z

6
00:00:12,800 --> 00:00:13,950
in a book like this.

7
00:00:13,950 --> 00:00:17,180
And even though most of us don't really
reach for this technology anymore,

8
00:00:17,180 --> 00:00:20,480
consider that it's really the same
as your iPhone or Android phone

9
00:00:20,480 --> 00:00:23,720
or other device, which has all
of your contacts top to bottom

10
00:00:23,720 --> 00:00:25,850
and you can scroll
through them from A to Z,

11
00:00:25,850 --> 00:00:29,210
or you can search for them by typing
into the little autocomplete box.

12
00:00:29,210 --> 00:00:32,070
How is even your phone
solving this problem?

13
00:00:32,070 --> 00:00:34,740
Well let's consider a simple approach.

14
00:00:34,740 --> 00:00:37,870
I'm going to look at the first page
and look for someone on the phone book.

15
00:00:37,870 --> 00:00:40,400
Suppose that person's name is
Mike Smith, last name starting

16
00:00:40,400 --> 00:00:42,320
with S. Let me go ahead and look down.

17
00:00:42,320 --> 00:00:43,340
He's not here.

18
00:00:43,340 --> 00:00:47,000
Let me turn the page.

19
00:00:47,000 --> 00:00:47,900
This is an algorithm.

20
00:00:47,900 --> 00:00:51,680
It's a step-by-step process for
solving a problem, finding Mike Smith.

21
00:00:51,680 --> 00:00:54,940
Is this algorithm
correct, would you say?

22
00:00:54,940 --> 00:00:55,450
Yeah.

23
00:00:55,450 --> 00:00:58,570
I mean, it's pretty slow, it's pretty
stupid, in that it's going to take,

24
00:00:58,570 --> 00:01:01,960
my God, forever, like, hundreds
of page turns to find Mike Smith.

25
00:01:01,960 --> 00:01:04,240
But if he's there, I
will find him according

26
00:01:04,240 --> 00:01:05,900
to this step-by-step approach.

27
00:01:05,900 --> 00:01:08,810
What if I speed things up a bit just
because it's tedious, otherwise?

28
00:01:08,810 --> 00:01:14,530
So I do two, four, six, eight,
10, 12, 14, 16 and so forth.

29
00:01:14,530 --> 00:01:16,450
Is that algorithm faster?

30
00:01:16,450 --> 00:01:17,200
Absolutely.

31
00:01:17,200 --> 00:01:18,250
Literally twice as fast.

32
00:01:18,250 --> 00:01:18,940
Is it correct?

33
00:01:18,940 --> 00:01:19,870
AUDIENCE: No.

34
00:01:19,870 --> 00:01:20,530
DAVID MALAN: No.

35
00:01:20,530 --> 00:01:21,450
Why?

36
00:01:21,450 --> 00:01:22,430
[INTERPOSING VOICES]

37
00:01:22,430 --> 00:01:24,010
DAVID MALAN: Yeah, we might skip them.

38
00:01:24,010 --> 00:01:26,640
I might get unlucky and
eventually, I might get to the S's.

39
00:01:26,640 --> 00:01:31,330
But darn it if Mike wasn't in between
two pages as I turn them at once.

40
00:01:31,330 --> 00:01:32,520
So it's not a fatal flaw.

41
00:01:32,520 --> 00:01:34,440
That algorithm, I could
fix by just saying

42
00:01:34,440 --> 00:01:38,940
if you hit the T section or
maybe Sn instead of Sm, just back

43
00:01:38,940 --> 00:01:43,680
up one or so pages just to fix
that bug or mistake, so to speak.

44
00:01:43,680 --> 00:01:45,970
But it, at least, is twice as fast.

45
00:01:45,970 --> 00:01:48,600
But if this phone book
has 1,000 something pages,

46
00:01:48,600 --> 00:01:53,970
it's still going to take me maybe 500
pairwise turns just to find Mike Smith.

47
00:01:53,970 --> 00:01:56,030
That's a while just to look someone up.

48
00:01:56,030 --> 00:01:57,990
But most of us, if you've
used this technology,

49
00:01:57,990 --> 00:02:01,210
instead, did what, back in the day?

50
00:02:01,210 --> 00:02:05,250
Go roughly to the middle if there
aren't little letters on the side off

51
00:02:05,250 --> 00:02:05,960
which to cheat.

52
00:02:05,960 --> 00:02:07,090
So roughly into the middle.

53
00:02:07,090 --> 00:02:08,350
I'm in the M section.

54
00:02:08,350 --> 00:02:11,560
Now the M's, of course, mean
that Mike is not this way,

55
00:02:11,560 --> 00:02:12,700
which would be the A's.

56
00:02:12,700 --> 00:02:15,460
He's probably this way toward
the Z's because S, of course,

57
00:02:15,460 --> 00:02:17,050
is between the M and the Z.

58
00:02:17,050 --> 00:02:21,190
So at this point, I can literally
tear the problem in half,

59
00:02:21,190 --> 00:02:27,160
throw half of the problem away very
dramatically and unnecessarily,

60
00:02:27,160 --> 00:02:30,420
making the point that we've now gone
from 1,000 some odd pages to what?

61
00:02:30,420 --> 00:02:31,280
500.

62
00:02:31,280 --> 00:02:32,200
And I can do it again.

63
00:02:32,200 --> 00:02:33,500
Ah, I went a little too far.

64
00:02:33,500 --> 00:02:37,030
I'm now in the T section, so I can
tear the problem in half again,

65
00:02:37,030 --> 00:02:42,730
throw that half away, and now I'm
down from 1,000 to 500 to 250 pages

66
00:02:42,730 --> 00:02:46,970
only, after just two steps
in this step-by-step process.

67
00:02:46,970 --> 00:02:49,660
And if I repeat this again and
again and again, hopefully, I'll

68
00:02:49,660 --> 00:02:53,560
be left, ultimately, with,
say, just one page on which

69
00:02:53,560 --> 00:02:55,910
Mike Smith either is or is not.

70
00:02:55,910 --> 00:02:57,950
And I can call him or quit.