CS50 Lecture 0: Computational Thinking, Binary, and Problem Solving

[MUSIC PLAYING] [AUDIENCE EXCLAIMING]

[APPLAUSE] SPOT: Hello, world.

This is CS50, Harvard University's introduction to the intellectual enterprises of computer science and the art of programming.

Woof, woof. [LAUGHTER]

I'm sorry, Dave. [PINK, "WHAT ABOUT US"] What about us?

What about us? La-da-da-da-da-da-da. La-da-da-da-da-da-da.

We are searchlights. We can see in the dark.

We are rockets pointed up at the stars. We are billions of beautiful hearts.

And you sold us down the river too far.

What about us? What about all the times you said you had the answers? What about us?

What about all the broken happy ever-afters? What about us? What about all the plans that ended in disaster?

What about love? What about trust? What about us?

La-da-da-da-da-da-da. La-da-da-da-da-da-da.

La-da-da-da-da-da-da. La-da-da-da-da-da-da.

DAVID J. MALAN: All right. So--

[APPLAUSE, CHEERING] This is CS50, Harvard University's introduction

to the intellectual enterprises of computer science and the art of programming. And this is Spot.

And our thanks to our friends at 3D Cowboys for bringing him by class today. Perhaps a round of applause for our special Professor [INAUDIBLE]..

[APPLAUSE] My name is David Malan. And I actually took this class, CS50, myself, some years ago.

But I almost didn't. And I didn't because when I got to campus, as a first-year, I really gravitated toward things already familiar, things

with which I was already comfortable, specifically, government. And I came in here thinking I was going to major or concentrate in government. And it was only once I got to sophomore year, fall semester,

that some friends of mine were coming to this class called CS50 that was very much to beware at the time, in that it was an unfamiliar field to so many of us, myself included.

But I got up the nerve to go over the threshold, sit in on the first class, just shop it, so to speak. And I was hooked.

I found that homework was, for the first time, fun. And this was after having enrolled only because the professor let me enroll pass/fail or [INAUDIBLE] because I didn't really

think I could even cut it. But fast forward to five Mondays later in the semester, I actually switched to a letter grade, deciding,

wow, this is actually something for me. And I say this because computer science, what I didn't realize about it at the time, really

is this very general purpose way of thinking and way of solving problems. And even if this is the only CS class you ever take, even if this is the only formal training you have in programming

as a practical skill, it's just so darn applicable to so many other fields-- the arts, humanities, social sciences, natural sciences, and beyond, and certainly within the STEM fields,

themselves. That said, it's going to often feel a little something like this. This is from our friends at MIT, down the road, which is one of their hacks

whereby they connected a fire hydrant to a drinking fountain, with a little sign up there that says, "GETTING AN EDUCATION FROM MIT IS LIKE DRINKING FROM A FIRE HOSE," which is to say that it's

going to feel, quite often, in this class, too, that there's just a lot of information. And you can't possibly absorb it all, but realize

that's to be expected, especially in an introductory class. The whole point is for so much of it to feel new, but with practice, with time, with years, even, looking back, will you get all the more

comfortable with the material. But you're not meant to feel comfortable along the way. And so let me encourage you, invite you, expect

you to get comfortable feeling uncomfortable along the way, whether you have or have not prior computer science or programming experience.

Now, back in my day, the class' syllabus was a little bit different. And, really, when I and all of my classmates exited the class, we would say to friends that we learned how

to program in C, which is a language that we, ourselves, will still learn in this class. But that was it for languages.

But nowadays, as you'll see, we'll explore not just this older language called C, but a more modern language called Python that's very much in vogue for data science, and web applications,

and much more. But we'll also introduce you, along the way, to another language called S-Q-L or SQL, which is specifically for databases.

And SQL is a different type of programming language that's just going to give you different ways of solving problems, different building blocks with which to express problems you want to solve.

We'll introduce you, toward the end of the semester, yet another language, JavaScript, often used with markup languages called HTML and CSS, with which maybe you

have some experience if you've made websites. But we'll do this because so many of today's actual real-world software is web-based.

Or it's phone-based, mobile-based, but even then, it's using these same languages, like JavaScript. And so by the end of CS50, in particular,

you won't know how to program in X, or Y, or Z, per se. But, period, you'll learn how to program. And, indeed, among the goals of this class

is to equip you with enough of a set of concepts, enough practical skills and experience that after CS50, again, if you never take another CS class, you can teach yourself new languages.

And you won't feel-- you won't have been reliant on a class to, indeed, introduce you to each and one of those ideas.

And what are we going to do, then, in this class? And, really, what are we going to start doing today? Well, we're going to learn how to solve problems.

And that's really what computer science is all about. We'll, very specifically, today, knock off a few to-dos. We'll learn how to represent simple things, like numbers.

We'll learn how to represent letters of an alphabet, like English. We'll learn how to represent colors-- red, green, blue, and everything in between.

We'll learn how to represent, more interestingly, full-fledged images that you might see on the web or your phone. We'll talk about representing videos and even audio files.

So, by the end of today, alone, you will exit here with a newfound mental model for how you can represent all of today's media and multimedia that we take for granted

and use most every day. But we'll also focus today, ultimately, on how to write algorithms, like step-by-step instructions for solving

some problem, specifically, implementing algorithms with code. And that's what we'll find. An algorithm is just something you can express

in English or any human language, but code is a translation of that to, presumably, the 0's and 1's that you've probably heard is all that computers ultimately speak.

And if you're feeling like that's a lot for today, if you're feeling like that's a lot for the whole semester, realize and take comfort in knowing that -thirds of you

have never taken a CS course before. So even if you think, like I did all those years ago, that, surely, my friends, the kids I didn't even in the class,

must know more than I, have been programming since they were six years old. That's just not the case.

You're in very much good company. And within the class will you find different tracks, by way of the homework assignments, called "problem sets,"

by way of the sections or recitations. There will be different tracks for those of you less comfortable, more comfortable, somewhere in between.

And if you really don't know why you are here today, we'll even have sections for those least comfortable, where you just don't necessarily feel ready to dive into CS or maybe STEM, more generally.

But we'll get you there by way of the course's support structure. And it's very much grounded in this mindset. What ultimately matters in this class is not so much

where you end up relative to your classmates, but where you end up relative to yourself, when you began. So whether you have or have not prior programming or CSS experience,

it's not going to matter when it comes to evaluation, when it comes to the output, be it a grade, or a satisfactory mark, or the like. It's going to depend on, really, where you are today,

in this, what we call week zero, versus the very end of the semester, when you will have built something grand, of your very own, in software. But CS50 is also characterized, fairly uniquely,

by its community, its culture. And along the way, you'll see that your experience is punctuated by a lot of social and academic events alike.

CS50 lunches, most every Friday, we'll gather at a nearby restaurant called Changsho where we'll have Chinese lunch together. And as many of you as might want to attend

that week will be able to join us, sit down, and chat casually with me, the course's teaching staff, friends of ours, alumni from industry, as well. CS50 Puzzle Day, coming up this weekend, will be an opportunity,

even if you have no prior CS experience, just to solve problems, not jigsaw puzzles, but puzzles in the logical sense. We'll hand you a packet of puzzles--

logic problems, or riddles, or the like-- that you, as teams, can solve together. And at the very end, we'll walk you through.

And along the way, there'll be not only these puzzles, but pizza, and prizes, and so much more, as well. Towards the end of the semester, we'll have a CS50 Hackathon whereby

we'll get together around 7:00 PM, at the start of reading period, and we'll finish up around 7:00 AM the next morning. And it will be this opportunity to really bond

with your classmates, your project partners, if you work in a team, on your very own final project, which is meant to be a capstone of the course, something you build, yourselves,

that we don't hand you a specification for. But it's your final offboarding, so that when you exit CS50, you don't need CS50 anymore.

You don't need me. You don't need your TF. You can actually write code and solve problems on your own.

So this picture here is one of our past photos from earlier in the evening. Things get a little quieter as we then, around 5:00 AM, drive anyone who's still awake and energetic to a nearby IHOP

for pancakes, around then. But here is how most of the evenings tend to end for at least some of your classmates prior.

But at the very end of the class is the so-called CS50 Fair, an exhibition of all of your final projects for friends, faculty, students, and staff across campus, whereby

you'll be invited to a space like this. Bring your laptop. Bring your phone, whatever it is you have built and created.

And we'll just show it off for a bit of the afternoon, complete with music, and friends from industry, and candy, and all what makes gathering together at term's end fond.

And you'll wear, ultimately, very proudly, we hope, your very own "I took CS50," stating, very matter of factly, what I did some years ago; that, indeed, this was a course I, myself, took.

So, today, let's focus, then, on computer science, like what is it. Well, it's really the study of information. But, really, it's, more specifically, about solving problems,

using certain ideas and techniques, all of which you'll exit the course with. So, as such, problem solving is a goal that we'll approach by way of something called "computational thinking."

So computational thinking, you can oversimplistically think about it as thinking like a computer. But it's really the application of ideas that we'll dive into today

and we'll finish some weeks from now, that you can apply to problems from this field or most any other, but in a computational, that is, a very methodical, very careful way.

And that's what CS really did for me and does for a lot of people. It helps clean up your thought processes. Even if you go off into the real world and do nothing in tech,

you have an ability, after classes like this, to express yourself a little more correctly, more precisely and, generally, having better command

of your own ideas and your language. So what's problem solving? Let me propose that this is it.

This is as simple as we can make today's goals and the semester's goals. Problems to be solved look like this. You've got some input, the problem to be solved.

You've got a goal being the output, like the solution there, too. And then somewhere in the middle is the secret sauce, where we'll spend the next several weeks figuring out how

we can convert these inputs to outputs. But before we can do that, we all just have to agree on how to represent these inputs and outputs,

whether it's with English or, really, any type of language. But, as I spoiled earlier, you probably came in here already with a general sense that, yeah, computers somehow

only speak or know 0's and 1's, the so-called binary system. But that's just one way of representing information. Even simpler than binary is unary.

So if you've ever, at this age or any prior age, counted on your fingers, this is unary notation, whereby each of your digits, your fingers literally represent some piece of information;

taking attendance, like 1, 2, 3, 4, 5. But on your one human hand, how high can you count in this unary notation? AUDIENCE: Five.

AUDIENCE: Five. DAVID J. MALAN: Five, I'm hearing five. Six, I heard one six.

But I'm going to go further and say the answer, if you're clever about it, is actually-- AUDIENCE: 40?

DAVID J. MALAN: Not quite 40. You overbid, but-- AUDIENCE: 31.

DAVID J. MALAN: 31 is as high as I can actually count. And that's because if I actually-- and if you're thinking this is weirdly painful now, it will be, but this

is my hand representing the number 0. Normally, in unary, this is 1, 2, 3, 4, 5, of course, obviously. But what if I take into account the order in which I'm

putting my fingers up and down? So maybe this is still 0. Maybe this is still 1.

But maybe this is now 2, where it's just the single second finger up, not two of them, total. Maybe this is now 3.

Maybe this is now-- often offensive, with just the middle finger up. This is now [LAUGHS] 5. This is now 6.

This is now 7. And my hand just hurts too much if I try to count higher than seven. But, theoretically, because each of my fingers can be down or up

and I've got five of them, that's actually 32 possible permutations, up and down. But wait a minute.

We said, 31, but if you start at 0. You have to subtract 1 from the biggest possible value. So this is to say you and I have been using unary because it's just simple,

and it gets the job done. But if we just think about representation a little more cleverly, we can do exactly what computers do, using not what mathematicians call

"base-1," where the finger is either there or it's not, but base-2. And in base-2, we just need two digits at our disposal. And we could call these digits 1 and 2, A and B, black or white.

We just need two words to describe two pieces of information. Computers keep it simple. And just like we humans start counting 0, 1, 2, 3 on up,

computers use 0 and 1, and that's it. But that's by convention. But why do they do that?

Well, it turns out, when you use base-2, otherwise known as binary, well, it just maps really readily to the real world. Because, at the end of the day, what do we all

do, if you've got a laptop, or a phone, or any device? You plug it into the wall because it needs electricity at some point. And what if you have electricity or not?

Well, there's your two possible values. Either it's there, or it's not. And because computers are electrical devices,

this is why binary is just useful. It's nice and simple. Either electricity is there, or it's not.

So when you plug this device in and you've got all these electrons or whatever flowing, maybe if we just hang on to some of that electricity,

we can represent what we'll call a 1. And maybe if we let it dissipate or go away, that's a 0. So on and off maps very readily to this idea of just 0's and 1's.

And if you've ever thought of this, now, as binary digits-- "bi" implying 2, 0 and 1-- well, if you've ever heard this term now, "bit," it just means binary digit.

A single bit is just a 0 or 1. But we could have called these things anything we want. Now how does this map to be clear to the real world?

Well, we can't see the tiny little switches inside of our Macs, PCs, and our phones that are actually turning the electricity on or off, storing electricity or not.

But they're called transistors. They've got millions of them in today's hardware. And they're just on or off, like a switch or a light bulb.

So, for instance, if there's no electricity, the switch is off, we would call this, by convention, a 0. If, though, you throw the switch and it actually turns on, we would call this--

AUDIENCE: On. DAVID J. MALAN: --an "on," exactly, a 1. We could have reversed it.

But this is just the way the world decided to standardize. And that's it. So you've either got something on or off, a 1 or a 0.

And this, then, is this thing we know now as a binary digit or a bit. So once we've got these values, what about how-- how can we go about, perhaps, representing things?

Well, you know what? It turns out we've got a lot of light bulbs right here. Let me grab-- thanks.

Excuse me, spot. Let me grab the little music stand here. Let me borrow a couple of these bulbs and see

if we can't make clearer than my hand, alone, what's going on here. So I'm going to go ahead and grab two of these. And I'll just put them here.

And I can turn these things on or off now. So if I've got two bits, two switches, two transistors, if you will, well, if I go ahead and turn on this one, I'm representing what number in binary,

perhaps? AUDIENCE: 1. DAVID J. MALAN: So just 1.

Now, if I'm using unary, I would turn this one on and be done with it. And that's 2, but not in binary. Binary, it's the permutations, which ones are on and off, that matters.

So what, now, am I representing here, perhaps? AUDIENCE: 2. DAVID J. MALAN: 2.

So this is when I put my single pointer finger up. But then when I did this, in my human hand, this was like representing the number 3.

How do I represent the number 4. Yeah, I need another light bulb, so I need more hardware, so to speak. So if I turn--

if I leave this one-- if I turn this one on, this one off, this one off, now I have the number 4. And someone tell me, saying the words "on"

and "on" and "on," or "on," or "off," or "on," using combinations of "on," "off" and-- "on" and "off," how do I represent 5, from your left to your right?

How about over here? AUDIENCE: On, off, on. DAVID J. MALAN: "On, off, on," I heard.

And that's exactly right. And how do I represent, maybe, 6? Over here?

AUDIENCE: Off, on, on. DAVID J. MALAN: Off, on, on, not quite. From left to right?

AUDIENCE: Off-- the other way. DAVID J. MALAN: The-- [LAUGHS] OK, so from right to left.

So I think we leave this one on. This one, I'm going to claim, represents, now, 6 and 7. AUDIENCE: On, off.

DAVID J. MALAN: I'm just going to-- it's actually going to be "on, on, on." Now, if you're wondering, where are these people coming up with these combinations, there's actually a system here.

It's actually hard for me to do it backwards. But it turns out there's actually a system that's not all that unfamiliar. In fact, let me propose this.

Let me propose that we consider what you and I all learned in grade school, which was something like the base-10 system, 10 meaning that you use 10 different digits, not two, 10.

So 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, that's the base-10 system, otherwise known as decimal, "dec" implying 10. So that's what you and I use every day.

Well, let's think about how we represent numbers in decimal, in the normal human way. Well, here is a number.

It's what number, of course? AUDIENCE: 123. DAVID J. MALAN: 123.

So we all just have an intuition for that, obviously. But it's not necessarily 123. You're just assigning meaning to the positions of these digits.

This is really the pattern 1-2-3. But you immediately jump, mathematically, to 123, but why? Well, odds are, in grade school, you learned that the rightmost digit is

the ones place or the ones column. This is the tens place or the tens column. This is the hundreds place.

And so why is this relevant? Well, this is like doing 100 times 1 plus 10 times 2 plus 1 times 3 or, if we multiply that out, 100 plus 20 plus 3,

ergo, the number, now, that we just take for granted is 123. But that's in base-10, the so-called decimal system, whereby each of these digits is in a different column.

And those columns are, again, ones place, tens, hundreds. If we keep going, thousand, ten thousand, and so forth. But where did these come from?

Well, here's the base. If you remember exponents and all of that, this is just 10 to the 0, 10 to the 1, 10 to the 2, ad infinitum.

And so, now, what if we just changed the base from 10, 0 through 9, to just two digits, 0 and 1? Well, now the math is fundamentally the same.

But it's 2 to the 0, 2 to the 1, 2 to the 2, which gives us the ones place, twos place, and fours place. Now, why is this relevant?

If you've got three light bulbs or three bits that are off, off, off, what have I done? 4 times 0 plus 2 times 0 plus 1 times 0 is, obviously, the number

you and I know, in decimal, as 0. This, though, represents the number you and I know as-- AUDIENCE: 1

DAVID J. MALAN: This represents-- AUDIENCE: 2. DAVID J. MALAN: --3, 4.

And just to be clear, this is why, when I grabbed the additional light bulb, we claimed that this now was 4. Because we had "on, off, off," "on, off, off."

This now is 5. This now is 6. This now is 7.

And if I wanted to count higher, what would the pattern of 0's and 1's be for the number 8? AUDIENCE: 1, 0--

DAVID J. MALAN: 1, 0, 0, 0. So we just need more hardware, more bits. So it wasn't arbitrary, even if it was non-obvious,

what I was actually doing with turning these light bulbs on and off. Now, it turns out here we are talking about how to represent information, like numbers, but we could also use bits, 0's and 1's, light bulbs

to represent instructions, as well. Because, at the end of the day, that's all computers do. They process data, information of some sort, whether it's files,

or numbers, or images, or videos, or the like. And you do things with those files. You open them.

You print them. You edit them and the like. So there's this notion of instructions, what the computer can actually do.

And I bet we could come up with some pattern of 0's and 1's or, equivalently, light bulbs that tell even Spot what to do. Maybe, go up, or down, or left, or right.

And it could certainly do this autonomously by using various sensors. We need to keep things safe today. We're using Wi-Fi in sending Spot these very instructions.

But what's happening, wirelessly, with our friend Andrew, here, is, essentially, he's sending Spot instructions just encoded, wirelessly, somehow, as patterns of 0's and 1's.

And the folks at Boston Dynamics, who built this robot, programmed Spot to recognize certain patterns as meaning "up," a certain pattern as meaning "down," "left," "right,"

and any number of other things. So, in fact, Spot, come on over here, if you could. Come on, Spot.

[FOOTSTEPS] OK. So Spot, for instance, may very well have a pattern

of 0's and 1's that represents shake. Shake, Spot. So he could do that and any number of other movements, as well.

And maybe, especially with sensors here and also a little human help over here, for today, what if we went ahead and did something-- maybe ask Spot some questions?

So let's go ahead, and we'll start simple. Spot, here we have some bits, "off, off, on." Spot, what [LAUGHS]-- OK.

Spot, what is this representing, "off, off, on"? [SPOT TAPS STAGE] Correct?

I think so. Very horse-like, OK. Thank you.

All right, so a round of applause for Spot here. [APPLAUSE] All right.

So, Spot, what if we [LAUGHS] turn-- OK. We'll turn that one off here.

How about if we turn this one on? So it's "off, on, off." Spot, what's this number?

[SPOT TAPPING STAGE] Is that correct? Nice.

OK. [APPLAUSE] [LAUGHS] How about one final flourish?

How about, Spot, instead of "off, on, off," let's go ahead and do "off, on, on"? So think, in your mind's eye, what the answer should be.

All right, Spot, "off, on, on." [SPOT LANDING ON THE STAGE]

OK. And a round of applause for, Spot, as well. [LAUGHS]

[APPLAUSE] So this is to say, no matter how-- thank you, Spot.

No matter how fancy today's hardware or software is, it really just boils down to representing information and instructions.

And computers, and phones, and the like really are just operating on those same pieces of information, whether implemented in 0's and 1's or with, really, anything else.

All right. So, where can we take this, once we have this agreed-upon system for representing [LAUGHS] information?

Well, it turns out that using three bits, three 0's and 1's, at a time, isn't actually all that useful. And you and I, even in conversation, don't often say the word "bit."

We say the word "byte." And what is a byte, if familiar? Yeah?

AUDIENCE: It's eight bits. DAVID J. MALAN: So it's just eight bits. It's just a more useful unit of measure.

And it happens to be a power of 2, 2 to the third, which just makes math work out cleanly. But it's just a convention, to have more interesting units of measure

than individual bits. So a byte is eight bits. So, for instance, this represents, using eight bits, eight light bulbs,

the number you and I know is 0. And this byte of all 1 bits-- now you've got to do some quick math-- represents what number, instead?

So it's all 1's; eight of them, total. How about over here, on the end? AUDIENCE: 255.

DAVID J. MALAN: So it's, indeed, 255. Now, that's not the kind of math that you need to do in your head for a class like this, but you could.

This is the ones place, twos, fours, eight, 16, 32, 64, 128. And because they're all 1, you just have to add up all of those columns' values. And you get 255.

But a little mental trick, too, is that, if you've got eight bits and each of them can be two possible values, 0 or 1, that's like 2 possibilities here times 2 times 2 times 2 times 2, eight times.

So that's 2 to the eighth, so that is maybe a little easier to do. That's 256. Or easier, in the sense that you get used to seeing these numbers in CS.

That's 256. But wait a minute. How do I reconcile this with your 255?

Because you start at 0. So you lose one on the high end because we started counting and representing the number, like 0.

All right. Questions on how we've represented just numbers or, for instance, instructions to Spot, thus far?

Any questions on binary, unary, or the like? No? All right, so seeing none, let's let things escalate a bit.

So how do you represent letters because, obviously, this makes our devices more useful, whether it's in English or any other human language.

How could we go about representing the letter A, for instance? If, at the end of the day, all our computers, all our phones have access to is electricity; or, equivalently,

switches; or, metaphorically, tiny little light bulbs inside of them that can be on and off-- that's it. There's no more building blocks to give you.

How could we represent something like the letter A? Yeah, how about here? Yeah?

AUDIENCE: You could assign a number. DAVID J. MALAN: Perfect. So we could just assign every letter a number.

And we could do this super simply. Maybe 0 is A, and 1 is B. Or maybe 1 is A, and 2 is B. It doesn't really matter, so long as we all agree and we all

use the same types of computers, in some sense, ultimately. Well, for various reasons, the humans that designed this system, they went with the number 65.

So, nowadays, anytime your computer is showing you the capital letter A on the screen, underneath the hood, so to speak, it's actually storing a pattern of 0's and 1's that represents the number 65.

And it tends to use seven bits or, typically, eight bits, total, even if it doesn't need all of those bits in total. So how do we get there?

Well, here, for instance, is that same pattern. Here is that pattern of bits that represents 65. And why?

Well, quick check here. This is the ones place, twos, fours, eights, 16, 32, 64's place. OK, so 64 plus 1 gives me 65.

So that is to say here's how a computer, using some light switches, so to speak, would represent the number 65. And our Macs, our PCs, our phones just all know this.

So whenever they see that in their memory, so to speak, they show a capital letter A on the screen. So that's it.

That's the system known as ASCII, the American Standard Code for Information Interchange. And the A is actually operative there because we're only talking, thus far,

about English letters in our alphabet. And, in fact, I claimed, a moment ago, that we only use seven, maybe eight bits to represent letters of an alphabet.

So, just to come back to you, if I may, how many possible letters of the alphabet could-- how many possible letters of any alphabet could we represent with eight bits?

AUDIENCE: 256. DAVID J. MALAN: 256, the numbers 0 through 255. Now, that's more than enough for English because we've

got A through Z, uppercase, lowercase, a bunch of numbers, a bunch of punctuation symbols. But in a lot of languages, with accented characters, a lot of Asian characters,

this is not nearly enough memory or bits with which to represent all of those possible values. So we need to do a little better than ASCII,

but we can build on top of what they did years ago. So here is a chart of ASCII codes. It's just a bunch of columns showing us the mapping between letters

and numbers. So, for instance, up here is the capital letter A, 65; capital B, 66; capital C, 67; dot, dot, dot.

72 is H. 73 is I and so forth. There's some weird things over here, like special symbols, that we'll learn about over time.

But there's a mapping between every English letter of the alphabet and some number, just as you'd propose, both for uppercase and lowercase.

So, for instance, if we highlight just a few of these for now and I say that I've just received a text message or an email that, underneath the hood, so to speak, if I have the ability

to look at what switches are on and off, I received this message here. Well, first-- and this is not what CS is about, but just fun fact. Does anyone know what number this would represent in decimal,

if this is the binary pattern, like ones place, twos place? AUDIENCE: 72? DAVID J. MALAN: 72 is correct.

And again, not, intellectually, all that interesting and this is not the kind of math that we spend all day as CS-- a computer scientist doing.

But it's just following the same darn pattern, which is to say it might look cryptic, but, conceptually, intellectually, it ultimately is exactly as we did before.

So, yes, I'll spoil the rest of the math. It's 72, 73, 33. Now, anyone remember, in your mind's eye, what message we just spelled?

AUDIENCE: Hi. AUDIENCE: Hi. DAVID J. MALAN: Yeah, so it is, in fact, "Hi!"

Though, no one really said that excitedly. What's the 33, if you noticed? AUDIENCE: Exclamation point.

DAVID J. MALAN: OK, so a lot of people noticed. Yes, it's an exclamation point. And that's, indeed, noticeable right here.

33 is the exclamation point. And that's just something, eventually, that might sink in. But, for the most part, if you remember capital A is 65,

you can figure out at least 25 other answers to these kinds of questions because they're all contiguous like that. So there's the exclamation point.

But at the end of the day, we might just have this mapping known as ASCII. And it's how our phones, and computers, and devices, more generally, actually store information.

So we thought we'd make-- maybe take a little pressure off of me here. And could we maybe flip things around?

How about we try applying this newfound knowledge-- if it's, indeed, new to you-- with seven volunteers, seven bits, if we could? OK.

I saw your hand first. Come on down. Maybe your hand, there.

OK, three, come on down over here. How about four and five? Yep, come on down.

Yep, in the black shirt, yep. How about let me go farther back? How about in the green, over there?

And how about you, seven, over here? All right. Come on down.

[CHATTER] Come on down. So a round of applause for our brave volunteers.

[APPLAUSE] All right. So if you'd like to stand, roughly, side by side, here in the middle

of the stage. First of all, thank you.

Let's see. 1, 2, 3, 4, 5, 6, 7, perfect. OK.

And let's go all the way over to this place, here. If you would like to introduce yourself to the class. RACHEL RICHEY: I'm Rachel Richey.

DAVID J. MALAN: OK. And what year? Anything about you?

RACHEL RICHEY: Oh, first year, concentrating in CS. DAVID J. MALAN: OK. Welcome to the stage.

Next. SPEAKER: Hi. I'm [? Kang. ?] Also a first-year concentrating in CS.

SPEAKER: Hello. My name is [? Lam. ?] I'm a [INAUDIBLE] student from education department. DAVID J. MALAN: Nice.

OK. Next. JORDAN MITTLER: Hi.

I'm Jordan Mittler, concentrating in economics and maybe some CS. SPEAKER: So, hi. I'm [? Natalia. ?] First year, and I want to do CS.

SPEAKER: Hi. I'm [? Khadija. ?] I'm a first-year, and I want to do CS. DAVID J. MALAN: [LAUGHS].

SPEAKER: Hello. I'm [? Caleb. ?] And, once again, first year, concentrating in CS. DAVID J. MALAN: OK.

Wonderful. A pattern, yes. Thank you.

Thank you. [APPLAUSE] So, if you haven't guessed already, each of these volunteers

is going to represent a bit, from left to right, or right to left, in this case. So let's see.

If you want to represent-- how about the twos place? How about the fours place, the eighths place, 16ths place, 32's, 64, and 128? Although, wait a-- I think I screwed up.

We needed one-- eighth volunteer. I think you know-- well, I think-- [CLEARS THROAT] Spot?

OK. Come on over. If you guys could step forward a little bit, and then scooch this way,

just to give Spot some room. [FOOTSTEPS] So Spot will represent the ones place.

Now, what our volunteers have on the back of their sheets of paper are little instructions. We're going to spell out a three-letter word in English by using three bytes,

from left to right, because now we have eight volunteers. I'm going to propose that you raise your hand, if you're supposed to represent a 1.

Or you just stand there, without raising your hand, if you're meant to represent a 0. And what we'll have the audience do is do the quick math

to figure out-- one, two, three-- each letter, what number is it. What letter is it? And we'll see what word that we have finally spelled.

All right. So, in round one-- you have instructions on your back of your sheet that will tell you to--

what your number is. If you're 0, stand there. If you're a 1, raise your hand.

[PAPER RUSTLING] What number do these guys seem to be representing?

AUDIENCE: 68. DAVID J. MALAN: 66, I think. 64 plus 2, so 66, which is the letter--

AUDIENCE: B. DAVID J. MALAN: OK, so, B. OK, so, B. All right. Hands down.

Second letter is going to be spelled how? [SPOT LANDS ON THE STAGE]

AUDIENCE: Whoa. AUDIENCE: Whoa. AUDIENCE: Whoa.

DAVID J. MALAN: [LAUGHS] All right. What are we spelling now? [INDISTINCT CHATTER]

I think-- psst, yep, OK. Yeah, I think you're one. [LAUGHTER]

OK. Now what number are we spelling? AUDIENCE: 79

DAVID J. MALAN: 79, I heard, which is the letter? AUDIENCE: O. DAVID J. MALAN: O. OK.

So hands down. Thank you, Spot. One final flourish.

So we've spelled B-O-- third letter, go ahead.

[SPOT LANDS ON THE STAGE] What number, now, is this? AUDIENCE: 87.

AUDIENCE: 87. DAVID J. MALAN: I heard it here, 80-- AUDIENCE: Seven.

DAVID J. MALAN: --seven, which is? AUDIENCE: W. DAVID J. MALAN: W, which, of course, spells "bow."

So if our volunteers could take a bow, Spot included. [APPLAUSE]

So this will make more sense in week one, when we have an assignment involving a certain someone from the Nintendo World.

But we have a lovely parting gift for each of you. SPEAKER: Thank you. [LAUGHS]

DAVID J. MALAN: Thank you for volunteering. SPEAKER: Thanks. DAVID J. MALAN: You might need to share it with the folks next to you.

[CHATTER] Oop, here we go.

There we go. Thank you-- SPEAKER: Thank you.

RACHEL RICHEY: Thank you. DAVID J. MALAN: --so much. One more round of applause, if we could, for our volunteers.

Thank you. [APPLAUSE] Did you lose something?

OK. All right. So, [LAUGHS] Spot's had it.

So let's see, then, if we've solved, now, the problem of representing English letters of the alphabet, being able to spell out words like "bow," B-O-W. What if we actually do

have accented characters? What if we do have other glyphs that we want to represent? Well, here, of course, is a standard US English keyboard, which a lot of you

might have. But there's also characters that you can type much more easily if you have a foreign keyboard, relative to the US,

or with certain keystrokes on your own Mac, PC, and phone. But, nowadays, too, there's this menu that, probably, you've used in the past hour or two to actually send some emoji.

An emoji, even though they look like pictures and they actually are pictures on the screen, they're, technically, just characters, characters of an emoji alphabet

that happened to use a certain pattern of 0's and 1's to represent each of these faces, each of these people, and places, and things. And it turns out that one of the reasons that we have just

so many [LAUGHS] such characters nowadays is because we now use Unicode instead of ASCII. So Unicode is a superset, so to speak, of ASCII,

which is to say that we, humans, realized, some time ago, that just using eight bits to represent letters of the alphabet certainly isn't very good when we want to represent

other, non-English languages. So Unicode doesn't just use eight bits. It sometimes uses 16 bits per character, sometimes 24 bits per character,

and sometimes even 32 bits per character. Now, why those numbers? That's just one byte, two bytes, three bytes, or four bytes.

And that gives us-- does anyone know? That gives us the ability to represent as many as 4

billion possible characters. Because if the longest one is 32 bits, that's 2 to the 32, which, if you do out the math, trust me, is roughly 4 billion.

So that's a lot of characters. And we've got a lot of room, then, for these emoji. But it's not just about having fun, pictorially, on the screen.

Unicode's mission really is to represent and to preserve all human languages digitally, both past, present, and future. So it is really about capturing the entirety of human knowledge,

as we've expressed it in language, but also giving this newfound ability that's been used centuries ago, too-- in writings, on walls, and the like-- pictograms via which

we can still communicate, even independently of our own human language. So we'll reduce it, today, to just patterns of 0's and 1's, but

the problem being solved is much greater and well-beyond CS, itself, there. So here is a pattern of 0's and 1's using Unicode, so more than eight bits, that represents a very popular emoji, which

might be a bit of a hint. This is the most popular emoji, as of last year, at least, statistically, internationally.

[INTERPOSING VOICES] DAVID J. MALAN: Does this help? It's, roughly, this number here.

No? It's this one here. So this is the most popular emoji, by most measures, as of last year.

But it doesn't always look like this. Those of you who have a Mac or an iPhone recognize this symbol, perhaps, immediately.

Those of you with Android devices or other platforms might notice that it's the same idea, but it's a little bit different. And this is because, too, emojis, at the end of the day,

just represent character, but those characters can be drawn, can be painted in different ways. And reasonable people will interpret differently

this emoji, whose official name is "face with tears of joy." And, indeed, Google interprets it a little differently from Apple, versus Microsoft, versus Meta, versus other companies, as well.

So you can almost think of those different companies as having different fonts for emoji. And that really starts to connect things to the world of text and characters.

So, just so you've seen it. More on this, another time. It turns out that emoji and, really, characters, in general,

we don't use binary 0's and 1's to represent them because no one, myself included, is going to recognize what's what. It's just too much math.

It's not interesting. And even decimal numbers-- that was 4 billion or some-- I don't remember which number is which.

So we represent things a little more compactly. And this, too, admittedly, still looks cryptic, but this is a Unicode code point that uses another system, mathematically,

called base-16 or hexadecimal. More on that, another time. But it's just a way of representing numbers even more succinctly,

writing less on the screen, because you're using not just 0 through 9, as in decimal. But you're using A through F, as well, so a few letters

of the English alphabet come into play. But, for now, that's just a little easier to remember, too, for people who care, that that is the number that

represents "face with tears of joy." But what if we want a customized emoji? And this, increasingly, is the case.

Here, for instance, are the five skin tones that phones, and laptops, and desktops, nowadays, support. It's based on something called the "Fitzpatrick scale," which essentially

categorizes human skin tone into six or, in this case, five different categories, from lighter to darker. But this suggests that, wow, if we want to represent people

with five different skin tones, like this, that could significantly increase how many unique patterns of 0's and 1's we need for every possible face.

But if we think about it from an engineering perspective, we can actually just think of skin tone as modifying some default color, for better or for worse.

And yellow is the de facto default, Simpson style. But to modify it to look more genuinely human-like, from lighter to darker, well, maybe we just use the same pattern of bits

to represent a human thumb, for instance, thumbs up or thumbs down. And we just, then, modify that character to be displayed with a different skin tone.

So, for instance, here, then, is the "thumbs up" that you might use on various platforms. And let me just stipulate that this is the Unicode code point.

That is the number that Macs, PCs, and phones use underneath the hood to represent the default yellow "thumbs up." But if you want to give it a medium skin tone,

you still use that same number, that same pattern of 0's and 1's, or switches, underneath the hood. But you use a few more switches that the computer or phone

will interpret as, "Oh, you don't want to see the default in yellow because of this second number that's in the computer's memory somewhere. You want me to adjust it to be the medium skin tone or any

of the other values, instead." So that's the engineering solution to this problem of just trying to represent different ranges of emoji here.

Well, what about something like this? There's a lot more combinatorics, nowadays, on your keyboard for relationships, for instance.

So here is a "couple with heart" here. So the couple, here, of course, is represented with, apparently, this number here.

But that's it. But if you want to be more specific-- like man and woman, or man-man, woman-woman-- it's the same idea,

but we just need to express ourselves a little-- with a little more information. So, for instance, the way the Unicode folks came up with,

years ago, to represent, for instance, a woman with a heart and a man, from left to right, would be using these values. So things just escalated quickly, but only

in the sense that we're using more bits, more 0's and 1's, to represent, more expressively, this particular combination. So this happens to be the number in Unicode

that represents the woman at left. This is the number that represents the man at right. And this is the pair of numbers that represents

the heart in the middle, sometimes red, sometimes pink, displayed here as pink. But if we want to change the combination, for instance, to be, say, woman--

if we want to change the combination to be woman-woman, notice that, now, the left and the rightmost numbers match. Or if we flip it back to man-man, it's just using different numbers

on the tail end again. And meanwhile, if I rewind, there's these two identical values here. These are called zero-width joiners or ZWNJ characters.

It just is a special number that humans reserve to say, glue the emoji at the left to the emoji on the right and so forth. So it connects ideas in this way.

So there's actually a lot of emojis, nowadays, that are a combination of different things. "Heart on fire" is one that's, technically,

the combination of a heart emoji, the fire emoji, joined together, numerically, in this way. So computer scientists who come up with these things

are just reducing things to representations. All we have at our disposal are 0's and 1's. So we all just need to agree, ultimately--

whether we're Google, Microsoft, or the like-- how we're going to standardize these kinds of things as information. Questions, then, on how characters are represented in a computer,

be it English or any other language? Yeah. AUDIENCE: How is the plus a number?

DAVID J. MALAN: How is the what? AUDIENCE: The plus, the U+. DAVID J. MALAN: Oh, the U+ is just a convention, really.

So U+ represents a special Unicode character, which is a U with a plus in the middle. And this is just the convention for saying,

hey, everyone, here comes a number that represents a Unicode code point. The U and the 1 have no-- sorry. The U and the plus have no mathematical significance.

It's just a visual clue to folks. Other questions on representing text in this way? All right.

So what about colors? We've already started looking at pictures. Well, how are those pictures, be it emojis or anything else, represented?

One of the most common ways is just with RGB-- red, green, and blue. It turns out that if we just keep track of how much red should

be on the screen, and how much green, and how much blue, combined together, that gives us every color of the rainbow, from white to black and everything in between.

So how do we represent an amount of red, and green, and blue? Well, frankly, just with three different numbers. And this is how computers typically represent colors.

Every one of the dots on your computer screen or your phone screen is called a pixel. And every single dot underneath the hood has three numbers associated with it,

so three numbers, three numbers, three numbers for every little dot. And those three numbers, together, say how much red, green, and blue should the device display at that location.

So, for instance, if you had a dot on your screen that said, "use this much red, this much green this much blue," because each of these numbers, I'll tell you, are one byte or eight bits,

which means the total possible values is 0 to 255-- let me just ballpark that the 72, it feels like a medium amount of red because it's in between 0 and 255.

73 is a medium amount of green, and 33 of blue is just a little bit. So if you combine a medium amount of red, green, and a little bit of blue, anyone want to guess what color of the rainbow this is?

AUDIENCE: Brown. DAVID J. MALAN: Sorry? AUDIENCE: Brown.

DAVID J. MALAN: Brown? So, close. It's a little more yellow than it is brown.

But if we combine them, it looks a little something like this. This is just CS trivia, not something that even I would be able to eyeball, unless I came up with that particular example.

But wait a minute. We've seen these numbers before. 72, 73, 33 represented what--

AUDIENCE: Hi! DAVID J. MALAN: --a few minutes ago? So it meant "Hi!" but here I am, claiming, no, no, no, no,

that means yellow. How do you reconcile this? Well, at the end of the day, this is all we have,

0's and 1's, whether you think of them as numbers, or letters, or even colors now. But it depends on the context.

So if you've received a text message or an email, odds are the pattern of 0's and 1's that the computer is showing you are going to be interpreted as text because that's

the whole point of a text message or an email. If, though, you opened up MacOS's or iOS's or Windows's or Android's calculator app, the same pattern of 0's and 1's might

be interpreted as numbers for some addition, or subtraction, or whatever. If you open the same pattern of 0's and 1's in Photoshop, like a graphics program, they're going to be interpreted, in that context,

as colors. So context matters. And, indeed, as soon as next week, when you

start writing code in that language called C, the onus will be on you, the programmer, to tell the computer, interpret the following sequence of bits as a number, or a letter, or something else.

And you won't have to even worry about what the 0's and 1's are, but you need to give the computer a hint as to what type of file or piece of data you're representing.

So that gives us bits. And you can actually see these dots, these pixels on the screen. Let me zoom in, zoom in.

And here we have it, just with this emoji, which, at the end of the day, is a picture that someone at Apple, in this case, drew. And you can see-- if you really zoom in, or take your phone or TV

and really put it close to your face, you'll see all of these dots, depending on the hardware. And each of these dots, these squares, is

storing 24 bits or three bytes, 24 bits, 24 bits, 24 bits. And that's whey, dot, dot, dot, if you've got a photograph, for instance, that's three megabytes, which

is 3 million bytes, well, odds are there's 1 million pixels therein because you're using three bytes per pixel to represent each of those colors.

That's a bit of an oversimplification, but that's why images and photos are getting bigger and bigger nowadays. Because we're throwing even more pixels into the file.

Music-- [MUSIC PLAYING] --how could you represent music, digitally,

using just 0's and 1's, or numbers, really? Any instinct, whether a musician or not? Yeah.

AUDIENCE: The notes could be represented by a number. DAVID J. MALAN: Yeah, so we can just represent notes by a number. So A is some number, and B. And maybe sharp or flat is some other number.

But note might not be quite enough for some-- yeah? AUDIENCE: [INAUDIBLE].

DAVID J. MALAN: Ah, OK. So one note-- one number to represent the note, itself, the sound or the pitch; one other number to represent the duration.

In the context of piano, how long is the human holding the key down? And maybe I can think of a third, the loudness. How hard has the person played that note?

So, minimally, with three numbers, you could imagine representing music, as well. And, indeed, that's very well might be what computers

are doing when you listen to sound. What about video? How could you represent videos, as well?

Yeah? AUDIENCE: Through many images. DAVID J. MALAN: Yeah, many images.

So if you've ever produced a film or looked at some of the fine print, 30 frames per second, FPS, or 29 frames per second is just how many pictures are flying across the screen.

But that's really all a video file is on a computer, lots of pictures moving so quickly in front of us that you and I, our brains, interpolate that as being actual motion.

And, in fact, from yesteryear, motion pictures, it's like pictures that are giving the illusion of motion, even though there's only 30 or so of them flying across the screen.

So we have a way, now, to represent information, both as input and output, whether it's numbers, letters, images, anything else. Let's now focus on what's inside of that black box,

so to speak, wherein we have algorithms, step-by-step instructions for solving some problem. Now, what do I mean by "algorithms" or "step-by-step instructions"?

Well, maybe, if we were to turn this into code-- and that's how we'll connect the dots, ultimately, today. Code is just the implementation, in computers, of algorithms.

An algorithm can be something we do in the physical world. Code is how we implement that exact same idea, in the context of a computer, instead.

And here, for instance, is a very common application inside of a computer, for your context. This is the iOS version of the icon.

And, typically, if you click on that icon, you'll see something like all of your contacts here, typically, alphabetical, by first name or last name.

And your phone or your computer lets you often search for someone's name at the very top. And it will autocomplete, and it'll be pretty darn fast.

But it'll be pretty darn fast because the programmers who implemented that application are looking for someone quickly for you. Now, I can do this old school style, whereby we have one of these things

from yesteryear, an actual phone book. So, in a physical phone book like this, you might have 1,000 pages. And on every page are a bunch of names and a bunch of numbers.

And as I flip through this, I could look for someone specific. So suppose I want to call John Harvard, who's-- the first name, of course, starts with a J. Well, I could just turn, page by page,

looking for John Harvard. And if he's not there, I keep turning and turning. So this is an algorithm.

I'm stepping through the phone book, one page at a time. Is it correct, this algorithm, assuming I'm looking down? So, yeah.

I mean, it's stupidly slow because why am I wasting my time with the A's, and the B's, and the so forth? I could probably take bigger bites out of it.

But it is correct. And that's going to be one of the goals of writing code, is to, of course, solve the problem you care about correctly.

So correctness goes without saying, or else what's the point of writing the code or solving-- or implementing the algorithm?

All right. Well, let me at least speed things up. So, instead of one page at a time, so, two, four, six, eight--

no, ignore that-- 10, 12, 14, 16, and so forth. It's a little hard to do, physically, but it sounded faster. It was twice as fast, theoretically, but is it correct?

AUDIENCE: No. DAVID J. MALAN: So, no. Why?

Yeah? AUDIENCE: Yeah, you might [INAUDIBLE]. DAVID J. MALAN: Yeah, I might miss John Harvard because, just by accident,

he might get sandwiched between two pages. But do I have to throw the algorithm out altogether? Probably not.

Once I reach the K section, which is past the J section, I could double back at least one page, at least, [PATS TELEPHONE BOOK] and just make sure I didn't blow past him completely.

So that is twice as fast, because I'm going two pages at a time, plus one extra step. So it's still an improvement.

So the first algorithm, worst case, if it's not John, but someone whose name starts with Z, that might take me a full 1,000 steps.

The second algorithm is just 500 steps because I'm going two pages at a time plus one, in case I have to double back, but that's in the worst case.

But most of us in the-- in yesteryear, and what Apple, and Google, and others are actually doing is, in software or here, physically, we're typically going, roughly, to the middle.

Especially if there's no cheat sheet on the side, like A through Z, I'm just going to go to, roughly, the middle. And, oh, here I am, not surprisingly, in the M section.

But what do I now know. If this is the M section, where is John Harvard? So, clearly, to the left, alphabetically.

And so here is where we can take a much bigger bite out of the problem. We can really divide and conquer this problem by tearing [TEARS BOOK] the problem in half, throwing half of it

away, 500 pages away, leaving me with a smaller problem, half as big, that I can really just now repeat. So I go, roughly, here, and now I'm in the E section.

So I went a little too far back. But what do I now know? If this is the E pages, where's John?

AUDIENCE: To the right. DAVID J. MALAN: So now he's to the right. So I can-- again, hopefully, he's not on that page.

I can tear the problem in half again, throw that 250 pages away. And now I've gone from 1,000 to 500 to 250 pages. Now I'm moving because the first algorithm was one page at a time,

second was two. This is hundreds of pages at a time. And if I go, roughly, again, to the middle; roughly,

to the middle; roughly, to the middle, hopefully, I'll find John Harvard on one final page. Can only do this once, but one final page.

So that invites the question, I would think, if the phone book does have 1,000 or so pages, how many times can I divide the problem in half to get down to one last page?

So it's, roughly, 10. And the quick math is 1,000 goes to 500 to 250 to 125 to 67 something. So we have to deal with rounding issues, eventually.

But assuming we work out the math, it's, roughly, 10 page tears. And that's crazy faster than 1,000 pages and still faster than 500 pages. So it's fundamentally better.

And, indeed, if I finally get to that final page, in the software world, you'd see something like this, John Harvard and his number, which you're welcome to call or text.

But that's how we now have our answer, much like the single page there. But let's consider just how efficient that actually is. So here's a very rough, broad-- with broad strokes, a chart.

So here's an xy plot. So here, on the horizontal, is going to be the size of the problem. And, by that, I mean, how many pages are we trying to go through?

This would be zero pages. This would be a lot of pages. How much time does it take to solve the problem?

How long does it take to find John Harvard or anyone else? This means no time. This means a lot of time.

So what's the relationship among these algorithms? Well, the first one is actually just a straight line. If there's n pages in the phone book, well, I

claim that it's a one-to-one relationship. Because if Verizon or the phone company adds another page next year, that just means I might have one more step next year,

as well, to find John Harvard or anyone else. But the second algorithm, it's also a straight line, but it's lower, even though it might not look obvious.

And what do I mean by that? Well, let me just draw some temporary lines. If this is how many pages are in the phone book-- dot,

dot, dot-- notice that it takes this much time, on the red line, to solve the problem. But if I, instead, use the second algorithm,

it takes me half as much time. So, even though they're both straight lines, one is strictly lower than the other, which means it's faster.

It's better. But the third algorithm is a fundamentally different shape, and it looks a little something like this.

And it looks like it's going to flatten, flatten, flatten out, but it never does. It just rises ever so slowly.

And what this means is that if maybe Cambridge and Allston, here in Massachusetts, merge next year, so we go from 1,000 page phone book to a 2,000 page phone book, that means, if we're here this year,

we're over here next year. It's not all that much higher. But it would be much higher if we were using the first two algorithms.

Why? It'd be an extra 1,000 steps to find someone in that combined phone book or maybe another 500 steps.

But, to be clear, if we're using my third and final algorithm, how many more steps will it take me next year, when Cambridge and Allston merge into one 2,000-page phone book?

Just one more step, no big deal. It's one more page tear. And this is what we mean, ultimately, about not just writing

code or implementing algorithms that are correct, but, now, that are well-designed or efficient, specifically. And this is what makes someone a better programmer, perhaps,

than someone else, or a better problem-solver than someone else, is acquiring, over time, these skills. So that, sure, you could solve the problem quickly and dirtily,

so to speak, but if you're going to have a lot of data eventually, be it in your phone book or maybe your Google website index, if you're searching the web, you're going

to want to try to think about how to design algorithms that look like this. Mathematically, this is called a logarithm. And it's log base 2 because I'm halving, halving, halving, again and again.

But, for now, just know that it's a fundamentally faster and different shape. So, among our goals in CS50, ultimately, is not just

to write and solve problems correctly, but, ultimately, ever more efficiently, as well. Any questions, then, on these ideas of efficiency and design?

Any questions here? Yeah, in back? AUDIENCE: [INAUDIBLE].

DAVID J. MALAN: A good question. Just to repeat it, can a graph like this capture the accuracy of the algorithm? Short answer, no.

For instance, if I drew a straight line that is super low on this graph, which would imply that the algorithm takes the same amount of time, no matter how many pages there are,

my algorithm might actually be to just pull a random page from the phone book, one step, and say, here it is. But that's not necessarily going to be accurate,

unless I get really, really lucky. So the graph really only speaks to efficiency and the design of the algorithm, not the correctness of it.

To analyze the correctness, you need to use another mechanism altogether, namely, logic. Other questions now, on efficiency, in this way?

No? All right. So, with that in mind, let's begin to translate this to some actual code.

And, in fact, before we look at, today, one actual programming language, albeit a graphical one, let's consider something called pseudocode. So pseudocode has no formal meaning.

Generally, you write it in English or whatever your own human language is. But you write your thoughts down tersely, succinct, but precisely. You try to really convey your thoughts, not with a wave of the hand,

metaphorically, but step by step, precisely. So what do I mean by this? Here might be some representative pseudocode

via which I describe that third and final algorithm in a way that I could hand it to you and you could do the same at home. Or I could hand it to someone at Google, and they could implement it in Android.

Or I could hand it to someone at Apple, and they could implement it in iOS. So, step one, I claimed, was "Pick up phone book." Step two was "Open to the middle of the phone book."

Step three, "Look at the page," as I did. And now things get a little more interesting. Step four, "If person is on page," I have to make a decision.

Presumably, what should I do if John Harvard is on the page I'm looking at? So stop and probably make the call, or email, or whatever the goal might be. And so I'm going to actually indent this, visually, by a few spaces,

just to make clear that you should only do line five if the answer to line four is yes. Otherwise, you don't bother.

The next thing I'm going to do, line six, is consider another possibility. "If the person I'm looking for is earlier in the book," what do I want to do?

Well, I could write-- I could describe this in a bunch of ways. I'm going to do this tersely, as follows.

"Open to the middle of the left half of the book, so it's open to the middle of the left half of the book. And then, what am I going to do?

Well, I've just divided the problem into something smaller. But it's fundamentally the same problem. It's just a fewer number of pages.

So I'm just going to go back to line three and do it again because the problem is just getting smaller and smaller, presumably. Else, if the person I'm looking for is later in the book,

open to the middle of the right half of the book, and, also, "Go back to line 3." But there's a fourth possibility and its failure

to realize, sometimes, that there's other possible outcomes that make computers crash, or spinning beach balls, or the like, if a programmer doesn't anticipate some situation.

What's the fourth possible situation, when looking for John Harvard? AUDIENCE: If they're not in the book. DAVID J. MALAN: If they're not in the book, at all.

And, indeed, I might get to the very last page and John Harvard's not even on that one. I'd better handle that and say, else, as a catchall, just quit altogether.

And, truly, often, in your Macs, PCs, phones, when they freeze, or, again, spinning beach ball, or the like, and just weird things happen, that's just

because some human made a dumb mistake. And they didn't realize that you could somehow get your phone or your laptop into a configuration that they didn't anticipate.

So we're going to try to handle that here. Now this is just one way of writing pseudocode. There's no one way to do this.

All of us in this room could come up with slightly different pseudocode. But I think you'll find characteristic are certain building blocks in all of our answers.

Here, in yellow, are what, as of today, we're going to start calling "functions," technically speaking. These are like actions or verbs that literally, in this case, tell me

what to do. Next, we're going to have these things, conditionals, forks in the road, so to speak, that take me down this path or another,

metaphorically. So I do this thing or something else. But how do I decide if I want to go this way, or this way,

or this way, or this way? I need to ask a question. And in programming, we'll typically use what

are called Boolean expressions, named after a mathematician, Boole. And a Boolean expression is essentially just a question with a yes/no answer, a true or false answer, a 1 or 0 answer.

It doesn't matter how you think about it, but it's got two possible answers. And so you can think of these as being expressions with question marks, even though I didn't draw such.

Person on page, person earlier in book, person later in book, those are Boolean expressions. And they tell me whether I should go down one fork in the road or another.

And, lastly, there's this, "Go back to line 3," in two different places. That represents what we call a "loop," some kind of cycle that's doing something again and again.

Now these are just a few building blocks here-- functions, conditionals, Boolean expressions, loops. But you'll find that they're characteristic of so

many different languages, one of which we'll look at today, another of which we'll look at next week. And those include, indeed, C, and Python, and other languages still.

And so this is why we focus on these basics and fundamentals in these early days because we're going to see them again and again.

So even if you feel like that fire hose is hitting you sometime, we'll give you, today, ultimately, more visuals by which you can hang onto, so as to actually write code, ultimately,

in different languages and solve all sorts of problems. Now, we'd be remiss in not bringing up what's behind characters like Spot, and ChatGPT, and other software, artificial intelligence.

And it turns out, to get to the point of AI, we're actually going to need more building blocks than just functions, and loops, and conditionals.

It's not going to be quite that simple. But this has been a lot, so far. Let's go ahead, here, and take a five-minute break.

And when we resume, we'll take a look not only at AI, but also a specific language called Scratch. So no cake, just yet, but we'll come back in five.

Before we dive back in, I just wanted to call out a special guest that we have here today, beyond Spot, someone who's come from even farther away.

And, in fact, if any of you have taken CS50x, the OpenCourseWare version of the class, or dabbled in it over the past few years in some of CS50's online social communities,

you might have had your questions answered by a certain human from New Zealand. And she's come all this way, today, to spend this lecture with us.

This is CS50's own Brenda Anderson. If you might come up for acknowledgment from all of us here. [APPLAUSE]

It's not much, but just a little token of our thanks. Brenda has helped, truly, thousands of students online

for the past many years. And, in fact, her own daughter has been the artist behind the duck that's about to loom large in CS50 this year and beyond.

So, thank you to Brenda. [APPLAUSE]

All right. So it's hard to escape a discussion of artificial intelligence, nowadays, but we thought we'd use this as an opportunity

to connect some of these dots. Because, indeed, over the course of the semester, we'll be-- not only be talking about artificial intelligence or AI,

but really using it all the more constructively to help you solve problems, help you get unblocked when you hit a wall, cognitively or syntactically, when writing code.

And, indeed, it's no accident that we have this duck here, looming large, which is really the embodiment of the sort of AI that you'll experience within CS50, itself, this year.

So let's talk about the so-called chatbots that inspired some of those headlines with which we began class, that weren't quite on the nose.

So the class will still be taught by us humans, but helped by this CS50 duck, a chatbot of sorts. Now what do I mean by this?

Well, it turns out that, when it comes to implementing something like an artificial intelligence, we don't quite have all of the building blocks yet, certainly after just today's week zero,

to implement something like that. But I think we can skate in that direction, intellectually. So, for instance, if we were to take a stab at implementing our own chatbot--

some interactive text-based program that talks to us, and answers questions, and the like-- we could try borrowing some of today's ideas already, those functions, conditionals,

loops, and more. And I could write something like this. If I am writing code or pseudocode for a chatbot,

I could program the chatbot to do something like this. If the student says, hello, to the chatbot, then the chatbot should say, hello, back.

Else, if the student says, goodbye, well, the chatbot should say, goodbye, back. Else, if the student asks how you are, the chat bot should say that it's well.

But things get a little harder when you start asking more interesting questions, like, else, if the student asks why 111 in binary is 7 in decimal.

Now, you could imagine that we just have a conditional, with this Boolean expression, that programs the chatbot to just give you the answer and explain, in an English sentence, why that, in fact, is.

But what if you, the student, asks why 110 is 6 in decimal or why 010 is 2? I mean, you can just imagine the explosion in the amount of code that we would have to write to just anticipate every darn question that you

might ask about today and every other class, not to mention all of the knowledge in the universe. So, surely, there are other ways to implement algorithms

that allow something like a chatbot or AI, more generally, to be fed input, still, like all of the internet, all of the worldwide web, all of the pages and textual content therein,

but to let it just figure out how to answer our questions based on those kinds of inputs, assuming the inputs, themselves, are accurate. So "large language models" is a term you might

have heard bandied about over the past several months, or LLMs. And a large language model really is an implementation, in software, of code that actually takes, as input, lots and lots of language--

like the text of lots and lots of web pages, dictionaries, encyclopedias, Wikipedias, and the like-- and infers, from the patterns of English words or any human language,

what a typical human might actually say when asked a question. And some of these questions are easy, right? Probably, on the internet, alone, not to mention everyday life, if someone

extends their hand and says, "Hi. How are you," odds are, with 90% probability, you're going to say, "Good.

Thanks. How are you?" So I bet we could write software that just

infers what it should say, probabilistically, statistically, based on those kinds of patterns online. And that's, indeed, where the world is starting

to go, when it comes to the most sophisticated of algorithms, where you and I, the humans, we don't try to anticipate every possible input.

Rather, we give it a more general purpose input, like all human knowledge, and ideally just let it figure things out. Now, we're not quite there, yet.

And odds are you've heard of hallucinations or just mistakes that these large language models make. But their inputs are imperfect.

And sometimes there's a bit of randomness sprinkled in because you don't want the thing to always say the exact same thing. Even you and I might say, "Eh, I'm not that great today" 10% of the time.

So you need to perturb the output in some way. But within CS50 and within this world of large language models, we do have these tools like ChatGPT, and Bing, chat, and others.

And we'll stipulate that, for CS50's purposes, the direction we're going this year is that this is what's in the syllabus, dot, dot, dot;

that it will not be allowed, it will be considered not reasonable to use AI-based software, other than CS50's own. So the goal here is not to simply take away

tools that are clearly inevitable, in my view, and clearly helpful and productivity savers. But we'd like there to be some guardrails, intellectually, on just how

helpful these chatbots are. Because as you've probably seen, if you ask it a question, these chatbots are already pretty good at not just helping

you finish your current thought, but it'll hand you your second and your third thought and do the assignment for you. But I think, through prompting, so to speak,

we'll be able to coax some of our own tools, being computer scientists, ourself, in a direction that you actually find to be the right balance, akin to having

a good tutor by your side 24/7, who doesn't just hand you answers, but, indeed, tries to lead you to the same. So you actually get something out of the experience,

and, ideally, three-plus months from now, those training wheels can come off, too. And you're able to still stand on your own.

So it will be reasonable to use CS50's own AI-based software which will actually take the form of a CS50 duck, which is actually available now-- and we'll use it throughout the term-- at CS50.ai, a web-based application

that's quite similar to ChatGPT, but that has the personality of a CS50 teaching fellow or TF, or teaching assistant, TA, that also happens to think of itself as a duck.

And for reasons we'll get to in a couple of weeks time, but rubber ducks, in particular, are a thing in programming. But more on that, before long, as you can even see from the one

there on my desk. With that said, too, well, I'm going to call out CS50's own Brenda Anderson, whose daughter, Sophie, kindly not only created

the first incarnation, digitally, of this duck, but also, most recently, once it actually did more than quack a random number of times in response to questions, has now

been virtually brought to life, too. So, all that and more, over the coming weeks, but you'll find, ultimately, that the goal is to really bring to life the availability of an AI-based tutor

that you have access to, a friend in your-- next to you, that will help guide you through a lot of the course's challenges along the way.

And we actually rolled it out this past summer, already, with some of your predecessors, through the Harvard Summer School. One student wrote, at summer's end, that this duck

"felt like having a personal tutor-- I love how AI bots will answer questions without ego and without judgment generally entertaining even the stupidest of questions

without treating them like they're stupid. It has, as one could expect, an inhuman level of patience." So there's actually something really there because as many teachers

as there are in CS50-- myself, the course's preceptors, teaching fellows, teaching assistants, and course assistants-- there's only so many of us.

And we're only awake so many hours of the day. And I think you'll find, too, that we're on the cusp of something pretty remarkable, in the coming years, where

it's going to get a lot more enabling, now, to learn material not only within the confines of a class, but on your own, ultimately, as well. And as one other student put it, at summer's end, with respect to the duck,

"Love love loved the duck. We're friends now." So that, too, awaits.

But, first, we're going to need to start with the basics. And we started today by talking about binary. And darn it, here it is again.

So we can't actually get to the point of using, or solving, or implementing AI until we understand this. And odds are most of you won't know, at a glance, what this piece of software

does. But these are the 0's and 1's that represent, perhaps, the first program that any programmer writes, which is now a clue to some

of you who have dabbled in code before. What does this pattern of 0's and 1's tell a typical computer to do? Might someone guess?

AUDIENCE: "Hello, world." DAVID J. MALAN: It's going to have it say, "hello, world," which is one of the very first programmer-- programs

that most any programmer writes. Should you be able to recognize these 0's and 1's? Do I recognize these 0's and 1's?

No, not at all. I just happen to know that they are the same. And that was a leading question.

But they are representing data and instructions, ultimately, data like H-E-L-L-O, comma, W-O-R-L-D and an instruction like, "Print that data to the screen."

As for what these patterns of 0's and 1's are, this is not something that a computer scientist or programmer worries about. We just stipulate that, OK, someone, somewhere knows how to do this.

And it's probably someone like Intel, who makes the hardware inside of the computers. But you and I, starting now, already, in week zero,

can start to view binary more abstractly. We don't care about the 0's and 1's. We only care that you can use 0's and 1's

to represent more useful quantities, like numbers, and letters, colors, and more. So this, next week, is going to be the code we actually

start writing at a keyboard. And this is that language called C. It's the same language I, myself, learned years ago, when taking CS50, when all we learned at the time was C.

But this, too, has some crypticness to it. And if you've never programmed before, you can probably wrap your mind around, OK, I'm guessing the "printf" prints out the "hello, world."

But what's with the semicolon, the quotes, the backslash, and the curly braces, the #include, and all of this stupid syntax? A lot of this, in the beginning of any class, is really a distraction.

It is not intellectually interesting. But it's the stupid kind of stuff that's going to trip you up quite often. And so, today, what we'll do is focus not

on syntax, characters on the keyboard, but ideas because what really matters in this program is that "printf" is a function here for our purposes.

And that function is to display information on the screen. Everything else, as we'll soon see, has value and will be understood by you, before long, but for now, it's a distraction.

Let's focus on those building blocks. When it comes time to write code, though, for the curious, especially if you've programmed before, we'll

use a very popular free and open-source tool called Visual Studio Code, or VS Code. We'll use a cloud-based version of it that we pre-install everything

you need in the cloud for you so you don't have to deal with headaches like getting your Mac or PC to work. You'll use instead this URL, cs50.dev, but more

on that in next week, week one. For now, we'll use another cloud-based editor called Scratch. And odds are some number of you use this probably

as early as like middle school or the like. And that was fine to create your own animations, games, interactive art, or the like.

But we'll use it today for just a bit. And we'll use it in the course's first homework, AKA problem set 0, to explore now some of these same ideas.

And among the goals today for the remainder of today is not to focus so much on Scratch and the particulars because this is not a language that you're

going to use often but to give you very visual representations of ideas so that when things do escalate next week to C, to the more cryptic, it's the same ideas just typed out instead of dragged and dropped.

So by that, I mean this. I'm going to go ahead and share in just a moment the user interface of Scratch. But what's nice about Scratch is that this

is how we're going to implement that same program today. These are two blocks or puzzle pieces on the screen, and they've been interconnected to tell the computer to say "hello, world"

on the screen. The user interface that we're about to use will look generally something like this.

It's a web-based editor that you can also download it locally to use offline. And you'll see that at the left here are a whole bunch of puzzle pieces

or blocks. They're categorized by color, and the blue ones tend to relate to motion, for instance.

The purple ones represent looks. The pink one represents sounds. The yellow one represents events.

More on that soon. The orange ones represent control, and then there's operators, variables, my blocks, and even some extensions

we can install as well. So it just categorizes things visually and colorfully so that you can find what you're looking for.

But we're going to use these puzzle pieces to drag and drop them onto this area here. And we're going to connect them when we want them to do something.

What can they do? Well, by default, Scratch comes with this cat here, otherwise known as a sprite, which is a character in a game or in a graphics context.

And this cat lives in this two-dimensional world in which the cat can go up, down, left, right. And you can actually change the cat's costume

to be a dog, a bird, or anything else. It really is more of an idea than it is a specific animal in this case. But the world that Scratch lives in looks a little something like this.

It's like a Cartesian plane with x-coordinates and y-coordinates. And the numbers don't so much matter fundamentally, except that when you want the cat or any character to go up,

down, left, or right by some amount, it's useful to know, for instance, that 0, 0 is the middle, 0 comma 0 for x comma y. All the way up is a y value of 180.

All the way down is -180. All the way to the left is -240. All the way to the right is 240.

And generally, you're not going to have to worry about numbers. You're going to use these relatively-- go right, go left, go up, or down. But that's just the world that Scratch itself lives in here.

So let's go about using Scratch here. I'm going to change over to my cloud-based editor here, where I've gone to scratch.mit.edu.

And I've clicked Create in order to create a project. And that gives me this blank canvas here. And I'm going to do these somewhat quickly because I kind of know

what I'm looking for. But part of the process with problem set zero is going to be clicking, and dragging, and sort of scrolling around

to see what building blocks exist. But I know under Events there's this puzzle piece here when green flag clicked.

Why is that germane? Well, if I zoom out, and go back to Scratch's world at the right here, notice that above Scratch's world there's

a green flag, which is going to mean go, and a red stop sign, which, of course, is going to mean stop. So if I drag this puzzle piece anywhere into the middle,

it's just going to plop where I put it. But what that means semantically is when someone clicks that green flag, I want Scratch the cat to do this other thing.

Well, what do I want it to do? Well, let me go under Looks. And looks here in purple have some puzzle pieces like this.

Well, I can say hello for some number of seconds, or I can just go ahead and say hello. So let's do that.

I'm going to drag this say block. And notice that as soon as I get close enough, it's going to magnetically want to connect.

So I can let go, and they snap together automatically because they're the right shape. I don't have to say hello, exclamation point.

I can change it to the more canonical, hello comma world. So anything in this white oval is editable that you can change as just text there.

If I now zoom out, let me go ahead and click the green flag. And voila-- this should be my first program in Scratch. Hello, world.

Without any of the distractions of syntax or weird characters on the screen, it's just done what I want it to do. All right.

Let me go ahead and click Stop there. And let me make it a little more connected to what we've discussed thus far.

So this puzzle piece here, say hello, world, represents what type of building block using the vocabulary of today? So it's a function.

So these purple blocks are functions, say, hello, world. And let me give you another piece of terminology. These white ovals that take textual input--

in general, those are called parameters or arguments. And they customize the behavior of a function. So a parameter or an argument customizes,

modifies the default behavior of a function, like in this case, say. Similarly, in the C code from earlier that we'll see next week, the printf function took a quoted phrase like, hello, world, similarly as input.

But more on that in the future. So how does this connect to the mental model we presented earlier? Well, here's problem-solving as I described it earlier, inputs to outputs

with algorithms or code in the middle. Well, what we've got here really is an input of, hello, world, the white oval. The function or algorithm that it's going into as input is the say block.

And what is the output of using this say block, the say function? It's the visual effect of having the cat have the little speech bubble appear above its head, saying, hello, world.

So everything we do, in fact, can be mapped back to that very simple idea of inputs and outputs. Well, let's make it a little more interesting, though.

It's a little boring to just say "hello, world" all the time. Let me go ahead and drag this away. And if you just drag it to the left and let go, it gets automatically deleted.

Let me go under Sensing in light blue here. And you'll see there's a bunch of blocks, one of which is an ask block, an ask function, which is going to prompt

the human, me, for some input. So let me go ahead and drag that over here, and it snaps together. I could change the question, but I'm OK with that question.

We'll use what's your name. But notice that this block, ask, is a little special. It is not just going to display like a speech bubble on the screen.

It's actually going to return a value, and this is another term of art today and onward. A return value is some value that can be handed back to you conceptually

from a function so that you can do something with it. It's as though the ask function asks someone for their name, writes it down on a piece of paper, and hands you the piece of paper.

You can do anything now that you want with that name. And here is how you access the name in this special block called answer, which, again, will start calling a return value.

So if I want to say "hello" to someone specific, I'm going to do this. Let me zoom out. Let me go back to Looks, and let me go back to Say.

And I'm going to change the say block here to "hello, comma." Then I'm going to zoom out. Well, I need two inputs, I think.

So I'm going to grab another say block, and I'm going to put it below. And I could just type "David," but this is going to defeat the whole point of asking me for the name.

And it will only work for me. So I don't want to do that. So let me go back to Sensing, and notice the shape is important here.

Even if it's not quite the same size, the shape matters. And I can actually drag this and change the input of this say function to be whatever that return value is, that piece of paper

that has the person's name on it. And it grows to fill, but now we have a program that I think when I click the green flag-- watch-- is going to prompt me.

What's your name? And now I have room to type down here. So I'm going to type D-A-V-I-D. I'm going to hit Enter,

and it should say "hello, Dave." Wait. Hmm.

Huh. Maybe it was-- didn't work. D-A-V-I-D. Here we go.

Hello, David. Hmm. It's missing the hello, but I'm quite sure we have a hello right there.

So what explains this bug or mistake? Yeah. AUDIENCE: [INAUDIBLE].

So they overlap. DAVID J. MALAN: Exactly. Put another way, my Mac, my PC, it's just so darn

fast that it did exactly what it was supposed to. But it said "hello, David" so fast that we didn't even see, we being the human, the slowest part of the puzzle, see the actual hello.

So there's a few different ways to fix this, as you know. We could have it say "hello" for some number of seconds. So I could kind of do that.

So let me do this. I can decouple these by just dragging and letting it go so that they're magnetically far apart.

Let me go ahead and drag this one, say hello for two seconds. I'm going to change the grammar here to be hello comma again. I'm going to go ahead and disconnect these two.

I'm going to throw away the old one that I don't want to use. And I'm going to reconnect this so that now-- OK.

It's going to say hello for two seconds and then my name, hopefully. So let me click Stop and Start. D-A-V-I-D. Enter.

OK. So it's better, but it's kind of poorly implemented. Like, come on.

I just wanted to say hello comma David. Why is that hard? Well, maybe we can actually combine these a little differently.

And let me propose this. Let me actually get rid of these blocks again. And let me go ahead and just say one thing.

But can I somehow combine this to say hello comma David all in one breath? Well, it turns out if I go under Operators, I know from having played with this before that there's this puzzle

piece down here called join. It's an oval. It's a little big, but, again, it will grow to fill.

And by default, it wants to join two words, "apple" and "banana." But those are just placeholders. So let me go ahead and drag this over the default hello.

Let me change "apple" to hello comma space and then banana. Let me go back to Sensing. Let me grab answer and drag and drop that.

So now notice that I'm kind of layering my ideas. And put another way, the output of this join block is presumably going to join two things together,

apple and banana or hello comma David. And then the output of join is going to become the input to say. So aesthetically, it just looks better.

It's still correct, but it's just better. So if I type "David," and hit Enter, hello, David. This is what a normal program would presumably

do, not show you part of the phrase and then the rest of the phrase. Like, it's just better in this way. So let's connect this now to this same puzzle piece and this methodology.

So here's that same puzzle piece, ask. How do we fit it into this input and output flow with algorithms? Well, the input to that puzzle piece is something like, what's your name,

question mark. Then the algorithm or the code implementation thereof is this ask block and wait so the human has a moment to type their response in.

The output of that function recall is a return value. You don't see anything on the screen by default because we've not used say yet, but we get this return value.

And let me scooch everything over now so that we can now join those inputs together. So here's this puzzle piece.

Let me go ahead and propose that the inputs now to the join block are two arguments or two parameters, so to speak, hello and answer. They go into that join puzzle piece, whose purpose in life

is to return one joined version thereof. Let me slide this all over logically now so that now that output becomes the input to the say block

and now is why the cat has the speech bubble saying all at once, hello comma David. So what we've done here is kind of composed the output

and from one function into the input of another. And you can think of this in a couple of different ways, left to right, as I did there, or kind of

like stacking these things on top of one another. But at the end of the day, even as programming gets more and more powerful for us, it's just inputs and outputs, inputs

and outputs. And thankfully, with built-in functionality from our friends at MIT who designed Scratch, I can even do something playful like this.

I can go to that Extensions button at the bottom. And there's a lot of fancy things I can add here, like text-to-speech. So let me go ahead and choose text-to-speech.

And let me go ahead here and change the say block in purple. Let me get rid of the say block, and let me borrow this. Let me get the speak block like this.

And now let me drag and drop this oval. It's going to grow to fill. And I think it's just about to be a little more interesting.

Let me click Play now, and hopefully this isn't too loud. D-A-V-I-D. Enter. SPEAKER: Hello, David.

DAVID J. MALAN: OK. [APPLAUSE] Thank you.

Thank you. That's a low bar. [CHUCKLES] Let me go ahead and set the voice too.

And you might now remember how we began class, where we had a robotic, computerized voice. Well, we didn't use Scratch at the time, but we could change this in Scratch

alone to be a little different. So D-A-V-I-D. SPEAKER: Hello, David.

DAVID J. MALAN: OK. Little creepy, but we can play all day long with that. But the point is that these functions are just

now doing something a little different. But it's just these inputs and outputs. Well, let's make the cat more like a cat.

Let me go ahead and throw away all of this asking question stuff. Let me go up to Sound, and let me go ahead and drag the play sound meow until done.

And here too it comes with meow. You can add your own sounds as well. But I'm just going to use the default meow and here too.

Hopefully, this won't be too loud. Let's make the cat meow by clicking Play. [MEOWING]

OK. It's a little piercing, but it's cute. And if I want the cat to meow twice, I could just play the game twice.

[MEOWING] All right. But it would be nice to just get it to meow automatically two, or three,

or more times. So you know what I could do? I could just drag a second one of these.

Actually, you know what? I could even just right-click or Control-click and duplicate them. But I'll just keep dragging and dropping.

There's different ways to solve problems. And now let me click Play. [MEOWING]

OK. Cat does not sound particularly happy. So we could go under--

how about Control? We could wait one second. Now, there's no room, but it will sort of expand to give room for me.

So let me try this. And now it's going to wait one second in between meows. [MEOWING]

OK. Let me stipulate that is correct.

If my goal is to get the cat to meow three times, it meowed three times. But per our discussion earlier of algorithms and the design thereof, this is not the best design.

[MEOWING] OK? [LAUGHTER]

Thank you for playing along at home. Yeah. In what sense is this arguably not well-designed?

Yeah. AUDIENCE: You repeated yourself. DAVID J. MALAN: I repeated myself, which actually in programming

tends not to be a good thing. Now, it was easy. I almost resorted to copy-paste, which saves me time upfront.

But just imagine a contrived scenario. Now, what if I want it to wait like two seconds in between? All right.

It's not that big a deal. I change it here, and I change it here. But what if the program is meant to meow 10 times?

Then I have to change it here, and here, and here, and here, and here. And eventually I'm going to screw up. Humans are fallible.

I'm going to overlook one of them. One time, it's going to be one second. Another is going to be two, and just stupid things will happen.

You're setting yourself up for failure if you design things poorly. And so I would propose that we use another type of building block to solve this instead.

Yeah. AUDIENCE: [INAUDIBLE] DAVID J. MALAN: Yeah.

So we could use a loop and just write minimal code but to accomplish even more functionality. So let me throw away most of these blocks.

And let's go and grab this repeat block, which we haven't used yet, but it's right there. And as the name suggests, this will allow

me to repeat something some number of times. Let me put these two puzzle pieces inside. It'll grow to fill.

Let me reconnect it to the green flag. I'll change the default 10 to a 3. And now--

[MEOWING] It's just sort of better because if now you want it to meow more times,

you change it one place. If you want it to slow down, you change it in one place. There's no room for error.

And that's generally a good thing. But this is silly. Like, Scratch comes with a cat.

Why didn't MIT give us a puzzle piece called "meow?" Like, why am I implementing the idea of meowing myself? Like, that took me what?

1, 2, 3, 4 puzzle pieces. Why isn't there just one puzzle piece that meows for me? This too we can do in code, be it in Scratch, or C, or other languages too.

I'm going to go down to these pink my blocks here, where I can create my own puzzle piece. And I'm going to call this literally "meow."

And I'm going to go ahead and just click OK. And notice that it's given me this new type of start connector. It's a start puzzle piece that nothing goes above it.

But you can put anything you want below it. And I'm going to go ahead and cheat here. I'm just going to grab my existing code, so to speak.

This is code I'm writing, even though it's puzzle pieces. And now let me just claim, and I'll move this aside. Here is now an implementation of my own function,

my own block called "meow," whose purpose in life is to meow until done and then wait one second. But what's powerful now is notice at top left, now that I've made the block,

I can use it any number of times. So I can grab this meow block, drag it over here, and you know what? Now that "meow" exists as an idea, I can abstract that away.

And I'm just going to arbitrarily drag it way to the bottom. I'm not deleting it. I'm just putting it out of sight, out of mind so

that we can focus now on this idea. And I claim that this implementation of meowing is sort of better because it's more compact, it does what it says,

and I don't care about the implementation details of "meow." So this idea of abstraction, something we're going to use frequently. To abstract something away is to simplify.

Don't think about the underlying implementation details. Just care about what it does or what it's called. Someone has to care about the implementation details,

like me 30 seconds ago. But here on out, I don't need to care. And so in fact, you and I are using the abstraction

that is Scratch because I don't know how to put a speech bubble on the screen. I don't know how to create that sound, meow. MIT did that, and they abstracted those pieces

of functionality away already for us by just giving us these puzzle pieces we see here. So the code will work the exact same.

[MEOWING] But it's sort of better designed now because now I've abstracted away the idea of meowing.

But I bet I can improve this further. Can I get rid of the repeat block altogether? And let me just tell the meow block how many times to meow.

Well, let me go down to the bottom and look at the implementation details. I'm going to right-click or Control-click on this, and I'm going to edit it.

So I'm going to make a change. And I didn't do this before, but I'm going to call it "meow," as before. I'm going to add an input.

And just so I know what it says what it does, I'm going to add the word "times" here. And I'm going to change this placeholder to n.

n for "number" is the go-to placeholder any time we want to talk about a number in CS. So now notice the puzzle piece looks a little different.

It takes an argument or a parameter called n, which represents the number of times you want the thing to meow. Now, that doesn't do that yet.

So let me go back to my other code. Let me just decouple these temporarily. I'm going to move my loop into my implementation of meowing.

But I don't want to hard code, that is literally write the number 3 anymore. I'm going to grab this oval and put it there. So now I've generalized the function.

So now it will meow any number of times, 0 on up, by executing that loop and now more powerfully. Out of sight, out of mind.

Notice that my code just became so darn simple. Like, my function is called "meow." It meows some number of times.

All I have to do is type a number there, and it just works. And I don't care any more about those lower-level, so to speak, implementation details.

So here, no surprise. If I type in the number 3, zoom out, and hit Play-- [MEOWING]

--it still works just fine. So any questions on what we've just done here? It's still just meowing, but that's besides the point.

It's this creation of our own functions, this modularity, this abstraction that's going to be the idea that keeps coming back to us. No?

All right. So let's make this a little more cat-like. Let me throw away all of this code.

And let me go ahead-- oops-- let me throw away this code first and then the rest of this code. And let me go ahead and give myself another green flag block.

And let me go ahead, and let's create a cat that allows us to pet it by moving my cursor over the cat. And maybe it likes that, so it'll meow when I do that.

So let me go under Control, and let me grab this if conditional, which we talked about as a building block earlier. Let me go to Sensing, and we haven't used this before.

But here is a weird sort of diagonal shape that says touching mouse pointer question mark. So that's a Boolean expression.

So I'm going to drag that, and it's definitely the wrong size. But it is the right shape, so it will grow to fill. And the question I want to ask is if the cat is touching the mouse pointer,

then go ahead and meow happily. So let me grab the meow sound, put it in there. And so I think when I click the green flag to start the program,

and now I let the mouse pointer touch the cat, we should hear-- huh. huh.

Doesn't seem to be working. There's a bug or a mistake in this program too. What did I do wrong?

Yeah. AUDIENCE: You didn't specify the sprite [INAUDIBLE].. DAVID J. MALAN: I don't need to specify the sprite explicitly

because a detail I didn't discuss earlier. In the bottom right of the screen, notice that the cat is already selected.

So this code relates to that cat. So your instinct is good if we had two or more sprites, but I just have one, so I'm covered there.

Other thoughts. Yeah. AUDIENCE: It only checks once.

DAVID J. MALAN: It only checks? AUDIENCE: Once. DAVID J. MALAN: Once.

So I click the green flag. The computer did what I told it to do. The mouse pointer was not touching the cat at that moment

because it was touching the green flag. So, of course, it didn't meow. So what maybe is the fix here?

What puzzle piece can we add? AUDIENCE: After the green flag is [INAUDIBLE].. DAVID J. MALAN: OK.

OK. Interesting solution. So let me go ahead, and under Control let me grab a-- wait one second.

I'm going to change the 1 to 5, and now I'm going to click the green flag. So here we go. 1, 2, 3, 4, 5.

Damn it. [MEOWING] OK.

That was yours, not mine. [LAUGHTER] It didn't work.

AUDIENCE: [INAUDIBLE] DAVID J. MALAN: Sorry? AUDIENCE: [INAUDIBLE]

DAVID J. MALAN: Oh, maybe forever. So your approach would work, but it's very much a hack, if you will. Like, I would have to time it perfectly so that the mouse pointer is touching

it, or, conversely, I have to drag it there and just leave it there for five seconds. And that's a little weird because you don't just touch a cat

and then five seconds later it meows at you. Like, presumably, we want it to be more interactive. So I like this idea of a loop.

Right? Why don't we just tell the cat to forever listen for the cursor as by using not repeat but forever?

Let me move this in here. So now the cat's going to be told when the green flag is clicked just forever, if touching, if touching, if touching.

Oh, meow when actually touched. So now if I zoom out and hit Play, nothing's happening. I don't have to wait any number of seconds.

But when I do touch the cat-- [MEOWING] [APPLAUSE]

[CHUCKLES] Fan section here. Thank you. [MEOWING]

So now it's actually working quite well. So there we have sort of a logical bug. But it does make sense if you think about what it was

you told the computer to actually do. Well, let's make things even more interesting by using one of these extensions.

In this bottom left corner, this is how I got to text-to-speech earlier. Let me go to Video Sensing over here too. And I can actually-- there we go-- literally, the video has come on.

Let me go ahead and do this. Get rid of this code, and let me step out of the frame. When video motion is greater than--

well, this is CS50, so let's just type in 50, which is just a measure of motion. Let me go and play sound meow.

OK. And let me stop and restart. All right.

So there's the cat. [MEOWING]

OK. It worked. The cat's a little insensitive.

[MEOWING] There we go. Actually, you know what?

Maybe it's just-- let me put-- let's change it. 20. Oh, my God.