DAVID MALAN: --that's OK.
So, surely then there are these bugs, and that's fine, and so think back--
Coming up is perhaps the algorithm that CS50 is known for, which I certainly
inherited from some professors pass, but you pick up this here phone --
DOUG LLOYD: Yeah, you don't see those very often anymore.
DAVID MALAN: They're really hard to find.
In fact, we've had to circulate calls for donations
online of phone books in towns that actually still print these things.
DOUG LLOYD: And we've actually gotten several,
so thank you to all the people who sustained
the shipping of just pure paper to us.
DAVID MALAN: I know, they're not even cheap to ship because they're so heavy.
And the bigger the better too for the demonstration.
But anyhow, if you just take a phone book,
the goal here is to demonstrate through dividing and conquering,
this perhaps the most intuitive of algorithms,
but an algorithm that you might not necessarily
call an algorithm because it really is just common sense to most people.
And so what we're trying to do in this case I would argue
is, capture again, some familiarity that students already
have whether with binary on the one hand or now
with algorithms on the other hand, and start
to formalize their understanding of that so that they
can leverage it in new contexts.
DOUG LLOYD: And in this phone book we're looking
for Mike Smith, who was actually the professor of CS50
when I took CS50 just before you took over in 2007,
but the choice of Mike Smith is actually a strategic one.
There's a reason behind-- of course it's that,
but there's also a strategic reason behind why we
choose to search for him in particular.
DAVID MALAN: Well, S is just kind of nice, so if you search by last name
it means I can do one flip to the right, do another flip to the right,
claim to have gone slightly too far, such
that I end up in the T section for instance,
so that I can then double back to look for Smith.
You don't want to pick like M, because then algorithm's over pretty fast.
DOUG LLOYD: Right, it works right away.
So it gives you a chance to explore all of the different--
although students have not yet encountered this term,
conditional branches of the algorithm.
DAVID MALAN: Yeah, exactly.
But there's a lead up of course, we don't dive right into the intuition,
instead I propose verbally, well, why don't I just look for Mike one page
at a time.
And it's a good question to ask, especially
to make sure students are indeed following along,
because invariably someone might think or say, no, that's incorrect.
And here we have an opportunity to introduce the distinction right
from the get go between correctness, or design, or quality of design,
not to mention other axis along which you
might evaluate some problem solving.
But it's indeed correct to go one page at a time,
but it's not correct of course to go two at a time
because almost always there's one student who realizes, wait a minute,
what if Mike is between two pages as you're going by two at a time.
So that's a good opportunity too for a branch like, well,
if you hit the page right after Smith double back one page.
DOUG LLOYD: Right, you have a certain--
Yeah, you can handle that.
DAVID MALAN: That's the best part too.
Everyone's always so--
DOUG LLOYD: Oh, the dramatic toss?
DAVID MALAN: --so impressed when I tear that phone book down that spine.
DOUG LLOYD: I think actually a couple of years
ago there was a piece of tape that ended up on the--
DAVID MALAN: Yeah, there have been some failure.
It's unclear if that was malicious that year not,
someone reinforced the phone book before I went on--
DOUG LLOYD: That's not fair.
DAVID MALAN: --to lecture.
I have struggled once in a while, but all the better, it
makes for a funny demo.
DOUG LLOYD: Do you practice before hand?
DAVID MALAN: No we don't have enough phone books to practice.
So it's usually fun to toss half the phone book at someone in the audience
gently if they'd like to keep it.
DOUG LLOYD: Yeah, that's a fun souvenir.
DAVID MALAN: But this is the key point at the end,
and you don't want to flip again, and again,
and again, it will quickly become tedious.
You want to end up with a theoretically one single page on which Mike either is
or is not.
At which point the algorithm ends.
But there's an opportunity next, and you see the glimpse of it
here on the screen, to also through this demo
introduce pseudocode code because it's pretty intuitive to flip to the middle,
keep flipping half, in half, in half, and tearing,
but now start to slap some structure on that I think is a helpful exercise
to bridge these worlds of just talking through intuitive problems,
to formalizing some actual formative code.
DOUG LLOYD: Right, expressing it in a language
that students are familiar with, and even adopting, as we'll soon see,
conventions of indentation to suggest what
they might see later on down the road with C other programming languages
that use indentation to demarcate different blocks of code,
as we do there on line four.
DAVID MALAN: And even here, it's a simple thing,
but it's an opportunity to reinforce what we just talked about previously
in so far as it's natural to start counting from zero,
when you're using binary since all of your bits are zeros by perhaps
initially, and so this is a nice subtle way of reinforcing that.
Unfortunately it's a bit misleading too, because most every text editor
these days just naturally starts numbering lines at 1,
so I have sort of misgivings there, but I
feel it's easier to just start from zero here rather than suddenly change tack
just minutes after that particular demo.
And this was actually a judgment call too,
so for years have we used in step 7 and step 10 this go back to syntax, which
is effectively go to in a lot of languages,
but I'm OK with that because I think if you're numbering the lines
it's super readable here, and even though we don't necessarily
introduce formally the go to statement, and we don't encourage it in class,
it's a very natural way of expressing a loop.
DOUG LLOYD: Yeah, if you tried to use English to structure,
I think those lines of code, lines 3 to 11 there is a loop,
I think it would be a bit more convoluted.
DAVID MALAN: Indeed.