[MUSIC PLAYING]
DAVID J. MALAN: All right.
This is CS50, Yale
University's introduction
to the intellectual
enterprises of computer science
and the arts of programming.
All of that and so much more will
make great sense before long.
And I thought I'd mention that
Benedict and I actually go way back.
He and I were classmates at
Harvard some 20-plus years ago.
And we went through our
archives, even though this
was well before digital
cameras, and found this one.
I used to go over to Benedict's room.
And I was friendly with some
of his roommates as well.
And if you can see here, this is a stack
of some very cheap pizza in Cambridge,
Massachusetts, from Pizza Ring.
It was so amazing that they
would give you two pies at once
in the same box for like $8.
And if we enhance here, this
is our own Professor Brown.
So he and I go way back.
And it's only fortuitous that we've now
come full circle and are together now,
teaching this course here at Yale.
So if you are leaning
toward computer science,
you might already have some comfort with
the idea of being in a class like this.
But odds are, you don't.
And in fact, if you're anything
like me back in the day,
I had no interest in
or really appreciation
of what computer science was
back in my first year of college.
And in fact, when I got
to college, I really
gravitated toward things
I was more familiar with.
At the time, I'd come off
the heels of high school.
And I really liked a constitutional
law class in high school.
And I liked history and
that sort of domain.
And so I just kind of
naturally gravitated
when I got to Cambridge
toward government,
which was the closest concentration
or major there in Cambridge.
And I was still, nonetheless,
kind of a geek as a kid.
I certainly played with
computers or computer games.
But I never really took
a genuine interest in it.
And even my friends,
ironically in retrospect,
who did take computer
science in high school,
I thought they were actually
the geeks and didn't really see
the appeal of heads down at a
computer monitor, typing away,
door closed, fluorescent lights.
It just didn't really make
any sense to me or resonate.
But I finally, sophomore
year, I got up the nerve
to shop a course that was
and still is now called CS50.
It was being offered only
at Harvard at that time.
And even then, I only got up the
nerve to go into that lecture hall
because the professor at the
time let me sign up pass-fail,
since I really rather
feared failure of some sort
because it was just so
new and unfamiliar to me.
But long story short, I ended
up falling in love with it
once I actually came
to realize what it was.
And no joke, on Friday evenings,
when back then the homework
assignments or problem
sets would be released,
I would legitimately look forward
to going back to my dorm room--
7:00 PM, the p set would
be released-- and diving
into that week's programming challenge.
But why?
So at the end of the day, computer
science really isn't about programming.
It's probably not about what you
perceived your own friends as doing
in high school versions thereof.
It really is about problem
solving more generally.
So if you're feeling at all
uncomfortable with the idea of shopping
or taking a class like this, realize
that most of the people around you
feel that same way.
2/3 of CS50 students each year
have no prior CS experience.
So even though on occasion it
might sound like it, perhaps
based on answers that others seem
to be giving or facial expressions
they might be having, it's
really not actually the case.
2/3 of you are feeling as
uncomfortable or less comfortable
as I was back in the day.
But the course itself, as
you'll see in the syllabus,
really focuses on students individually.
There is no course-wide
curve per se, but rather
what's going to matter
ultimately is not so much
where you end up relative to your
classmates at the end of this course,
but where you end up relative
to yourself as of today,
and focusing on that delta and that
sense of progression yourselves.
So what then is computer science?
I daresay we can simplify it as this.
So problem solving.
What does it mean to solve a problem?
And that domain itself doesn't
have to be engineering,
doesn't have to be science per se.
Really, I daresay we
can generalize problem
solving to be a picture like this.
There's some kind of input, the
problem that you want to solve.
And there's an output, hopefully
the solution to that problem.
And then between is this sort of
proverbial, a proverbial black box,
this sort of secret sauce
that somehow takes that input
and produces that output.
And it's not yet apparent
to us how it does that.
But that's the goal,
ultimately, of computer science
and solving problems more generally.
But to get to that
point, I claim that we
need to talk a little bit about
what computer scientists would
call representation, like
how you actually represent
those inputs and those outputs.
And odds are, even if you really
aren't a computer person yourself,
you probably know that computers only
speak a certain language of sorts,
an alphabet called binary.
So binary.
But probably fewer of
you have an appreciation
of what that actually means
and how you get from 0s and 1s
to Google documents and Facebook and
Instagram and applications and all
of the complexities that we use
and carry around with us every day.
But let's start with the simplest
form of representation of information.
Like if I were to start taking
attendance in this room,
I might, old school-style, just
take a piece of chalk or a pencil
and just say, OK, 1, 2, 3, 4.
And then I might get a
little efficient and say 5,
just to make obvious that it's a 5.
But these are just
hash marks on a screen.
And of course, I don't
have to do it in chalk.
I can just do 1, 2, 3, 4, 5
and then count even higher
if I use other digits as well.
And digits, it's kind of
a nice coincidence there.
And we'll come back to
that in just a moment.
This system of using hash marks on the
board or using your own human fingers
is what's called unary,
uno implying one,
where the hash mark is
either there or it's not.
And so, 1, 2, 3, 4, 5, it's like
using sticks or fingers or hash marks.
That's unary notation.
There's only one letter in
your alphabet, so to speak.
And it happens to be a 1 or a
hash mark or a finger, whatever
the unit of measure happens to be.
So you can get, though, from using
that unary notation of course,
counting up even higher if we use
more hash marks or more fingers.
And we get to the more familiar
system that we all use,
which is called the decimal
system, dec meaning 10.
And the only reason for that is because
you've got 10 letters in your alphabet
so to speak, 0 through 9.
10 total digits.
And these are the kinds of numbers
that you and I use and sort of take
for granted every day.
But a bunch of you already know
and realize that computers somehow
only speak 0s and 1s.
And yet, my god, a computer,
my phone, any number
of electronic devices these days, are
so much more powerful, it would seem,
than us humans.
So how is it that using
just 0s and 1s, they
can achieve that kind of complexity?
Well, turns out it's pretty much
the same way we humans think.
It's just we haven't thought this
way explicitly for quite some time.
For instance, on the
screen here is what?
Shout out the obvious.
123.
All right.
But why is that?
123.
Really, well, all that's on
the screen is three symbols.
And frankly, if we rewound quite
a few years in your development,
it would look like just
three cryptic symbols.
But you and I ascribe
meaning to these symbols now.
But why?
And from where does this meaning come?
Well, if you roll back
far enough in time,
odds are you'll recall that when
thinking about a number like 1,
a pattern like 123, we sort of instantly
these days intuitively ascribe meaning.
So this is the so-called
1s column or 1s place,
this is the 10s column or 10s place, and
this is the 100s column or 100s place.
And so all of us rather
instantaneously these days do the math.
100 times 1 plus 10 times 2 plus 1 times
3, which is, of course, 100 plus 20
plus 3, which gets us back, to
be fair, to the same symbols.
But now they have
meaning because we have
imposed meaning based on the
positions of those values
and which symbols they are.
So all of us do this every day any
time we stare at or use a number.
Well, it turns out that
computers are actually
doing fundamentally the same thing.
They just tend to do it using
fewer letters in their alphabet.
They don't have 2s and
3s, let alone 8s and 9s.
They only have 0s and 1s.
But it still works, because instead
of using these values, for instance,
I can go ahead and use, not 0 through
9, but just 0 and 1 as follows.
Let me give myself sort of
three placeholders again,
three columns if you will.
But rather than call this
1, 10, 100, which if you
think about it are powers of 10--
10 to the 0 is 1; 10 to the
1 is 10; 10 to the 2 is 100--
we'll use powers of 2.
So 2 to the 0 is going
to give us 1 again.
2 to the 1 is going to
give us 2 this time.
And 2 to the 2, or 2 squared,
is going to give us 4.
And if we kept going, it'd be 8, 16, 32,
64, instead of 1,000, 10,000, 100,000,
1,000,000, and so forth.
So same idea.
Just a different base
system, so to speak.
Indeed, we're using now binary, because
we have two letters in our alphabet, 0
and 1, hence the bi prefix there.
So in binary, suppose that you use,
for instance, these digits here,
these symbols, 000.
What number is the computer storing
if it's somehow thinking of 000,
but in binary, not decimal?
Yeah, it's just 0.
The decimal number you and I know as 0.
Why?
Well, the super-quick math is,
well, this is just 4 times 0 is 0,
plus 2 times 0 is 0,
plus 1 times 0 is 0.
So that gets us back, of course, to 0.
But in the computer, if it were instead
storing a pattern of symbols that
isn't 000, but maybe 001, you
can probably imagine that now--
just do the quick math-- this is
now the decimal number we know as 1,
because it's 4 times 0,
2 times 0, but 1 times 1.
Skipping ahead, you might be inclined
now to represent the next number here
as what?
It's obviously not 002, because
we don't have access to a digit 2.
We only have 0s and 1s.
So you might be inclined to do
something like this, 11, right?
Because if I'm counting to
2 on my fingers, it's 1, 2.
So two hash marks on the
board would seem to give me 2.
But not in binary.
This is unary.
What do I get in binary
with the pattern 011?
AUDIENCE: 3.
DAVID J. MALAN: Yeah,
so it's actually 3.
So the correct way of counting up from 0
on up in binary would be to start as we
did, 000.
Then we go up to 001.
Then we go up to 010.
Now we go up to 011.
And anyone, how do you count to 4?
What's the pattern of symbols then?
Yeah, 100.
Now skipping ahead, if we wanted to
represent not 4, but rather this value,
how high up can we go
with just three columns?
Seven, right?
So it's 4 plus 2 plus 1 gives you 7.
So if you wanted to represent
8, what happens next?
Yeah, so you sort of carry the 1.
So just like in our human
world, when you go from 9 to 10,
you typically carry the 1 to
a new column over to the left.
Exact same idea.
So the number 8 in binary, so
to speak, would now be this.
But you need a fourth column, just like
you would in our human decimal world.
So what then is the mapping
between these low-level ideas
to actual physical computers?
Well, inside of computers
today, whether it's
your Mac or PC or your iPhone or
your Android phone, are millions,
millions of things
called transistors, which
are tiny little switches
that just turn on and off.
If you've ever heard of a CPU, the
central processing unit, that's
the brain of the computer, or the
phone these days, that just has so many
of these microscopic switches
that can turn things on and off.
What are they doing?
They're really just storing
or not storing electricity.
After all, what's the only thing you
and I do probably at the end of the day
or even in the middle of the day if
we want to keep using our devices?
We plug them into the wall
or we plug it into a battery.
So there's some low-level flow of
electrons, or however that works.
But generally speaking,
the only physical input
to your phone or your
computer these days
is an electrical socket or some
battery in the wall or elsewhere.
And that's kind of an
interesting principle,
because if the only input you have
is there's either electricity flowing
in the form of electrons or whatnot,
or there's no electricity flowing,
like the battery is dead or the
plug isn't plugged in, well,
that gives you two total states in
the world, two different conditions
that your device can be in.
It's either plugged in or not.
It's either drawing power, or it's not.
And what's perfect about binary is
that you have two digits, 0 and 1.
That's all we have in the
physical world when it
comes to charging some physical device.
So there's this really nice
mapping between 0s and 1s
and electricity or no electricity,
or turning something on
and turning something off.
So for instance, if we use a very large
transistor like this physical phone,
I might say I have one
switch on this phone.
And indeed, I can now
turn it on like this.
So my phone, this
physical device or switch,
might now be representing
the number we know as 1.
And if I go ahead and turn it off,
it's now representing, of course, 0.
And if I grabbed a couple of more
phones and sort of held them like this,
you could imagine that each of
these phones or, in turn, switches
is just representing
a column and a value.
So if you give me two phones, I can
count from 00 to 01 to 10 to 11.
And that's 3 total.
So with two phones, or two
switches, I can count as high as 3.
If you want me to count
higher, to like 7,
I'm going to need a third
phone or a third switch.
Or an 8, I'm going to need a
fourth phone or a fourth switch.
So this is what all of those transistors
or switches inside of your computer
are being used for,
to store information.
So once you have that
ability to store information,
you can start to represent
anything that's familiar, right?
With just 0s and 1s,
switches that are on and off,
you can represent these numbers
that we think of as binary now.
But you can map them,
so to speak, to decimal,
like the number 7 or the number 8.
So how in the world, if all
the phone or computer has
is electricity and these switches
and this ability to think in binary,
how do you get to
letters of the alphabet?
How do you send a text message?
How do you write a document,
which, of course, involve
alphabetical letters, not just numbers?
What's the leap we now need to make?
Well, we'll leverage what's
called in computer science
this notion of abstraction.
We're not going to spend any
more time in this class talking
about electricity.
That's sort of a very
low-level detail, so to speak.
In fact, we might rarely talk
about binary, which conceptually
is one level higher in your mind
now than the electricity that
flows from the wall.
Who cares how the
electricity works or flows?
I just know that I can
turn something on or off.
From that, I can get binary.
But if I have only have binary,
I can only represent numbers.
Now I want letters.
So we need to now take
things up a notch,
so to speak, and start to use
these same ingredients to represent
things like the letter A. So
how, whether you know this
or not coming in the door, how, given
only those inputs to the problem,
might we think now about representing
the letter A in a computer?
If all that we have is binary or,
in turn, switches or, in turn,
electricity.
What do you think?
AUDIENCE: Using 8 bits.
DAVID J. MALAN: Using 8 bits.
So that's in the right
direction, indeed.
I'd probably want more than
just three or four columns.
And indeed, you've used
the right term here.
If you've ever heard
the expression bits,
that just stands for binary
digits, condensed into one word.
And so these indeed
represent bits, a 0 and 1.
OK, so yeah, we're going
to need a few more bits.
But how do we get to the letter A?
How do we build up conceptually?
How about in back?
AUDIENCE: [INAUDIBLE]
ascribe a value to A.
And then isn't that
like the alphabet model?
DAVID J. MALAN: Yeah, I
mean, that's literally
all we can do is to-- all we have
is the ability to store numbers.
We humans just need to
decide, you know what?
In the context of a text message or
the context of Google Docs or Microsoft
Word, you know what?
When you see a certain pattern of
bits, don't display it as a number.
Display it as a letter instead.
So we might go super simple and
say A is 1, and B is 2, and C is 3,
and so forth.
Well, humans decided not to use
quite that mapping years ago.
It turns out that the capital
letter A in your phone or computer
is actually stored using
the number 65 in decimal.
So the pattern of bits that
gives you the number 65
is what your phone or
computer is storing
if you want to represent the number 65.
And humans came up with mappings for B
and C and D and other letters as well.
And they called this mapping
ASCII, the American Standard
Code for Information Interchange.
Not interesting what the acronym stands
for, but that it's indeed exactly
as you described, a mapping
between numbers and letters.
So if we take this a
little further, here's
where the mapping goes thereafter.
B is 66, it turns out.
C is 67, and so forth.
And so if right now you were to
receive a message from a friend that
happened to be implemented
using 0s and 1s,
and those 0s and 1s that
you just received wirelessly
somehow were representing the numbers,
say, how about 72, 73, 33, what message
did your friend just send you?
If they sent you 72, 73, or 33.
AUDIENCE: It's HI.
DAVID J. MALAN: Say again.
HI.
And then that's H-I. What
might the third one be?
AUDIENCE: Exclamation.
DAVID J. MALAN: Yeah,
you would only have to--
you would only guess this
unless you knew coming
in it's indeed an exclamation point.
Because H-I is 72, 73 exclamation point.
If we actually looked beyond
the dot, dot, dot on my slide,
we would see that 33
is among those values.
And indeed, that is how a computer
represents an exclamation point.
You receive either via wire
from your desktop computer
or wirelessly on your
phone or laptop a pattern
of 0's and 1's that represents
the number, 33 in this case.
And underneath the hood, really
then, it's just some pattern of bits.
It might be represented using light
bulbs, sort of old school style.
It might be represented using hash marks
on the screen or 0's and 1's that you
might draw.
We can all just agree that there's
probably a way to represent 0's and 1's
by just turning things on and off.
Now we can kind of think at
a higher level of abstraction
from the electricity
down here, binary here,
and now this thing called ASCII, which
is one level conceptually above it.
And indeed that's where we get
this notion of abstraction.
You have a low level
detail, that frankly is not
really all that
interesting to a lot of us.
Who cares how electricity works?
We just care that it does work.
But if you stipulate that it does,
now you can represent decimal numbers.
And then we can all agree
to have some mapping
as you propose to letters as well.
So two fundamental ideas so far,
representation and abstraction,
that give us the more familiar.
But what about any of the other
symbols that we all use, right?
American Standard Code for
Information Interchange
is itself a little biased
toward American English.
And indeed, that's
what happened early on.
There were only 128 and then
eventually 256 possible characters
that you could represent in a
computer, which was generally
biased to A through Z, capital and
uppercase, some letter, some numbers,
and some punctuation as well.
But there's a lot more symbols
in other languages that
aren't represented on
a typical keyboard,
for instance any accented character,
and Asian languages having
a whole symbology as well.
There's a lot more characters in the
world than 128 or 256, certainly.
So how do we get there?
Well, the world came
up with, indeed, yet
other characters that you're familiar
with as well, not to mention all
of these guys which you probably
use pretty incessantly these days.
Those are just characters
on the keyboard.
They don't look like
letters in any language.
They look like a little
comic book characters.
These emojis are actually just a mapping
from numbers to letters, as well.
And that is thanks to
something called Unicode.
So years after ASCII was decided by
a whole bunch of folks decades ago,
Unicode was developed to not use
a total as you proposed 8 bits,
but Unicode allows you to
use maybe 16 bits or 24 bits
or even 32 bits, which means the
more columns you have, the way bigger
numbers you can represent, because
you keep having more and more and more
columns or places.
So Unicode allows you way
more than the original value.
So for instance as of this
year, we double checked,
this is the most popular emoji
still in use to this day.
This is the face with tears of joy.
They all have names, as well.
Anyone want to hazard a guess
as to what number this is?
It's not 65.
It's not 66, not 72, 73, 33.
We've seen those.
AUDIENCE: 100.
DAVID J. MALAN: 100.
Higher.
AUDIENCE: 1,000.
DAVID J. MALAN: 1,000.
Higher.
AUDIENCE: Billions.
DAVID J. MALAN: A billion is too high.
It is 128,514, completely arbitrary.
But we humans, unbeknownst
to us, have agreed
that this number shall be displayed
as a picture of a smiling face, that's
smiling so much that it has
tears of joy in its eyes.
And every other emoji you've ever
sent, similarly has a mapping as well.
But if you really want to
take the fun out of emojis,
next time you send an
emoji to a friend, this
is literally what you're
sending to your friend.
Some esoteric pattern of 0's
and 1's that their phone is just
displaying in a more interesting
way using a font of sorts
to interpret those bits.
All right, so that was a whirlwind
tour so far from electricity
on up to emojis.
Any questions so far?
Yeah.
AUDIENCE: How does syntax work in
terms of, like, when we have words,
we have spaces in between them so we
know when one starts and the next ends.
But on a computer, do you have--
is it just a long sequence
of 1s and 0s and switches.
How does the computer know when to stop?
DAVID J. MALAN: Really good question.
So in simplest form, if you go way
back into time when you had those old
big monitors called CRT
or Cathode Ray Tubes
where you could actually see the dots
composing the letters on the screen.
If you have a childhood
calculator, that's kind of similar.
The little LED show you really
the physical representation
of those values.
When you don't have fonts,
everything is just fixed width,
like someone built a
piece of hardware that
will display the first character here,
the next character here, and so forth.
And typewriters in
yesteryear did exactly that.
There was no proportionality.
There was no kerning, so to
speak, between characters.
But once you have fancier
Macs and PCs and phones
these days were born
for the notion of fonts.
And Apple years ago really
spearheaded this, especially.
So there are other 0's and
1's in any word document
or any Google document that you use that
are storing other patterns of bits that
essentially tell the MAC,
PC or phone what font
to use to display those characters.
And these days-- and we'll talk about
this actually in just one moment--
your screen is just this amazing canvas
of like millions of dots called pixels.
And these fonts can sort of use
those pixels in different way.
And sometimes they'll be more squished.
Sometimes they'll be wider.
But it's more 0's and 1's.
And humans just needed to decide,
Apple and Microsoft and elsewhere,
what patterns of bits represent
Times New Roman or Comic
Sans or some other such fonts as well.
All right, so suffice it to say
that in a smiley face like face
with tears of joy, there's
a lot of yellow dots
or it would seem or just yellow color.
And indeed that dot is
generally known as a pixel.
Well a pixel is sort of another
thing that-- well, the computer
has got to represent it somehow.
After all how does the computer know
to show me yellow or green or blue
or anything else?
Well, it reduces to pixels, as well.
You might have heard this acronym
in some context in the past.
RGB stands for?
AUDIENCE: Red, green, blue.
DAVID J. MALAN: Yeah, red, green blue.
And if you hadn't heard that
before, it's no big deal.
It just describes a common
convention for computers
to store any color of the rainbow.
They breakdown every color you can
think of into some amount of red,
some amount of green,
some amount of blue,
that if you overlap those three shades,
you get the color that you want,
for instance something like yellow.
So for instance, if we
consider this picture here,
this is three pixels side by
side or really RGB, a triple
if you will, three
different values of sorts.
So red comes first.
Green comes second.
And blue comes next.
So really underneath the hood, suppose
that your computer were storing
the same numbers as before,
72, 73, 33, but now it's
in the context of Photoshop or
a browser or some program that's
designed to show graphics and not text.
Well, the computer will
interpret potentially
that same pattern of 0's and
1's in just a different way.
Rather than display
them as text, like HI!
H-I exclamation point, it'll display
it as the combination of these three
colors.
So you'll take some amount of red, some
amount of green, some amount of blue.
And it looks like a good amount of red,
a good amount of green, and less blue,
just based on those numbers
72, 73, and then less, 33.
And if you actually combine those with
each other, what you'll ultimately get
is, if we merge them together,
that same shade of yellow.
Now let me stipulate
for the moment that each
of those values of red and green
and blue by human convention
tend to use 8 bits.
So with 8 bits, anyone want to
guess how high you can count
if you have 8 columns on the board?
AUDIENCE: [INAUDIBLE]
DAVID J. MALAN: Yeah, you
have to do some quick math.
But if you literally went 1, 2, 3,
4, 5, 6, 7, 8, this is the 1's place.
This is the 2's place, the
4's place and so forth.
If you do that math, you
can count as high as 255
using 8 total bits or 8 total columns.
This is very common unit of measure.
And it's one of those things eventually
that will just become second nature,
because it's used in so many places.
And indeed it's used in colors.
The computers of today typically use
8 bits, eight 0's and 1's to represent
how much red you want for every
dot on the screen, 8 more bits
to represent how much green you
want on the screen, 8 more bits
to represent how much blue.
So they spend 24 bits total to
represent how much red, how much green,
how much blue each dot on
your screen should be and then
display the resulting value as it
might be here with this yellow dot.
But the only thing that's
changed is the context
in which those bits are interpreted,
not a word processing program.
But like a graphics program, it
still reduces to 0's and 1's.
And you can see these
pixels or dots, right.
This is that same emoji as before.
And if I start to zoom in on this,
you start to notice a pattern.
And indeed that like lovely shade of
yellow and the black eyes and so forth
are actually just a whole bunch of
dots that when you look at it normally,
they're so small you don't realize
that it's a very jagged image.
But if you zoom in on it
quite a bit, you actually
start to see the pixels on the screen.
And you can kind of do this, not
so much with phones these days,
if you've ever heard of retina
displays and the fancy things
that Android phones and
iPhones have, your human eyes
can't really even see the dots anymore.
But if you go home to your
TV or look at an older TV,
especially and get way too close
to be comfortable watching it,
you'll actually see
these same dots as well.
And that just means every one of
the yellow or black or gray dots
on the screen is being represented
by this Mac or PC using 24 bits.
So the top left hand
corner, that's 24 bits.
The next dot over is 24 more
bits, 24 more bits, and so forth.
So if now you've ever taken
a photo and you've stored
the file like a JPEG on your
computer and it takes up 1 megabyte.
One megabyte means one million bits--
1 million bytes.
And a byte anyone know?
AUDIENCE: 8 bits.
DAVID J. MALAN: It's just 8 bits, right?
One bit is pretty useless, right.
You can only count to 1.
But 8 bits, you can count,
we just said, to 255.
So most people in the
world talk about bytes.
One megabyte just means
one million bytes.
So that's a lot more 0's and 1's.
So once you have a file on your
hard drive storing an image,
the bigger the photo is, the
bigger the file is going to be.
Or the higher the resolution is,
the more dots your photos have,
the bigger the file is going to be.
Why?
Well, because for every
one of those dots we--
at the risk of oversimplifying-- you
have to store another 24 bits, 24
bits, 24 bits, 24 bits, and so forth.
So the bigger the image, the more
disk space it's going to take up
and the fewer files you can even
store, therefore, on your Mac or PC.
This is why, ultimately,
you run out of space.
Now I borrowed this from online.
We'll see if it sort of remains
a thing this year as well.
But you might have noticed quite
a few GIFs, Graphical Interchange
Formats being posted to this Facebook
and certainly many others online.
You might have noticed that some of
those graphics are sometimes animated.
They literally say GIF.
And if you click on it,
something sort of happens.
And sometimes you can upload videos,
certainly to sites like Facebook
as well, and hit a play icon.
And then that plays as well.
Well, how does that fit
into this sort of hierarchy?
Well, again, we started with
electricity, 0's and 1's, then
we had letters.
But instead, if you don't interpret
those 0's and 1's as letters,
but sort of conceptually think about
them now as colors, you have images.
That's all an image is, a
bunch of dots or pixels.
Well, what is an animated GIF?
If you've ever seen
some meme going around
where there is sort of an animation,
it's just image, image, image, image.
And sometimes it loops--
image, image, image, image--
and it creates the illusion of motion.
If you were a kid and ever
had one of those flip books
with like hundreds of pages
of like cartoon drawings,
and you flip it really fast, that's
just creating the illusion of a video
by showing you lots
of frames per second.
And that's all the video is.
Once we agree that,
yeah, I can store images
because this is just a bunch
of pixels, each of which
is interpreted left to right as red,
green, blue, red, green, blue, how
much color I want for each dot.
Well, then all you need to do
is store more of those pixels
to represent the second frame of a
movie, the third frame of a movie.
And in our human world
in Hollywood most movies
are 24 frames per second
or 30 frames per second.
That just means when you're watching
a video or even an animated GIF,
you're watching dozens of
images fly by your eyes
every second creating the
illusion, therefore, of motion.
And that's all a video file is.
And so here too, you
can take the fun out
of clicking on any of the means
online because you're just
looking at bits and bits and bits flying
across the screen in some pattern.
Musically as well, if
you've ever played a tune
on a keyboard or some
other device, well, we
could think about how we can
represent sounds as well, right.
These are musical notes, so to speak.
And each of those notes might
be played on, for instance,
a piano for some unit of time.
So maybe one second per note
or much faster than that.
So you could imagine maybe
storing with 0's and 1's the note
you want to represent, maybe A or B
or C or D, E, F, G, the amount of time
that you want to play that note for.
Maybe it's a split set and maybe
it's a quarter of a second,
maybe it's a full second or the like.
And if you really want to
get fancy, we can maybe
store a third value,
how loud do you want
that note to be at some moment in time.
And if you just imagine now these
triples, note and duration and volume
and just keep doing note, duration,
volume, note, duration, volume, now
you have a whole musical staff
that can be played audibly so
long as you have speakers as well.
So it's just using these bits in
different patterns in different ways.
So that's how we might
represent inputs and outputs.
When you save a file on Microsoft
Word or Adobe Photoshop,
you're creating an output by saving
these patterns of 0's and 1's
to your computer's, say, hard drive.
All right, so that gives
us inputs and outputs.
But what's inside of
the so called black box?
This really is where computer
science now comes into play.
These are things called algorithms.
And in your own understanding now
what is an algorithm if you could?
What's an algorithm?
Let me go a little farther back.
Yeah, in the back.
AUDIENCE: Instruction.
DAVID J. MALAN: An instruction
to do something, presumably.
Other perspectives?
And algorithm is an
instruction, something else?
Yeah.
AUDIENCE: A path to follow.
DAVID J. MALAN: A path to follow.
So a logical path to follow, yeah.
And let me combine those two.
It's really like step by step
instructions for, shall we say,
solving a problem.
That's all an algorithm is.
And so when you hear about
algorithms and machine learning
and artificial intelligence
which use algorithms,
those are just step by step
instructions that computers
are using to solve some problem.
So that's, I claim, what would be
inside of this black box in the middle.
So what might a sample algorithm be?
Well one that you saw an
illusion to a little bit
ago is this old school
device here, so a phone book.
And inside of a phone book are hundreds
or thousands of names and numbers,
typically alphabetical from A to Z.
And even though this is old school
and most of us don't
even use these anymore,
frankly, it's the same thing in
our Android phones and iPhones.
Those just happen to be
digitally implemented.
But they're still sorted
A to Z, top to bottom.
And so instead of flipping through pages
one at a time or two at a time, now
we're just kind of scrolling
through one at a time.
But of course, on our phones,
you can search for things,
and you can type in a friend's name
and try to look them up in your phone.
Well, back in the day, you would
do that's similar in spirit,
but you would have to do it with
your own human eyes and not software.
But how is software implementing
that same step by step approach?
Well, if I want to find someone
like Mike Smith in this phone
book, last name Smith
starting with S, well, I
could certainly just start at the
beginning and look on the first page.
And nope, he's not there.
Second page, nope, he's not there.
Nope, he's not there.
One page at a time.
That is a step by step
process, an algorithm.
Is it correct?
AUDIENCE: Yes.
DAVID J. MALAN: Yeah, it's correct
in the sense that if Mike is in here,
I will find him if he is.
Is it good algorithm?
AUDIENCE: No.
DAVID J. MALAN: No, I
mean it's pretty stupid.
This is going to take me forever
to go one page at a time.
So in grade school I
could do things twice as
fast by going 2, 4, 6, 8, 10, 12--
that's actually easier said than done--
and so forth and fly through
the phone book twice as fast.
Is that algorithm correct?
AUDIENCE: No, it isn't.
DAVID J. MALAN: No.
Why, what's the catch?
AUDIENCE: You could skip him.
DAVID J. MALAN: Yeah, I could
skip them accidentally, right?
Once I get pretty deep into the
phone book I just might get unlucky
and he happens to be sandwiched
in between two of the pages
that I'm flying through.
So they're still fixed.
I don't have to just never
use two things at a time.
I can just make sure that when
I hit Sn in the phone book
or maybe the T section, I know I have
to at least double back maybe one page.
So I can fix that bug or mistake, as
it would be called in programming,
and then see if he's on that page.
But most of us if we're going
to use this technology at all
are not going to search
one or two pages at a time.
What's a normal person going to do?
AUDIENCE: Just open it.
DAVID J. MALAN: Sorry.
AUDIENCE: Just open it.
DAVID J. MALAN: Just open it.
OK, I am in the M section.
I don't see Mike.
AUDIENCE: Keep going.
DAVID J. MALAN: Keep going where?
AUDIENCE: To the S,
like there's more pages.
DAVID J. MALAN: OK some more pages.
But direction matters.
So I probably want to go to like
this way to the S's if I'm ending up
in the middle in the M's.
But what does that mean?
It means that I know Mike is not in
any of this half of the phone book.
So both figuratively and literally,
we can tear the problem in half,
tear the problem in half.
And now I'm left not with one byte
or two bytes out of the problem
as my first algorithms
involved, now I've
taken like 500 bytes out
of the problem all at once.
But they're not incorrect, right.
I know Mike, as you say, it's not
there because he's toward the S's.
All right, what do I do now?
I open it up.
All right, ah, slightly too far.
I'm in the T section now.
What do I obviously do next?
Now he's this way.
But that means there are like 250
pages that I know he's not on.
So again, my algorithm
of 1 and 2 at a time
is completely blown away by this
much faster algorithm as well.
And I can repeat and I
can repeat and repeat.
And if I did it right, hopefully,
I'm going to end up with, eventually,
if we fast forward one
page and Mike Smith
is either on the phone
book's page or he's not.
I can go ahead and call him then.
So this is just intuitive.
And frankly, that's
exactly what your phones
are doing when you search for a friend.
It happens in a split second.
But your phone typically, if you're
looking for Smith in your phone,
it's not searching from top
to bottom among your contacts.
It's jumping mathematically
to whatever the middle is.
And that's probably M, give or
take, depending on the distribution
of your friend's last names.
And then it's going to
jump forward or back,
without you seeing this as
a human, finding that value.
And what's the takeaway there?
Well, just how much
more efficient was this?
Well, the first
algorithm, how many steps
might it take me in 1,000 page
phone book to find Mike Smith?
Yeah, I don't know like 700,
800 something like that,
like hundreds of pages.
What about the 2's
approach, 2 pages at a time?
Like 350, 400 pages, right,
half as many pages, since I'm
flying through twice as fast.
How many times is it going to take
me to look for Mike Smith using
the third algorithm where I kept
dividing the problem in half,
dividing and conquering if you will,
and it started with 1,000 pages?
AUDIENCE: Three.
DAVID J. MALAN: Three, more
than three, unless I get lucky.
It's closer to 8, 9, 10, right,
because 1,000 in half is 500,
then 250, then 125,
then I have to round.
And then I keep going.
But I can do that
10-ish times, depending
on the precise number of pages, 9 or
10 times will get me to one final page.
So that means I started
with 1,000 pages at first.
I can in 10 steps, your
phone can in 10 steps,
find that friend in the phone
book, if they are actually there.
The first two algorithms would have
taken 700 steps, 350 steps, or at worst
the whole phone book if, I just
keep going and don't find him.
The algorithm that we had more
intuitively is indeed the same.
And without getting too
mathematical, we can actually
appreciate this even graphically.
So here's sort of a very simple
chart on the x-axis or horizontal,
it's the size of the problem, like
how many pages are in your phone book.
The vertical axis on the
left is how much time does it
take you to solve the
problem-- seconds, page turns,
whenever your unit of measure is.
Well, the first algorithm
I can draw like this.
It's a straight line.
The slope has a 1 to 1 ratio, because
if Verizon or the phone company
next year adds one more
page to the phone book,
that might push Mike
one more page forward.
So that might take me one
more unit of time to find him.
So a 1 over 1 slope.
The second algorithm is
also a straight line.
It's just lower than the red line,
because for any given number of pages
on the x-axis, wherever
I want to put my hand,
I'm going to hit the
yellow line at some point,
and that's how many page
turns or seconds it takes,
but if I go higher up,
twice as high up, then
I'll see how much time the first
algorithm took, the red line,
because it's working half as fast.
But the third algorithm is what
we'll call this curved green line.
It's a different shape
and even if you have
hazy memories as to what
the term means, it's
what we called at some point in your
mathematical backgrounds, logarithmic.
And if you haven't seen this term, not
to worry if it's unfamiliar altogether.
But this has a fundamentally different
shape, a fundamentally different shape.
It's not a straight line.
It's curved.
And notice that it almost kind
of sort of gets flat even.
It never becomes flat.
It just grows or rises ever so slowly
as you go farther and farther out.
Why?
Well, think about it
from another perspective.
If Verizon doubles the number of
people in the phone book next year,
maybe two towns East Haven and
New Haven merged together into one
bigger phone book with
twice as many pages,
well, how many more steps
will take you to find
Mike Smith next year, in that case?
Like, one more step.
That's a really powerful idea, just
to go up one second or one page turn
on the vertical axis,
you have to go way,
way out on the x-axis, which again
represents the number of pages.
And that's a powerful algorithm.
And what I claim is that
even if you're feeling
uneasy with the idea of computer
science, let alone programming,
a lot of the ideas we're going
to explore this semester really
are as familiar as that.
And it's really just a
process of translating
those ideas and that human intuition you
already have into what we'll call code.
And what a perfect setup to actually
introduce some code, but not
in specific programming language.
So we'll begin with this, pseudocode.
So pseudocode is not a formal language.
There's no one way to write it.
And everyone of us on the staff
might write the following algorithm
in a slightly different way.
You just use English
like syntax and grammar
or whatever your spoken language
is to convey your ideas.
So for instance to
implement that algorithm
that I ended on, finding Mike Smith
by dividing and conquering again
and again, how would Express that a
little more methodically in such a way
that another person or ultimately
a computer could understand?
Well, I might jot down that step
1 is just pick up the phone book.
That's where I began.
Step 2 would be open to the middle of
the phone book, you know, give or take.
I can be a little sloppy about it
even if I want in the human world.
And it will average out in the end.
Step 3, look at the names, looking
for Mike Smith on the current page.
It's the M section, so I already
know he's not going to be there.
So then I have to ask
myself a question, though.
If Smith is among the names,
what do I probably want to do?
Call him or do something
with that information.
So I'll indent that
underneath to make clear
that there's cause and effect here.
If step 4 is true, then
I should do step 5.
That's all the indentation means.
But if Mike is not on
the page I'm looking at,
which he's not going to
be if it's the M section,
then I might ask well else if Smith
is earlier in the book to the left
then what do I want to do?
Well, as you proposed, go to the
left of the book, and in this case,
open to middle of left of book.
And if I then don't find that he's
earlier in the book, but rather,
then I have to go back to line 3.
Why?
Well let's be clear, if on line
6 Smith is earlier in the book,
he's to the left of where I am in
the book, what do I want to do?
I want to open to the middle
of the left half of the book.
And then go back to step 3 because the
next step should be, look at the names,
if I've just jumped
elsewhere in the book.
And I can repeat the same process again
and again without writing this down
to be 20 or 30 or 40 lines.
I can reuse some of my own
syntax to be more efficient.
But if Mike is later
in the book, I instead
want to open to the middle of
the right half of the book,
and then again, go back to
step 3, because I want to see
if he's on now that page to the right.
Now I'm not quite done.
Mike's either there or he's
to the left or to the right.
Or there's one fourth case, so to speak.
AUDIENCE: He's not there.
DAVID J. MALAN: He's not there.
And I should consider this.
So if I want to make
sure I should say else.
If he doesn't fall into any of those
three scenarios, I should just quit.
And if we fast forwarded a bit among
the delights in any programming class,
ultimately is your first of many
bugs or mistakes that you might make.
And you've seen bugs before in the
world of Macs and PC and even phones.
If you've ever seen annoying little
spinning beach ball on Mac OS,
or you've seen the little hourglass
things spin endlessly on Windows,
or if you're iPhone or Android
phone just freezes altogether,
very likely the human who wrote the code
that your phone or laptop are running
at that moment just didn't
anticipate some fourth
or some fifth possible scenario.
And therefore, there was no
line of code that the computer
could use to handle that scenario.
So it just crashes or spins forever or
reboots or does something unexpected.
So even something like this,
if you left out this condition,
you might be looking for Mike
endlessly, spinning beach ball,
if you never actually tell
yourself to quit or to exit.
So we'll see more evidence
of that before long.
But let's apply some now programming
terms to these ideas here.
So highlighted in
yellow now or henceforth
are what we're going to call functions.
These are just actions or verbs
that tell the computer or the human
or the robot what to
do in pseudocode here.
Those are all verbs or actions.
Here we have what I'm going to call--
what we're going to call conditions
or branches.
These are like decision points or
metaphorical forks in the road.
You're either going to
go this way or that way
just like in the phone book or maybe
a third or fourth direction as well.
But how do you decide what
road to go down logically?
These are a little more fancy
called Boolean expressions,
after a mathematician
named Boole in yesteryear.
And a Boolean expression
is just a question
that has a yes no answer or a true false
answer, or, if you will, a 1 0 answer.
We could reduce that to bits as well.
Lastly, we'll have these
things highlighted here,
which we're going to call loops.
And going back to line 3 is
indeed inducing this kind of idea,
go back and do something again such
that you're in some kind of cycle
or as we'll say a loop.
And those are four of
the ideas in programming
that we'll see now in actual
code and four of the ideas
that will persist throughout
the whole semester.
These relatively simple
building blocks that you and I
use every day, either intuitively
or maybe even on paper,
are just ways of breaking down
problems into step by step instructions
or, again, algorithms.
But we're going to add a few things
to the list in just a moment, things
called variables which you might recall
from algebra or math more generally,
things called threads which are a
little more specific to computing,
and events which we'll see,
especially later in the semester.
But we're going to do this as playfully
as we can by way of this character
here named Scratch.
And odds are some of you probably
used in high school, middle school,
in grade school--
yes, a few.
So Scratch is this amazing
language from MIT's Media
Lab developed some years ago.
And, indeed, it's targeted
primarily at younger students.
But it actually encapsulates
all of these ideas
that we've discussed thus far.
And we use it in CS50 as a springboard
in the first week to our second week,
wherein next week we'll introduce
you to a language or two--
a week and a half about, we'll introduce
you to a more text-based language,
more traditional language called
C. But let's see if we can't see--
no pun intended-- let's see if we can't
see some of these same ideas in some
of the code here as well.
So I'm going to go to a
website here Scratch.MIT.edu.
And ultimately, in a week and a
half when the first problem set
or programming assignment
for the course is due,
we'll provide you with all of
this step by step instructions
to do the same thing yourself.
The first thing you can do is
you'll see in the homework is
to create something in Scratch.
And you'll be prompted first to create
a user name and password so that you
have somewhere to save your file.
But I'm just going to do
my things here on the fly.
And by default, you'll see an
environment that looks like this.
And I'm going to go ahead
and dismiss the default
tutorial, just to give a definition
of what's here on the screen.
So on the left hand side here is a
whole bunch of seeming puzzle pieces,
little colorful blocks
that in just a moment
I'm going to drag and drop and
interlock them like an actual puzzle.
In the middle here is what we'll
just call the programming area.
This is the editor where I'm going
to drag and drop those puzzle pieces.
And over here is what
MIT calls the stage.
It is the area of the screen where
Scratch, the default cat that we see,
can move up, down, left,
right make sounds, or do
any number of other things.
So we're going to create
code by dragging and dropping
those puzzle pieces into the middle.
And then when I click the Start
button, effectively, well, things
start to happen.
So perhaps the very first thing or
simplest thing I can do with Scratch
is this.
Notice how in the left hand side here,
there's these colorful categories
that just group different ideas into
different types of puzzle pieces
or blocks.
The first one up here under
Events is where I want to begin.
The act of clicking a start
button on a phone or a laptop
is what a computer
scientist calls an event.
It's something that happens that
the computer can listen for.
And we'll see now that there's
this little green flag,
like in a game, that when
clicked over here at top right,
will just start the code running
based on whatever I've typed.
Now the only thing I want to do is
make Scratch look a little different.
And if I scroll over to
Looks over here in purple,
there's a whole bunch of puzzle
pieces, one of which is just say Hello
by default. So I'm going to go ahead and
drag and drop that puzzle piece next.
And notice that as I get close
to an existing puzzle piece,
they're sort of magnetic
and they want to interlock.
So if I just let go,
they now snap together.
And one of the very first
programs written years ago,
historically, had just this
phrase here, hello world.
Some of the very first few words
ever spoken in a computer program.
So we'll repeat that legacy here.
So I now have a program.
It's super simple.
It's only got two puzzle pieces.
But how do I go ahead and play it?
Well, the code is telling me what to do.
When the green flag is clicked,
go ahead and say, hello world.
So that is a program, right?
There's no text.
There's no C++.
There's no Java.
There's no Swift or any languages that
might generally have heard of thus far.
Scratch itself is a language
that happens to be graphical.
But it has the same ideas that
we'll see in fancier form soon.
In fact, what has just happened--
let me go back for just a moment
here over to the where we began.
And you'll recall we had this
definition of problem solving.
Inputs passed into algorithms
which yields outputs.
Well, let me propose that we consider
the input in this particular program
just to be this, hello
world, the words I happen
to type into that little ovular box.
Then the algorithm is
just to say something,
like that is the code that's
taking as input those words.
And what is the output going to be?
Well, hopefully, if the
code works, it's going
to make the cat say with a little
speech bubble, hello world.
That's the output.
So this super simple program
already fits into this paradigm.
Well, what if I want to do
something a little more interesting?
Let me go over here now.
And let me go ahead and let's see what
else can I have Scratch do for me here?
It looks like there's a whole
bunch of movement that I can do.
It looks like there is
a whole bunch of Looks
I can give him with saying something.
It looks like their Sound capability.
Let me scroll down here
to Sensing, for instance.
This one's interesting, ask,
what's your name, and wait.
So I can maybe make this
program more interactive
so that I have to do something
beyond just click a green flag.
Well, let me go ahead and get
rid of this for just a moment.
And get rid of a block, you can
just take it to the left and let go.
And it disappears.
Let me drag this one in here.
And I'm fine with that, ask,
whats your name, and wait.
And notice over here, this
puzzle piece is a little special.
It comes with a sort of special
dependent piece, the answer
that the human has typed
into their keyboard.
So how do I go ahead and use this?
Well, let me go back to Looks up here.
Let me go ahead and say
something for two seconds.
And what do I want to say here?
Let me go ahead and say, hello comma.
And then let me go back to
Sensing to get this thing.
Oh, no, sorry.
Let me go ahead and get
one more puzzle piece.
Say something else for two seconds.
But notice this, I don't have
to say anything there per say.
I can instead go to this answer.
And even though it doesn't
quite look like it will fit,
these blocks will grow to fill.
And indeed, it feels like it's magnetic.
Now I can say, hello comma,
and then say so and so's name.
So let's try this.
Let me go ahead now and
click the red stop sign, now
the green flag, what's your name.
I'll go ahead and type
in David and hit Enter.
Hello comma David.
I mean, kind of underwhelming and
kind of stupid, aesthetically, why?
Like what rubs you the wrong way?
AUDIENCE: It's too long.
DAVID J. MALAN: It's like two seconds
hello David, like I just want to say it
all in one breath, if you will.
But I can't type in words and
then drag that puzzle piece there,
because it's going to overwrite
or fill the white oval.
So what can I do?
Well, if you start to
poke around-- and this
is a lot of what
programming is initially,
just reading the documentation or
googling for definitions of functions
that exist you haven't heard of yet
or just skimming a list like this.
Well, I'm going to go down
here and scroll further.
Well, this is a little weird for a
default example, join apple and banana.
But those are just sample
words that you can plug in.
So you know what I'm going to do,
I'm going to grab this answer.
And I'm going to move--
I'm going to get rid of
the second say block,
because I really just
want one thing to happen.
And you know what?
I'm going to change
apple to hello comma.
And I'm going to change
banana to answer.
And joining is going to
do what's more fancily
called a concatenate, combine
two things left and right.
And then let me go ahead and drag this.
It's going to magnetically
snap into place.
And now I think we have the
right idea, what's your name.
Let me try it again.
David.
Hello comma David.
But notice how we're sort of building
up almost vertically on the program
by nesting and nesting and kind
of stacking these puzzle pieces.
But that's OK.
And notice here what's happening.
So this puzzle piece here, Ask, is
somehow asking the user for input
and then returning it in some
sense, handing it back in a variable
as we'll call it called Answer.
So in computer science and programming,
we don't call variables x, y, z.
Typically, we give them actual names
that are more descriptive, like Answer.
So here is a variable storing an answer.
And we can now use that here.
Well, what is Join?
Join is another function,
an action or verb,
that's going to join two
inputs together and create
one new output like hello comma David.
That output can become some
other function's input,
hence the stacking that I'm doing.
So hello comma David is what's
actually passed into the Say function.
And that's why I see my
name ultimately printed.
So if we break this down into
the same paradigm as before,
if we start with problem
solving as before,
the input initially to the Ask
block is, what's your name.
And the algorithm in
question is, of course, ask.
The output of that is whatever the
human's answer was stored in this thing
called a variable, just by
Scratch for me automatically.
Well, then if I consider the second
line of code, there's two inputs,
and that's OK.
You don't have to pass in just one
input you can pass in zero or one
or two or more.
Hello comma and answer are my
two inputs to this process.
The algorithm now is going
to be that join function.
And it's going to figure
out how to combine
these two things, left and right.
The output is hopefully going
to be hello comma David.
But now that output,
if we shift it over,
can become the input to some
other algorithm or function.
And that function here might be say.
And that hopefully is
going to output hello comma
David right out of the cat's mouth.
So again, problem solving is
reduced to different forms
based on the language you're using.
And at the moment the
language we're using
is indeed this language
called Scratch that
allows us to program, literally, by just
dragging and dropping puzzle pieces.
Any questions then on
these steps thus far?
No.
All right, well let's try something
a little fancier how about this?
Instead of when the
green flag is clicked,
let's actually make them can do
something a little more interesting
like play sound meow until it's done.
[CAT MEOWING]
OK, adorable didn't take much
effort, but an adorable program.
But if I wanted it to
meow again, I can do--
[CAT MEOWING]
--click the green flag.
[CAT MEOWING]
Click the green flag.
This is not the most interactive.
Well, it's actually very interactive.
It's not the most automated
program, like if you have to play--
[CAT MEOWING]
--the game again every time
you want to hear the cat meow.
[CAT MEOWING]
So what kind of programming
construct or idea
can we use from before to automate this?
AUDIENCE: A loop.
DAVID J. MALAN: Yes, some kind of loop.
So if I kind of poke around in Scratch
indeed under Control in orange,
there's a couple of looping blocks,
repeat some number of times 10
by default, but I can
change that, or forever.
I can the cat meow forever
if I do something like this.
Let me grab the forever block.
And I don't want to put it here.
I want to logically kind of break
this up and reconstitute it.
Let me put it in here.
And again that gap will
grow to fill the block.
Now let me connect it to the green flag.
So that now--
[CAT MEOWING]
--I mean, it's not a
very happy cat perhaps.
[CAT MEOWING]
So maybe I should grab this.
[CAT MEOWING]
And notice this is all very interactive.
[CAT MEOWING]
Let me wait one second
after playing the sound.
[CAT MEOWING]
Now it's a little less
worrisome what the cat is doing.
[CAT MEOWING]
And so we now have a program
that's actually using a loop.
[CAT MEOWING]
Well, we can use loops in other ways.
Let me go ahead and open
up something that I--
let's have the cat, for
instance, count up here.
So how about this?
Let me get rid of this.
Let me undo this.
And let me go ahead and grab a variable.
And it turns out you don't have
to just use the answer that we
got from the Ask block.
That variable you just kind of get
automatically for free in Scratch.
You can make your own.
So I'm going to actually
create a variable here.
And I'm going to call it counter.
And sure, I'm going to click OK.
Notice, it gave me now a new
orange puzzle piece called
counter that I can now use somewhere.
So it also gave me these
other orange puzzle
pieces, like set counter to zero.
And that's what I want to do.
I don't want to just--
I want to write a program now
in a loop just counts upward.
So to do this, I'm going to
grab that and set the counter
to equal to 0, then forever.
I'm going to go ahead and what I'm
going to save the value of that counter.
So I'm going to drag this in here.
2 seconds is going to take too long.
So let's just change it to 1 second.
Now I'm going to go back
to my variable category.
And I'm just going to drag this
one in here, just as I did before
with like hello, my name.
And then sure, I'll go ahead and wait
1 second just to slow things down.
And then I'm going to
go back to variables.
And again, I'm doing this
quickly only because I've
kind of tinkered with this before.
I'm going to change the counter by 1.
So notice I've made a fancier program.
But logically, it's just
going to set the counter to 0.
And then it's forever going to say
the counter's value, wait a second,
change the counter by 1, then do it
again and again and again and again.
There won't be any sound this time.
But we will see that Scratch in this
way can count, it would seem, from 0
on up to infinity, theoretically.
But we'll see that infinity-- things
tend to break as you approach infinity
in most programs.
But more on that before long.
Well, let me go ahead and open a
few that I brought with me here.
In fact, on the course's website,
you'll see for every lecture,
whether here or online, all
of the materials that we use
and what I'm doing is running
source code, programming code.
And if I click on Studio here,
I'll actually see all of the code
that I brought with me today.
And I'm going to go ahead and
open up an example now called Pet.
What about a program now that
synthesizes those two ideas
using sound in a loop,
but also using that loop
to do something again and again?
Well, let me go ahead and
see what happens here.
I'm going to go ahead and See Inside.
And you can actually see
the code in question.
And now watch this.
I've clicked the green flag, but
nothing seems to be happening.
What should I do?
And I clearly wrote
this program already.
AUDIENCE: Put the mouse over the cat.
DAVID J. MALAN: Yeah, I should put
the mouse over the cat it seems.
Why?
Because it says forever
ask the following question
if you're touching mouse pointer,
then play the sound meow until done.
So let's try that.
Here we go.
[CAT MEOWING]
Ah, so now it's like--
now it is more interactive.
[CAT MEOWING]
And you're sort of petting
the cat with your cursor.
[CAT MEOWING]
But if you hold it there,
gets a little noise.
[CAT MEOWING]
Let me go ahead and open a
slightly different one, Pet1.
Notice, I'm starting to count
zero, just as I did here,
just because that's a computer science
convention to start counting at 0.
So Pet1 is now my second example.
Let me go ahead and see inside this one.
It's a little more involved.
[CAT MEOWING]
What should I perhaps not do this time?
[CAT MEOWING]
It's a little small.
Let me zoom in.
[CAT MEOWING]
All right, so now logically--
[CAT MEOWING]
--it seems clear that I
shouldn't, for instance do--
[LION ROARING]
--that.
[CAT MEOWING]
So don't pet the cat in
that particular case.
But again, notice, all we're
doing, even though the programs
are getting a little more fancy
and a little more involved,
I'm just composing more
advanced algorithms using all
of these individual building blocks.
We can make a really adorable
cat, for instance, do this.
Let me go ahead and repeat
the following forever.
Let me go ahead and
find the Motion block.
And I'm going to go ahead and point
towards the mouse pointer my, cursor.
And then I'm going to go ahead
and use this one, move 10 steps.
But I'm going to do
it one step at a time.
A step is like dots
on the screen, pixels.
So one step means at one dot
at a time, instead of 10.
Let me play this.
And now we have sort of
a cat that follows me.
But I'm much faster than him.
And so I could, for instance
stop this, have him work faster,
and do 10 times as many things.
And now he'll actually follow
my cursor until he gets there.
And now this is kind
of a bug or my mistake,
right, like he's apparently
going just past my cursor.
So then he's doubling back.
But then he's gone just too far.
So he's doubling back.
So this is a bug.
And it's because I'm
taking 10 steps at a time.
It's kind of jumping over my
cursor, in this case here.
Well, let's go ahead and make
something a little more involved.
Let me go ahead and
open this one, Bounce0.
So I'm going to go ahead and open
this one, just as you can do later.
Bounce0 takes that same idea,
but automates it this time.
So this is kind of interesting, because
it's now responding to its environment.
And if I zoom in there, notice that it's
still the same amount of movement idea,
but it's not following my cursor.
But it is asking the
question, if you're touching
the edge, a Boolean expression,
turn yourself around 180 degrees.
Now we could do something
kind of interesting there.
Notice that in Scratch, and now
this has less academic value,
has this ability to play with sounds.
And if I go in here for instance and
Add Sound, oops, not Search for Sound.
And I go ahead and Record Sound and
allow my microphone to be used again.
Ouch.
OK that's what the word Ouch looks
like apparently in a computer.
And now let me go ahead
and go back to code.
And now if I go to Sound, you'll
see play sound meow until done.
That's fine.
But what I actually want to
do is play sound recording 1.
That was the default
name I just gave it.
So now.
Ouch.
Ouch.
Ouch.
[LAUGHTER]
OK, so we can do even
more than that there.
But you know what this
looks a little silly.
So, you know, the sound aside.
Ouch.
He's not really-- ouch-- walking--
ouch-- right, he's not really walking.
He's just kind of sliding
across the screen.
But you know what?
What is just walking well
walking is really just animation.
And if this is what the cat
looks like by default. What
if I use some graphic artistry and
just kind of give him another look,
another costume as Scratch calls it.
And now I'm in slides.
I'm just going to go back and forth
left and right, first, second, first,
second.
And if I do this, you know, now it
kind of looks like he's walking.
This is like a really bad flip book.
Like you have every page he just
moves like halfway toward his step.
But that's really all animation
is, is tricking our human eyes
into thinking that something's
happening in real time
when really you're just seeing
photographs fly by your eyes.
But I can go ahead and do this.
So in fact if I go into Bounce1, I
did this in advance already here.
And this one's just a
little fancier, such
that now he's really moving, right?
And if you really want to see it, we
can move just five steps at a time.
Actually that's-- oops,
not 51, 1 step at a time.
And he's moving slower, but now it's
changing costume a little too fast.
So it's only once we kind of find
the sweet spot, maybe 50 step, OK,
now a little too fast.
[LAUGHTER]
But this is all animation
is, whether you're doing it
in software or manually
or flip book style,
you just have this ability to
create now the notion of motion.
But there's some other features too.
We've seen variables
as I mentioned before.
But it turns out we can take advantage
of fancier techniques in programming
as well, like in the sea lion here.
So this one's interesting
because this is the first Scratch
program for which I
kind of have to scroll
to see two different
algorithms, both of which
are going to run when the
green flag is clicked.
And we won't get into
the weeds of the code.
All the code is online.
And for the first problem set you'll
be able to take a closer look.
But notice what happens
with this program.
[SEA LION BARKING]
He just barks--
[SEA LION BARKING]
--endlessly in a loop--
[SEA LION BARKING]
--because, notice this, there
is this forever block down here.
[SEA LION BARKING]
This is annoying.
[SEA LION BARKING]
And if you can read the code,
how can I stop him from barking?
[SEA LION BARKING]
AUDIENCE: The space bar.
DAVID J. MALAN: Yeah.
[SEA LION BARKING]
There seems to be the space bar.
[SEA LION BARKING]
If key space is pressed, set a
variable called muted to true.
[SEA LION BARKING]
Rather check if muted is true.
[SEA LION BARKING]
And if so change it to false.
[SEA LION BARKING]
Else set it to true.
[SEA LION BARKING]
So if I hit the space bar, now he stops.
But I haven't stopped the program.
If I hit the space bar again--
[SEA LION BARKING]
--he's still going.
But what I'm doing is I'm
changing a variable called
muted to true or false to 1 or 0.
And then up above in my code,
I'm actually checking here.
If muted is false, then
play the sea lion sound.
So if it's not muted, go
ahead and play the sound.
So it's a way of creating your
own questions that you yourself
can answer ultimately, so that you
can finally have more interactivity.
And speaking of interactivity too, if
you ever played the game Marco Polo
in like a pool as a kid, for instance,
it's this game where one person--
everyone-- one kid like covers his
or her eyes, and then everyone--
they yell out Marco-- and I look
like an idiot right now, don't I--
and then everyone else yells out polo.
And you try to find the other person in
an otherwise dark space or pool space
with your eyes closed.
So if I go ahead and play this now,
notice what if I hit the space bar now,
the orange puppet says Marco and
then the blue puppet says Polo.
Now it's not hard to
implement that in code
with just one single
script, as Scratch calls it.
But notice that each sprite
here can have its own scripts.
This is the orange Muppet script.
This is the blue one's script as well.
So notice that what
the orange guy is doing
is this, if the key space is
pressed, say Marco for two seconds.
But other sprites, other
characters, can't just
look on the screen for what's happening.
They have to be communicated
with more programmatically.
So there's this notion in
computer science called events.
This puppet can broadcast an event,
which is like a secret message
that only computers can hear.
And the blue puppet, notice,
can be listening for that event.
And he can respond,
not when the green flag
is clicked, but to a
different event when he
receives this event from someone else.
So you can have multiple characters on
your screen somehow intercommunicating
in this way, as well.
And lastly, let's go ahead
and take a look at this here.
I'm going to go ahead and open
up an example of coughing,
so kind of a simple example.
And this example of coughing
just has a sprite doing something
like this, cough, cough, cough.
It works.
It's correct, if my goal
was to cough three times.
But it's poorly designed, right, like
even knowing what we know already,
you can kind of imagine
doing this better using what?
AUDIENCE: A loop.
DAVID J. MALAN: Yeah, so using a loop.
So in fact in Cough1, which is a newer
version of this, it's the same idea.
Let me See Inside.
Let me hit Play.
It does the same thing.
But notice that I'm using the
repeat block, so not forever,
because I only want
to cough three times.
Forever would be bad, probably.
But three times seems reasonable.
But I can do it now in a loop.
But notice, that if
you wanted to now use
this notion of coughing in
like another program you write,
it's a little annoying that
you would just kind of copy
paste these puzzle
pieces again and again
and again anywhere in your program when
you want to make a character cough.
But what Scratch provides us with
has actually this capability as well.
At the very bottom of Scratch is
this pink piece for Make Block.
You can make your own functions.
You can make reusable puzzle pieces that
you can then use in different places.
And so, for instance, if I want to
make a puzzle piece that coughs,
so that I don't have to
construct it from scratch
like that-- no pun intended--
notice what I can do here.
I can literally in Scratch--
and this may be something you
use for your own problem set--
define a new pink piece called
cough or whatever you want, attach
some puzzle pieces below it,
like say cough for 1 second,
then wait for 1 second.
And then you can use that puzzle piece
in your own code sort of out of sight,
out of mind.
Now I can program like this.
So a moment ago there was like
five or six puzzle pieces.
Now it's been whittled down to
three by making my own puzzle piece
cough that takes its own input
and produces its own output.
And suffice it to say, you can have
your own functions, your own pink puzzle
pieces that take one input or two inputs
not just zero inputs in this case.
And it's a way of modularizing
your code ultimately and making
it ever more usable.
So that was a lot of
little demonstrations.
But it's worth kind of
bringing this all together.
Ultimately in problem
set 0, the challenge
ahead is going to make
anything of interest
to you, whether it's a game, an
interactive animation, or artistic work
all implemented in Scratch.
And we thought we'd share with you
the project from a former student here
called Ivy's Hardest
Game, not to intimidate.
But we'd need in closing
just one brave volunteer
who would be comfortable playing one of
your predecessor's homework assignments
in front of a few people
and on the internet.
Hi, yeah, OK, right
there in the green is it.
Yeah, come on down.
What's your name?
AUDIENCE: Owen.
DAVID J. MALAN: Owen.
OK, come on down.
All right yes.
Encourage him.
[APPLAUSE]
OK, OK, sorry your name again was?
AUDIENCE: Owen.
DAVID J. MALAN: Owen.
David.
Nice to meet you.
Come on around.
I'm going to go ahead
and full screen the game.
We won't actually look inside.
I'm going to go ahead
and click the green flag.
And you're just going to use the
keyboard ultimately to play this game.
[MUSIC PLAYING - NFL THEME SONG]
OK, you can raise the
volume a little bit, Brian.
[MUSIC PLAYING - NFL THEME SONG]
Oh, yeah.
[MUSIC PLAYING - MC HAMMER, "YOU CAN'T
 TOUCH THIS"]
(SINGING) Can't touch this.
Can't touch this.
AUDIENCE: I move cursor to the right?
DAVID J. MALAN: So you'll notice now.
I'll explain the pedagogy ultimately
of what you're now doing here.
[MUSIC PLAYING - MC HAMMER, "YOU CAN'T
 TOUCH THIS"]
[LAUGHTER]
So what is the Yale symbol?
Now it's wearing a
costume that's not a cat.
It's instead the Y, Yale logo.
There's a second sprite,
MC Hammer at the end.
He's the one who's trying to
touch with the other sprite.
There's now two more crimson
sprites, Harvard logos.
Each of which has its own
puzzle pieces all operating
when the green flag started.
There he goes.
[LAUGHTER]
[MUSIC PLAYING - MC HAMMER, "YOU CAN'T
 TOUCH THIS"]
And notice, Owen is not able
to go past the black walls.
[LAUGHTER]
[MUSIC PLAYING - MC HAMMER, "YOU CAN'T
 TOUCH THIS"]
AUDIENCE: Aah.
[MUSIC PLAYING - MC HAMMER, "YOU CAN'T
 TOUCH THIS"]
DAVID J. MALAN: OK, here comes MIT.
[MUSIC PLAYING - MC HAMMER, "YOU CAN'T
 TOUCH THIS"]
AUDIENCE: Aah.
[MUSIC PLAYING - MC HAMMER, "YOU CAN'T
 TOUCH THIS"]
DAVID J. MALAN: You'll notice the
MIT sprite is a little smarter,
artificial intelligence, if you will.
Nice.
AUDIENCE: Aah.
DAVID J. MALAN: OK,
the walls are now gone,
so there is no if touching
edge, then bounce anymore.
Nice.
[MUSIC PLAYING - MC HAMMER, "YOU CAN'T
 TOUCH THIS"]
[LAUGHTER]
Nice.
Two of them.
Notice they're clearly
pointing toward him.
AUDIENCE: Aah.
[MUSIC PLAYING - MC HAMMER, "YOU CAN'T
 TOUCH THIS"]
DAVID J. MALAN: Nice.
Oh.
AUDIENCE: Aah.
DAVID J. MALAN: Hang in there.
Class might run a minute or two late.
Nice.
Second to last level.
Yes.
All right.
[MUSIC PLAYING - MC HAMMER, "YOU CAN'T
 TOUCH THIS"]
Oh, Dartmouth got you.
[MUSIC PLAYING - MC HAMMER, "YOU CAN'T
 TOUCH THIS"]
Hang in there, a few more lives.
[MUSIC PLAYING - MC HAMMER, "YOU CAN'T
 TOUCH THIS"]
Hang in there.
[MUSIC PLAYING - MC HAMMER, "YOU CAN'T
 TOUCH THIS"] (SINGING) Can't touch
this.
Yes.
Yes.
AUDIENCE: Aah.
DAVID J. MALAN: One more try.
One more try.
[MUSIC PLAYING - MC HAMMER, "YOU CAN'T
 TOUCH THIS"] (SINGING) Break it down.
All right, a big round
of applause for Owen.
[APPLAUSE]
Here you go.
Thank you.
Allow us to conclude in our final
moments with a look now of what else
awaits with the course.
Just as in Cambridge
now, there is a tradition
here in New Haven of a
whole series of events.
The first of which is CS50 Puzzle
Day in just a weekend or so.
The second of which is the CS50
Hackathon, an opportunity with all
of your classmates up at Harvard,
if you'd like, to join us from 7:00
PM to 7:00 AM working
on your final projects.
And ultimately the CS50 Fair,
a campus wide exhibition
here at Yale of all of
your final projects.
So even if you've never
programmed before,
here is what awaits you in
the next weeks of class.
[MUSIC PLAYING - "LIVE IN THE MOMENT"]
(SINGING) My home is a girl
with eyes like wishing wells.
I'm not alone, but I'm still lonely.
Those days are done,
but I'm still glowing.
Ooh, la, la, la, la, la,
let's live in the moment.
Come back Sunday
morning, a lie, oh well.
When you're gone, goodbye,
so long, farewell.
Ooh, la, la, la, la, la,
let's live in the moment.
Come back Sunday morning
with that soul to sell.
When you're gone, goodbye,
so long, farewell.
My home is a girl who can't
wait for time to tell.
God only knows we don't need
history when your family swinging
from the branches of the trees.
God only knows we don't
need ghost stories.
Ooh, la, la, la, la.
All right, that's it.
Christina's 50th cake is now served.
