1
00:00:00,000 --> 00:00:00,080


2
00:00:00,080 --> 00:00:02,955
DAVID MALAN: --we'll generally
call a loop, some kind of cycle,

3
00:00:02,955 --> 00:00:04,794
because it's making
me do something again.

4
00:00:04,794 --> 00:00:06,960
DOUG LLOYD: So as we discussed
a little bit earlier,

5
00:00:06,960 --> 00:00:09,876
we're making a conscious effort here
to introduce students to concepts

6
00:00:09,876 --> 00:00:13,724
without introducing them too much
to the heavy theoretical math that

7
00:00:13,724 --> 00:00:14,640
might be behind these.

8
00:00:14,640 --> 00:00:19,180
And so this demonstration about
falling onto the phone book example

9
00:00:19,180 --> 00:00:22,800
where we did the counting by
one page, counting by two pages,

10
00:00:22,800 --> 00:00:26,040
then showing binary
search, gives us a way

11
00:00:26,040 --> 00:00:29,790
to show the different powers
or speeds of these algorithms

12
00:00:29,790 --> 00:00:32,279
without getting too heavy
into the math just yet.

13
00:00:32,279 --> 00:00:35,070
DAVID MALAN: Yeah, and I think it's
a nice way too of throwing away

14
00:00:35,070 --> 00:00:39,210
the distractions of what might be
this plot with an x-axis and a y-axis,

15
00:00:39,210 --> 00:00:41,460
and really just allowing
students to intuitively grasp

16
00:00:41,460 --> 00:00:44,865
that, OK, size of problem gets
bigger that way and time to solve

17
00:00:44,865 --> 00:00:47,460
gets bigger that way, and I
think that's pretty intuitive.

18
00:00:47,460 --> 00:00:51,084
And we certainly don't need
to slap a formal analysis

19
00:00:51,084 --> 00:00:54,250
at this point in the semester, we'll
come back to this in a few weeks' time.

20
00:00:54,250 --> 00:00:55,958
But I think it's
reasonable at this point

21
00:00:55,958 --> 00:00:59,460
to introduce N as just a generic
term for the number of pages,

22
00:00:59,460 --> 00:01:01,510
show the distinction
between N and N over 2.

23
00:01:01,510 --> 00:01:04,410
And what I try to do generally,
especially if I'm doing this demo not

24
00:01:04,410 --> 00:01:06,450
on a digital screen but
on like a chalkboard,

25
00:01:06,450 --> 00:01:10,780
is draw a vertical line as I'm sort
of imaginatively doing with my finger

26
00:01:10,780 --> 00:01:13,440
here to point out that every
line on the yellow line

27
00:01:13,440 --> 00:01:16,679
is half as high as the red line.

28
00:01:16,679 --> 00:01:19,470
But this is what's really important,
and indeed this is deliberate,

29
00:01:19,470 --> 00:01:24,004
the sort of stop light approach of red
is bad, yellow is OK, green is great.

30
00:01:24,004 --> 00:01:25,920
DOUG LLOYD: Yeah, it's
a simple reinforcement,

31
00:01:25,920 --> 00:01:28,490
but it does really
hammer home that point.

32
00:01:28,490 --> 00:01:32,220
DAVID MALAN: And what's powerful too
here, if you have enough of a classroom

33
00:01:32,220 --> 00:01:34,240
to walk left and right
on here, especially

34
00:01:34,240 --> 00:01:38,265
if you can exceed the screen, to point
out that that green line really, it

35
00:01:38,265 --> 00:01:41,040
does grow, and it doesn't
flatten out, but it

36
00:01:41,040 --> 00:01:45,850
grows so slowly that you can be way over
there and have a huge number of pages,

37
00:01:45,850 --> 00:01:47,600
but the time to solve
is still pretty low.

38
00:01:47,600 --> 00:01:50,970
DOUG LLOYD: Right, with 4 billion pages
in the phone book, the first example

39
00:01:50,970 --> 00:01:54,550
you've got 4 billion, with the
yellow line there it's 2 billion,

40
00:01:54,550 --> 00:01:56,722
but with the green line
it's only 32 steps to do it.

41
00:01:56,722 --> 00:01:58,680
DAVID MALAN: And that's
what's pretty powerful.

42
00:01:58,680 --> 00:02:00,596
And that's why I think
it's important in class

43
00:02:00,596 --> 00:02:03,480
to actually fast forward to
pretty big numbers, the 4 billion

44
00:02:03,480 --> 00:02:08,580
which at least has the
relevance of being 2 to the 32,

45
00:02:08,580 --> 00:02:12,330
but to point out to students just,
my god, you go from that many pages

46
00:02:12,330 --> 00:02:15,600
so quickly to just one, it's I think
more compelling than to only go up

47
00:02:15,600 --> 00:02:21,920
to 1,000 pages where dividing it in 10
times is great but it's not as magical.

48
00:02:21,920 --> 00:02:24,450
DOUG LLOYD: It doesn't have that impact.

49
00:02:24,450 --> 00:02:26,030
I agree.

50
00:02:26,030 --> 00:02:26,795