DAVID J. MALAN: All right, thank you so much.
My name is David Malan.
I teach a class called CS50 at Harvard, which
is our introductory course for majors and non-majors.
To give you a bit of context, in the course's first lecture,
we talked about computational thinking.
We do a demonstration with an old school phone book,
dividing and conquering it by tearing it in half and in half.
And at this point in the beginning of the semester have we given students
a mental model for what computer science is, namely problem solving,
with a mental model like this, where any problem has input, the problem you want
to solve, output, which is the solution there too, and in between
there is the interesting part, the algorithm via which
you take those inputs from outputs.
Thought we'd now fast forward a few weeks into the class,
after which we talked a little bit about a computer's memory,
to give students a mental model for what's underneath the hood.
But also to now focus not so much on code, but on algorithms and ideas,
and ultimately on creating in the class one or more memorable moments.
And in the real world, I would spend a little more time on this,
move a little more quickly, take a little more audience participation.
But to give you a whirlwind tour, thought
we'd begin exactly how we kick this off with, which is the picture like this.
This, of course, is one of the components inside of your computer's
memory, and one of these little black chips
is where all of your computer's bytes are, so to speak.
And recall that we can think about these bytes
is being laid out in a grid or a canvas like this.
And we could even number these bytes.
The top-left one might be bite 0 and the bottom-right one
might be byte 1 billion.
But let's abstract away from the actual hardware now,
focusing really on just this canvas in which we can put anything,
numbers or letters or anything more.
And let's consider what we might do with this canvas
if you want to store some data like maybe seven numbers.
If we have seven numbers, we really just need seven of these boxes.
So let's ignore the distraction of all of those boxes
and focus on just these seven here.
And it turns out that if you look at a contiguous chunk of bytes--
that is, bytes that are back to back to back to back,
this is what we might call an "array" in a language like C. Which is to say,
a chunk of memory that you can store anything you want in it.
In this case, we'll do numbers back to back to back.
The catch is, though, that even if we fill this array
with some numbers like these, you and I, of course, have this bird's eye
view of the array of numbers.
And if I asked you to find the number 50, you could go, boom,
it's obviously right there.
But a computer doesn't really have that bird's eye view.
A computer can really only look at one of these boxes at a time.
And in fact, if you think of these boxes now as yellow doors,
the doors are effectively all closed.
So this is what a computer sees by default,
but it can absolutely move through these doors, opening one door at a time,
looking for something of interest.
Which is to say, here's another problem, the problem of searching,
the problem of searching for a number, for a letter, a name, a web page,
or anything along those lines.
And wonderfully, this fits in to our existing mental model.
This is just a problem to be solved-- that of search, where we've got input
and we want output, the solution there, too.
In this case, of course, the input's going
to be those seven doors, all of which are closed by default.
And the output recall might be framed as a bool, a Boolean, which
is an answer true or false--
either this number is there or it is not.
But of course, the interesting part is, what is
inside of this black box, an algorithm?
And so here's where we might consider a couple of approaches
to solving this problem.
And let me go ahead and grab an old school whiteboard here,
with what I put on it here as a whole bunch of pieces of paper
that have come in advance with two arrays, if you will.
Along the top of the whiteboard here, I've put seven pieces of paper,
behind which are a whole bunch of numbers.
And then I've got another array of seven doors
here, behind which there is another set of seven numbers.
But if we consider the top row here of seven doors, all of which are closed,
and I asked you to find a number like the number 0, well, how might
you do this?
Now breaking the fourth wall, I might have a student come up
to the front of the class and actually walk us through one or more
of these algorithms.
And for instance, their instinct is, for 0, well,
let's start here at the beginning.
Unfortunately, that's not 0, that's a 4, so perhaps they
might take one step further and reveal to us the 9.
That too, is not 0.
It's a bit of a jump, in fact.
But if we keep going, unfortunately, we found 8.
If the student keeps going-- ugh, 2, still not there.
Now we've jumped back up to 7, still not there.
5, and of course, if the student chooses, in a pedagogically optimal way
where, voila, there we are at the 0.
So we could consider now not just the correctness of this algorithm
recall-- that is, does it find the answer, yes or no, correctly
or not, which it does seem to, but what about the efficiency?
It would seem to have taken me quite a bit of time
to find one number among seven, because in that worst case,
I had to search behind all of the doors.
And that's about as good as we or as our volunteer
could have done, because even if they had gone from the right to left, yes,
they might have gotten lucky this time, but of course,
they might get unlucky next time if the numbers
were ordered in a different way.
And indeed, these numbers were randomly sorted.
We could do no better than going left to right, right to left, or even randomly,
keeping track of where we've been in the general case.
But suppose I give you a different assumption,
and I allow you to assume that the numbers behind the bottom array
of doors are all sorted, from smallest on the left to largest on the right.
How now might you go about solving the same problem?
Here we might have another student come up,
and perhaps, they thought back to that phone book
example, where we started in the middle and then went right or to the left.
And so a typical student might optimally start right here in the middle,
looking for, say, whoops, the number 7.
Where is the number 7?
Well, it doesn't seem to be here in the middle.
But now based on this sorted assumption, we
can throw away consideration of all of those doors on the left,
and we can maybe now divide the problem again in half and go over here.
Oh, we seem to have gone a little too far, so maybe let's now go to the left,
dividing the problem further.
And then, in just three total steps, have we found now,
it would seem, the number 7.
And indeed, this same enhancement is going
to apply even if we have twice as many or 10 times as many doors,
if we indeed divide and divide and divide and conquer the problem
like we did some weeks ago in class, can we more efficiently solve this problem.
And these approaches to the problem, of course, have formal names.
At this point in the class, we might more
formally introduce what we know, of course, as a linear search.
We might provide some students with some representative pseudocode
and walk through why this might now explain what I just did,
or ideally, our volunteer just did.
We might provide some pseudocode for now what we know is binary search, again,
ideally, describing more algorithmically what the students themselves have done.
And we might even take a turn for something a little more graphical.
Not getting into the weeds of the math, but the shapes
of these algorithms in terms of their asymptotic running
times like Big-O of n or Big-O of log n just a few weeks in.
But of course, this sort of cliffhanger by the end of the class
is, well, wait a minute, how did we get the bottom array of doors sorted?
Well, that itself is a whole other problem, where you take unsorted input,
you want sorted output.
And gosh, if that takes even more time than to search the thing,
should we even bother sorting the data from the get-go, or just resort
from going, as we did initially, from left to right?
So that, of course, would be an algorithm
for another day, when we dive into something
like bubble sort, or selection sort, merge sort, or the like.
Now to put my-- breaking the fourth wall again,
other variants of the same approach using
simple pieces of paper and chalkboards, have been a digital version.
When I had a touchscreen in class one year,
I whipped something up in JavaScript and HTML and actually tapped the boxes,
or had our volunteer do that, just to make it a little more real.
We got especially creative pre-COVID and found a whole bunch of gym lockers
that we put on stage and had our volunteer come up and physically open
and close the doors, making quite a rattle the whole time.
And in this past year, a silver lining of COVID shutting everything down
on campus is we had an opportunity to literally use
real doors on stage of a theater that was otherwise idled by no attendees.
And so we had an opportunity to film similar examples, taking input via Zoom
from students-- looking here, for instance, the number 6, which,
thanks to the prop shop in the theater, ended up
being a very fuzzy character here.
Now I thought I'd use 60 of my final seconds
here just to give you a real world demonstration of how this doesn't
always go pedagogically optimal.
And so I indeed sometimes have to whisper
in the ears of a student or sort of coax them to what would ideally
be pedagogically ideal, but even then, it's always a teachable moment,
even if the demonstration goes off the rails,
or if the student doesn't quite do what you hope them to do.
So Sean has blessed our sharing this some 10 years now
after it happened, but here is the first row of doors.
Your goal is, only using the top array here, find me the number 7.
And we are then going to critique how you go about doing it.
Find us the number 7, please.
[LAUGHTER]
No.
[LAUGHTER]
5, 19.
13.
[LAUGHTER]
It's not a trick question.
[LAUGHTER]
1.
3.
[LAUGHTER]
Go on.
Only in the top row.
So you've got three left.
So find me 7.
17.
[AUDIENCE SHOUTING]
7!
What I always loved about that moment is how the entire audience sort of
rallied to Sean's support, sort of like a Price Is Right moment.
And even though it took us quite a while to find the number 7,
it indeed lent itself to a whole conversation
about alternative algorithms there too.