So it is my greatest pleasure to welcome you all here today
for the first lecture of, well, Introduction
to Computing and Programming.
Also known as CS50 or well, CPSC 100, officially here at Yale.
>> So we couldn't be more excited to welcome you all here.
My name is Patrick Rebeschini.
I'm the head instructor for the class.
I am here representing a group of about 60 staff members
that will work with you throughout the semester.
This number is almost 60 of us.
Yet along the extraordinary level of commitments
that we put into this class, makes CS50 the class
at Yale University that offers the greatest level of support
to all of you.
And we couldn't be more proud of offering this class here again.
>> In fact, as you will soon experience, CS50 is much more than a class.
It's a community.
And you will be part soon of this community.
This is the second year that Yale is offering this class.
We are building on the extreme success of last year, where
for the first time, here at this university,
undergraduate learning assistant were adopted in classrooms.
It all started with this class last year.
>> So as you know, the class is taught jointly with Harvard University.
To teach this course we are relying-- we can
count on the great expertise of David Malan and the Harvard team.
So David has been teaching CS50 for well, 10 years now.
And every year he has been pushing the boundaries
and improving the classroom experience.
Again, we couldn't be more happy to continue this collaboration with them.
>> In fact, one of the most interesting parts,
I will say of running this class now, both at Harvard and here at Yale,
is the really incredible cross-fertilization
of ideas, aimed at improving the learning experience to you all.
So as a result of this extensive collaboration between the two
university, CS50 is proud to announce the new version this year
with noticeable changes.
David will all tell us about them now.
So please-- this being said, please join me
and welcome to give a big round of applause
to welcome David and Harvard team here at Yale.
>> [APPLAUSE]
>> DAVID MALAN: Thank you.
Thanks.
This is CS50, Harvard University's and Yale University's introduction
to the intellectual enterprises of computer science
and the art of programming.
And what that means is that this course ultimately, is about problem solving.
Indeed many of you might have come out of high school
or have spent the past couple of years wondering what some of your friends
did last year or in other classes.
And yet, the reality is, no matter what we
do at the end of the day in this class, it's going to be about problem solving.
>> And as such, perhaps take some reassurance in the fact
that 73% of the students that take this class, both here
at Yale as well as at Harvard, have never taken a CS class before.
So if you're sitting here in the audience today wondering
why you are sitting here in the audience today,
or maybe you just followed along with some friends,
or maybe you've been a little curious as to what
computer science and programming is, realize
that most of your classmates to the left and to the right of you
are very much in that same demographic.
>> And indeed, if we look at last year statistics
within the student body of CS50, both here and at Harvard, 58% of students
describe themselves as less comfortable.
9% is more comfortable.
And then 33% is somewhere in between.
And there's no formal definition of what these buckets means.
You sort of know you're less comfortable if you are.
You're feeling a little uneasy with maybe being in the class.
You're not quite sure if a computer science class is ultimately for you,
and realize that you are in very good company.
And indeed the grading, and the assessment,
and the feedback, and all of that support structure in the class
is ultimately very much individualized.
More so than most any other class by design.
And indeed, what ultimately matters in this class is not
so much where you end up relative to others,
but where you, in week 11 or last, and relative to yourself in week
0 here our first.
So what does that mean?
Well, this means of those 73% of students last year that had never taken
a CS class before, by the start of the semester they
were dabbling in a language called Scratch, which we ourselves
will see here today.
And by the end of the semester had they gone
through this entire list of challenges.
Starting with a language called c.
Implementing, what's at first glance, going
to be a bit of a challenge for some, but fairly gratifying once you
get Super Mario bouncing up and down a pyramid
implemented, albeit, with just something called ASCII art.
Implementing last year-- what the students last year then
did after that was implement their own Caesar cipher and vigenere cipher.
So encryption algorithms with which you could
scramble information and then unscramble information to send secret messages.
The game of 15.
If you remember from childhood or some party favor,
that little plastic game where you move the numbers up, down, left and right
to try to get them in order, actually implementing that game
and solving the logic required there.
And then we dabbled in forensics last year.
>> So by mid-semester, students who had never
used their keyboards for this purpose before,
were writing software to recover, so to speak,
JPEGs or photographs that we had accidentally
deleted from a digital memory card from a camera.
Recovering secret messages from inside of a bitmap image,
and other such types of graphics as well.
>> We then transitioned to giving the whole class a dictionary.
Just a really big text file with 150,000 English words.
And everyone was challenged to somehow read, so to speak,
those words into memory.
Into the computer's memory.
And then answer questions of the form, is this a word?
Is this a word?
Really just implementing a spell checker.
And then challenging each other with a big board--
a leader board to see who could use the least amount of memory,
in the least amount of time to actually spell check large documents.
>> We transitioned from then to implementing ones own web server.
So not making web pages in languages like HTML and CSS, if you're familiar.
But actually implementing the server that
listens on the internet for requests from browsers
and then responding to those requests.
Then implementing our own e-trade like website, where
students could buy and sell stocks.
Drawing in nearly real time stock quotes from Yahoo Finance.
And allowing students to see how their portfolio develops.
And then finally a mash up of Google News and Google
Maps whereby students by term by terms end
had the ability to click, and round, and search on a Google map.
And then see all of the news articles that
are proximal to those particular areas.
So truly going from zero to 60.
>> And along the way having what we had last year called, hacker additions.
That raise the bar further for those of you
who might very well have a good amount of experience being in that 9%
of more comfortable.
So realize that there's a very high ceiling
even within those challenges for students
coming from a different background.
Because at the end of the day, we're ultimately
focused quite simply on this.
>> But what does this mean, problem solving?
So let's propose that we distill it like this.
So problem solving is really just this kind of picture.
So you've got inputs to some problem, something you actually want to solve.
The goal is to get outputs, a solution to that problem.
And then in the middle is what we'll call a black box.
You don't necessarily know or even care what's inside that black box.
All you know is that when you feed input into it,
you hopefully get output or a solution from it.
And while today we'll look both at inputs and outputs,
we'll long term, and over the course of the whole semester,
focus on what's inside that box.
>> And therein will lie something called algorithms.
Step by step instructions for actually solving some problems.
But what's an example of some inputs?
So maybe a simple thing at the start of every school year, someone
might want to take attendance.
So we might do one, two, three, four, five, six,
and how would I keep track of that information.
I might just go one, two, three, four, five, six.
And just use sort of single digits.
>> Or I could actually record this a little longer term.
And how do I represent all the humans in this room?
Well, I might do something like, OK.
I see one person.
All right.
I see another person, a third person, and so forth.
But no one counts people like this.
So literally, most of us if we're even going to draw anything at all,
are probably going to go one, two, three, four,
maybe get a little fancy, five, six, seven, eight, nine, ten and so forth.
>> And that's actually a system called unary.
Uno, like uno implying one, where you just have one letter of the alphabet.
You've just got this hash mark.
And I, for efficiency, just drew these hash marks, ultimately
as straight lines.
But I could have drawn them as little stick figures.
Where to represent one person, one input,
I just draw a stick figure or a hash mark.
But this isn't all that expressive.
>> If all I have is these hash marks, let alone stick figures,
how might I represent something like the number 15?
Or 15 people in the room?
I might have to do something like 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
14, 15.
It just does not scale very well.
As the inputs get large, we need a better system than this.
>> And it turns out that the system that computers use
is not all that different from what you and I know.
In fact, most people in this room, even if you are among those less
comfortable, don't necessarily know how your Mac or PC really works,
you've probably at least heard, that underneath the hood are 0's and 1's.
The so-called binary system.
So indeed, computers have more than just hash marks in their vocabulary,
but not as much of a vocabulary as we humans.
>> Indeed, we humans don't use binary.
Bi meaning 2, 0 and 1.
But decimal, deca meaning 10, 0 through 9.
So we have a lot more expressive capabilities in our normal human world.
But I'd argue that these systems, binary, and decimal, and everything
in between and beyond, are actually all quite familiar.
For instance, consider this example here, 123.
So this really is, of course, a number we know as 123.
But all I just drew was just this pattern of symbols, glyphs so to speak.
Sort of shapes on the board in chalk.
>> But why do we immediately and intuitively grasp this as 123?
Well, if you were like me in grade school,
you probably learned that this is the 1s column, this is the 10s column,
this is the 100s column.
And why is that useful?
Well, it's simple arithmetic you now do to get from a pattern of symbols
to a number we understand intuitively.
Is what, 100 times 1, and then 10 times 2, and 1 times 3,
which of course is just 100, and this is 20, and this is three.
And so if we add those together-- ah.
So therein lies the sort of reasoning behind why this set of symbols
means something real and numeric.
>> Well, computers do the exact same thing, but they only can count as high as one.
Whereas I was able to count as high as three.
And in fact, if I kept going I could go as high as nine in this system.
Computers only have zeros and ones in their alphabet.
>> So what does that mean?
Well, it just means that if a computer wants to represent, say the number 0,
maybe using three characters-- three letters of the alphabet so to speak,
that's how a computer represents 0.
So not all that scary so far.
It's exactly what we humans would do.
And in fact, most of us would just ignore the leading zeros anyway.
>> A computer, if it wants to store the number 1,
turns out is going to do this.
And a computer to store the number 2 is not
going to do the unary system, which I alluded to earlier.
It's actually going to do this.
And this is probably where the pattern starts
to become less obvious for most folks.
That's 2, this is 3.
Curiously, this is now 4.
And now it really does seem to be perhaps cryptic,
but it's not if we consider what binary really means.
It means you have two letters of your alphabet.
So two possible characters for each placeholder.
>> So that really means we're going to need a 1s place, or 2s place,
a 4s place and then 8, and 16, 32, and 64.
And what's the difference there?
Like these are 1, 2, 4, 8, 16, 32, 64.
And before we had 110, 100,000, 10,000.
What's the similarity there?
And what's the pattern?
Yeah.
STUDENT: Powers of 2 instead of powers of 10.
DAVID MALAN: Yeah.
Powers of 2 instead of powers of 10.
And so if I wanted to keep going, 8, 16s and so forth--
but now if you have this sort of clue, now the binary system
is actually pretty straightforward.
Why is this pattern of 0's in the world of computers 0?
Well because it's 4 times 0, 2 times 0, 1 times 0 and you get 0.
>> Why is this the number 1?
Same reasoning, but now we have a 1 in the 1 column.
Why is this 2?
We have a 1 in the 2s column.
And how then do I represent say, the number 7 in binary?
Say louder.
>> STUDENT: Three 1s.
>> DAVID MALAN: Three 1s.
So 1, 1, 1 because we just need 4 plus 2 plus 1 gives me 7.
All right.
So from there how do we represent 8 with 3 placeholders?
Yeah.
>> STUDENT: 1, 0, 0, 0.
>> DAVID MALAN: Yeah 1, 0, 0, 0.
And yet maybe, I kind of technically need
to add another placeholder to the board.
If I want to fit that I indeed need to do something like this.
So I actually need to use now the 8s column, and that's fine.
But the curious thing in computing is that that's going to cost us something.
You need more RAM in your computer now.
You need more memory because you need something
physical to store that additional bit, so to speak.
Binary digits.
And indeed all that's happened here, like the decimal system,
if we keep adding numbers up and up and up, we go to 5 to 6 to 7 to 8
it's like carrying the 1, literally.
And then everything else goes back down to zero.
>> But how do we actually represent these things physically in a computer?
Well, at the end of the day, the only physical input going into my computer
here is this power cord, so electricity or electrons from the wall.
And so how do I get from something physical like that to actually
representing an idea like this instead.
>> Well, what could we do?
We could consider that, all right, maybe if electricity is flowing
I could store it and hold on to it.
And if I'm holding on to some electricity,
that's just going to arbitrarily represent a 1.
And if I pull the plug and there's nothing there,
you know that's just going to arbitrarily represent a 0.
>> So if something's there, 1.
If nothing's there, 0.
Or you can make this a little more visual.
Here is a 0.
There's nothing interesting going on about the back of my phone.
But if I allow a little bit of electricity to flow,
even though it's a little bright in here, my flashlight went on.
So I'm storing a charge and ergo, this phone now represents a 1.
So 0 1.
>> So with 1 iPhone how high can I count using this kind of approach?
I mean to 1.
It's not all that compelling.
So what more could we do?
Well let's see, is anyone on their phone right now that I could borrow?
Anyone who has a phone with a flashlight built in?
May I borrow?
I don't need it unlocked.
All right.
Thank you.
Let me borrow this.
All right.
So if I now scroll up and here, what am I representing now?
Yeah.
So it's a three because this is in the 1s column, this is in the 2s column.
So 1 plus 2 is 3.
And then if we try to get really creative-- oh, thank you.
Very preemptive.
All right.
I now have three iPhones.
All right.
>> And now this-- I won't do any further than this.
What am I representing now?
Just sevens.
But I needed physically more memory in this case.
But that's all it is.
You can think of what's going on-- thank you-- inside of your phone
as just being a switch that's being turned on and off.
>> And if you've ever heard the word transistor.
Or if you've ever heard the marketing speak Intel inside,
that's speaking to the kind of hardware that's inside of your computer.
Intel makes CPUs, central processing units,
which are like the brains inside of your computer.
And these CPUs and things they're connected
to have lots and lots of tiny switches.
Millions, billions of switches that can either be on or off.
>> So computers, thankfully, like our Macs and PCs,
can count way higher than 7 or 8 because they have way more than three
or four bits.
Way more than the equivalent of the three flashlights that we just had.
But now this starts to get pretty uninteresting quickly.
If I now want to actually be able to do something more interesting,
I want to be able to jump to something like this.
>> So ASCII, it's not really a useful acronym, but American Standard Code
for Information Interchange.
It just means, some years ago we humans decided,
you know what, we want to be able to do more with computers than just numbers.
We don't want them to just be expensive calculators,
we'd like to be able to do things like word processing, albeit very simply.
Later we had email and other such media.
>> And so the world decided some years ago according to this system ASCII,
you know what?
In certain types of programs any time you
see the equivalent of the number 65, like the pattern of bits.
And we could do the math here on the board.
The pattern of bits that represent 65.
Don't think of it as 65 in decimal.
Think of it as arbitrarily, but globally, consistently as the capital
A.
And then the world decided, you know what?
Let's take another pattern of bits.
And if we ever see the number 66, let's just
assume that that is the capital B. Fast forward to H
and I, if you see 72 or 73, that should be an H and an I, respectively.
And so as long as the whole world agrees upon this.
So that when you receive an email, or you would get a file on a USB stick,
or something like that-- when you see that pattern of bits,
you know that it should be this letter or some other letter.
>> But it's context specific, right.
An email program might interpret these things as characters,
but a graphing calculator or calculator might represent or interpret
these things, of course, as letters.
>> So with that said, quick little review.
This is maybe a three character e-mail that's been sent to me.
Underneath the hood it's all in 0s and 1s, But we don't care.
We're going to start to abstract above the 0s and 1s to letters.
And if I see a pattern of 0s and 1s that really represent 72, hint, hint, 73,
and then 33, what's the message?
>> STUDENT: [INAUDIBLE]
DAVID MALAN: So if you think back just a moment ago, HI
was the message I was trying to communicate here because H is 72,
I is 73, and now 33-- you wouldn't necessarily know this in advance,
but it turns out if you actually see more of the chart and the system
that humanity agreed upon years ago, it's just an exclamation point.
And indeed, there is a pattern of symbols and numbers for every character
that you might have on your keyboard.
>> All right.
Let's abstract further.
If we don't want to just have things like numbers and letters,
we actually want to implement graphics.
Well, if you've ever heard the acronym RGB.
It's kind of dated now, but it's still kind of there.
RGB is red, green, blue.
And it's just a system of saying, you know what,
let's use three sets of bits.
A set of 8 bits, another set of 8 bits, and another set of 8 bits.
And let's use those bits to store how much red we
want on our screen, how much green we want on our screen,
and how much blue we want on our screen.
And this just means that if you have a lot-- a big number for red,
that means give me a lot of red.
If you have a big number for green, give me a lot of green.
And if you have just a little bit of blue or a small number like 33,
give me a little bit of blue.
And if you happen to combine those three magnitudes, so to speak,
you get this-- you barely can see on the projector here, but this murky
shade of yellow or brown.
>> But this is to say, using that pattern of 8 plus 8 plus plus 8--
that pattern of 24 bits is how a computer would
store that shade of yellow in one tiny dot a pixel on the screen.
So we've gone from 0s and 1s to decimal numbers to letters of the alphabet.
Or more interesting, colored dots.
>> Well, what of course then comes next?
Well, what is an image that you see on Facebook or get in an email?
Or the like?
What is the definition technically of an image?
Yeah.
What is an image composed of if you look really close at your screen?
Yeah.
It's just a whole bunch of pixels.
In fact, if you take your laptop maybe later on,
and look really closely at it-- depending
on how expensive the laptop is and how high quality the screen is,
you might very well see all of the little dots on the screen.
>> And those dots or pixels, which means there's
24 bits representing every pixel in that photograph that you see on Facebook,
or that you just took on your iPhone recently.
And so that's how we get to things like graphics.
Well, what's a video?
A video is just a set of graphics flying by the screen again
and again and again.
And so videos really, are just patterns of bits representing grids, rows
and columns of dots, flying by the screen image,
after image, after image, a.k.a.
Motion pictures.
So that's it for inputs and outputs.
>> All we have now is an assumption that, you
know what, if we want a computer to represent information,
we have a system for doing it.
We can do it with 0s and 1s at the end of the day.
But we can abstract, so to speak, on top of that
so as to represent more interesting things.
And here on out in CS50, and in computer science more generally,
we now stand on the shoulders of all the people who
came before us who figured that out.
And now just assume that computers can represent inputs and outputs.
>> But now let's actually do something with them.
So an algorithm is just a set of instructions, step by step,
for solving some problem.
And what might one such problem be.
So this is an old school technology, a phone book.
And inside of a phone book is a whole bunch of names and numbers.
And those names are generally sorted alphabetically.
>> So if I wanted to find someone in this phone book like Mike Smith,
what's a typical human going to do?
Well, you could simply open it up, look at the first page.
I don't see Mike Smith.
Turn to the second page, I don't see Mike Smith.
And just keep going and going.
Is this step by step approach correct?
Yeah.
It's kind of stupid, right.
It's inefficient, right.
Because it's going to take forever to get to Mike, but it is correct.
Because if Mike is here I will indeed find him.
>> So what's a slightly more reasonable person going to do?
They might still open to the front, and maybe fly through the phone book
two pages at a time.
Two, four, six, eight.
I can't actually physically do it very well.
But in theory, this should be twice as fast, two pages at a time.
Is this algorithm correct?
>> STUDENT: [INAUDIBLE]
DAVID MALAN: Not necessarily.
Good.
Why that caveat?
>> STUDENT: Because he could be on one of the pages that you're skipping.
DAVID MALAN: Yeah.
So even if I get closer and closer.
What if he's just accidentally, by bad luck, sandwiched between the two pages
that I'm flying over?
So we need a fix for this.
We actually need to then say, wait a minute,
maybe if we go too far, maybe if we hit the T section,
for T coming after Smith, then we should at least double back at least one page.
So fixable, but there is a conditional issue there.
So it's twice as fast, but you might have to double back just a little bit.
But no one in his room, even if you don't really use phone books anymore,
is going to start at the beginning.
What are you going to do looking for Mike Smith?
You're going to go roughly to the S's.
Or if you don't really have the cheat sheet on the paper,
you're going to go at least roughly to the middle.
And certainly not to the front of the book.
You're going to look down.
And mathematically you're probably going to see the M section, which
is roughly in the middle.
And then you're going to realize, what is true?
Where is Mike?
>> STUDENT: [INAUDIBLE]
DAVID MALAN: Yeah.
So he's over on this side.
And so what can you do?
Well, both figuratively and literally can you tear the problem in half once?
And then know that you can throw this half of the problem away.
And now we're left with fundamentally the same problem, but it's half as big.
And so now what's the set of instructions?
What's the algorithm for finding Mike Smith?
It's the exact same thing.
>> Now this happens to be the M section and this is the Z section,
but the fundamental formula is still the same.
Go roughly to the middle, look down, oh, darn it.
Now I'm in the T section, I've gone too far.
But here too can you apply that same logic.
Throw half of the problem away and now we're
left with a problem that's a quarter of the size.
And we can repeat, and we can repeat, and we can repeat until theoretically
there's just one page left on which Mike either is or isn't.
>> So what's so powerful about this idea?
I mean after all, it's pretty intuitive.
No one's going to start at the beginning of the phone book
and flip 1,000 pages to find Mike Smith.
Most everyone in this room is going to do roughly that kind of algorithm
save for the tearing.
>> And so why did we do that?
Well, consider the efficiency.
Consider just how much better this algorithm was by breaking it down
into its component parts.
So what did I first do?
I picked up the phone book.
And a computer scientist, and a programmer,
more generally it turns out, is going to start counting everything at 0.
>> Why?
Well, it's a little strange that we humans count, generally,
starting from one.
Because what's the smallest number we can clearly represent based
even on our old grade school math?
Well, it was 0, whether it's in decimal or binary.
And so you'll see in the world of computing and programming,
specifically, we start counting everything from 0.
>> So I picked up the phone book step 0.
I'm going to open to the middle of the phone book.
And that's indeed an expression of what I did.
And then step two was look at the names.
Step three is a little different conceptually.
I'm asking myself a question.
If Smith is among the names, I'm going to make a decision.
If he's among the names, then I'm going to call Mike.
And I'm going to make a decision based on that piece of information.
>> However, if not, if Smith is earlier in the book to the left,
I'm going to open to the middle of the left half of the book.
And then here's the cleverness, I'm going to go back to step two.
I'm going to sort of stand on my own shoulders
and just repeat the past work I did.
But the work I have left is less, and less, and less.
But it's still going to work.
But if Mike, instead, is later in the book to the right,
I'm going to open to the middle of the right half of the book,
then go back to step two.
>> But there's actually a fourth scenario.
Mike's either here, or here, or here, or--
>> STUDENT: Not there.
DAVID MALAN: Not there.
And indeed, if we don't anticipate this fourth and final scenario
our program might be buggy or flawed in some way.
Else, quit in the case that we haven't found Mike at all.
And indeed, if you've ever noticed your computer hanging, or all
of a sudden word or some other program just quits unexpectedly,
and sometimes thee error message is literally that.
This program quit unexpectedly.
It can be for any number of reasons.
But sometimes it's something as simple as this.
The human programmer who wrote that software
didn't realize that, oh, there's a forth thing that can actually happen.
And if you don't write code to capture that fourth scenario,
it is indeed unexpected sometimes what the computer might actually do.
Now let's call out a few of these things.
So in yellow here, I have highlighted terms
that henceforth we're just going to call functions.
Functions in the world of programming are just like actions,
statements of actions.
So pick up, open to, look at, call, open, open, quit.
That's a function, a procedure, an action, any number of synonyms
would work as well.
Now what are these things now in yellow?
If else, if else, if else, these are what
we're going to call conditions in programming,
or branches, decision points, if you will.
But how do you know which fork in the road to take, so to speak?
We need to highlight the terms to the right
there, which are these yes, no questions.
These true false questions.
Smith among names?
Smith earlier in book?
Smith later in book?
These are questions to which there is a yes, or no,
or equivalently true, or false, or equivalently, one or zero answer.
>> And meanwhile there's just one last piece.
This here has what kind of effect?
Whether or not you program before, how would you
describe what step seven and 10 are doing?
What did you say?
STUDENT: A recursive step.
DAVID MALAN: A recursive step.
Yes, essentially.
It's technically iterative here if you're familiar.
But we'll come back to that.
But it's doing something clearly.
Again, it's inducing a cycle, a loop, right.
You're literally going back to some earlier step.
And so indeed, this is going to implement some kind of cycle.
But you're not going to get stuck in this endlessly, right.
Because if you're constantly checking is Mike here, or to the left, or not here,
eventually he's not going to be there.
And you can just quit altogether as per that last line.
>> So that's it for vocabulary.
And this was what we would generally call pseudocode code.
It's not an actual language.
It's just very terse English, but it communicates the point.
There's no formal structure here.
You just use it's few words, but as clear words
as you can to communicate your idea.
>> Now how good is that algorithm and how much better is it?
Well, we don't have to get into the specifics of numbers or anything
like that.
But we can look at the shape of this solution.
So if we just draw some xy plot here on the horizontal axis here.
Let's just call the size of the problem.
And a computer scientist would typically use n as the variable here.
So n pages, or n people in the room, or whatever it is you're trying to count.
>> And then on the vertical axis on the left, that would be the time to solve.
So how many seconds does it take me to find Mike Smith?
Or how many steps does it take?
How many page turns does it take?
So that's how much it costs me in time to solve a problem.
And we might draw the first algorithms slope, if you will,
as just this straight line in red.
And I'll call it n.
>> Why n?
Why is it just this one to one relationship?
Well, if Verizon or whatever phone company
adds one more page to the phone book next year,
that might push Mike one more step closer to the end,
depending on where that page is.
And so the effect might just be to add one more second.
Or one more page turn.
A one to one ratio.
>> By contrast, the second algorithm.
How much faster was that intuitively?
Where I went two pages at a time?
Yeah.
>> STUDENT: [INAUDIBLE]
>> DAVID MALAN: Yeah.
So it's going to be twice as fast.
And we would draw that here depending on the scale.
It still is a straight line, but lower than the red line.
Because for some number of pages, if it takes
you this many steps with the first algorithm,
it's going to take you half as many steps with the second.
And so the yellow line describing the second algorithm
is just going to be below it.
>> But what's really powerful is to think about the third and final,
and amazingly most intuitive algorithm, that has this shape.
Technically we would call this a logarithmic curve.
Log base 2 of n in this case.
But that doesn't really matter.
What matters really is the fundamentally different shape that it has.
And you can consider just how much shorter this line really
is in the long run.
It's constantly increasing.
It doesn't flatten out perfectly.
But it grows ever so much more slowly as the problem gets bigger and bigger.
And you can think of it this way-- if Verizon doesn't just
add one page next year but doubles the number of pages in the phone book,
the first algorithm might take twice as many steps.
If it's 1,000 pages this year, 2,000 pages next year,
Mike might be that much farther away.
So it's 1,000 extra steps to find him.
The second algorithm might be only 500 more
steps to find him because again, I'm flying through it two at a time.
>> But what about the third algorithm?
If Verizon doubles the size of the phone book
next year from 1,000 to 2000 pages, how many more steps
is my third algorithm going to take?
Yeah, it's just one.
And that's the powerful idea.
You can take 1,000 page bite out of that problem at once.
And now if you consider a silly scenario,
but it kind of speaks to the power of this kind of intuition--
if a phone book had, like, four billion pages, feels like a really big problem.
And indeed, it might take me four billion page
turns to find Mike Smith in that case with the first algorithm.
But how many steps would it take in the third algorithm
to find Mike among four billion pieces of paper?
So four billion you tear in half.
You get two billion.
Then one billion, then 500 million, 250 million, 125 million-- but it
feels like this is going to take a while.
I might need 32 fingers to count up that high.
But it is indeed as few as 32 page tears.
You can go from four billion to one page dividing
the original number of pages in half 32 times
until you're left with just that single page.
>> Now, of course, I'm cheating here.
It's not that we are just being sort of stupid entirely with the first two
algorithms.
I am cheating in some sense, or really I'm leveraging an assumption.
What was true about the phone book in its original form that allowed
me to even use that third algorithm?
Yeah?
AUDIENCE: It was alphabetized.
DAVID MALAN: It was alphabetized, right?
If it were just in random order, this is a waste
of time, this whole conversation.
I have to look at every page if it's in random order
to find Mike Smith before I can conclude he's there or not.
And so the corner we have cut is that I have
assumed that someone else in this case did the work for me.
And so that ultimately invites the question, well, wait a minute.
How do you sort 1,000 pages of names and numbers?
That's actually a different problem, something
we'll come back to in the future.
But when you think about websites like Facebook and Google for Gmail
and things like Google's own search indexes,
when you have millions or billions of pieces of data being stored these days,
searching-- and not to mention sorting those problems--
is ultimately a challenge unto itself.
And indeed, this then is just one of those challenges
that we'll be looking at.
>> So now let's take a moment and take a look at CS50
itself and give you a sense of what's in store this semester.
Indeed, if you haven't already, do take a look at this URL.
And as Patrick alluded to, this year we're
making a significant investment all the more in the course's support
structure in terms of the TAs and the CAs, office hours,
sections availability, and digital materials online, as well.
Indeed, in terms of the course's lecture, we're here today.
And the expectations this year officially of the course
are attend to today, the course's last lecture, and a course
roughly in the middle of the semester with every lecture in between
made available generally on a Friday afternoon
online, both for Yale students and Harvard students this year.
Indeed, one of the fundamental changes is
that we're adopting at Harvard a paradigm very much
like we did here last year and now this year,
so that similarly, we still film most of the course's lectures in Cambridge
but make them available earlier than we have in the past
so that those of you-- if you would like to, for instance,
get a head start on materials on the the first weekend rather
than the second weekend, you'll have access to these kinds of materials,
searchable, embeddable, hyperlinkable to related resources all the earlier.
In terms of the topics, to give you a sense of the course's trajectory--
and some of this might be jargon for now, but not for long, rest assured.
We'll start today, ultimately, with looking at one programming
language called Scratch.
We'll transition thereafter next week to something called C
and then looking at other building blocks for solving problems,
things called arrays and algorithms, how we use memory to our advantage
and disadvantage, and things like data structures,
and then toward the tail end of the class looking at machine learning
and looking at another language called Python,
how the web works, how the internet more generally works, protocols like HTTP,
languages for databases like SQL, JavaScript for the web,
and ultimately tying all of those together.
>> And so indeed, at the end of the day, you
will not learn in this class Scratch or C or Python or SQL or JavaScript.
You will instead more generally learn computer science and the foundations
thereof, and you will learn how to program
in any number of these languages along the way.
So indeed, one of the goals of the course in the end
is to take off all of the course's training wheels by those final weeks
so that after this, you can return to your own fields--
whether that is or is not computer science
or engineering, in the natural sciences, arts, humanities, or beyond--
and bring some of this course's ideas and this field's
ideas and practical skills to your own domain
in order to solve problems therein.
>> What we'll be doing here meanwhile in most Thursdays after today
is with the course's heads leading what we'll call walkthroughs
of the course's problem sets.
So each week when we have a problem set, we'll
be walking through in a location like this the course's challenges,
offering you some tips and tricks and design techniques.
But if you're not able to make those in person,
realize those same resources will be embedded
by one of the course's teaching assistants
in the problem sets themselves, as well.
>> The problem sets this year, unlike last year, based on feedback,
will still be released on Fridays.
But rather than being due the subsequent Friday,
thereby giving you only seven days, will effectively be due 10 days later.
And indeed, this will mean that they'll overlap by a weekend.
But we hope this year especially this will
allow students to better accommodate ebb and flow in their schedules,
whether it's academics or extracurriculars or athletics
or midterm season.
You can either front-load or back-load your week focusing on CS50 based
on your own week's actual course load.
>> The problem sets themselves will cover a range of languages,
though we'll focus predominantly early on on C
before we focus thereafter on higher level, more web-centric languages.
And then a couple of FAQs here-- should you take a class like CS50
as a first-year?
So absolutely.
And indeed, it's not necessarily something
you should postpone until you've cut your teeth on other types of classes.
But rather, consider that for many students,
myself included back in the day, this is a very unfamiliar field,
especially if you never did take a AP CSA
or something like that in high school.
But realize that early on, whether it's this course
or some other introductory course, now is indeed the best time,
I think, to find some new path or some new academic interest, as well.
And then taking with other courses-- so one of the key differences here
versus Harvard is that we only take four courses per semester
at Harvard for some reason.
And you guys actually pull off some 36 courses in total
over the course of your four years, which means generally four or five
classes.
And I do think it's quite fair to say and to disclaim CS50, by design, is
probably not the type of class that you should typically
take with four other courses for a total of five
because psets are by design fairly intensive.
Indeed, I too learned this back in the day.
I wouldn't describe CS50 and computer science, programming
as so much hard as it is just time-consuming.
It's not the kind of thing where after dinner, you
can go back to your dorm room, sit down, and start
focusing on the pset thinking, all right,
I'm gonna bang this out tonight and then move
on to my next subject the next day.
Sometimes you just hit a wall.
You have bugs in your code.
You don't necessarily know how to solve some problem.
And one of the key features of programming for myself to this day
is you just kind of need to take a step back sometimes, sleep on it
or think on it over the course of a jog or some other activity,
and then come back to it fresh.
And you just need these windows of time.
>> And indeed, that's why we've lengthened the amount of time
available for the problem sets this year and also, per that URL
I put up earlier as to what's new this semester,
trimmed the problem sets so that they're fundamentally no less rigorous,
and the takeaways are no less, but there's a lot less front matter,
a lot less legwork that you need to do at the front of every problem set,
as you'll see, before you can actually dive into the meat of it.
So realize that those and other changes are on the horizon
to better accommodate students, but ultimately to make sure
that the takeaways are indeed as high as possible.
So while more work than it might be in a typical class,
we do hope that the returns for you and the takeaways for you
and the skills and ideas with which you exit
are all the more compelling as a result.
And to get you there-- and this is one of the key takeaways,
as Patrick alluded earlier-- is the course's support structure.
So not only does CS50 have one of the largest course staffs on campus.
It also has one of the most undergraduate.
Indeed, CS50 last year was the first class
to have an undergraduate teaching staff.
And testament to that success do now many other courses within Yale CS
have that, as well.
And for students, specifically, will these TAs and course assistants
be supporting a whole network of support resources,
among them sections or recitations, weekly opportunities
to have more intimate discussions and reviews of material targeted
for different tracks, for students less comfortable, more comfortable,
or somewhere in between.
These will follow the availability of the lectures by several days each week
on Mondays and Tuesdays.
And then office hours-- one-on-one opportunities
for help from the course CAs and TAs will be on Wednesdays and Thursdays
and Sundays at multiple times, all of which
will be posted on the course's website, even more than last year, as well.
>> But what's key to CS50, if not admittedly a bit unusual,
is the course's culture that we've tried to cultivate,
both in Cambridge for many years and now most recently in New Haven.
And in fact, coming up this Saturday, if you haven't heard,
is CS50 Puzzle Day, which has nothing to do with computer science
but is entirely designed to send a message that computer science is
about problem solving.
And indeed, if you'd like to partner with one or two or three friends
and form a team for CS50 Puzzle Day, take a look
at the adverts that are on the way out.
And three hours of pizza and puzzles and prizes await.
And indeed, for the first time this year,
it won't be held jointly with Harvard.
It will be here independently at Yale.
So keep an eye out for those if you haven't.
Most every Friday in the semester do we try to make a big class
feel small and bring some 50 students to lunch with the course's staff,
with alumni, friends from industry to talk
about what life is like after a class like CS50 and over the summers
and after graduation.
So keep an eye out for invitations to that.
For the first time ever this year will we
hold the first ever CS50 coding contest, an optional opt-in opportunity
mid-semester, after all of us have had some six or seven weeks of programming
in C under their belts to compete, if you would so choose-- again
on teams-- trying to solve as many challenges
as you can in programming with friends of yours against others.
>> And toward the tail of the semester will we charter some buses,
actually spend some time in Cambridge, if you'd
like to join us, for the so-called CS50 hackathon.
At 7 PM we'll begin.
Around 9 PM, we'll have pizza.
Around 1:00 AM, we'll have burritos.
And anyone still awake on the bus ride home around 5:00 AM,
we'll stop off for pancakes at IHOP on the way home--
a 12-hour opportunity to immerse yourself with classmates and staff
in the course's final project, which is an opportunity
to go well beyond the course's problem sets
and design and implement most anything of interest to you,
that will ultimately be featured here in Commons.
The first ever CS50 fair was last year, an end-of-semester exhibition
or celebration of what everyone in the class had accomplished,
especially those, again, who went from nothing to something, from zero to 60,
having no prior background and exhibiting, ultimately,
something for the whole campus and, if online, the world to see, as well.
>> Now, these here are just a few of the TAs and CAs that makes CS50 possible.
Allow me to invite any of those staff members
who are here to come up on stage, as well as the course's heads,
to offer some words of inspiration, as well.
>> ANDI: Hi, guys.
Can you guys hear me?
Thanks for joining us on this lovely, rainy Thursday afternoon.
My name is Andi.
I'm a junior in Berkeley.
And along with Stelios and Summer, we will be your three head teaching
assistants for this upcoming year.
So, I guess, show of hands-- how many of you
have no intention of being a CS major nor really diving deeply
into computer science as a major here?
Awesome.
That's brilliant.
>> So I'm actually a global affairs and cognitive science major.
I literally came to Yale with the intention
of never having to look at a number ever again in my life.
When I came to Yale, this was something that was never on my radar.
I wanted to learn about poetry.
I wanted to learn about international affairs.
I wanted to learn about watercolor drawings.
Yes, we offer a class on watercolor drawings.
>> But I never really was interested in anything STEM related.
But then the older I got, the more I realized
that every field really in some sense employs computer science,
or if not computer science, computation.
In fact, for my global affairs capstone project,
we're using data analytics to analyze terrorist attacks
for Boko Haram in Nigeria.
And so as you can see, regardless of what major you end up pursuing
or what your interests here at Yale are, programming and the foundations
of whatever skills are super useful.
And CS50 really is well equipped to kind of lend a lot of its resources
to you, regardless of how comfortable you are
or how interested you are in pursuing the class.
>> Summer's going to talk a little bit about what you guys are
going to learn about this year.
SUMMER: Hi, everyone.
I'm Summer Wu.
I'm a junior in Morse.
And I actually started out as a CS50 student myself.
So three years ago, I was on a gap year.
I'd never taken a CS class in high school,
but I thought that in my free time, it'd be cool to learn how to code.
So I did a quick Google search, looked for what was available online,
and saw this video with muppets and DJs and cool websites.
I was like, I want to learn how to do that.
>> So I took the course, and I just fell in love with it.
But I remember being so jealous of the kids who could attend the hackathon,
attend Puzzle Day, attend office hours, get help from TAs in person.
And so I never imagined that I'd get the chance
to be here involved in the course that first got
me interested in computer science and is the reason why
I'm a computer science major today.
So I'll warn you, this class is going to stretch you.
It's going to challenge you.
But it's also going to teach you how to do things
that you never imagined you could.
>> STELIOS: Hi, everyone.
My name is Stelios.
I am a junior in Branford College and a CS major.
I'm also from Athens, Greece.
I'm really looking forward to meeting all of you,
chatting with you at section, at office hours, at Friday lunches.
I'm really excited because we've put so much effort
into creating a unique support structure for all of you
to make your experience with the course the best possible.
And I hope that although most of you have probably not taken a CS
course before, I hope that's CS50 for you is what sparks interest
to further pursue computer science in the future,
as it has done with so many people in the past.
So thank you for being here, excited to see you.
Jason Hirschhorn.
JASON HIRSCHHORN: Hi, everybody.
My name is Jason Hirschhorn.
I live in Silliman.
And I went to Harvard as an undergrad and majored in social studies
and minored in computer science.
And one of my principal roles here is to support this wonderful staff
as they support you all.
In fact, this is not all of them.
There are 55 undergraduates and graduates here to support you all.
And I daresay one of the best parts of the course for you
all is getting to work with them, getting to know them,
getting to see them, both in CS50 and outside of CS50 this semester
and for many semesters to come.
So hopefully you'll take the course because hopefully you
get to interact with the wonderful staff we have on stage.
>> SPEAKER: Well, let me finish by saying it will be fun.
DAVID MALAN: Well, thanks to our whole team.
Allow me to dim the lights and allow some more of our team,
both from Cambridge and New Haven, to say hello as these guys file off.
And after that will we transition to the first of our programming engagements
with this language called Scratch.
So thanks to the team.
Let's dim the lights and hear from a few others.
>> [APPLAUSE]
>> [VIDEO PLAYBACK]
>> -The mission of CS50 is to make you more comfortable with a totally new way
of thinking, this computational mindset.
-It made computer science interesting, which
is something I didn't really realize was possible until I took the class.
-I was like, whoa.
I'm really translating my thoughts into a computer right now.
>> -Even if you don't have any background in computer science or any experience,
this is actually the class for you.
>> -So I definitely want my students to just
get excited about computer science.
Not just programming, but thinking like a computer scientist
is really what I want to try to teach my freshman.
>> -CS50 is hard and rewarding.
>> -An experience.
>> -Extravaganza.
>> -It's bringing us to the next level.
>> [MUSIC PLAYING]
>> -The TFs are, I think, the lifeblood of the course.
>> -I'm excited to have my students I'm helping
have that aha moment to realize what they're actually trying
to do, to figure out how to do a pset.
>> -CS50's definitely a hard course.
But unlike any other course really at Yale,
it has such a great, supportive community.
-You absolutely don't need to know anything
about coding to be able to take the course.
-It's amazing to watch how far people come in one semester.
>> -You weren't alone sitting in your room learning to code,
but it was more than just a class.
It was an experience.
-The best way to learn concepts and to process them is by teaching others.
>> -What is the telephone split?
>> [MUSIC PLAYING]
>> -And this is CS50.
>> [MUSIC PLAYING]
>> -This is CS50.
>> -Got a problem?
Tear it in half.
>> [MUSIC PLAYING]
>> Throw it away.
>> DAVID MALAN: All right.
So let's tackle-- in a little bit, incidentally, it's
been this tradition for some reason for 10 years
to serve cake at the start and the end of CS50.
So awaiting you at the end of today, in addition to syllabi,
will be some cake as well, and the course's staff to say hello.
But now, let's transition to the first of our languages, where
we'll spend really just a week and one problem set on this domain, Scratch.
And you'll find if you've programmed before, many
of the ideas and the possibilities are familiar to you.
But you'll find that it's fun along the way
to figure out exactly how to translate some of the ideas you already know
to this particular environment to really impress your family
and friends with your work, which can go online, if you so choose, afterward.
>> And if you have no prior experience and are
among the majority of students less comfortable,
realize that many of the ideas we just explored with reality-- things
like phone books and attendance and so forth-- translate
fairly nicely to a computer, but not if you use,
initially, a language like this.
So this is a program written in a language called C.
And we'll spend quite a bit of time in C, ultimately.
But odds are, this will look a bit cryptic to you at first glance.
In fact, there's a lot of weird syntax, parentheses, angle brackets,
curly braces, quotes, and semicolons.
And indeed, if you dive into programming for the first time
looking at and trying to create stuff like this, honestly, you get so mired
so often in just stupid minutia that has nothing
intellectually interesting about it.
>> But imagine if you could create this same program-- which,
as you might kind of infer, probably prints "Hello, world" somehow or other.
We can distill that same idea into just two puzzle pieces, if you will.
Indeed, Scratch is interesting because it's this graphical language.
You can drag and drop these puzzle pieces that only interlock
if it makes logical sense to do so.
And so in Scratch, we'll soon see, this is
how you would implement that same program, with just two puzzle pieces
that pretty much do what they say.
>> But we'll see in just a moment that some of the building blocks that we alluded
to earlier and a few more are all that ultimately are going to constitute
some of our earliest programs.
We're going to have things like functions-- just
actions that do something, like say hello, world.
We're going to have loops, things that induce cycles
again and again, just like we did a moment ago with searching
for Mike Smith.
Variables, like in algebra, if you have x or y, that can store a number.
Well, in a program, you can actually store more than just numbers.
You can store words and sentences and graphics and other things still.
Boolean expressions, just questions-- yes or no, true or false.
Conditions, making decisions based on those yes/no answers.
>> And then fancier things like array and threads and events
and any number of other features, but all of which
map very nicely to very friendly blocks like this.
This is going to be a function, a purple puzzle piece that just says
what its name is-- in this case, say.
And then often, there's a white box that you
can type in or drag some value into.
And that's what's generally called an argument or a parameter.
It's a way of altering the default behavior of a puzzle
piece or a function so that it does something custom for you like saying,
hello, world or hello, Andy or hello, Jason or some other sentence instead.
>> If you want to say that a lot-- literally forever--
you can take another puzzle piece called forever
and just sandwiched the two together like this.
And that loop, as the picture suggests, means just say hello, world forever,
again and again and again.
Or, if you only want to do it a finite number of times, like 50 times,
there's going to be another puzzle piece for that-- repeat 50 times.
>> Meanwhile, if you want to have a variable
in this language we're about to play with,
you can use a orange block like this.
And this variable I arbitrarily called i for integer.
And I just set it equal to 0.
And so maybe i, in this case-- this variable--
represents someone's score in a game.
You start at zero, and every time you make a goal or something like that,
you get one additional point.
>> You can ask questions in Scratch.
If we drag and drop puzzle pieces in a moment like this,
you can ask questions like, well, is i less than 50?
Maybe you need 50 points to win.
And so this would be the question you'd ask.
Or, more generally, you could say is x less than y,
where there's two variables involved?
Now, this one is a lot bigger at first glance,
but really not all that more complex.
>> This is just a combination of conditions and variables
and Boolean expressions to ask three questions-- is x less than y?
If so, say so.
Say, x is less than y.
Else, if x is greater than y, else x must be equal to y.
And whereas with Mike Smith, there were four scenarios, here
in the world of numbers, x is either less than, greater than, or equal to.
All we have are three forks in the road.
And then there's fancier puzzle pieces like this
for things like arrays, where we're going to be able to store information.
We're going to see blocks that allow us to implement multiple threads,
another feature we'll use, and then also something called events.
But before we get to that point and create even,
ultimately, our own custom puzzle pieces, let's
actually open the program itself.
>> So this is Scratch.
It's available at scratch.mit.edu.
And you're welcome to play now or later, as well.
This happens to be the offline version.
For people who don't necessarily have great internet,
you can download the same software, as well.
And there's really only three components to this software.
On the top left-hand corner of the screen is the sort of stage
that Scratch, who by default looks like a cat, lives inside.
He can move up, down, left, and right and do any number of other things,
and can look any number of ways based on the costumes that you assign to him.
But this is what we'll call a sprite, a sort of character.
And you can have multiple characters, as we'll soon see.
>> In the middle now are all these puzzle pieces and these categories or pallets
thereof.
So right now, I clicked on Motion.
And so I'm seeing all of the motion-related puzzle pieces or blocks,
so functions that have to do with going up,
down, left, or right or some other operation.
But if I clicked on Looks, you could see things like the say block
that we saw just a moment ago.
And if I click on Control, you'll see things like the repeat and the forever
and the if block that we saw a moment ago.
>> And so you'll find that we'll just scratch
the surface of some of the puzzle pieces together,
but it's all fairly intuitive and point and click.
Indeed, Scratch was designed for younger students
to help give them an outlet for creative thinking.
And yet wonderfully, it's a wonderful stepping stone
to exactly the ideas we're going to explore in C and Python and JavaScript,
as well.
>> On the right-hand side, finally, here is this, the so-called scripts area.
And this is just the blank slate with which you begin to write a program.
And I'll exactly that.
Now, I happen to know where things are because I've done this a few times.
But I know that under the Events category,
there's this block here-- when green flag clicked.
And notice if I zoom out and back in over here on the stage,
Scratch lives within this little rectangular world,
atop which is a green flag and a red stop sign.
So go and stop, respectively.
>> And so what do I want to do when that green flag is clicked?
Well, let me go to that Looks category.
And let me go ahead and drag and drop this.
And notice as soon as it gets close, they're sort of magnetic.
So if I now let go, it snaps together nice and cleanly.
And I'm going to go ahead and say something like hello, world
for two seconds.
Let me zoom out and click now the green flag, and say, hello, world.
All right.
So that's all fine and good.
Not all that exciting.
Let's make it a little cuter.
And I know that in advance, Scratch happens
to come with some cute things like this.
So play sound meow until done.
So let's do this.
>> [MEOW]
>> Aw, that's adorable.
And if I click it again--
>> [MEOW]
>> And again.
>> [MEOW]
>> But I keep having to reanimate Scratch.
But I can do better than this.
Why don't I just drag three of these.
And now it's three times as adorable.
>> [MEOWING]
>> OK, actually, it's a little creepy.
So we need something in between there.
If I go to Control, it looks like there's actually a wait block.
And so notice if I hover over there-- and let me make this a little bigger.
If I hover, it's going to snap into place.
So wait one second, wait one second.
Let's hit green flag again.
>> [MEOWING]
>> OK, a little more natural, but not very efficient.
So this is correct if my program's goal was meow three times.
But it's not very well-designed.
I kind of cut some corners.
I got a little lazy.
What feels like-- what do I seem to have done poorly, would you say?
Yeah?
Yeah, in the middle.
AUDIENCE: Used more memory than you needed to
because you're using so many different line.
DAVID MALAN: Yeah, so more lines.
And it wouldn't necessarily be memory, though it could be seen as that way.
But it's definitely-- there's redundancy.
And I literally kind of dragged and dropped the same things.
And if you kind of extrapolate-- if it's not obvious here-- well, how would
I meow 30 times?
I would drag and drop, like, 30 more pairs of puzzle pieces.
And surely, there's a better way.
And we've seen a better way.
What intuitively would be the better way?
Yeah, just use a loop.
No copy and paste.
And indeed, anytime this semester if you start
finding yourself dragging and dropping, or really copying and pasting,
dangerous habit to get into because this is just not very maintainable.
For instance, if I want to change the sound to something else,
I have to change it now in three locations instead of just one.
Because indeed, if I break this away-- I'm
just going to decouple it like that.
Let me grab a repeat block, and then click three, type three,
throw some of these away by just letting go.
And then notice it doesn't look like it fits,
but magnetically, it's going to not only snap in place
but grow to fit the shape.
So that's good.
And now if I click play.
>> [MEOWING]
Very nice.
All right.
And now it's very easy to change, too, because I can just
change one number in one place.
But this, too, is not all that interesting.
Let's actually have Scratch not meow, but move.
Let me go to Motion and move 10 steps inside of-- whoops, let me fix this.
Let me have it move 10 steps-- actually, let's not do repeat.
Let me grab a control block, and do the following forever.
Forever, move 10 steps.
And click Play.
>> OK.
So thankfully, he stops.
Otherwise, kids would get very upset when they sort of lose their cat.
But at least I can drag him back into the screen.
But this is not all that great of a game or animation.
It would be nice if maybe he bounced off the edge.
So what do we do?
What construct do we need to have Scratch decide to bounce, do you think,
even if you've never seen Scratch before?
Yeah, in back.
AUDIENCE: You need an if block or if-then.
DAVID MALAN: Yeah, so some kind of if block or if-then.
So actually, we have one of these here.
So if-- so let me get rid of the movement.
Let me zoom in so it's bigger.
So how about this.
Forever, if Sensing-- we've not seen this before.
I need a Boolean expression.
And it turns out if touching what?
If touching the edge, what do I want to do?
Well, if I go back to Motion, turns out, oh, I can turn around.
Let me drag this in here.
Why don't I go ahead and turn around 180 degrees?
>> And now, let me just move at the end.
I could put the movement at the beginning or the end.
But logically, every time I move, I want to check, am I touching the edge?
Am I touching the edge?
So that logically I turn around if so.
So let's hit play.
>> OK.
So it's slightly buggy, so to speak.
And a bug is just a mistake in a computer program.
But at least it's working.
And in fact, I can go in here.
And let me make it not 10 steps at a time, but this is all animation is.
This is all a cartoon or even a movie is.
Let me move 20 steps at a time.
So 20 times as many things are happening once, or twice as many, in this case.
And he's moving faster.
Let me change to 30.
100.
1,000.
And it's going really fast.
And this is-- yeah, OK.
>> So now we're just messing with it.
OK, so buggy.
But we can drag him out of the way here.
But we can make more fun with this, too.
How about this-- he's upside down.
But it turns out Scratch-- and there is actually,
I have to disclaim, no academic value to what I'm about to do.
But if I open up the microphone, let's stop him and do something like this.
Ouch!
>> [LAUGH]
>> That was adorable.
Thank you.
Now, this is what my voice looks like when I yell ouch.
I don't think we caught your laughter.
That's OK.
Let me save this as "ouch."
Let's save this as "ouch".
And now we'll go back to Scripts.
And now I need-- let's see, Sound.
Oh, play sound ouch.
So if I'm touching the edge, let me first play ouch, and then turn around.
And now let's put him in the middle.
>> [SAYING "OUCH"]
>> Twice as fast.
>> OK.
But it's literally doing what I'm saying.
So it is in fact correct, it's just a little annoying quickly.
So let's add something more interesting to this.
Let me actually open up one that I made in advance,
aptly called Pet the Cat, that does this.
Here's the script up here.
What is this going to do in English terms?
What's this designed to do?
Yeah, let's go some-- yeah?
>> AUDIENCE: When you pet the cat, it meows.
DAVID MALAN: Yeah, so when you pet the cat, it's going to meow.
So in other words, there's now a forever loop still, combined
with a condition, combined with a Boolean expression,
combined with a couple of functions, the effect
of which, once I play this program, is nothing
happens until I move the cursor closer and closer and closer and--
>> [MEOW]
Then it's like petting the cat.
[MEOW]
Only once you actually move the cursor over him.
Now, I also whipped up don't pet the cat, which does this instead.
>> [MEOWING]
>> So he's just constantly meowing.
>> [MEOWING]
>> But if I get too close--
>> [MEOWING]
>> [ROAR]
>> So how does this work?
Now I just have a two-way fork in the road.
If touching mouse pointer, then play the lion sound.
Else just play the meow sound, and then wait three seconds so
that it's kind of doing it very tranquilly.
All right.
So that's combining some more ideas still.
Let's take a look at this example I whipped up called threads.
And this one is fundamentally different in that it leverages
a feature of many programming language called
threads, the ability of a program to literally do two things simultaneously.
Indeed, these days if you're using Google Docs or Microsoft Word,
and your document's constantly being spell-checked even as you type-- or you
hit Command-P or Control-P and print something,
it's printing while you continue typing.
Programs today can indeed do multiple things at once, just like in Scratch
here.
>> So here, I have two sprites now, a bird and a cat.
And if I click on each of those characters one at a time,
I see right now the bird's scripts at top right.
Now I see the cat's.
Bird's, cat's.
So each of them have their own script.
But notice, what puzzle piece do they both begin with?
When green flag clicked.
And bird, when green flag clicked.
So when I click the green flag, both of those scripts or programs
are going to run in parallel.
And you'll notice that the bird is just mindlessly bouncing off the edge.
The cat clearly has been programmed with a strategic advantage.
And--
>> [ROAR]
All right.
So the cat caught the bird in this case.
Why is that?
Well, notice first we just have the bird just mindlessly going
to this initial location, and then forever,
if not touching the cat, just move.
And if you're on the edge, bounce.
And just move.
And if you're on the edge, bounce.
But the cat, meanwhile, has some additional logic
that says this-- first, just so that this isn't completely biased
against the bird, notice that I've used a green puzzle piece there
that actually picks a random number.
A feature of many languages is to give you random or pseudorandom numbers.
So in this case, the cat initially chooses a random number between, like,
90 degrees and 180 degrees, essentially, so
that there's a little bit of variance.
And then forever, if touching the bird, play the lion sound.
Otherwise, just point toward the bird.
Point toward the bird.
Point toward the bird, which is a puzzle piece unto itself in this case.
Well, we can do one other thing here.
Let me open up the events program here.
And here we again have two sprites, which look like these two puppets here.
And what's interesting here is this.
The orange guy has this set of puzzle pieces here.
Forever do the following-- if the space bar is pressed,
then say, Marco, and then broadcast an event.
And meanwhile, the blue guy here has this-- when you receive the event,
say Polo.
So it turns out in Scratch and in other languages,
there are ways for two programs or two scripts, in this case,
to intercommunicate so that when I hit the space bar, he says Marco.
And the other one hears that, so to speak, and says Polo in response.
So you can write programs that actually interact in this way.
And if I do this one instead, I can even add variables,
just using one sprite in this case.
This one's especially annoying.
>> [SEAL BARKING]
>> Now, notice on the right we've got some additional logic over here.
How do I stop this seal from barking?
>> [SEAL BARKING]
>> It looks like on the right-hand side is what's playing the sound.
But it's only playing a sound if what is true?
If a variable-- orange block-- muted is zero.
How do I change muted to be 1, meaning true, make this muted?
Apparently, the other script, I can hit the space bar, and now he stops.
So we can have this intercommunication across scripts, as well,
by just sharing a variable across the two like this.
Now, this isn't all that interesting.
Let's go ahead and do this and combine a lot of these ideas with this program
here.
Before we do that, though, how about one volunteer?
Let me take the pressure off of me because I don't actually
play this game.
Let's have someone we haven't seen before.
You have to be comfortable coming up on stage here, on camera.
OK, come on up.
Very brave.
What's your name?
>> IDRIS: Idris.
DAVID MALAN: Sorry?
IDRIS: Idris.
DAVID MALAN: Idris, nice to meet you.
Come on up.
And now, on your own mobile phone, do you play Pokemon GO?
>> IDRIS: No.
DAVID MALAN: Really?
IDRIS: Yeah.
DAVID MALAN: OK.
All right.
Well, nice to meet you.
Come on over.
I don't either.
So we'll figure out together how to play this, which someone actually
went and implemented in Scratch by changing the cat to essentially
different characters all together.
And if I fullscreen this here, we're going
to see the following game together.
Still loading, still loading.
Come on.
Let me do this.
Come on.
This game is so big that it crashed.
Stand by.
Try this once more.
Come on.
All right.
>> There we go.
OK.
Green flag.
So here we go.
>> [MUSIC PLAYING]
>> Choose the middle level here.
Click the blue guy there.
All right.
And you can use the arrow keys-- up, down, left, right.
Now, let's consider as we do this-- and then go after the character there.
Yep.
And now click him with the mouse.
Oh, yeah.
Move.
Where's the arrow?
Here you go.
So click on there.
Yeah.
All right.
So now, I'm told you have a Poke ball, that if click it, it will do that.
Very good.
In practicing for today, I found this version of the game's
actually not very hard.
So if you want to go again here, walk down to this Poke ball.
And then go take a right.
Try clicking on it.
Oh, actually, that's the store, apparently.
OK so close that.
Never done that before.
Maybe go up to this thing up here.
Oh, there you go.
Wait, there's one over there.
Oh, there's another.
OK.
Down.
Yeah, click.
>> OK, that's very cute.
OK, very well done.
This game is not very hard.
OK.
Congratulations.
Here, we have a CS50 stress ball for you.
But consider for just a moment what some of the takeaways are there.
Easier than the real game, apparently.
But all we have going on here is a character
that probably has some kind of loop associated with it.
It's not a cat.
It's this character instead.
And that loop is just constantly saying, if up arrow pressed,
if down arrow pressed, if left arrow pressed or right
arrow pressed, move up or down or left or right.
Or if there's another puzzle piece there that says when touching another sprite,
when touching one of the characters to the Poke ball, if touching,
then do this.
>> So all of the ideas we've been using thus far really
can just be applied in this particular context to play this game, as well.
Let me go ahead and pull up one other here, in fact.
Let me go ahead and pull up, let's say, this.
This is something we remixed.
Made by one of our students in Cambridge,
and then I went through and changed pretty much every instance of Harvard
to Yale this time.
Would someone like to compete against the Ivies
here in another accumulation of all of these ideas?
Come on down, yes.
What's your name?
>> DINA: Dina.
>> DAVID MALAN: Adina?
>> DINA: Dina.
>> DAVID MALAN: Dina, come on down.
All right, Dina.
So this game gets harder and harder, because in this game,
there's variables being used as well that are constantly keeping track
of what level you are in the game.
So nice to meet you.
Come around here.
And so the goal here is to sort of make your way through a maze
that this student implemented.
>> And just to set the stage, each of these pictures on the screen
is its own sprite, its own character.
So these were by default cats, but the student changed them
to the various Ivies logos here.
And then you'll see that just by using conditions and loops
and functions and more, you get this.
>> [MUSIC PLAYING]
[MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
>> Yeah, OK.
Yeah, keep going.
First level's very easy.
You've just got to go over there.
But again, consider, this is just a loop listening for the arrow keys--
up, down, left, right.
And now a sensing block.
Very nice.
>> [MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
>> Very nice.
>> [MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
>> Very nice.
Pretty easy, Crimson.
All right.
Levels-- uh-oh.
>> [MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
>> And again, in these three Harvard crests,
you just have logic saying if on edge, bounce.
>> [MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
>> OK, what you're doing is more interesting than why.
Very nice.
Uh-oh.
>> [MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
I think you have to sacrifice yourself.
[MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
Quick!
>> [MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
Nice.
That's OK.
You'll get it.
Yes, yes!
Very nice.
>> [CHEERING]
>> [MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
>> Nice!
>> [MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
Got it.
Come on!
Second to last level.
>> [MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
>> All right.
>> [MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
Yes.
Good use of variables here.
[MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
Yes.
[MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
Nice.
[MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
It's OK.
We got to get to the end.
There.
Oh!
>> [MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
>> Might run late today, but it's gonna be worth it.
>> [MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
>> You can do it!
Yeah!
>> [CHEERING]
>> [MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
>> This one's really hard.
>> [MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
>> We'll give you two more lives.
Can you do it?
>> [MUSIC - MC HAMMER, "U CAN'T TOUCH THIS"]
>> All right.
How about a big round of applause nonetheless.
You got to the second to last level.
Thank you.
>> [APPLAUSE]
>> So this is only to say how much you can do with these kinds of things.
And realize, too, that when puzzle pieces don't exist--
and indeed, this is going to be one of the powers with the first problem
sets and beyond-- is to actually create your own.
And this is just a snippet of one of the examples
you'll be able to play with online, where
if you don't have built into Scratch something like a cough puzzle piece,
you can actually make it yourself.
>> And so all of this and more awaits.
And just to paint a final picture of indeed what's
ahead in store for the class for you, based on some pictures from classmates
past, allow me to dim the lights one last time and show you CS50.
>> [MUSIC PLAYING]
>> All right.
That's it for CS50.
Cake is now served.
>> [MUSIC PLAYING]