[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.
[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.
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.