1
00:00:00,000 --> 00:00:00,500


2
00:00:00,500 --> 00:00:02,050
DAVID MALAN: --that's OK.

3
00:00:02,050 --> 00:00:05,850
So, surely then there are these bugs,
and that's fine, and so think back--

4
00:00:05,850 --> 00:00:09,870
Coming up is perhaps the algorithm that
CS50 is known for, which I certainly

5
00:00:09,870 --> 00:00:13,555
inherited from some professors pass,
but you pick up this here phone --

6
00:00:13,555 --> 00:00:15,930
DOUG LLOYD: Yeah, you don't
see those very often anymore.

7
00:00:15,930 --> 00:00:17,790
DAVID MALAN: They're
really hard to find.

8
00:00:17,790 --> 00:00:21,540
In fact, we've had to
circulate calls for donations

9
00:00:21,540 --> 00:00:24,780
online of phone books in towns that
actually still print these things.

10
00:00:24,780 --> 00:00:26,180
DOUG LLOYD: And we've
actually gotten several,

11
00:00:26,180 --> 00:00:28,013
so thank you to all the
people who sustained

12
00:00:28,013 --> 00:00:29,940
the shipping of just pure paper to us.

13
00:00:29,940 --> 00:00:32,790
DAVID MALAN: I know, they're not even
cheap to ship because they're so heavy.

14
00:00:32,790 --> 00:00:34,830
And the bigger the better
too for the demonstration.

15
00:00:34,830 --> 00:00:36,579
But anyhow, if you
just take a phone book,

16
00:00:36,579 --> 00:00:40,260
the goal here is to demonstrate
through dividing and conquering,

17
00:00:40,260 --> 00:00:42,772
this perhaps the most
intuitive of algorithms,

18
00:00:42,772 --> 00:00:44,730
but an algorithm that
you might not necessarily

19
00:00:44,730 --> 00:00:47,820
call an algorithm because it really
is just common sense to most people.

20
00:00:47,820 --> 00:00:50,370
And so what we're trying to
do in this case I would argue

21
00:00:50,370 --> 00:00:53,460
is, capture again, some
familiarity that students already

22
00:00:53,460 --> 00:00:55,620
have whether with binary
on the one hand or now

23
00:00:55,620 --> 00:00:57,030
with algorithms on the
other hand, and start

24
00:00:57,030 --> 00:00:59,238
to formalize their understanding
of that so that they

25
00:00:59,238 --> 00:01:01,150
can leverage it in new contexts.

26
00:01:01,150 --> 00:01:03,150
DOUG LLOYD: And in this
phone book we're looking

27
00:01:03,150 --> 00:01:05,400
for Mike Smith, who was
actually the professor of CS50

28
00:01:05,400 --> 00:01:09,600
when I took CS50 just before
you took over in 2007,

29
00:01:09,600 --> 00:01:13,370
but the choice of Mike Smith
is actually a strategic one.

30
00:01:13,370 --> 00:01:16,080
There's a reason behind--
of course it's that,

31
00:01:16,080 --> 00:01:18,150
but there's also a strategic
reason behind why we

32
00:01:18,150 --> 00:01:19,774
choose to search for him in particular.

33
00:01:19,774 --> 00:01:23,460
DAVID MALAN: Well, S is just kind of
nice, so if you search by last name

34
00:01:23,460 --> 00:01:27,810
it means I can do one flip to the
right, do another flip to the right,

35
00:01:27,810 --> 00:01:30,180
claim to have gone
slightly too far, such

36
00:01:30,180 --> 00:01:32,280
that I end up in the T
section for instance,

37
00:01:32,280 --> 00:01:34,380
so that I can then double
back to look for Smith.

38
00:01:34,380 --> 00:01:36,860
You don't want to pick like M, because
then algorithm's over pretty fast.

39
00:01:36,860 --> 00:01:37,580
DOUG LLOYD: Right, it works right away.

40
00:01:37,580 --> 00:01:39,780
So it gives you a chance to
explore all of the different--

41
00:01:39,780 --> 00:01:41,988
although students have not
yet encountered this term,

42
00:01:41,988 --> 00:01:44,175
conditional branches of the algorithm.

43
00:01:44,175 --> 00:01:45,300
DAVID MALAN: Yeah, exactly.

44
00:01:45,300 --> 00:01:48,990
But there's a lead up of course, we
don't dive right into the intuition,

45
00:01:48,990 --> 00:01:52,770
instead I propose verbally, well, why
don't I just look for Mike one page

46
00:01:52,770 --> 00:01:53,550
at a time.

47
00:01:53,550 --> 00:01:55,350
And it's a good question
to ask, especially

48
00:01:55,350 --> 00:01:57,630
to make sure students are
indeed following along,

49
00:01:57,630 --> 00:02:02,550
because invariably someone might
think or say, no, that's incorrect.

50
00:02:02,550 --> 00:02:05,310
And here we have an opportunity
to introduce the distinction right

51
00:02:05,310 --> 00:02:09,780
from the get go between correctness,
or design, or quality of design,

52
00:02:09,780 --> 00:02:12,120
not to mention other
axis along which you

53
00:02:12,120 --> 00:02:14,129
might evaluate some problem solving.

54
00:02:14,129 --> 00:02:16,170
But it's indeed correct
to go one page at a time,

55
00:02:16,170 --> 00:02:18,180
but it's not correct of
course to go two at a time

56
00:02:18,180 --> 00:02:21,096
because almost always there's one
student who realizes, wait a minute,

57
00:02:21,096 --> 00:02:25,376
what if Mike is between two pages
as you're going by two at a time.

58
00:02:25,376 --> 00:02:27,750
So that's a good opportunity
too for a branch like, well,

59
00:02:27,750 --> 00:02:31,340
if you hit the page right after
Smith double back one page.

60
00:02:31,340 --> 00:02:33,060
DOUG LLOYD: Right, you have a certain--

61
00:02:33,060 --> 00:02:34,557
Yeah, you can handle that.

62
00:02:34,557 --> 00:02:36,140
DAVID MALAN: That's the best part too.

63
00:02:36,140 --> 00:02:36,820
Everyone's always so--

64
00:02:36,820 --> 00:02:38,236
DOUG LLOYD: Oh, the dramatic toss?

65
00:02:38,236 --> 00:02:41,310
DAVID MALAN: --so impressed when I
tear that phone book down that spine.

66
00:02:41,310 --> 00:02:42,844


67
00:02:42,844 --> 00:02:44,760
DOUG LLOYD: I think
actually a couple of years

68
00:02:44,760 --> 00:02:47,020
ago there was a piece of
tape that ended up on the--

69
00:02:47,020 --> 00:02:49,020
DAVID MALAN: Yeah, there
have been some failure.

70
00:02:49,020 --> 00:02:51,120
It's unclear if that was
malicious that year not,

71
00:02:51,120 --> 00:02:53,190
someone reinforced the phone
book before I went on--

72
00:02:53,190 --> 00:02:54,356
DOUG LLOYD: That's not fair.

73
00:02:54,356 --> 00:02:55,657
DAVID MALAN: --to lecture.

74
00:02:55,657 --> 00:02:57,990
I have struggled once in a
while, but all the better, it

75
00:02:57,990 --> 00:02:59,264
makes for a funny demo.

76
00:02:59,264 --> 00:03:00,930
DOUG LLOYD: Do you practice before hand?

77
00:03:00,930 --> 00:03:03,657
DAVID MALAN: No we don't have
enough phone books to practice.

78
00:03:03,657 --> 00:03:06,740
So it's usually fun to toss half the
phone book at someone in the audience

79
00:03:06,740 --> 00:03:08,190
gently if they'd like to keep it.

80
00:03:08,190 --> 00:03:09,480
DOUG LLOYD: Yeah, that's a fun souvenir.

81
00:03:09,480 --> 00:03:11,100
DAVID MALAN: But this is
the key point at the end,

82
00:03:11,100 --> 00:03:12,720
and you don't want to
flip again, and again,

83
00:03:12,720 --> 00:03:14,469
and again, it will
quickly become tedious.

84
00:03:14,469 --> 00:03:18,330
You want to end up with a theoretically
one single page on which Mike either is

85
00:03:18,330 --> 00:03:20,010
or is not.

86
00:03:20,010 --> 00:03:22,437
At which point the algorithm ends.

87
00:03:22,437 --> 00:03:25,020
But there's an opportunity next,
and you see the glimpse of it

88
00:03:25,020 --> 00:03:26,960
here on the screen, to
also through this demo

89
00:03:26,960 --> 00:03:30,210
introduce pseudocode code because it's
pretty intuitive to flip to the middle,

90
00:03:30,210 --> 00:03:32,790
keep flipping half, in
half, in half, and tearing,

91
00:03:32,790 --> 00:03:37,470
but now start to slap some structure
on that I think is a helpful exercise

92
00:03:37,470 --> 00:03:40,740
to bridge these worlds of just
talking through intuitive problems,

93
00:03:40,740 --> 00:03:42,820
to formalizing some
actual formative code.

94
00:03:42,820 --> 00:03:44,736
DOUG LLOYD: Right,
expressing it in a language

95
00:03:44,736 --> 00:03:48,390
that students are familiar with, and
even adopting, as we'll soon see,

96
00:03:48,390 --> 00:03:51,060
conventions of indentation
to suggest what

97
00:03:51,060 --> 00:03:54,960
they might see later on down the road
with C other programming languages

98
00:03:54,960 --> 00:03:58,100
that use indentation to demarcate
different blocks of code,

99
00:03:58,100 --> 00:03:59,760
as we do there on line four.

100
00:03:59,760 --> 00:04:00,870
DAVID MALAN: And even
here, it's a simple thing,

101
00:04:00,870 --> 00:04:03,911
but it's an opportunity to reinforce
what we just talked about previously

102
00:04:03,911 --> 00:04:06,280
in so far as it's natural
to start counting from zero,

103
00:04:06,280 --> 00:04:10,230
when you're using binary since all
of your bits are zeros by perhaps

104
00:04:10,230 --> 00:04:13,722
initially, and so this is a nice
subtle way of reinforcing that.

105
00:04:13,722 --> 00:04:16,680
Unfortunately it's a bit misleading
too, because most every text editor

106
00:04:16,680 --> 00:04:19,380
these days just naturally
starts numbering lines at 1,

107
00:04:19,380 --> 00:04:21,570
so I have sort of
misgivings there, but I

108
00:04:21,570 --> 00:04:25,590
feel it's easier to just start from zero
here rather than suddenly change tack

109
00:04:25,590 --> 00:04:27,740
just minutes after that particular demo.

110
00:04:27,740 --> 00:04:29,490
And this was actually
a judgment call too,

111
00:04:29,490 --> 00:04:34,740
so for years have we used in step 7 and
step 10 this go back to syntax, which

112
00:04:34,740 --> 00:04:37,180
is effectively go to
in a lot of languages,

113
00:04:37,180 --> 00:04:39,930
but I'm OK with that because I
think if you're numbering the lines

114
00:04:39,930 --> 00:04:43,440
it's super readable here, and
even though we don't necessarily

115
00:04:43,440 --> 00:04:49,690
introduce formally the go to statement,
and we don't encourage it in class,

116
00:04:49,690 --> 00:04:51,720
it's a very natural way
of expressing a loop.

117
00:04:51,720 --> 00:04:55,170
DOUG LLOYD: Yeah, if you tried
to use English to structure,

118
00:04:55,170 --> 00:04:58,161
I think those lines of code,
lines 3 to 11 there is a loop,

119
00:04:58,161 --> 00:04:59,910
I think it would be a
bit more convoluted.

120
00:04:59,910 --> 00:05:01,445
DAVID MALAN: Indeed.

121
00:05:01,445 --> 00:05:03,135