oh I think I made a mistake when I first
got here as a freshman some years ago
I immediately grads gravitated toward
things familiar to me right like I knew
in high school that I was
I liked history I really liked my
constitutional law class and so when I
sat down with my Proctor my Resident
Advisor that first week those first
weeks of school and was thinking about
what courses should I take and what
should I concentrate in or major in I
really stuck with those things that I
already knew and so I signed up as a
government concentrator a gov major and
I spent the next year and a half of my
life taking government classes and
related fields and statistics and math
and so forth and yet when I was in high
school I still had this curiosity about
other fields and I rather postponed in
my mind once I became a freshman oh I'll
I'll study some Dramatic Arts later on
some some Latin later on even then some
archeology later on I kind of kept
thinking I'll get to my electives but
first I'm gonna focus on just getting
done what I think I should get done and
it was completely to the exclusion of
computer science as well in fact I was
always a bit of a geek but I never had
taken any CS courses in high school I
still remember kind of peering through
the door of our computer science lab and
wondering like what my dear so I thought
dear friends were actually doing with
their heads hunkered down and typing
away on some keyboard and to me it was
just C++ or Java or these these names
that I had heard but didn't really know
what they are and indeed that was what
was true I didn't really know what this
other field was and I didn't take this
class cs50 my freshman year because I
was frankly scared of it it had and
still has to some extent this reputation
to beware because it's so unfamiliar to
so many students myself included and it
wasn't until my sophomore year that I
finally got up the nerve to sign up for
cs50 after shopping it for one week but
even then the only reason I got my foot
in the door was because the professor at
the time let me sign up for the course
pass/fail because I think the crux of it
for this field and a few others was that
I I feared failure you know not doing
well in a world that was completely new
to me I assumed that every other kid in
the class it's surely been programming
since he or she was like 12 years old
reality was that's actually not the case
even today over almost 70% 70% of the
students in cs50 were actually just like
me and have never
studied computer science before but
eventually I figured out and that first
semester I figured out exactly what it
was that this field was it wasn't about
Java or C++ or even about programming it
was really about problem solving and
thinking more carefully more
methodically about problems and how you
can divide them and conquer problems in
the real world sometimes with the help
of a computer but frankly you don't even
need the help of a computer to solve
these kinds of problems really you just
need a an algorithmic way of thinking a
more methodical way of thinking so what
might this mean so all of us these days
have these kinds of devices in our
pocket and when you actually use it for
old-school purposes like making a phone
call you might open up your contacts and
maybe a little inefficiently scroll
through the list of friends and family
starting with the A's all the way down
to the Z's or maybe a little more
cleverly you might do autocomplete and
start searching but how does that work
it's actually not all that different
from our approach in yesteryear to
looking up people we know in this device
right there's a whole bunch of names
alphabetically in this and they have
corresponding numbers and that's exactly
the same thing that's going on in your
iPhone or Android phone or the like so
let's consider how the phone these days
actually finds the friend or family
member you want to call quite quickly in
using this is the the metaphor really
the derivative of what that or what the
origin of what that device is so I could
open up this phone book if I'm looking
for someone like my friend Mike Smith
and look down at the first page see that
he's clearly not on it because Smith
starts with s and so I just keep turning
the pages one at a time looking for Mike
now obviously this is pretty slow and
it's gonna take me forever to find him
but that's okay I had sort of I knew
algorithms from when I was growing up I
don't have to do things one at a time I
can do them two at a time so two four
six eight and this too is gonna take a
lot longer but of course no one in this
room is gonna do that and our iPhones
and Android devices don't do that what
would you do instinctively if you had a
book that's even this big to find
someone like Mike Smith yeah so split it
roughly in the middle and of course I'm
gonna end up in roughly like the M
section give or take and Mike's not in
the M section because Smith again starts
with s but what do I know about Mike
Smith where is he in this book now yeah
he's kind of over there to the right
because s comes after the middle of the
phone book and so both physical
but if Oracle II can I divide and tear
this problem in half leaving just half
of the phone work done where I don't
actually need this phone book anymore so
leaving just half of the phone book but
what can I do next I can really just
repeat that process now of course maybe
I've gone a little too far this time and
I'm in the T section not the esses but
that's okay because I can again tear the
problem in half leaving me now with
maybe not a thousand pages or 500 maybe
I'm already down to like 250 pages and
just look at the progress I'm making
through the phonebook rather than one
page at a time or two pages at a time
but apparently hundreds of pages at a
time and if I can continue this divide
and conquer or if we call it by its
fancier name binary search by meaning
too and we keep dividing it in half
hence the two do we eventually end up
hopefully with one page on which Mike
Smith actually is now what does this
mean to be more efficient it clearly is
faster than just looking through every
page or every other page of the
phonebook but if we just think about
fundamentally what we just did this
doesn't even relate to computers it just
relates to thinking we're carefully
about a problem if we think about I saw
that souvenir to go if we just think
about what we just did well let's just
consider very generic not mathematically
oriented at all chart where this is like
the size of the problem I care about and
by size I mean like numbers of pages in
the phone book it's okay you can keep it
the number of pages in the phone book
and let's just call the vertical axis
here time and what's the relationship
among these three algorithms we just
tried well the first algorithm was just
one page at a time and every page might
take me one second or half a second or
whatever so it's a very straight or
linear relationship more pages or time
more pages more time meanwhile if I do
two pages at a time it's still the same
a linear relationship I'm just going
twice as fast so the shape of that curve
is the same shape but it's lower because
if I consider this many pages in the
first algorithm it took me this many
steps but in the second algorithm takes
me half as many steps because I'm going
to two at a time but what's the shape of
that third and final and frankly much
more intuitive algorithm that all of us
have been taking for granted all these
years even if we've never studied
computer science or programming or
programmed it turns out it's much
doesn't get negative it turns out it's
much more curved like this it happens to
be called logarithmic but the point is
that in order for this third algorithm
to take more time you really have to
keep going and going and going and
really see how far out it goes before it
really makes a fundamental impact on the
amount of time it's taking put another
way if I double the number of pages in
that phone book tomorrow how many more
steps would it take me to find that same
person Mike Smith just one more step so
if you double the number of pages the
amount of time required to find Mike
Smith really just inches up ever so
slightly it doesn't maintain this same
relatively slow approach now we can
actually do this in another way what's
another algorithm we might have in a
venue like this well kind of be nice to
know how many people are here so I could
do it old-school new one two three four
five six seven eight okay that's gonna
take forever so I know how to do this
better 2 4 6 8 10 12 14 foot dang if we
can't learn a little something from this
now I can't quite do this on my own but
what if we just said you know we need to
leverage everyone here and in fact let
me let me do this let's consider how we
might visualize the counting of each
other here I need eight volunteers who
didn't know they were gonna be
volunteers earlier do Bob about all
seven of you stand up if you could I can
we steal a number eight over here come
on over all right so I'm gonna give each
of these students here your very own
cs50 pen all right and so you're each
holding a pen and let's go ahead and do
this if we could seven eight if all of
you guys want to just wrote spin around
for the most uncomfortable thing you're
gonna do today let's do you in advance
well huh this is the class of 2020 -
welcome to your classmates and what's
your name Miranda Andrea Lindsey
Virginia Anna Sarina multi-and Dora all
right so thank you all of you for
volunteering so let's count the aid of
you now there's obviously eight so we
know the answer to this stay right there
if you could but how could I go about
counting just these eight one two three
four or two four six eight so that's
going to take me eight steps or
or four steps but can I do it in three
and I count these same groups the same
group of eight students with just three
steps so let's consider this how about
this could half of you give away your
pen to someone else
two standing and then if you gave away
your pen just sit down so half of you
who are standing give away your pen to
someone else and then that same half sit
down
so now four of you are still standing
and each of you presumably have to two
to two pens
well let's repeat this so half of you
give your pens away to someone else
still standing and then sit down and now
there's just two of you and in a moment
there's gonna be one lucky winner of
eight pens so if the half of you just
one of you could give your pens away and
then sit down okay and then sit down
what's your name again Lindsey is
holding 8 pens has the final tally but
how many times did we do that we did it
1 2 3 times because we went from 8 to 4
to 2 and then we were left with just the
one person standing with all eight pens
so a round of applause if we could for
our volunteers you should probably give
them back to everyone yes so let's end
by just considering how we can really do
this n mass because it would take me
forever to count 2 4 6 8 so could we
actually do this together more
intelligently leveraging that same
algorithm that same step-by-step
approach to solving a problem as follows
if I were to say re this half of the
room counts yourselves this half of the
room count yourselves we could just
combine the result just like these
volunteers we repeatedly combining their
results so I don't have unfortunately
hundreds of pens on me but I can give
you each a number so let me just
virtually give you each the number one
including our volunteers everyone will
participate if you could so everyone for
the moment think of yourself as the
number one and now this is the awkward
part for all of us if you would humor me
and everyone stand up also in place so
everyone at this moment is thinking of
the number one and just as with our
volunteers we're just going to do one
round together and then we'll pause
reset and make sure we're good to go and
then repeat each of you is the thinking
of the number one if you could each verb
give away half of you give away that
number to someone else next to you okay
so at this point if you gave away your
number sit down is half of you seem to
have done so at this point in the story
just a quick sanity check everyone who's
standing should probably be thinking of
the number two okay so we're about to
repeat this whereby half of you next
need to give away your number which is
now to to someone else they add it
together and let me propose repeat until
there's one person standing
[Applause]
[Music]
and continue to repeat give away your
number and let someone else take it from
there
[Music]
[Applause]
okay keep repeating if you're standing
and not talking to someone try to give
your number away
[Applause]
[Music]
okay take another moment give your
number away to someone else if you can
and then sit down
[Applause]
all right I'll help out if need be if
it's a little too awkward to shout your
number I hear someone's offering 15 if
someone wants the 15 of 16 all right let
me facilitate at this point just because
it might be getting a little awkward so
whoever's still standing I brought my
calculator just so I don't screw up my
own arithmetic er what number you
thinking of you are 32 so go ahead and
sit down you are thinking you are 37 go
ahead and sit down you're 44 go ahead
and sit down who's still standing
64 go ahead and sit down who's still
standing there 67 go ahead and sit down
who's still standing
45 okay you're said 45 go ahead and sit
down back there
64 go ahead and sit down over here
48 go ahead and sit down back there
sorry 24 go ahead and sit down who's
still staying one more 31 and 81 both of
you can sit down is anyone still
standing right here in the middle 36
go ahead and sit down oh right here 24 I
promise this algorithms fast 24 go ahead
and sit down okay and back there 16 all
right
so did I miss anyone did I miss anyone
all right so let's consider for just a
moment what should have just happened on
each iteration or cycle of that
algorithm half of you were sitting down
then another half then another half so
we were taking great big bites out of
this same problem just like we were
taking big bites out of the phonebook
and just as these eight we're
iteratively having themselves again and
again and because each of them gave
their pen away on each iteration but we
preserve the number of pens just as you
as you gave your number one or number
two or whatever it was away we preserved
the total edition theoretically the last
person standing which I guess will be me
because I did all the adding here should
have the total count of people in this
room now the total I got arithmetic Li
by adding that all up is that there are
according to this algorithm 600
and 13 people in the room but we did it
the old-school way during that same
algorithm and the number we got earlier
was just over 850 people so that so
that's okay that's okay this is our
first example perhaps of a bug or
mistake in a program and well we'll come
back to that this fall
but rest assured even if this was not
within your comfort zone or if you've
never taken a CS class before do
consider exploring some new unfamiliar
field in any of our four fields here and
beyond and do as I wish I had done way
back then allow me to step off stage
though and paint a picture in closing of
not only the material in the world that
awaits you but also the community on
this particular film that was put
together by one of cs50 zone former
students Emily you who's behind the
camera here right now now on cs50 s
production team paints a picture of the
world that awaits you
what about
[Music]
we are on
but the star
[Music]
[Applause]