CS50 Video Player
    • 🧁
      • 🍨
      • 🍇
      • 🍿
    • 0:00:00Introduction
    • 0:01:15This is CS50
    • 0:08:35Computer Science
    • 0:09:44Unary
    • 0:11:28Binary
    • 0:23:58ASCII
    • 0:33:42Unicode
    • 0:38:45Color
    • 0:42:27Representation
    • 0:47:20Algorithms
    • 0:57:34Pseudocode
    • 1:03:32Artificial Intelligence
    • 1:09:21Scratch
    • 1:16:15Hello, World
    • 1:19:00Hello, You
    • 1:27:02Meow
    • 1:32:21Abstractions
    • 1:37:23Conditionals
    • 1:41:14Oscartime
    • 1:49:52Ivy’s Hardest Game
    • 0:00:00[MUSIC PLAYING]
    • 0:01:15DAVID MALAN: All right.
    • 0:01:17This is CS50, Harvard University's Introduction
    • 0:01:21to the Intellectual Enterprises of Computer Science
    • 0:01:23and the Art of Programming.
    • 0:01:25My name is David Malan, and I actually took this class myself some years ago,
    • 0:01:28but I almost didn't.
    • 0:01:30It was my first year in college and my roommates
    • 0:01:32and I were living in Matthews Hall, for those familiar.
    • 0:01:35[CHEERING]
    • 0:01:36Nice, Matthews.
    • 0:01:37Our claim to fame, actually, at the time was that our room was literally
    • 0:01:41Matt Damon's just three years' prior.
    • 0:01:43So onward from that.
    • 0:01:45But my first year, I didn't really have the nerves
    • 0:01:48to set foot in this classroom, let alone computer science.
    • 0:01:51In fact, for me, computer science, and CS50 in particular,
    • 0:01:54was very much this class to beware.
    • 0:01:56Like, I was kind of comfortable with computers,
    • 0:01:59but I certainly wasn't among those more comfortable with computers.
    • 0:02:02And so I shied away my first year.
    • 0:02:04Instead, I actually took a whole lot of classes in government.
    • 0:02:07In fact, in high school, I was really enjoying history.
    • 0:02:09I loved this constitutional law class that I
    • 0:02:11took my senior year of high school.
    • 0:02:13And so I figured, OK, if that's what I liked in high school
    • 0:02:15and if that's where my comfort zone was, that's
    • 0:02:18probably what I should be doing in college.
    • 0:02:20And so I essentially declared as my concentration or major government
    • 0:02:23for the first year, year and a half of school.
    • 0:02:25But my sophomore year when I was living actually in Mather House instead.
    • 0:02:31OK, no one from Mather.
    • 0:02:32In Mather House instead, it was--
    • 0:02:35I sort of followed some friends, I think the first week
    • 0:02:38of class in September of that year to a class called CS50.
    • 0:02:41And honestly, once I stepped foot in that classroom,
    • 0:02:44the professor at the time was a famous computer scientist
    • 0:02:47by the name of Brian Kernighan, now at Princeton.
    • 0:02:49Like, I was hooked.
    • 0:02:51And literally would I go back thereafter on Friday evenings when, at the time,
    • 0:02:55problem sets were released and sit down at 7:00,
    • 0:02:578:00 PM on Friday nights and dive into homework.
    • 0:03:00Which isn't necessarily something we recommend, per se.
    • 0:03:03But for me, it was like this sign that, wow, I've sort of found my calling.
    • 0:03:07I found my classmates here on campus.
    • 0:03:10And that's not going to be the case for everyone.
    • 0:03:12Certainly, we have no expectations that after taking one computer science class
    • 0:03:15that you will or might want to take others.
    • 0:03:17But what's so empowering about computer science and CS50
    • 0:03:20in particular is it's so applicable to the broader world,
    • 0:03:24whether you're in the arts, humanities, social sciences, natural sciences,
    • 0:03:28or beyond, it's just so applicable the concepts and the practical programming
    • 0:03:32skills with which you will exit a class like this.
    • 0:03:36Now it's going to be challenging along the way, and indeed, I put in my time
    • 0:03:39back in the day, and even I did find it challenging.
    • 0:03:42And here, for instance, is a photograph of a very famous MIT hack,
    • 0:03:45so to speak, from down the road, whereby it communicates
    • 0:03:48that getting an education from MIT is like trying to drink from a fire hose.
    • 0:03:53Which is to say there's going to be so much information, like so much new stuff
    • 0:03:56that certainly on any given day of the week,
    • 0:03:58you're not going to be able to absorb all of it that first time around.
    • 0:04:02But at the end of the day, it's through that challenge, putting the time in,
    • 0:04:06that the returns are therefore just so much higher at the end of the course.
    • 0:04:10And indeed, will you walk out of the course with a much better understanding,
    • 0:04:14not only of computer science and programming,
    • 0:04:15but ultimately how to teach yourself new technologies and beyond.
    • 0:04:20For the next three plus months, will we have teaching fellows,
    • 0:04:23teaching assistants, course assistants, and myself by your side
    • 0:04:26guiding you through the course's material.
    • 0:04:27But the goal by term's end is to take those and leave those training wheels
    • 0:04:32off so that you're well-equipped to go teach yourself
    • 0:04:36new ideas beyond the class itself.
    • 0:04:39Take comfort, though, in knowing that most CS50 students have never
    • 0:04:42taken a CS course before, and indeed, as per the syllabus,
    • 0:04:45what ultimately matters in this course is not so much where
    • 0:04:48you end up relative to your classmates but where you end
    • 0:04:50up relative to yourself when you began.
    • 0:04:53And when you began is thus today.
    • 0:04:55And so consider just how comfortable or uncomfortable
    • 0:04:58you are with computing, let alone computer science and programming,
    • 0:05:01particularly if you've never explored either in a classroom before,
    • 0:05:04and consider the delta just a few months from now that will really
    • 0:05:08describe how far you have come.
    • 0:05:10And that is all that matters, not how much
    • 0:05:12the student to the left or the right, in front or behind you right now, knows.
    • 0:05:17With that said, let me add some additional inspiration, if I may.
    • 0:05:21Here's a photograph of my own very first homework assignment in CS50 from 1996,
    • 0:05:27and I will draw your attention to the fact
    • 0:05:28that even though this is a so-called hello world program that we'll
    • 0:05:32play with ourselves next week, it is pretty much literally the shortest,
    • 0:05:37easiest program you can write in a programming language called C.
    • 0:05:40I still somehow got minus 2 on my very first homework
    • 0:05:44assignment, which is to say, we're all going to make mistakes along the way.
    • 0:05:48But the goal will be to learn and enjoy that process here on out.
    • 0:05:53At the end of the day, too, like me, you'll
    • 0:05:55exit with your own proudly held high took
    • 0:05:58CS50 t-shirt as is our tradition too.
    • 0:06:01With that said, there are so many other traditions within CS50,
    • 0:06:04both on campus and off.
    • 0:06:05And in particular, do we try in CS50 to provide not only the academic support
    • 0:06:10structure that you might want going through the class,
    • 0:06:12but also a collective shared community experience.
    • 0:06:15Which is to say in just a few days we'll start off the term formally
    • 0:06:18with CS50 Puzzle Day, which is not only an opportunity
    • 0:06:21to get together with friends, with pizza and prizes
    • 0:06:24and also logic puzzles of sorts, but really to send the message that computer
    • 0:06:27science itself is not about programming, it's not about C,
    • 0:06:30it's not about Python, it's not about programming languages per se,
    • 0:06:33but about problem solving, ever more so collaboratively with other smart people
    • 0:06:38by your side in this class or beyond.
    • 0:06:40And indeed, are there, toward the end of the semester, reinforcements
    • 0:06:44of the same by way of a little something that we call the CS50 Hackathon, which
    • 0:06:47will be an opportunity overnight to dive into your own final projects,
    • 0:06:51the capstone of this course, thereafter followed by the CS50 fair,
    • 0:06:55which will be a campus wide exhibition for students, faculty,
    • 0:06:58and staff across campus of your very own final projects, be it your very own web
    • 0:07:02app or mobile app or anything else you decide to create by term's end.
    • 0:07:07And indeed, the objective at the end of the day,
    • 0:07:10truly with that final project in particular,
    • 0:07:13is going to be to create for yourselves, for your classmates,
    • 0:07:16for attendees, something that we didn't even teach you how to do.
    • 0:07:20And indeed, that will signal ultimately that you're indeed on your way
    • 0:07:23and ready.
    • 0:07:25Toward that end, thought we would give you a sense of CS50's past
    • 0:07:29by way of this short video, if we could dim
    • 0:07:31the lights, that paints a picture of all that awaits here and beyond.
    • 0:07:37[VIDEO PLAYBACK]
    • 0:07:40[MUSIC PLAYING]
    • 0:08:33[END PLAYBACK]
    • 0:08:34DAVID MALAN: All right, so welcome aboard to CS50 and computer science
    • 0:08:38itself.
    • 0:08:38So what is computer science?
    • 0:08:40Well, put simply, it's the study of information.
    • 0:08:42Like, how do you represent it and how do you process it.
    • 0:08:45But more fundamentally, what we'll teach you in this class
    • 0:08:47is computational thinking.
    • 0:08:49That is to say, the application of ideas from computer science
    • 0:08:52to problems of interest to us within the class and problems of interest to you
    • 0:08:56after the class.
    • 0:08:57And so at the end of the day, what computer science really
    • 0:09:00is is about problem solving, ergo that sort of global applicability.
    • 0:09:04And by problem solving, we mean something quite simple.
    • 0:09:07In fact, we can distill it as follows with this mental image.
    • 0:09:10This is problem solving.
    • 0:09:12You've got some problem to solve, thus known as the input
    • 0:09:14that you want to solve.
    • 0:09:15And the goal, of course, to problem solving
    • 0:09:17is to actually produce a solution.
    • 0:09:19So the output in this model would be the solution.
    • 0:09:22The interesting part ultimately is going to be in how you process that input
    • 0:09:26and turn it into that output, ergo solving problems.
    • 0:09:30But before we can do that, we all kind of have to agree how to represent
    • 0:09:33sent these inputs and outputs, especially
    • 0:09:35if we want to do it in a standardized global way using literally computers,
    • 0:09:39be them laptops, desktops, phones, or most any other kind
    • 0:09:42of electronic device nowadays.
    • 0:09:44So how can we do that?
    • 0:09:45Well, there's different ways to represent information in the world.
    • 0:09:48For instance, if I were to take attendance old school style, maybe
    • 0:09:51in a smaller room, I might do 1, 2, 3, 4, 5, 6, 7,
    • 0:09:55and so forth and just count people on my human hands.
    • 0:09:58That's actually known as unary notation, otherwise mathematically known
    • 0:10:02as base one, because you're using your fingers literally
    • 0:10:05in this model as digits.
    • 0:10:07But a little quick question.
    • 0:10:08How high can you count with one human hand?
    • 0:10:12Five is incorrect if you use a different base system than one.
    • 0:10:18So it's obviously correct if you're just using unary and just counting 1, 2, 3,
    • 0:10:224, 5.
    • 0:10:23But I dare say I can come up with more patterns in my human hand
    • 0:10:27alone that would enable me, without a second hand or a couple of feet,
    • 0:10:31to count higher than five.
    • 0:10:33In fact, maybe for those more comfortable,
    • 0:10:35how high could you actually count on a single human hand, perhaps?
    • 0:10:39So 31, believe it or not, is, in fact, the correct answer.
    • 0:10:44But why?
    • 0:10:44Well, here I initially started pretty naively.
    • 0:10:471, 2, 3, 4, 5.
    • 0:10:49And I just combined all of my fingers and counted the collective total.
    • 0:10:52But what if I'm a little more clever and take into
    • 0:10:54account the pattern of fingers that go up.
    • 0:10:56So maybe this is still zero.
    • 0:10:58This is one.
    • 0:10:59But now maybe we just agree universally that this is two.
    • 0:11:03Even though it's just my single pointer finger.
    • 0:11:06Maybe we all just agree that this is three with two fingers up.
    • 0:11:09Maybe we agree that this is often offensive with just one
    • 0:11:12middle finger up, but this would then be four.
    • 0:11:15This could then be five.
    • 0:11:17This could then be six.
    • 0:11:19This could be seven.
    • 0:11:20And if I keep permuting my fingers in this way-- allow me to spoil it--
    • 0:11:23this would be, in fact, 31.
    • 0:11:26But again, why?
    • 0:11:27But the difference here is that we're no longer using unary or base
    • 0:11:31one as a mathematician would say, but rather base two.
    • 0:11:34Because if we take into account not just the total number
    • 0:11:37of fingers that I'm using, but whether each finger is down or up being
    • 0:11:42therefore in two potential states.
    • 0:11:44Down, up, A, B, black, white, however you
    • 0:11:47want to distinguish those two states of the world,
    • 0:11:50you're now operating what's called base two, and perhaps more familiarly,
    • 0:11:53even if you're not a computer person per se, this is the so-called binary system.
    • 0:11:58And odds are, even if you're not a computer science person at all,
    • 0:12:01you probably generally know that computers only understand or speak
    • 0:12:04what alphabet, so to speak?
    • 0:12:07So ones and zeros, zeros and ones, otherwise known as the binary system.
    • 0:12:11And in fact, there's a term of art here that's worth noting.
    • 0:12:14When you're using zeros and ones, which, of course, are a total of two digits,
    • 0:12:18you have binary digits, so to speak-- bi implying two,
    • 0:12:21which means there's two possibilities, zero or one.
    • 0:12:24If we actually get rid of some of these letters and then join these two phrases,
    • 0:12:27here you have a technical term that is a bit.
    • 0:12:30A bit is just a binary digit, which is to say it's a zero or one.
    • 0:12:35And this is in contrast, of course, with the system
    • 0:12:38you and I know as the decimal system.
    • 0:12:40Dec implying 10, because in the real world
    • 0:12:42you and I daily use zero through nine, which is 10 possibilities.
    • 0:12:46Computers only use zero and one, that is to say two bits,
    • 0:12:50to represent information instead.
    • 0:12:52So how do we represent this information, especially when at the end
    • 0:12:54of the day what we're using are indeed computers and electronic devices?
    • 0:12:59Well, if I want to represent zero, I can actually think of this as analogous
    • 0:13:04to the physical world.
    • 0:13:05Maybe I have a light bulb that's off or on controlled
    • 0:13:08by a switch that turns it off or on.
    • 0:13:10So you can think of a binary digit that is a zero as really
    • 0:13:15just being a light bulb that is off.
    • 0:13:17By contrast, if you think of a one in the digital world as, of course,
    • 0:13:22being the second of two possibilities, you
    • 0:13:24can think of that in the human or analog world, the physical world,
    • 0:13:27as being a light bulb that is on.
    • 0:13:30And in fact, what's inside of your Mac, your PC, your Android phone,
    • 0:13:33your iPhone are millions of tiny little light switches
    • 0:13:36known as transistors that just can be turned on or off, on or off.
    • 0:13:41And essentially, you can use those transistors to store information
    • 0:13:44because if you want to store a zero, you turn one of those switches off.
    • 0:13:47If you want to store a one, you turn one of those switches on.
    • 0:13:50Of course, that sort of invites the question, well,
    • 0:13:53how do we count higher than zero or one?
    • 0:13:56Well, we would seem to need to use more than just
    • 0:13:59maybe a single bit, a single light bulb.
    • 0:14:02So if we wanted to count higher than, for instance, zero or one,
    • 0:14:05why don't we go ahead and maybe do this?
    • 0:14:07So just so I have some place to put these,
    • 0:14:10let me borrow some of our actual physical light bulbs
    • 0:14:12here from the stage.
    • 0:14:14And let me propose that now, with three bits on the stage, three light switches,
    • 0:14:20three transistors, whatever metaphor you're most comfortable with, this
    • 0:14:23is how a computer would represent a zero, because all of them are off.
    • 0:14:28So it's off, off, off.
    • 0:14:30But if a computer wanted to count to one, we could do naively this.
    • 0:14:34We could turn this on.
    • 0:14:35If the computer wanted to turn represent two, we could do this.
    • 0:14:39And if a computer wanted to represent three, we could do this.
    • 0:14:43But I'm kind of painting myself into a corner
    • 0:14:46and not using these light bulbs as cleverly as I could,
    • 0:14:49because at the moment I've only counted as high as three.
    • 0:14:52So if I want to count to four, to five, to six,
    • 0:14:54I'm going to need more and more light bulbs.
    • 0:14:56Can we be a little more clever?
    • 0:14:57Well, again, someone else who's among those more comfortable, what's
    • 0:15:01the spoiler here?
    • 0:15:02How high using binary zeros and ones could I
    • 0:15:06count with three light bulbs total?
    • 0:15:08In back?
    • 0:15:09Yeah.
    • 0:15:10So seven here is the answer.
    • 0:15:12And if that, too, you're sort of wondering,
    • 0:15:14how are people figuring out 31 and 7?
    • 0:15:16That's the goal at hand here.
    • 0:15:18So let me do this.
    • 0:15:19Let me turn all of these off again so that my three light bulbs or switches
    • 0:15:23again represent zero.
    • 0:15:25And the first one's easy.
    • 0:15:26This is how a computer would represent the number one.
    • 0:15:29It would be on, off, off.
    • 0:15:32How, though, is a computer going to represent two?
    • 0:15:35Well, just like my proposed finger example.
    • 0:15:37Let's do this.
    • 0:15:38Let's turn this one off and this one on.
    • 0:15:41That is how a computer would represent two.
    • 0:15:43By saying off, on, off.
    • 0:15:46In other words, 010 would be the way to pronounce it digitally.
    • 0:15:50What if I instead want to represent three?
    • 0:15:52That's how on my finger I did this, with two fingers.
    • 0:15:54Well, I'm going to turn this one on.
    • 0:15:56This is three.
    • 0:15:58Now, this will, for those less comfortable, be non-obvious.
    • 0:16:00This now is how I would represent the number four.
    • 0:16:06This is how I would represent five.
    • 0:16:09This is how I would represent six.
    • 0:16:12And this, as per the spoiler, is how I would represent seven.
    • 0:16:17So perhaps very non-obvious what it was I just did
    • 0:16:20or why I chose those patterns.
    • 0:16:22But I dare say if you rewind in your mind's eye or literally later on video,
    • 0:16:26you'll find that I actually did show you eight distinct patterns of light bulbs.
    • 0:16:31The first one was off, off, off.
    • 0:16:33The last one was, on, on, on.
    • 0:16:35And there were another six total in between then.
    • 0:16:37Well, wait, why seven?
    • 0:16:39Well, if you start counting at zero and I claim there's eight possibilities,
    • 0:16:42you can only count from zero to seven, as we will soon see.
    • 0:16:46So how are these patterns coming about and what is it
    • 0:16:49that our computers are actually doing?
    • 0:16:50Well, it's actually doing something a little like this, quite like in decimal.
    • 0:16:55So in the human world, you and I are very
    • 0:16:57much in the habit of using base 10, zero through nine, a.k.a.
    • 0:17:00Decimal.
    • 0:17:01Well, how do we use it instinctively as humans?
    • 0:17:05Well, what's this number obviously on the screen?
    • 0:17:08123.
    • 0:17:09But why is it 123?
    • 0:17:11Like, for years you haven't really thought
    • 0:17:13about why this pattern of symbols or digits on the screen,
    • 0:17:17one, two, three, represents mathematically this number
    • 0:17:20that you know obviously as 123.
    • 0:17:22But if you rewind to grade school, odds are,
    • 0:17:25like me, you were taught that the rightmost digit is in the ones column,
    • 0:17:28this second digit is in the tens column, this digit is in the hundreds column,
    • 0:17:32and so forth.
    • 0:17:33So even though none of us have to do this math explicitly,
    • 0:17:36what you're instantly doing is 100 times 1 plus 10 times
    • 0:17:392 plus 1 times 3, which gives you 100 plus 20 plus 3.
    • 0:17:44Oh, that's why it is 123, because these digits in this order
    • 0:17:50have that significance.
    • 0:17:52The digits to the left have more weight, so to speak,
    • 0:17:54than the digits to the right.
    • 0:17:56So what can we take away from this?
    • 0:17:58Well, let's generalize it first as just any three digit number.
    • 0:18:01So number, number, number.
    • 0:18:02The ones column, the tens column, the hundreds column.
    • 0:18:05But there's some math going on there, and it's not particularly sophisticated.
    • 0:18:08Those are actually powers of 10.
    • 0:18:10So 10 to the 0, 10 to the 1, 10 to the 2, and there's your decimal system.
    • 0:18:16Because the base in this value is a 10, that's
    • 0:18:20because there's 10 possibilities for each of those placeholders,
    • 0:18:23zero through nine.
    • 0:18:25But in the binary world, in the world of computers where all they
    • 0:18:28have are zeros and ones, why?
    • 0:18:30Because all they have physically is transistors.
    • 0:18:32Tiny, tiny, tiny light bulbs that can be off or on.
    • 0:18:35If you only have two digits to play with,
    • 0:18:37the 10 base should, of course, become a two base.
    • 0:18:41And now if we do some math here, 2 to the 0, 2 to the 1, and 2 to the 2,
    • 0:18:45you get the ones column, the twos column, the fours column.
    • 0:18:49And if we keep going 8, 16, 32, 64, 128 and so forth,
    • 0:18:53its powers of 2 instead of powers of 10.
    • 0:18:56But this is to say computers represent information
    • 0:19:00in exactly the same way you and I have since childhood,
    • 0:19:03but they have fewer digits at their disposal,
    • 0:19:06so these columns need to be weighted differently.
    • 0:19:09So we can still count from zero all the way up toward infinity.
    • 0:19:12So what does this mean?
    • 0:19:14Well, here we have three bits on the screen, 000.
    • 0:19:18If we were to convert this now mentally or on paper pencil to decimal,
    • 0:19:22how do we do it?
    • 0:19:23Well, 4 times 0 plus 2 times 0 plus 1 times 0.
    • 0:19:26That gives us the mathematical number you and I know as zero.
    • 0:19:29That was three light bulbs.
    • 0:19:31Off, off, off.
    • 0:19:33Well, what if we turn on one light bulb all the way on the right?
    • 0:19:36What decimal number does this binary number, 001 represent?
    • 0:19:42Just one, because it's 4 times 0, 2 times 0, 1 times 1.
    • 0:19:46Here's where things got more interesting,
    • 0:19:48even if non-obvious in light bulb form or even physical hand form.
    • 0:19:51010 in binary is what in decimal?
    • 0:19:55Two, because it's 2 times 1 and that's it.
    • 0:19:58011 in binary is, of course now three.
    • 0:20:02This is now four.
    • 0:20:03This is now five.
    • 0:20:05This is now six and seven.
    • 0:20:06On, on, on or 111 is the highest we can count with these three bits.
    • 0:20:11All right.
    • 0:20:12So how might a computer intuitively count as high as eight?
    • 0:20:16What do you need to do, presumably?
    • 0:20:18You're going to need to add a bit.
    • 0:20:20So you need another light bulb, another switch.
    • 0:20:22You need more memory, so to speak, to use nomenclature
    • 0:20:24with which you're probably familiar.
    • 0:20:26So in fact, if we change all of those to zero
    • 0:20:28but we give ourself one more bit for a total of four,
    • 0:20:31that's got to be the eighth place because there's just
    • 0:20:33another power of two.
    • 0:20:34So 1000 is the decimal number eight.
    • 0:20:38You don't say 1,000 in binary.
    • 0:20:40You literally say 1000.
    • 0:20:42But that is the number you and I know as eight.
    • 0:20:45And you can keep going up and up and up.
    • 0:20:46And how then computers with Excel or any kind of number crunching software
    • 0:20:51count really high and keep track of really big numbers?
    • 0:20:54The computer just throws more and more transistors at it, more and more
    • 0:20:58bits to count higher and higher and higher than this.
    • 0:21:02It turns out, though, one bit, three bits, even four bits
    • 0:21:05aren't that useful in practice because literally you can count
    • 0:21:08as high as seven or maybe 15 or 31.
    • 0:21:12So more commonly, as is commonly known, is to use a byte of bits instead.
    • 0:21:18How many bits is in a byte, for those familiar?
    • 0:21:21So it's just eight.
    • 0:21:22Why eight?
    • 0:21:22It's just more useful than one or two or three or some other number.
    • 0:21:26And as an aside, it happens to be a power of two, which
    • 0:21:29is just useful electronically as well.
    • 0:21:31So a byte then is just 8 bits.
    • 0:21:33And here are those columns I rattled off off the top of my head.
    • 0:21:36Here is how a computer would represent zero in decimal,
    • 0:21:40but using eight binary digits or bits.
    • 0:21:43Little trivia.
    • 0:21:44And again, this is not what computer science is about,
    • 0:21:46but it helps to know the lower bounds and the upper bounds
    • 0:21:49of these kinds of values.
    • 0:21:51How high can you count with 8 bits or 1 byte if this is zero?
    • 0:21:57Yeah.
    • 0:21:58So it's actually 255.
    • 0:22:00So if I were to change all of these zeros to ones
    • 0:22:02and then do some quick mental or calculator math, 128 plus 64
    • 0:22:07plus 32, 16, 8, 4, 2, and 1 would actually give me 255 total.
    • 0:22:13Plus 0, which gives me 256 total possibilities.
    • 0:22:18So this is only to say-- this is not, again, the kind of math
    • 0:22:21will frequently do, but you'll commonly see
    • 0:22:23in the computer world and programming world powers of two,
    • 0:22:26numbers like 255, 256.
    • 0:22:28Why?
    • 0:22:29Because these are the common units of measures that systems tend to use.
    • 0:22:34So let me pause here and see, with respect to binary, zeros,
    • 0:22:38and ones, transistors and the like, any questions or confusion we can clear up?
    • 0:22:46Oh, really good question.
    • 0:22:47Why are bits just on or off instead of maybe sort of 0%, 50%, 100%
    • 0:22:54by playing with voltages?
    • 0:22:55So the voltage inference of yours is actually correct.
    • 0:22:58That's what computers typically do.
    • 0:23:00Maybe they use 0-ish volts to represent 0, maybe 5-ish volts to represent 1.
    • 0:23:07It turns out it's just really easy to do extremes in computers.
    • 0:23:11If you start to split that range of voltage levels,
    • 0:23:14for those who remember any of their electricity,
    • 0:23:16it just gets harder and harder to be exact.
    • 0:23:18And if you get things a little too murky,
    • 0:23:20you might mistake a zero for a one or a two or a three.
    • 0:23:24So it turns out it's just simpler to use the binary system.
    • 0:23:27But there do exist computers known as ternary computers that actually
    • 0:23:31use three values, zero, one, and two, which is somewhere, of course,
    • 0:23:35between binary and decimal.
    • 0:23:36But you can do different things.
    • 0:23:38It's just simple on and off.
    • 0:23:39In case in point, I don't want to really be dramatic and turn off my computer,
    • 0:23:42but if I pulled out the power plug, that could be off, literally, a.k.a.
    • 0:23:46zero.
    • 0:23:46Plug it back in, that's a one.
    • 0:23:48There's just a cleanliness and simplicity to that.
    • 0:23:52Other questions or confusion that we can clear up?
    • 0:23:57No?
    • 0:23:58OK.
    • 0:23:59So if you're in agreement for the moment that, OK, using just zeros and ones,
    • 0:24:04we can represent any number we want from zero on up, let
    • 0:24:08me propose that we do more useful things with our computers and our pockets
    • 0:24:11and desktops and laps like represent letters,
    • 0:24:14for the sake of Google Docs, Microsoft Word, or any kind of text
    • 0:24:18that we might want to write.
    • 0:24:20So knowing now that computers only contain or only use zeros and ones,
    • 0:24:24and therefore only contain hardware like transistors,
    • 0:24:28how could you represent something like a capital letter
    • 0:24:30A in English inside of a computer?
    • 0:24:34Which, of course, is not a number anymore.
    • 0:24:37Like, what could we do?
    • 0:24:38Yeah?
    • 0:24:38AUDIENCE: We could use the alphabet and then use numbers.
    • 0:24:41DAVID MALAN: OK, yeah.
    • 0:24:42So we could take the alphabet A through Z in English
    • 0:24:44and we could just assign each letter A number.
    • 0:24:46And honestly, that is not only the correct answer,
    • 0:24:48it's really the only answer.
    • 0:24:50Because at the end of the day, if all you
    • 0:24:51have are zeros and ones available to you,
    • 0:24:54that is the entirety of the potential solution to this problem.
    • 0:24:59So it turns out that, yes, capital letter A, some years ago,
    • 0:25:02was decided by a bunch of people in a room shall be represented
    • 0:25:06with this pattern of zeros and ones.
    • 0:25:0801000001.
    • 0:25:11And now, trained as you are to do a bit of quick binary
    • 0:25:14math, what decimal number is used to represent apparently capital A?
    • 0:25:19So 65, because that's 64 plus 1 plus 1 times 1 is 65.
    • 0:25:24What is B?
    • 0:25:24Turns out it's 66.
    • 0:25:26What is C?
    • 0:25:2667.
    • 0:25:27So they kept things simple there on out.
    • 0:25:29Might have been nice if A were zero or maybe a were one.
    • 0:25:32But nope, we're stuck with 65 instead.
    • 0:25:34But everything after that is very much predictable.
    • 0:25:37And in fact, for lowercase letters, there's
    • 0:25:39a whole other set of numbers such as lowercase A happens to be 97,
    • 0:25:46lowercase B happens to be 98, and so forth.
    • 0:25:48But again, this is like CS trivia.
    • 0:25:50But what's important here is that there are indeed contiguous from 65
    • 0:25:54to 66 to 67 on up.
    • 0:25:56That's something we're going to be able to leverage beyond the letter A alone.
    • 0:26:00What is this system?
    • 0:26:01What is this mapping that you yourself propose?
    • 0:26:03It's ASCII, the American Standard Code for Information Interchange.
    • 0:26:06And indeed, it was a bunch of Americans years ago who came up with this system.
    • 0:26:10Unfortunately, at the time, they only allocated 7 and eventually 8 bits total
    • 0:26:17for representing letters, both uppercase and lowercase, numbers
    • 0:26:21on the keyboard as well, punctuation symbols as well.
    • 0:26:24And so per our conversation a moment ago, if the Americans in this room,
    • 0:26:29so to speak, only used 8 bits total, how many different characters can we
    • 0:26:34represent with a computer in this story?
    • 0:26:37So only 255, technically 256 if we, again, start counting from zero.
    • 0:26:43So that's not nearly enough to represent all human languages,
    • 0:26:47but it is enough to represent at least English, among some others.
    • 0:26:50So here, for instance, is a chart of the ASCII mapping.
    • 0:26:54And sure enough, if we zoom in on this column here, 65 is capital A,
    • 0:26:5866 is capital B, dot, dot, dot 72 is H, 73 is I, and so forth.
    • 0:27:03So there is a standardized mapping for at least all of these English letters.
    • 0:27:08Well, suppose you were to receive an email or a text message
    • 0:27:11or like a Google Doc containing this pattern of zeros and ones.
    • 0:27:15So 01001000 and so forth and so forth.
    • 0:27:20So 3 bytes worth.
    • 0:27:22Three sets of 8 bits.
    • 0:27:24That is to say 3 bytes, each of which represents a single letter in ASCII.
    • 0:27:30What message have you received?
    • 0:27:33Well, I'll do the math this time so we don't have to.
    • 0:27:35Suppose what you really received was decimal 72, 73, 33.
    • 0:27:40What message did you just receive?
    • 0:27:44If you recall the previous chart.
    • 0:27:46Hi was in fact correct.
    • 0:27:47Why?
    • 0:27:48Because H is 72, I is 73.
    • 0:27:50And wait a minute, 33.
    • 0:27:51So here's H. Here's I. 33, if we highlight it instead,
    • 0:27:56happens to be an exclamation point.
    • 0:27:58So that is literally what is going on underneath the hood, so to speak,
    • 0:28:01when you get a text message today that literally says in all caps
    • 0:28:04and an exclamation point, HI!
    • 0:28:06Your phone has received at least three bytes, each of which
    • 0:28:10represents a letter of the alphabet.
    • 0:28:12Your computer is quickly doing the mental math
    • 0:28:14to figure out exactly what numbers those are and then
    • 0:28:16looking up in the so-called ASCII chart in its memories, in some sense,
    • 0:28:20what letter should you actually see on the screen there.
    • 0:28:24And so if you were to then display that message,
    • 0:28:28you would see it indeed in English as opposed to those numeric equivalents.
    • 0:28:33How else might we use this then?
    • 0:28:37Well, here again is that chart.
    • 0:28:38And maybe just to vary things, maybe take a little pressure off of me
    • 0:28:40here, why don't we try spelling something else?
    • 0:28:43This time a different three letter word, but maybe eight volunteers.
    • 0:28:47Could we get a bytes' worth of volunteers?
    • 0:28:48And I can sweeten the deal with some stress balls in exchange.
    • 0:28:51You just have to be comfortable coming up on stage and being on the internet.
    • 0:28:54So yes.
    • 0:28:54One, two.
    • 0:28:56How about three, four.
    • 0:28:58How about five, six, seven.
    • 0:29:01And how about eight.
    • 0:29:02Come on up.
    • 0:29:03A round of applause for our volunteers.
    • 0:29:05Yep.
    • 0:29:05[APPLAUSE]
    • 0:29:11All right.
    • 0:29:12So what I'm going to have each of you do is
    • 0:29:14represent a bit in a particular order.
    • 0:29:17So if you want to just, in any order, line
    • 0:29:19yourselves up here facing the audience.
    • 0:29:21Come on over.
    • 0:29:23All right.
    • 0:29:24And we will have you represent-- well, we got to see who ends up where.
    • 0:29:27Scooch this way a little bit.
    • 0:29:29This way, this way.
    • 0:29:30All right.
    • 0:29:31So you shall be the ones place and just hold that in front of you.
    • 0:29:34Twos place.
    • 0:29:36Threes.
    • 0:29:37Fours place.
    • 0:29:39Eights place.
    • 0:29:4016, 32, 64, and 128.
    • 0:29:46And just compress yourselves a little bit if you could.
    • 0:29:49So each of these folks represents a bit in a particular place.
    • 0:29:53And let's say this.
    • 0:29:54If you're just standing there uncomfortably without any hand raise,
    • 0:29:57we'll assume that you're representing a zero, quite simply.
    • 0:30:00If your hand goes up, though, the audience
    • 0:30:02should assume that you're representing a one.
    • 0:30:04And therefore, what we'll do is spell out a three letter word,
    • 0:30:06and on each round of this, you'll either stay, stay like this,
    • 0:30:10or you'll raise your hand.
    • 0:30:11But first, let's actually meet some of our volunteers
    • 0:30:14here, starting with position number one, if you'd like to say your name,
    • 0:30:18perhaps where you're from and/or studying.
    • 0:30:20AUDIENCE: Hi.
    • 0:30:20My name is Brooke.
    • 0:30:21I'm from Indiana, and I'm studying biology and computer science.
    • 0:30:26DAVID MALAN: Nice.
    • 0:30:27Welcome.
    • 0:30:28AUDIENCE: Hi, I'm Becca.
    • 0:30:29I'm from, like, Maryland, DC area, and I'm studying electrical engineering.
    • 0:30:34DAVID MALAN: Welcome.
    • 0:30:35AUDIENCE: Hi, I'm Addison.
    • 0:30:36I'm from Maryland.
    • 0:30:37I'm studying engineering.
    • 0:30:40AUDIENCE: Hi.
    • 0:30:41I'm Sharon.
    • 0:30:41I'm from Rwanda and I'm studying CS and math.
    • 0:30:44DAVID MALAN: Welcome.
    • 0:30:45AUDIENCE: Hi, I'm Grace.
    • 0:30:46I'm from Alabama and I'm studying electrical engineering.
    • 0:30:49DAVID MALAN: Welcome.
    • 0:30:50AUDIENCE: Hi, I'm Angelina.
    • 0:30:51I'm from Maryland.
    • 0:30:52And also, I stay in Matthews.
    • 0:30:53DAVID MALAN: Nice.
    • 0:30:54Matthews.
    • 0:30:55Nice.
    • 0:30:56[APPLAUSE]
    • 0:30:58AUDIENCE: And I'm studying applied math and econ, as well as
    • 0:31:00environmental science and public policy.
    • 0:31:02DAVID MALAN: Welcome.
    • 0:31:03AUDIENCE: I'm Owen Bells and I'm from rural Virginia and I'm studying CS.
    • 0:31:07DAVID MALAN: Nice, welcome.
    • 0:31:08And?
    • 0:31:09AUDIENCE: My name is Max.
    • 0:31:10I'm from London.
    • 0:31:11I'm also staying in Matthews and I'm studying computer science
    • 0:31:14and neuroscience.
    • 0:31:15Thank you.
    • 0:31:16DAVID MALAN: Welcome aboard as well.
    • 0:31:17If you're wondering, too, why I was wearing
    • 0:31:19these glasses at the start-- so very common on the internet nowadays
    • 0:31:21as these POV videos.
    • 0:31:22So it turns out these Ray-Bans actually record video footage,
    • 0:31:25and we have a couple of them, and we'd thought we would offer them
    • 0:31:27to a couple of volunteers.
    • 0:31:28If anyone wants to record their point of view for everyone here.
    • 0:31:32And Vlad here is going to help make sure they're recording.
    • 0:31:34Second volunteer.
    • 0:31:35Yes, number two.
    • 0:31:36All right.
    • 0:31:37So as Vlad gets those set, on the backs of your pieces of paper
    • 0:31:41you have instructions for the following three rounds.
    • 0:31:44Each round represents a letter.
    • 0:31:45The audience participation part of this is
    • 0:31:47to actually do the mental math to figure out what number these volunteers are
    • 0:31:51representing.
    • 0:31:52So go ahead and execute round one, either keeping your hand down or raising
    • 0:31:58it appropriately.
    • 0:32:01OK.
    • 0:32:02What number are our volunteers here representing?
    • 0:32:05AUDIENCE: 66.
    • 0:32:06DAVID MALAN: 66, because we have a 64 plus a 2.
    • 0:32:09That then maps to what ASCII letter?
    • 0:32:11AUDIENCE: B.
    • 0:32:11DAVID MALAN: B was the first letter.
    • 0:32:13OK, hands down.
    • 0:32:14Round two, go.
    • 0:32:16A little harder.
    • 0:32:18What's now being represented?
    • 0:32:21AUDIENCE: 79.
    • 0:32:23DAVID MALAN: I'm starting to hear it.
    • 0:32:2479 is in fact correct.
    • 0:32:2779, because we have a 64 and an 8 and 4 and 2 and a 1.
    • 0:32:32So if it's a 79, we have the ASCII letter O.
    • 0:32:36So we've got BO, and then lastly, third round.
    • 0:32:39Go.
    • 0:32:42We have 01010111.
    • 0:32:47What number is this?
    • 0:32:48AUDIENCE: 87.
    • 0:32:49DAVID MALAN: 87.
    • 0:32:50Which spells the letter?
    • 0:32:51AUDIENCE: W.
    • 0:32:52DAVID MALAN: W. Which spells the word?
    • 0:32:54AUDIENCE: Bow.
    • 0:32:55DAVID MALAN: Not bow.
    • 0:32:56Take a bow if you could.
    • 0:32:57All right.
    • 0:32:58A round of applause for our volunteers here.
    • 0:33:00[APPLAUSE]
    • 0:33:01And come on off this way and help yourself to a CS50 stress ball.
    • 0:33:06Thank you to our volunteers.
    • 0:33:08So this is only to say we've now agreed on how we can represent numbers
    • 0:33:11from zero on up.
    • 0:33:12We've agreed on how we can represent letters.
    • 0:33:14But at least letters using ASCII, and in fact, these
    • 0:33:17are more than just decoration.
    • 0:33:18In fact, it's a little bit of trivia by lecture's end.
    • 0:33:21If you to come up for your very own CS50 stress ball,
    • 0:33:24turns out there are 64 light bulbs at the foot of the stage here.
    • 0:33:27If you break them down into 8 byte or single--
    • 0:33:318 bit or single byte chunks, there's an eight letter word
    • 0:33:35that happens to be spelled out today using this here ASCII chart.
    • 0:33:38So today's mystery is what exactly is that there word.
    • 0:33:42But of course, if you have only 8 bits, you can only represent, like,
    • 0:33:46256 characters, which sounds like plenty for English, and indeed, it is.
    • 0:33:51Zero through nine, A through B, capital and lowercase,
    • 0:33:54uppercase and lowercase, as well as punctuation.
    • 0:33:56But there's so many other human languages
    • 0:33:58in the world that have other characters.
    • 0:34:00For instance, we have not just the English alphabet
    • 0:34:03we might see here on a US English keyboard.
    • 0:34:05We have accented characters, we have various Asian languages
    • 0:34:09have even many more glyphs.
    • 0:34:10We need more than 256 possible characters.
    • 0:34:13And so nowadays computers do not just use 7 or even 8 bits.
    • 0:34:18They might use 8 bits for some letters, like all of the English letters.
    • 0:34:22They might use 16 bits for certain other languages.
    • 0:34:25Maybe even 24 or 32 bits.
    • 0:34:28And fun fact, if you have 32 bits--
    • 0:34:30and we have more than that on the stage.
    • 0:34:32If you've got 32 bits, you can actually represent
    • 0:34:35as many as 4 billion possible characters, which is quite a bit.
    • 0:34:40No pun intended.
    • 0:34:41So what else can we represent?
    • 0:34:43Well, the goal of this system, not just ASCII,
    • 0:34:46but something known as Unicode, which is a newer standard,
    • 0:34:49is to be backwards compatible with ASCII.
    • 0:34:51So humans left all of those other numbers alone, 65, 66, 67 and so forth,
    • 0:34:56but they added to it a super set of representations
    • 0:34:59that maybe are 16, 24, or 32 bits.
    • 0:35:03The goal being to be able digitally to represent all human languages, past,
    • 0:35:08present, and future, and even through pictograms, things
    • 0:35:12like smiley faces and the like, even people, places, things and emotions that
    • 0:35:17transcend human language.
    • 0:35:19And in fact, odds are within the past few minutes or hours, most of you
    • 0:35:23have used one or more of these here emoji, these pictograms, which it turns
    • 0:35:27out are just characters on a keyboard.
    • 0:35:30You might have to hit a special button to pull up that form of the keyboard,
    • 0:35:34but these are just here characters.
    • 0:35:36And so these emoji have exploded in popularity
    • 0:35:38for a number of reasons, one of which is, my God, what are we
    • 0:35:41going to do with 4 billion possible patterns of zeros and ones?
    • 0:35:44We can start to have some fun with it and represent things
    • 0:35:47beyond English and human languages alone.
    • 0:35:50Now, as an aside, when it comes to Unicode,
    • 0:35:53it turns out Unicode, years ago, standardized this pattern of 32 zeros
    • 0:35:58and ones to represent just one of those emoji.
    • 0:36:02So emoji tend to use even more bits here.
    • 0:36:04Anyone know what decimal number this is?
    • 0:36:08This is not a fun mathematical exercise.
    • 0:36:09The spoiler is 4,036,991,106 is the decimal number that actually represents,
    • 0:36:17as of present, the most popular emoji in the world.
    • 0:36:21Does anyone want to hazard a guess what emoji this here number represents?
    • 0:36:27AUDIENCE: Heart.
    • 0:36:27DAVID MALAN: Heart?
    • 0:36:28Hearts?
    • 0:36:29No, but it's actually this so-called face with tears of joy.
    • 0:36:33So perhaps think about the frequency with which you send that one.
    • 0:36:36And even though it's obviously a picture on the screen, sure,
    • 0:36:39it actually is more like a font, because underneath the hood,
    • 0:36:43it's indeed just a pattern of zeros and ones or a decimal number
    • 0:36:45that the computer is storing.
    • 0:36:47But the computer, be it Mac OS or Windows or iOS or Android,
    • 0:36:51know to display that pattern as this here picture.
    • 0:36:54But the pictures might look different depending on the hardware.
    • 0:36:57Why?
    • 0:36:57Because there's companies like Google and Microsoft and Meta and others
    • 0:37:01that have their own artists on staff as employees,
    • 0:37:04and those artists interpret the descriptions
    • 0:37:07like face with tears of joy differently.
    • 0:37:09So those of you with an Android phone actually see face with tears of joy
    • 0:37:13looking a little something like this.
    • 0:37:14And if you have Telegram, for instance, installed on your phone,
    • 0:37:17it's even more animated than that.
    • 0:37:19It's this here emoji using the same pattern of zeros and ones.
    • 0:37:23So different artists render these here emoji in different ways,
    • 0:37:27but all they are here are patterns.
    • 0:37:29Now, for all of the other answers, save one that was shouted out a moment ago,
    • 0:37:34this is a sort of cloud diagram of the most popular emoji as
    • 0:37:38of a couple of years ago per Unicode, whereby the size of the emoji
    • 0:37:42indicates its relative popularity.
    • 0:37:44So heart, I did here over here, is indeed
    • 0:37:46one of the most popular ones as well.
    • 0:37:49Question?
    • 0:37:50AUDIENCE: Why do certain emojis show up [INAUDIBLE]?
    • 0:37:53DAVID MALAN: Oh, really good question.
    • 0:37:54Why do certain emoji not show up on one device or another?
    • 0:37:57It depends on how recent the software is.
    • 0:37:59Pretty much every year the humans behind the Unicode consortium
    • 0:38:03release new emoji.
    • 0:38:04Which is to say they decide that this other pattern will
    • 0:38:07represent this new emoji, this other pattern will represent this new emoji.
    • 0:38:10And unless you update your phone, your laptop,
    • 0:38:13your desktop to the very latest software and the manufacturer of that device
    • 0:38:17or software also updates by hiring an artist
    • 0:38:20to draw those pictures in their own fonts, in their own style,
    • 0:38:23you're going to see usually just an empty black square or maybe just
    • 0:38:26a black and white heart instead of something more colorful.
    • 0:38:29Really just placeholders, because, it's as though you
    • 0:38:31don't have the right font installed or really,
    • 0:38:33you have an older version of that same font installed.
    • 0:38:36But it's become sort of an annual tradition that new and more emoji
    • 0:38:40are released every year, which is among the reasons why these updates contain
    • 0:38:44more and more.
    • 0:38:45Yeah?
    • 0:38:46AUDIENCE: How do you represent color in bytes?
    • 0:38:49DAVID MALAN: That is an amazing segue.
    • 0:38:50How do you represent color in bytes?
    • 0:38:53Well, you use RGB, which happens to be, by coincidence, the next slide.
    • 0:38:57So let's again, recap.
    • 0:38:59We know how to represent letters.
    • 0:39:00We know how to represent numbers.
    • 0:39:02We can even represent emoji.
    • 0:39:03But those emoji technically on the screen
    • 0:39:05are, of course, composed of colors, like a whole bunch of yellow
    • 0:39:07for that there smiley face?
    • 0:39:09How do computers, then, using only zeros and ones, represent colors?
    • 0:39:13Well, by convention, they typically use a system that, by an acronym,
    • 0:39:16is called RGB.
    • 0:39:17Red, green, blue.
    • 0:39:19And this is to say that a computer, to represent a single dot on the screen--
    • 0:39:23maybe this one, this one, this one-- will allocate some number of bits
    • 0:39:28or some number of bytes to represent the color of just that, their dot, otherwise
    • 0:39:33known as a pixel.
    • 0:39:34You can actually see pixels on your phone or even on your TV or monitor.
    • 0:39:37If you go really close, especially if it's an older monitor,
    • 0:39:40you can see the tiny little squares.
    • 0:39:42Each of those has some number of bits telling the device what color to use.
    • 0:39:47In particular, these devices typically use three numbers in total, three bytes.
    • 0:39:53So that is to say 24 bits per pixel.
    • 0:39:56And they do this.
    • 0:39:57If you were to represent a single dot on the screen using these three
    • 0:40:00numbers, just by intent here, this is 72, 73,
    • 0:40:0433, which in the context of a text message, an email,
    • 0:40:07a Google Doc represents, of course, hi, textually.
    • 0:40:11What if a computer uses that same pattern
    • 0:40:13of zeros and ones, that is the same pattern of decimal digits,
    • 0:40:17to represent the color on a screen?
    • 0:40:19Which is germane if you're opening an image using Photoshop.
    • 0:40:22So using a different piece of software that
    • 0:40:24knows about colors and images and not just text.
    • 0:40:27Well, this would imply that you want that dot on the screen
    • 0:40:30to have a medium amount of red, a medium amount of green,
    • 0:40:34and a little bit of blue.
    • 0:40:35Why do I say medium and little?
    • 0:40:37Well, again, if each of these numbers is using 8 bits or 1 byte,
    • 0:40:41the highest we can count, as we discovered, was 255.
    • 0:40:45So I'm kind of averaging here.
    • 0:40:46So 72 at a 255 feels to me like a medium amount of red.
    • 0:40:5033 feels relatively little blue.
    • 0:40:53But if now the computer combines those wavelengths of light, so to speak,
    • 0:40:58a medium amount of red, medium amount of green,
    • 0:41:00a little bit of blue, what you get is the color code for a single dot.
    • 0:41:03And does anyone want to guess what color roughly this represents,
    • 0:41:07these three bytes?
    • 0:41:10AUDIENCE: White.
    • 0:41:10AUDIENCE: Purple.
    • 0:41:11DAVID MALAN: Not white, not purple.
    • 0:41:12AUDIENCE: Brown.
    • 0:41:13DAVID MALAN: Not brown.
    • 0:41:14AUDIENCE: Yellow.
    • 0:41:14DAVID MALAN: Yellow, in fact, is the answer.
    • 0:41:16So it represents in a single pixel roughly this shade here of yellow.
    • 0:41:21Which is to say, if we look back at any of those emoji, which, again,
    • 0:41:25are represented by patterns of zeros and ones,
    • 0:41:27but you and I as humans perceive them as images on the screen--
    • 0:41:31let me actually go ahead and zoom and zoom in further
    • 0:41:33to one such sample emoji.
    • 0:41:35And when you zoom in far enough or you put the phone close enough to your face,
    • 0:41:38you can actually see all of those little dots known
    • 0:41:41as pixels, all of the little squares.
    • 0:41:43And given that so many of these pixels are yellow,
    • 0:41:46that is to say that that pattern of three bytes,
    • 0:41:4972, 73, 33, is used to represent this pixel.
    • 0:41:54Another 3 identical bytes are used to represent this pixel, this one,
    • 0:41:58this one, and so forth.
    • 0:41:59So now if you've taken digital photos on your phone or a camera,
    • 0:42:02you're probably generally familiar from the internet and hardware
    • 0:42:05today that a photograph is, what, 1 megabyte, 10 megabytes depending
    • 0:42:10on the resolution of it?
    • 0:42:12Well, megabyte means millions of bytes.
    • 0:42:14Where are all of these bytes inside of these photographs
    • 0:42:17or these images you're taking or downloading?
    • 0:42:19They correspond to every one of the single pixels on the screen.
    • 0:42:24There's at least three bytes being used to represent every one of those dots.
    • 0:42:30As an aside, bit of a white lie because nowadays there's
    • 0:42:32fancy compression software that can use fewer than that many bytes.
    • 0:42:36But in general, that's where all of those bytes, those millions of bytes
    • 0:42:40are coming from.
    • 0:42:41So how is that for an answer to how do we represent colors?
    • 0:42:45Thank you.
    • 0:42:46So if we agreed now that there's this way and perhaps
    • 0:42:50others to represent colors, well, how do we
    • 0:42:52represent not just images, but videos?
    • 0:42:55Well, videos once upon a time, or movies, were called motion pictures.
    • 0:42:59So motion pictures with motion.
    • 0:43:02Why is that?
    • 0:43:02Well, it's analogous to growing up.
    • 0:43:04If you ever played with one of these picture books-- and in fact,
    • 0:43:06there's memes nowadays that have made these popular again,
    • 0:43:09whereby why you have a whole bunch of images on individual sheets of paper.
    • 0:43:14And if you flip through them fast enough,
    • 0:43:16your human mind and eyes perceive it as actual motion,
    • 0:43:20even though you're just seeing image, image, image, image, image, image.
    • 0:43:24But it's so fast, it looks like motion.
    • 0:43:26That's all a video is on your screen.
    • 0:43:28That's all a film is on your TV.
    • 0:43:30It is not in fact, continuous motion.
    • 0:43:33It's maybe 30 frames or images per second, maybe 24 frames
    • 0:43:37or images per second.
    • 0:43:39Which is to say, we know how to represent numbers,
    • 0:43:41we know how to represent letters, we know how
    • 0:43:43to represent colors and thus images.
    • 0:43:45Now we kind of get videos for free because it's just more of the same.
    • 0:43:49Use more and more of those patterns.
    • 0:43:51Why are videos so darn large?
    • 0:43:53Why are they gigabytes to download, billions of bytes?
    • 0:43:56Because there's so many darn images.
    • 0:43:5830 some odd images per second in those kinds of videos.
    • 0:44:02And maybe lastly, just to top off our multimedia,
    • 0:44:05how could you represent sound?
    • 0:44:08Maybe musicians in the room.
    • 0:44:10How, using only zeros and ones, could you represent something
    • 0:44:13as sonorous as music?
    • 0:44:17Something analog as digital.
    • 0:44:18Yeah?
    • 0:44:19AUDIENCE: So each number corresponds to a frequency.
    • 0:44:21DAVID MALAN: Yeah.
    • 0:44:21So each number that we store in the computer
    • 0:44:23could correspond to a certain frequency, which
    • 0:44:25has a direct relationship to the sound or the pitch of a note.
    • 0:44:29For instance, in the world of piano and many other instruments,
    • 0:44:32you've got like your A, your B, your C, maybe you have sharps and flats as well.
    • 0:44:35We could just agree, like the ASCII people
    • 0:44:37did years ago, to represent the musical note A, let's use
    • 0:44:41this pattern, musical note A-sharp, let's use this pattern and so forth.
    • 0:44:45But maybe pitch alone or frequency alone is not enough.
    • 0:44:48Maybe we need that number, but maybe a second number
    • 0:44:51for the volume, the sort of digital equivalent of how hard
    • 0:44:54are you hitting the key on the piano.
    • 0:44:55Maybe a third number for how long are you holding the key down.
    • 0:44:59So maybe the pitch and the volume and the duration, kind of like RGB,
    • 0:45:05we could use three bytes to represent every musical note in some piece.
    • 0:45:10And if we wanted to keep track of what instrument should
    • 0:45:13be played by the computer to sound that music,
    • 0:45:16well, maybe that's just a fourth byte or something else as well.
    • 0:45:19Which is to say, at the end of the day, all
    • 0:45:21we have are these zeros and ones to throw at the problem.
    • 0:45:26So for now, that's it for representing information.
    • 0:45:29We've got our numbers, we've got our letters,
    • 0:45:31we've got our colors and images, our videos, and now sound.
    • 0:45:35Any questions on how computers, then, are representing, as promised,
    • 0:45:40those inputs and outputs using just zeros and ones?
    • 0:45:45Yeah, in the middle.
    • 0:45:47AUDIENCE: The computer is taking it as input.
    • 0:45:49DAVID MALAN: Correct.
    • 0:45:50So the computer is taking as input at the end of the day, zeros and ones
    • 0:45:53and is outputting zeros and ones.
    • 0:45:54However, as we'll learn in this class, by writing software,
    • 0:45:58by writing code that understands those zeros and ones we will enjoy
    • 0:46:02not just literally seeing zeros and ones,
    • 0:46:04we will see A, B, C, we will see colors, we will see video,
    • 0:46:08we will hear sounds so long as we write the code to interpret those zeros
    • 0:46:12and ones.
    • 0:46:12And indeed, it's worth noting now that same pattern
    • 0:46:15I keep using for an example, 72, 73, 33, how does a computer know?
    • 0:46:19Is that the message hi?
    • 0:46:21Is that the color yellow?
    • 0:46:22Is it a dot in a video alone?
    • 0:46:25Just depends on the context.
    • 0:46:26Simply put, if you're opening that pattern of zeros and ones
    • 0:46:30with Excel or a calculator program, odds are
    • 0:46:33the software will interpret those three bytes as numbers, of course.
    • 0:46:37If, though, you open that same pattern in a text messaging program,
    • 0:46:40Google Docs, Microsoft Word, that same pattern
    • 0:46:43will be interpreted as a sequence of letters.
    • 0:46:46Instead, if you open Photoshop, that same pattern,
    • 0:46:48you'll probably see a single dot that happens to be yellow.
    • 0:46:52Conversely, once you yourself are a programmer or even better programmer,
    • 0:46:56you will be able to write in code how you want the computer to treat
    • 0:47:00these patterns of zeros and ones.
    • 0:47:02You can essentially tell the computer, use this to store a number or a letter
    • 0:47:07or a color or something else.
    • 0:47:09That's the power the programmer themselves have at the end of the day.
    • 0:47:14Other questions on representing things with bits?
    • 0:47:19No?
    • 0:47:19All right.
    • 0:47:20So lastly, then, in this middle of this black box, so to speak,
    • 0:47:25is the sort of secret sauce that solves problems,
    • 0:47:27that converts those inputs to outputs, those problems to solutions.
    • 0:47:31So what is an algorithm?
    • 0:47:32It's really just step by step instructions for solving some problem.
    • 0:47:36And indeed, I think back to my own first time in CS50
    • 0:47:39where we learned the same from Professor Brian Kernighan.
    • 0:47:42And as luck would have it, just had my 25th reunion where we pulled some video
    • 0:47:45footage from 1996.
    • 0:47:47And so we're actually fortunate to have the very first few minutes of CS50
    • 0:47:52over 25 years ago when I myself took it.
    • 0:47:55But the lessons back then, as today, are fundamentally the same.
    • 0:47:59And what's important, indeed, is to not only express yourself correctly,
    • 0:48:03but precisely, as we'll explore today.
    • 0:48:06This then is Professor Brian Kernighan, who,
    • 0:48:09years ago, very memorably introduced us and my classmates to algorithms
    • 0:48:13by actually, in class, shaving his beard.
    • 0:48:17If we could dim the lights here for Brian.
    • 0:48:19[VIDEO PLAYBACK]
    • 0:48:20- The other thing that we're going to talk about in this class
    • 0:48:22is the notion of an algorithm.
    • 0:48:24An algorithm is a very precise description of how to do something.
    • 0:48:27And the operative word there is precise.
    • 0:48:29It has to be very, very, very, very precise.
    • 0:48:31And the task that I'm going to do is that I'm
    • 0:48:33going to trim my beard, which has gotten out of whack.
    • 0:48:40[APPLAUSE]
    • 0:48:45And I brought a variety of things which one might use to trim beards with.
    • 0:48:56[LAUGHTER]
    • 0:49:01[APPLAUSE]
    • 0:49:12[END PLAYBACK]
    • 0:49:13DAVID MALAN: So suffice it to say, I don't have much of a beard.
    • 0:49:15But I do have this here other technology known once upon a time as a phone book.
    • 0:49:20And these phone books, of course, have lots of information in them.
    • 0:49:22Happen to be storing numbers and letters in particular.
    • 0:49:25For those unfamiliar, they are storing human's names from A to Z
    • 0:49:29here in English and associated with everyone's name is a number.
    • 0:49:32So even if you've never had occasion to physically use this kind of device,
    • 0:49:35turns out it's pretty much equivalent to the contacts or the address book app
    • 0:49:39on your iOS phone or your Android phone as well.
    • 0:49:41Why?
    • 0:49:41Because if you pull up your contacts, of course,
    • 0:49:43you see some familiar names here alphabetized by first name or last name.
    • 0:49:47And if you click on any of those names, you
    • 0:49:49reach the person you're presumably trying to call or text.
    • 0:49:52Pictured here then is John Harvard's, whose number here is plus
    • 0:49:551-949-468-2750, which you're welcome to call or text at your leisure.
    • 0:49:59But here is John Harvard that's partway through the phone book digitally.
    • 0:50:04Well, it turns out that physically in the phone book,
    • 0:50:06we might use an algorithm, step by step instructions,
    • 0:50:09for finding John Harvard in pretty much the same way as iOS, Android,
    • 0:50:14Mac OS, Windows, or other operating systems themselves use.
    • 0:50:17So I could, when looking for John Harvard, first name, starting with J,
    • 0:50:21I could start at the beginning of the phone book
    • 0:50:23and start looking page by page by page for John Harvard.
    • 0:50:28And if he's there, I can call.
    • 0:50:30This is an algorithm.
    • 0:50:31It's indeed step by step, but that was a bug.
    • 0:50:33A few pages turned.
    • 0:50:34But is this algorithm correct?
    • 0:50:38Step by step, assuming I'm paying attention.
    • 0:50:41So yes, if John Harvard is in here, I will eventually
    • 0:50:44find him once I get to the J section.
    • 0:50:46Now, this is a little tedious.
    • 0:50:47It's going to take a while.
    • 0:50:48A few dozen, a few hundred pages.
    • 0:50:50So maybe I could do things a little smarter from grade school, like 2, 4, 6,
    • 0:50:558, 10, 12, 14, 16, and so forth, going twice as fast.
    • 0:51:00Is that algorithm correct?
    • 0:51:01So no, but why?
    • 0:51:03AUDIENCE: You could miss it.
    • 0:51:04DAVID MALAN: I could miss him, right?
    • 0:51:05I could just get unlucky, really, with 50/50 probability,
    • 0:51:08because John Harvard could be sandwiched between two pages.
    • 0:51:11Now, this isn't a complete loss, this algorithm.
    • 0:51:14Maybe what I could do is if I get past the J section to K,
    • 0:51:18I could double back at least one page just
    • 0:51:21to make sure I didn't miss John Harvard.
    • 0:51:23So I can still go twice as fast plus an extra step just
    • 0:51:26to make sure I didn't mess up.
    • 0:51:28So the first algorithm might take as many pages
    • 0:51:30as there are in the phone book.
    • 0:51:32So if this phone book has a thousand pages, in the worst case, if I'm not
    • 0:51:35looking for John Harvard, but someone whose name starts with Z,
    • 0:51:38might take me a thousand pages to actually get there.
    • 0:51:41Second algorithm, twice as fast.
    • 0:51:43Literally, it might take me 500 plus one step
    • 0:51:46to get there because I'm going two at a time,
    • 0:51:48so as long as I indeed fix that bug.
    • 0:51:50But what we used to do back in the day and what
    • 0:51:52your phone is doing today, albeit digitally,
    • 0:51:55is going roughly to the middle of the phone book, looking down and realizing,
    • 0:51:59oh, I'm accidentally in the M section, so halfway through the phone book.
    • 0:52:03But what do I now know about John Harvard?
    • 0:52:05Is he to the left or to the right?
    • 0:52:07So he's obviously to the left, because J comes before M. So what
    • 0:52:11I can do literally and what your computer does
    • 0:52:13figuratively is tear the problem in half, throw half of the problem
    • 0:52:17away, leaving us now with the same fundamental problem,
    • 0:52:21but it's half as big.
    • 0:52:22So I've gone from a thousand pages suddenly to 500 pages.
    • 0:52:26And compare this to the other two, 1,000 pages, 999, 998, versus 1,000 pages,
    • 0:52:33998, 996, 994.
    • 0:52:36That's still slow.
    • 0:52:37I went from 1,000 to 500 in just one step of this algorithm.
    • 0:52:41What do I do next?
    • 0:52:42I go roughly to the middle here.
    • 0:52:43Oh, I went a little too far.
    • 0:52:45I'm in the E section now.
    • 0:52:46So is John Harvard to the left or right now?
    • 0:52:49So he's to the right.
    • 0:52:50So I can again tear the problem in half, throw the left half away,
    • 0:52:53knowing now that John Harvard must alphabetically be in here.
    • 0:52:56And I can divide and divide and divide and conquer this problem again and again
    • 0:53:01by using that heuristic of going left or going right.
    • 0:53:04And I dare say, if I do this correctly, I'll
    • 0:53:06eventually be left with one single page on which John Harvard's number actually
    • 0:53:10is.
    • 0:53:11Or maybe he's not in the phone book at all.
    • 0:53:14So how many steps maximally might that third and final algorithm take?
    • 0:53:19It's not a thousand.
    • 0:53:20It's not even 500 or 501.
    • 0:53:22How many times can you divide a thousand pages in half again and again
    • 0:53:27and again, roughly?
    • 0:53:30AUDIENCE: I want to say nine.
    • 0:53:31DAVID MALAN: So 9, 10.
    • 0:53:32So typically 10 times, give or take.
    • 0:53:34There's a bit of rounding there because it's not a perfect power of two,
    • 0:53:37but roughly 10 times.
    • 0:53:39Like, that is fundamentally better than both of the two algorithms
    • 0:53:43because I go from a thousand pages to 500 to 250 to 125 and so
    • 0:53:48forth, literally halving the problem again and again.
    • 0:53:52So we can actually appreciate and see this even more so graphically.
    • 0:53:56And this is among the things we'll do later in the term
    • 0:53:58when we speak to not only writing correct code,
    • 0:54:01but is your code well designed?
    • 0:54:03Is it better than your previous code?
    • 0:54:06Is it better than someone else's code?
    • 0:54:07Is it better than some other product?
    • 0:54:09If you have given more thought to the algorithms and the quality thereof,
    • 0:54:13you can perhaps minimize the time required to solve problems
    • 0:54:17but no less correctly.
    • 0:54:18So if we have a simple xy plot here, on the y-axis or vertical
    • 0:54:21is the amount of time to solve in whatever unit
    • 0:54:23of measure, seconds, pages, however you want to count.
    • 0:54:26On the horizontal or x-axis is the size of the problem measured
    • 0:54:30in, for instance, numbers of pages.
    • 0:54:32So this would mean zero pages in the phone book.
    • 0:54:35This would mean a lot of pages in the phone book.
    • 0:54:37This would mean no time to solve.
    • 0:54:39This would mean a lot of time to solve.
    • 0:54:40What's the relationship then, among those three algorithms?
    • 0:54:43Well, the first one is essentially a straight line, a slope of one.
    • 0:54:47And if the phone book has n pages in it, we'll
    • 0:54:50describe the slope here as essentially 1 over 1 for the algorithm
    • 0:54:54with the first algorithm, turning page by page by page.
    • 0:54:58Which is to say, if we were to add one more page to the phone book next year,
    • 0:55:02first algorithm is going to take one more step.
    • 0:55:05But the second algorithm is definitely better.
    • 0:55:07It's definitely faster, but it's still a straight line.
    • 0:55:10So it's going to take roughly n over 2 steps on average, because you only
    • 0:55:14have to go through half of the phone book
    • 0:55:15because you're going two pages at a time,
    • 0:55:17instead of the whole phone book in the worst case,
    • 0:55:19if someone's name is Z, to go through every page in total.
    • 0:55:23So if we actually compare these-- let me just draw some dashed lines.
    • 0:55:26Suppose that you have this many pages in the phone book.
    • 0:55:29If you just draw this vertical white line here,
    • 0:55:31it's going to take this much time in red using the first algorithm,
    • 0:55:35but it's going to literally take half as much time
    • 0:55:37in yellow for the second algorithm because you're literally
    • 0:55:39going two pages at once.
    • 0:55:41But the third and final algorithm is a fundamentally different shape.
    • 0:55:45It instead looks a little something like this.
    • 0:55:48It looks like it's flatter and flatter and flatter.
    • 0:55:51It's always increasing.
    • 0:55:52It never gets perfectly flat.
    • 0:55:54But it grows so much more slowly as a function of phone book size.
    • 0:55:59And for those who recall their logarithms,
    • 0:56:02this would be described as log base 2 of n.
    • 0:56:04And in fact, that's where the math came from.
    • 0:56:06Log base 2 of 1,000 is roughly 10 in total,
    • 0:56:10even if you need a calculator to confirm as much.
    • 0:56:12But this shape is fundamentally different.
    • 0:56:15Why?
    • 0:56:16Well, suppose that Cambridge, where we are, and Allston,
    • 0:56:18the town across the street next year, combine their two phone books.
    • 0:56:21And they go from a thousand pages each to one phone book with 2,000 pages.
    • 0:56:25The first algorithm is going to literally take twice
    • 0:56:27as many steps or pages.
    • 0:56:29Second algorithm is going to take half as many or 50% more
    • 0:56:33because you're going two at a time.
    • 0:56:34But the third algorithm is going to barely miss a beat.
    • 0:56:37Why?
    • 0:56:38Because if this is a thousand pages here and 2,000 pages is over there,
    • 0:56:42just inferring from the shape of the green line,
    • 0:56:45it's not going to be much higher on the vertical axis than the other two were.
    • 0:56:50So more specifically, if you have a 2,000 page phone book next year,
    • 0:56:55how many more steps will it take you using that third and final algorithm?
    • 0:57:00Just one, because you'll divide and conquer a 2,000 page phone book
    • 0:57:03into a 1,000 page phone book, and then you're back at the original story.
    • 0:57:07And that's the sort of power of learning algorithms.
    • 0:57:10That's the power of learning computer science and learning how to program
    • 0:57:14is to be able to navigate big data, so to speak.
    • 0:57:17Things the size of google, things the size of artificial intelligence training
    • 0:57:20data sets using better and better, more clever
    • 0:57:23algorithms that perform faster, and therefore
    • 0:57:26not only make the software more competitive,
    • 0:57:27but also make it more usable and more favorable for people like you and me
    • 0:57:32when using that software.
    • 0:57:34So when it comes to implementing algorithms as programmers,
    • 0:57:39as computer scientists, what you're really doing is taking these algorithms,
    • 0:57:42which might be expressed in English conceptually as we just did,
    • 0:57:45but really just translating them to code,
    • 0:57:48be it C or C++ or Python or R or Ruby or any number of other languages that exist
    • 0:57:54in the world.
    • 0:57:54But for now, let's consider how we might implement
    • 0:57:57that algorithm using something that's literally still English, but pseudocode.
    • 0:58:01Something that is still correct, but precise and finite,
    • 0:58:05as per Professor Kernighan's advice, which
    • 0:58:07is to say use your own vernacular of English and just
    • 0:58:10say what you mean but very succinctly.
    • 0:58:12There's no one way to write pseudocode.
    • 0:58:14It's not some formal language.
    • 0:58:15I'm just going to convert the steps I did intuitively to step
    • 0:58:19by step instructions as follows.
    • 0:58:21Step one, what I did was pretty much pick up the phone book.
    • 0:58:25Step two, what I did was pretty much open to middle of phone book
    • 0:58:28for the third algorithm.
    • 0:58:30Step three, look at page.
    • 0:58:31Step four, if person is on page, then, step five, call person.
    • 0:58:37If that does not prove to be the case, step six,
    • 0:58:40else if the person is earlier in the book, then
    • 0:58:44open to the middle of the left half of the book and then go back to line three.
    • 0:58:51Then, else if the person is later in the book,
    • 0:58:55open to the middle of the right half of the book and, again, go to line three.
    • 0:59:00Else, there's a fourth and final case.
    • 0:59:03If the person like John Harvard is not on the page, is not earlier,
    • 0:59:06is not later, what's the fourth scenario we'd best consider?
    • 0:59:10He's just not there.
    • 0:59:11Else we should do something specific like quit.
    • 0:59:13Now, as an aside, everyone in this room has probably
    • 0:59:16had one of these stupid technical support issues
    • 0:59:18where your phone or your laptop or your desktop computer
    • 0:59:20just freeze all of a sudden, or maybe it spontaneously reboots for no reason.
    • 0:59:24Odds are that's because not you but some other human made a mistake.
    • 0:59:29They probably wrote code working at Microsoft or Apple
    • 0:59:32or Google or somewhere else, and they didn't actually
    • 0:59:34anticipate that, oh, there could be a fourth scenario that
    • 0:59:38could happen in the real world.
    • 0:59:40But if there's no code that tells the computer what
    • 0:59:42to do in that fourth and final scenario, who
    • 0:59:45knows what the computer is going to do?
    • 0:59:46It might, by default, reboot.
    • 0:59:48It might, by default, freeze.
    • 0:59:50That's just a hint of the bugs, the mistakes in software to come.
    • 0:59:54But even though this is just one way to write this code,
    • 0:59:58a.k.a. pseudocode, there are some salient characteristics
    • 1:00:01that we'll use throughout today.
    • 1:00:03One, there are these verbs, these actions.
    • 1:00:06And henceforth, as aspiring computer scientists or programmers,
    • 1:00:09we're going to start to call these by what a more and more technical audience
    • 1:00:12would.
    • 1:00:13These are functions.
    • 1:00:14A function is an action or a verb.
    • 1:00:17It's like a bite-sized task that a computer can do for you.
    • 1:00:20Those then are functions in this here pseudocode.
    • 1:00:23But there's other types of code in here.
    • 1:00:26There are these things here.
    • 1:00:27If else if else if else.
    • 1:00:29Those are examples of what we're going to start calling conditionals.
    • 1:00:32These are sort of proverbial forks in the road where maybe you go this way,
    • 1:00:35maybe you go this way, but you decide which way to go based on a question.
    • 1:00:40The questions that you ask are what we'll technically
    • 1:00:43call Boolean expressions named after mathematician Boole.
    • 1:00:47A Boolean expression is a question with a yes or no answer,
    • 1:00:51a true or false answer, a black or white answer, a one or zero answer.
    • 1:00:56There's two possibilities, and there's a hint of the binary underneath.
    • 1:00:59A Boolean expression is going to tell you yes or no, you
    • 1:01:03should go down that fork in the road.
    • 1:01:06Notice what's important here is that indentation mattered as a result.
    • 1:01:11Notice that on line four when I first asked if the person is on page question
    • 1:01:16mark, so to speak, I should only do line five per its indentation
    • 1:01:20if the answer is yes or true, I should only
    • 1:01:23open to the middle of the left half of the book and go back to line three
    • 1:01:26if person is instead earlier in the book.
    • 1:01:29So indentation in pseudocode and in many programming languages
    • 1:01:33has logical significance.
    • 1:01:35It tells you whether to do things or not.
    • 1:01:37But there's another construct in here.
    • 1:01:39Go back to.
    • 1:01:40Go back to, which literally makes me go back to line three, potentially
    • 1:01:44again and again and again, creating some kind of cycle
    • 1:01:47or what we'll typically call a loop instead.
    • 1:01:50So even in this relatively simple real world algorithm,
    • 1:01:54we have these four fundamental characteristics of most computer
    • 1:01:57programs that we will write in this class,
    • 1:01:59and you might write beyond this class, that we have some technical jargon now
    • 1:02:03to describe them.
    • 1:02:04But what's important to note is that line 8 and line 11,
    • 1:02:08even though they're saying go back to line three, go back to line three,
    • 1:02:11you might think you're running the risk of what
    • 1:02:13we'll call an infinite loop where you literally get stuck in a loop
    • 1:02:17forever, which doesn't sound like a good thing if, at some point,
    • 1:02:20you want to turn your computer off, even though it's still working.
    • 1:02:22But these will not induce infinite loops.
    • 1:02:26Why?
    • 1:02:26What is happening in this particular algorithm every time we go back to line
    • 1:02:30three that guarantees eventually we will stop going back to line three?
    • 1:02:35AUDIENCE: The person is on the page, you call it.
    • 1:02:37DAVID MALAN: Exactly.
    • 1:02:38If the person is on the page, we will call them or we will quit.
    • 1:02:41But more importantly, because we keep dividing and conquering the problem,
    • 1:02:45in this case, having the phone book, having the phone book,
    • 1:02:48eventually we're going to run out of phone book, in which case, indeed,
    • 1:02:51John Harvard is either on that page or not And we will call
    • 1:02:55or we will quit instead.
    • 1:02:56So we'll see in time.
    • 1:02:58And in fact, allow me to promise.
    • 1:02:59Odds are at some point you will write code
    • 1:03:01that seems to take control over the computer for you,
    • 1:03:04where it's doing something, doing something, doing something,
    • 1:03:06and it literally won't respond to you anymore.
    • 1:03:08That's just going to be because of a mistake, a so-called bug
    • 1:03:11that you yourself will invariably have added to your code accidentally.
    • 1:03:16But we'll show you ways for terminating it or breaking out of those conditions.
    • 1:03:20And indeed, what we'll do in just a little bit
    • 1:03:22after a break for today's lecture is explore not just these concepts,
    • 1:03:26but some of the ways you can use them to solve real and very
    • 1:03:29visual and audio problems.
    • 1:03:31But for now, let's at least connect it to something
    • 1:03:33that's been all too germane in recent months, the past few years, namely
    • 1:03:37artificial intelligence, which is a topic we'll come back to
    • 1:03:39at the end of the course, too, to give you
    • 1:03:41a sense of what the connection is with what everyone's
    • 1:03:44been talking about in the world of AI and what
    • 1:03:46it is we're going to spend the next few weeks building up to by writing code.
    • 1:03:50If you were to try to implement something like a chat bot,
    • 1:03:54for instance, that just answers questions and has
    • 1:03:56a conversation with you, you could do that using pseudocode,
    • 1:03:59and as we'll soon see, you can use C, Python, any number of other languages
    • 1:04:03too.
    • 1:04:04That pseudocode might look like this when implementing a chat bot.
    • 1:04:07You could tell the chat bot, if the student says hello to you,
    • 1:04:10then say hello back.
    • 1:04:12And the indentation, as per earlier, implies this is conditional.
    • 1:04:16Else if the student says goodbye to you, say goodbye to the student.
    • 1:04:20Else if the student asks you how you are, say you are well.
    • 1:04:24So you can just enumerate question after question after question
    • 1:04:27and just handle all of these conditional possibilities.
    • 1:04:30But things kind of escalate quickly, especially
    • 1:04:32with the tools of today like ChatGPT.
    • 1:04:35Are we really going to have the wherewithal as programmers
    • 1:04:37to write another conditional like else if the student asks why 111 in binary
    • 1:04:41is 7 in decimal-- like, this kind of hints at,
    • 1:04:43oh my God, there's an infinite number of things
    • 1:04:45this human could ask the chat bot.
    • 1:04:47Do we really have to write an infinite number of conditionals?
    • 1:04:51That's just not possible.
    • 1:04:53Like, there's not enough time in the day,
    • 1:04:55there's not enough lines of code available.
    • 1:04:57Artificial intelligence surely needs to be able to figure some of this
    • 1:05:00out instead.
    • 1:05:01And so indeed, this is not how you implement AI,
    • 1:05:05but rather how you implement an AI like a chat bot
    • 1:05:08is you typically train it based on lots and lots of data.
    • 1:05:12You give it lots of inputs, lots of inputs, training data,
    • 1:05:15and let it figure out what it should say in response to certain questions.
    • 1:05:20And it boils down to a lot of probability,
    • 1:05:22a lot of statistics, otherwise known now as large language models,
    • 1:05:26which, if we really peek under the hood, are actually typically implemented
    • 1:05:29with what are called neural networks inspired by the world of biology,
    • 1:05:32whereby we humans have all of these neurons that
    • 1:05:35transmit electrical signals such that my brain tells my hand to move
    • 1:05:38this way, this way, and this other way.
    • 1:05:40And so what computer scientists have been doing over
    • 1:05:43the past many years is implementing in software using literally zeros
    • 1:05:47and ones, graphs or networks, neural networks, that
    • 1:05:51look a little something like this, where each of the circles represents a neuron,
    • 1:05:54each of the arrows represents a pathway between them,
    • 1:05:57and provides as input to these networks huge amounts
    • 1:06:01of data like all of the internet, all of Wikipedia, all of the books
    • 1:06:04that it might consume as input.
    • 1:06:06And then the goal of this neural network, as per this single final neuron
    • 1:06:11right here, is to produce an answer to a question.
    • 1:06:14Maybe it's simple like, yes, no, or maybe it's something like the answer
    • 1:06:18to the 111 question or how are you or goodbye or hello or the like.
    • 1:06:23And what these neural networks do is use statistics and probability
    • 1:06:26and try to output the most probabilistically likely answer
    • 1:06:31to this question that's been asked and really just hope that it is correct.
    • 1:06:36There is no programmer at OpenAI or Google
    • 1:06:38or Microsoft that's trying to anticipate every one of these questions
    • 1:06:42we might ask, not only in English but in other languages as well.
    • 1:06:46So you might be wondering why there's this 8 foot duck on the stage.
    • 1:06:49So the persona that CS50's own AI takes is in fact that of a rubber duck,
    • 1:06:54because it turns out in programming circles--
    • 1:06:56and this is true long before CS50--
    • 1:06:58it has often been recommended to students and aspiring programmers
    • 1:07:01that you keep literally a physical rubber duck on your desk.
    • 1:07:04The idea being, in the absence of a friend, family member, colleague,
    • 1:07:08TA who could answer technical questions for you, if you're alone
    • 1:07:12in your room in Mather at night, you can talk to the duck, maybe door closed,
    • 1:07:17and ask the duck your questions, or, more importantly,
    • 1:07:20talk the duck through what confusion you're having.
    • 1:07:23And the mere act of talking through the problem,
    • 1:07:26explaining logically what you're trying to do, what you're actually doing,
    • 1:07:29and what the error actually is, invariably,
    • 1:07:32that sort of proverbial light bulb goes off and you realize, oh, I'm an idiot.
    • 1:07:36I hear in my own words where I've gone awry.
    • 1:07:38And even though this duck will never say anything back to you, that alone,
    • 1:07:42rubber duck debugging or rubber ducking, tends to be a valuable programming
    • 1:07:47technique, believe it or not.
    • 1:07:49But thanks to these large language models,
    • 1:07:51we have not only physical but virtual ducks as well.
    • 1:07:53And so available to you will be in this class not tools like ChatGPT
    • 1:07:57and the like, which are, through policy, disallowed.
    • 1:08:00It is not reasonable to use ChatGPT and the like.
    • 1:08:03But you are allowed and encouraged to use CS50's own AI based
    • 1:08:08tools, which resemble those same tools but know something about CS50
    • 1:08:12and aspire to behave akin to a good teaching fellow guiding you
    • 1:08:15to solutions as opposed to handing you something outright.
    • 1:08:19So this is a tool that will be available at literally
    • 1:08:21this URL throughout the course.
    • 1:08:22CS50.ai.
    • 1:08:24It will also be embedded in the programming environment you'll soon
    • 1:08:27meet, which is called Visual Studio Code, a cloud based version thereof.
    • 1:08:31The duck will live in that environment as well, as well as on stage from time
    • 1:08:35to time, which is to say we'll not only talk about, but use
    • 1:08:39throughout the course this thing known as AI.
    • 1:08:42But this is ultimately code that we're going to start writing next week.
    • 1:08:46And unfortunately, this code here is written
    • 1:08:47in a language called C. This is essentially the program that I lost
    • 1:08:51two points on some 25 plus years ago.
    • 1:08:53It does look admittedly cryptic.
    • 1:08:56That's why today what we'll focus on is not what this code looks like,
    • 1:09:01nor the zeros and ones that that code gets converted to so your computer
    • 1:09:06can understand as input what you want it to do.
    • 1:09:08We're going to focus on a much more visual incarnation of this.
    • 1:09:12But I know thus far this has been a lot.
    • 1:09:13So let's go ahead and take a five minute break here,
    • 1:09:16and when we come back in five, we'll do some actual programming.
    • 1:09:19So see you in five.
    • 1:09:21All right.
    • 1:09:24So it's now time to solve with actual code some actual problems,
    • 1:09:29albeit in a fun and visual and audio way.
    • 1:09:32But recall that where we left off was this.
    • 1:09:34Starting next week, you'll be writing code that ultimately looks like this,
    • 1:09:38but thankfully, you will not be writing zeros and ones,
    • 1:09:41and no normal person, myself included, can
    • 1:09:43understand what all of these zeros and ones are at a glance.
    • 1:09:46We could take out some paper, pencil, and probably
    • 1:09:48figure it out very tediously.
    • 1:09:50But this is exactly the point.
    • 1:09:52Computers only understand this stuff, but what we as programmers
    • 1:09:56will start writing today and beyond is code at a higher level.
    • 1:10:01And indeed, this is going to be--
    • 1:10:02this is going to be frequent within computer science
    • 1:10:05where there's different levels of abstraction that we operate at.
    • 1:10:08And the lowest level, the nittiest gritty, is like the zeros and ones
    • 1:10:11that computer understand.
    • 1:10:12That's it in this class for zeros and ones.
    • 1:10:14Hopefully you at least have wrapped your mind
    • 1:10:16around why zeros and ones can be used in triples
    • 1:10:20and as bytes to represent higher and higher numbers.
    • 1:10:23But let's just now agree that computers can do that.
    • 1:10:27Let's abstract away from that detail and focus
    • 1:10:30on higher level languages than zeros and ones, namely a language like this.
    • 1:10:34So this is an example of the very first programming
    • 1:10:36language I learned back in the day as per that homework in a language called
    • 1:10:40C.
    • 1:10:40It's an older language, but it remains one of the most popular languages
    • 1:10:44in omnipresent languages nowadays because it's incredibly fast
    • 1:10:48and it's particularly good at making devices operate quickly.
    • 1:10:53For us pedagogically, the value of C is not
    • 1:10:56that you're probably in Silicon Valley and other such jobs
    • 1:10:59going to be using C yourself that much, but because it's
    • 1:11:02going to provide a conceptual foundation on top of which we introduce
    • 1:11:06other languages, like Python, which is newer and improved, so to speak,
    • 1:11:10that gives you more and more functionality for free out of the box
    • 1:11:14by abstracting away some of the stuff we'll focus on in the coming days first.
    • 1:11:19So at the end of the day, you should better
    • 1:11:20understand languages like Python and JavaScript
    • 1:11:23and SQL because of your underlying understanding of a language like C.
    • 1:11:29But this is too much for the first day.
    • 1:11:30Many of you will think that this is too much for the second week.
    • 1:11:33But in fact, C is really only sort of scary
    • 1:11:37looking because all of this darn punctuation and syntax, the semicolon,
    • 1:11:40the parentheses, the double quotes, the curly braces, and the like.
    • 1:11:43And I concur.
    • 1:11:44This is intellectually uninteresting, and a lot of the challenges early
    • 1:11:48on when learning programming is you just don't have the muscle memory
    • 1:11:51that I or some of the teaching fellows might for knowing
    • 1:11:54what symbol should be where.
    • 1:11:56But that's going to come with time and practice, I guarantee it.
    • 1:12:00What we'll do for today, though, is just throw away
    • 1:12:03all of that intellectually uninteresting detail and focus really on ideas.
    • 1:12:08And some of you might be in your comfort zone
    • 1:12:10here because if back in middle school you
    • 1:12:12were playing with a programming language called Scratch,
    • 1:12:14you were probably using at the time just to have fun in class or out of class,
    • 1:12:18making games, animations, interactive art.
    • 1:12:20What you probably didn't use it for, at least in middle school,
    • 1:12:24was to consider and explore programming languages themselves.
    • 1:12:27But what's wonderful about Scratch, which is this graphical programming
    • 1:12:31language from down the street at MIT, where it was invented some years ago,
    • 1:12:34is you can program not by using your keyboard per se,
    • 1:12:37but by dragging and dropping puzzle pieces, otherwise known as blocks,
    • 1:12:41that will snap together if it makes logical sense to do so.
    • 1:12:45And what you won't have to deal with is parentheses and double quotes
    • 1:12:48and semicolons and all of that, at least until next week.
    • 1:12:51But the nice thing about Scratch is that after this week
    • 1:12:54and after the so-called problem set zero,
    • 1:12:56the first assignment in which you'll use Scratch,
    • 1:12:58you'll have a mental model via which it will be easier to pick up
    • 1:13:02all of the subsequent syntax as well.
    • 1:13:05So let's see how we can start programming in Scratch
    • 1:13:08by making the simplest of programs first.
    • 1:13:10You can do this at scratch.mit.edu.
    • 1:13:13You needn't do this now in the moment.
    • 1:13:15Problem set zero will walk you through all of these steps.
    • 1:13:17But what I've done here is opened up at scratch.mit.edu, precisely
    • 1:13:23the default web page therein.
    • 1:13:26This is after having clicked the Create button
    • 1:13:28in Scratch, which is going to allow me to create my first program.
    • 1:13:31But first, a tour of the user interface here,
    • 1:13:34and what is ultimately available to you.
    • 1:13:36Well, within the Scratch environment, we'll
    • 1:13:39see a few different regions of the screen.
    • 1:13:41One, we have this palette of puzzle pieces at left.
    • 1:13:44The blue ones relate to motion, the purple ones relate to looks,
    • 1:13:48the pink ones relate to sound, and so forth.
    • 1:13:50So the color of the blocks just roughly categorizes
    • 1:13:53what that block's purpose in life is.
    • 1:13:55We're going to be able to use those puzzle pieces by dragging and dropping
    • 1:13:58them from left to right.
    • 1:14:00In the right here, in the middle of the screen
    • 1:14:02is where I'm going to write my actual programs.
    • 1:14:04This is where I'll drag and drop these puzzle pieces,
    • 1:14:06lock them together, and actually write my code.
    • 1:14:09What am I going to be coding?
    • 1:14:11Well, I'm going to be controlling one or more sprites.
    • 1:14:13Much like in the world of games are familiar, a sprite is like a character
    • 1:14:16that you might see on the screen.
    • 1:14:17The default character in the world of Scratch
    • 1:14:20is, in fact, a cat that looks like this.
    • 1:14:22And if in this case, I have just one cat,
    • 1:14:24I can then make that cat do things in his own little world at top right
    • 1:14:28by making the cat move up, down, left, right,
    • 1:14:31spinning around, or doing other things as well.
    • 1:14:33But if you want to introduce a dog or a bird
    • 1:14:35or any number of other custom characters, you just add more sprites
    • 1:14:38and they get their own place in that same world.
    • 1:14:41As for how to think about movement in this world,
    • 1:14:43it's actually pretty familiar, even though it
    • 1:14:45gets a little numeric for a moment.
    • 1:14:47If Scratch at the moment is in the middle of the screen, the cat is at 0, 0
    • 1:14:52if you think about x, y-coordinates or latitude longitude.
    • 1:14:55If you move the cat all the way up, this would still be x equals 0,
    • 1:14:58but it would be y 180.
    • 1:15:00What's the 180?
    • 1:15:01180 pixels vertically or dots on the screen.
    • 1:15:04This is negative 180 pixels on the screen at the bottom.
    • 1:15:08By contrast, if you go left and right, your x value might change.
    • 1:15:11Negative 240, but y is 0, or positive 240 and y is 0 as well.
    • 1:15:17But most of the time you won't need to know or care about what
    • 1:15:20the pixel coordinates of the cat are.
    • 1:15:23All you're generally going to care about is the programmer, most likely,
    • 1:15:26is do you want the cat to go relatively up, down, left, or right,
    • 1:15:29and let MIT figure out the mathematics of moving this thing around
    • 1:15:32in most cases.
    • 1:15:34All right.
    • 1:15:35So let's go ahead and introduce the first of these programs
    • 1:15:37by doing something quite simple, as we did in C there, but a little more simply
    • 1:15:42by writing code as follows.
    • 1:15:44I'm going to go back to scratch.mit.edu.
    • 1:15:47I've already clicked, per before, the Create button.
    • 1:15:50And if I click on the yellow category of blocks here at left--
    • 1:15:53and I'll zoom in-- we'll see a whole bunch of yellow puzzle pieces.
    • 1:15:56And probably the most common one you will
    • 1:15:58use to write code in Scratch for just this first week is literally
    • 1:16:02when green flag clicked.
    • 1:16:04Why?
    • 1:16:04Well, if we go back over to the cat's world at top right,
    • 1:16:07notice that above the cat's rectangular world,
    • 1:16:10there's not only a green flag for starting,
    • 1:16:12there's a red stop sign for stopping as well.
    • 1:16:15So let's do this.
    • 1:16:16Let me go ahead and click and drag.
    • 1:16:18When green flag clicked anywhere into the middle and let go.
    • 1:16:21And now I'm going to go to looks, and it looks
    • 1:16:25like there's a whole bunch of purple puzzle pieces here.
    • 1:16:27I'm going to choose something simple like say hello, drag it.
    • 1:16:30And notice if I get just close enough, it's
    • 1:16:33going to want to magnetically snap together.
    • 1:16:35So I'll just do that and it does its thing.
    • 1:16:37The fact that there's this white oval with text
    • 1:16:39means that is an input to this, say, puzzle piece.
    • 1:16:44I can literally then change what the input
    • 1:16:46is if I want to more conventionally say hello, world.
    • 1:16:49Which in fact, according to lore, was the very first program written in C,
    • 1:16:54and nowadays in most every language, including in Brian Kernighan's book.
    • 1:16:59So hello world is generally the first program
    • 1:17:01that most any programmer first writes.
    • 1:17:03So that's it as programs go.
    • 1:17:05Let me go ahead and zoom out here.
    • 1:17:07Let me go over to the right and click the green flag, and somewhat excitingly,
    • 1:17:11maybe underwhelmingly, we've now written a program that quite simply says
    • 1:17:15hello world on the screen.
    • 1:17:17Now let's make this a little more technical for just a moment.
    • 1:17:19What is this here puzzle piece, as I keep calling it?
    • 1:17:22It's actually a similar--
    • 1:17:24it's an incarnation one of the ideas from our pseudocode before.
    • 1:17:29What did we call those actions and verbs last time in my pseudocode?
    • 1:17:33AUDIENCE: [INAUDIBLE].
    • 1:17:34DAVID MALAN: Functions.
    • 1:17:35That's right.
    • 1:17:36So these purple puzzle pieces here are indeed functions,
    • 1:17:40and some functions, as we can see, take inputs, like hello comma world.
    • 1:17:44After all, how does Scratch know what to say?
    • 1:17:47You have to provide the cat with input, which
    • 1:17:49is to say functions can indeed take inputs like this.
    • 1:17:52In this case one input, but we'll see opportunities
    • 1:17:54for passing in more input as well.
    • 1:17:56What the cat is doing though, visually on the screen here at top right,
    • 1:18:00is what's generally called a side effect.
    • 1:18:02Sometimes when you call a function, it does something visually.
    • 1:18:06And in this case, you're seeing literally a cartoon speech
    • 1:18:08bubble, hello world.
    • 1:18:09That is the side effect of this function.
    • 1:18:12So if we now want to map this to our world of inputs and outputs
    • 1:18:15and see where this side effect is, this is the paradigm
    • 1:18:17I proposed at the start of class that is computer science in a nutshell
    • 1:18:21and will be the framework we use literally
    • 1:18:23throughout the class, no matter how--
    • 1:18:26no matter how the languages in particular evolve.
    • 1:18:29So what's the input to this particular program?
    • 1:18:31Well, this white oval, hello world is my input.
    • 1:18:34The algorithm, step by step instructions for solving some problem,
    • 1:18:37is implemented in code, this language called Scratch
    • 1:18:41by way of this purple puzzle piece.
    • 1:18:43And the output of that function, given this input,
    • 1:18:47is the side effect whereby the cat indeed says hello world visually
    • 1:18:52on the screen in that speech bubble.
    • 1:18:54So the exact same paradigm with which we began today
    • 1:18:56governs how exactly this cat here works.
    • 1:18:59Well, let's actually go back to this program
    • 1:19:01and make it a little more interesting than that.
    • 1:19:03Let me go ahead and click the red stop sign.
    • 1:19:05And let me actually use a different type of puzzle piece, another function that
    • 1:19:09does something a little different.
    • 1:19:11First, I'm going to get rid of the say block.
    • 1:19:13So I'm going to not only pull it away, I'm
    • 1:19:15going to drag it over anywhere at left and just let go
    • 1:19:17and it will delete itself automatically.
    • 1:19:20Or I could right click or Control click, and from a little menu
    • 1:19:23I could also explicitly say delete.
    • 1:19:25And what I'm going to do now is under sensing,
    • 1:19:28which is a light blue shade of puzzle piece-- there's a whole bunch here,
    • 1:19:32but I'm going to focus on this one.
    • 1:19:33Ask something and wait.
    • 1:19:36And the default text is, what's your name?
    • 1:19:38And that's fine.
    • 1:19:38But because it's a white oval, that input
    • 1:19:40can be manually changed by me if I wanted to change the question.
    • 1:19:43I'm going to drag it over here.
    • 1:19:45It's going to magnetically snap together.
    • 1:19:48And I'm OK with that question.
    • 1:19:49But what do I want to say with the answer?
    • 1:19:52Well, let's go ahead and do this.
    • 1:19:53I could go to looks again.
    • 1:19:55I could grab another say block, let it snap in,
    • 1:19:59and I could say something like, hello, David.
    • 1:20:03But this is going to be the first of many bugs that I make,
    • 1:20:06intentionally or otherwise.
    • 1:20:08Let me click the green flag.
    • 1:20:09Scratch is now, just like in a web browser, prompting me for some input
    • 1:20:13here.
    • 1:20:14So let me go ahead and type in my name.
    • 1:20:15David.
    • 1:20:16Enter.
    • 1:20:17And voila.
    • 1:20:18It works.
    • 1:20:19Hello, David.
    • 1:20:20I'm kind of cheating, though, right?
    • 1:20:21Because if I zoom out, stop, and play again.
    • 1:20:25Let me type in Julia's name here, enter, and it still says hello, David.
    • 1:20:30So that didn't really implement the idea that I wanted.
    • 1:20:33All right, so how can I fix this?
    • 1:20:35Well, it seems that this time I want more than a side effect.
    • 1:20:38I want to use the value that the human types in.
    • 1:20:40And for this, we need another feature of functions,
    • 1:20:43which is that not only can they sometimes have side effects,
    • 1:20:46something visually happens.
    • 1:20:47Some functions can hand you back a value, a so-called return value,
    • 1:20:52that will allow you to actually reuse whatever the human typed in.
    • 1:20:57So a return value is something that gets virtually handed back to you
    • 1:21:01and you can store it in something called a variable, like x, y, and z
    • 1:21:04in mathematics, and you can generally reuse it one or more times.
    • 1:21:08So let me actually draw our attention then
    • 1:21:10to, at left, not only the blue puzzle piece, ask what's your name and wait,
    • 1:21:15but notice that there's a special puzzle piece below it,
    • 1:21:18this blue oval called answer, and that represents what a computer
    • 1:21:22scientist would call a return value.
    • 1:21:24So MIT has kind of bundled it together side by side
    • 1:21:27to make clear that one of those pieces relates to the other.
    • 1:21:30What it means is that I can do this.
    • 1:21:32I can drag this oval and use this oval as the input to the save function.
    • 1:21:37Now, notice it's not the same size, but it is the right shape, so that's OK.
    • 1:21:40Scratch will grow or shrink things to fit properly.
    • 1:21:44But this too isn't quite right.
    • 1:21:46Let me go ahead and do this.
    • 1:21:47Let me go ahead and stop that, click the green flag.
    • 1:21:50I'll type in my name again.
    • 1:21:51D-A-V-I-D. Enter.
    • 1:21:54And it's just kind of weird or rude.
    • 1:21:56Like, I wanted a hello at least, and it just said David on the screen.
    • 1:21:59OK, so I can fix that.
    • 1:22:00Let me stop with the red stop sign.
    • 1:22:02Let me just separate these temporarily.
    • 1:22:04And I can leave it in the middle there, but they
    • 1:22:06have no logical connection temporarily.
    • 1:22:09Let me go back up to looks.
    • 1:22:10Let me grab a say block, a second one, and let me go ahead
    • 1:22:14and say, just to be grammatical, hello, space.
    • 1:22:17And then I'll reconnect this here.
    • 1:22:19So at the moment it looks like what I want, I want a hello, comma,
    • 1:22:23and then the return value printed out based on whatever the human typed in.
    • 1:22:28So let me zoom out.
    • 1:22:29Let me click the green flag.
    • 1:22:30Again, what's your name?
    • 1:22:32D-A-V-I-D. And watch the cat's side effect.
    • 1:22:36Enter.
    • 1:22:38It's still not greeting me properly.
    • 1:22:41There's no hello.
    • 1:22:42And if in case it was too fast, let's do it again.
    • 1:22:44Green flag.
    • 1:22:45D-A-V-I-D. Enter.
    • 1:22:47It rudely just says my name, which is weird.
    • 1:22:49What's the bug here, though?
    • 1:22:51It's a little more subtle.
    • 1:22:53Why?
    • 1:22:54Yeah?
    • 1:22:54AUDIENCE: It's just quickly going.
    • 1:22:56DAVID MALAN: Yeah.
    • 1:22:57It's just too quickly going over the say command or the say function,
    • 1:23:00in this case.
    • 1:23:00My Mac, your PC, your phone, it's just so darn fast.
    • 1:23:03Both are happening, but too fast for my human eyes to even notice.
    • 1:23:06So we can solve this in a number of ways.
    • 1:23:09I could actually use a different puzzle piece altogether.
    • 1:23:11In fact, MIT kind of anticipated this.
    • 1:23:13Notice the first puzzle piece in purple is say hello
    • 1:23:16for a specific number of seconds, and you
    • 1:23:18can specify not just the message, but the number
    • 1:23:20of seconds, ergo two inputs, otherwise now known as arguments to a function.
    • 1:23:25An input to a function is just an argument now.
    • 1:23:28And that would be a fix here.
    • 1:23:30I could maybe a little more explicitly do this.
    • 1:23:33I could go under events, scroll down a little bit, and-- sorry,
    • 1:23:37under control in orange, I could grab a wait block
    • 1:23:40and I could kind insert it in the middle.
    • 1:23:42And this might actually help.
    • 1:23:43So I could click on the green flag.
    • 1:23:45D-A-V-I-D. Enter.
    • 1:23:47Hello, David.
    • 1:23:49And I could change the timing to be a little more natural.
    • 1:23:51But what if I want the cat to just say hello, David all in one
    • 1:23:55breath, so to speak.
    • 1:23:56Well, for that I'm going to need to use a slightly different technique as
    • 1:23:59follows.
    • 1:24:00Let me go ahead and get rid of the wait.
    • 1:24:02Let me get rid of the second say block and stop the cat with the stop sign.
    • 1:24:06Let me go under operators here and let me somewhat cleverly grab this.
    • 1:24:10A join block at the bottom.
    • 1:24:12By default, it's using apple and banana as placeholders,
    • 1:24:15but those are white ovals so I can change those.
    • 1:24:17Let me drag this over the white oval for the save function and let
    • 1:24:22go, and it will snap to fill.
    • 1:24:23Let me go ahead here and type hello, comma, space instead of apple.
    • 1:24:28And what should I do instead of banana?
    • 1:24:31AUDIENCE: Answer.
    • 1:24:32DAVID MALAN: Yeah.
    • 1:24:33So it'd be answer return value--
    • 1:24:35the return value.
    • 1:24:36So let me go under sensing again.
    • 1:24:39Let me just drag another copy of it.
    • 1:24:41And you can use these again and again and again.
    • 1:24:42They don't disappear.
    • 1:24:43I want to drag answer over banana so that the second input to join
    • 1:24:49is actually, if you will, the output of the ask block, like that.
    • 1:24:53And it snaps to fit.
    • 1:24:55So now if I go ahead and click the green flag once more.
    • 1:24:57D-A-V-I-D. Enter.
    • 1:24:59Now we have the behavior aesthetically that I cared about.
    • 1:25:03But beyond the aesthetics of this, the goal here
    • 1:25:06really was to map it to, again, this same paradigm, which we'll see here.
    • 1:25:10The algorithm and the output and the input for this example are as follows.
    • 1:25:14The input to the say block was, quote, unquote, what's your name?
    • 1:25:17The function, of course, implementing that algorithm in code
    • 1:25:20was the ask and wait block.
    • 1:25:22The output, though, of the ask block recalls not some visual side effect.
    • 1:25:27It is a return value called answer, like a variable,
    • 1:25:30a special variable like x, y, and z in math.
    • 1:25:32But in this one, we generally in programming
    • 1:25:35describe variables with actual words, not just letters.
    • 1:25:38But this output of the say block, I kind of want to make room for it
    • 1:25:43to pass it into the say block as a second argument.
    • 1:25:47So let's do this.
    • 1:25:47Let's take one step back and propose that now for the join
    • 1:25:51block that I just used.
    • 1:25:53It takes two inputs hello, space and answer.
    • 1:25:57The function in question is indeed the join block.
    • 1:26:00The output of this had better be hello, David.
    • 1:26:03What do I want to do with the output of the join block?
    • 1:26:05Well, let me clear the screen.
    • 1:26:07Let me move this over, because now the output of the join block
    • 1:26:11is going to instantly become the input to the say block
    • 1:26:15so that the output now in this multistep process
    • 1:26:18is the side effect of hello, David.
    • 1:26:21So the fact that I nested these blocks on top of one another
    • 1:26:26was very much deliberate.
    • 1:26:27If I zoom in here, notice that hello and answer are on top of join, join
    • 1:26:33is on top of the say block.
    • 1:26:34And if you think back to high school math,
    • 1:26:36this is like when you had parentheses and you
    • 1:26:37had to do the things inside parentheses before the things outside parentheses.
    • 1:26:41It's the same idea, but I'm just visually stacking them instead.
    • 1:26:44But outputs can become inputs depending on what the function there expects.
    • 1:26:49Let me pause here and see if there's any questions
    • 1:26:51about not so much what the cat is doing, but how the cat is doing this.
    • 1:26:58Questions at hand?
    • 1:27:02All right.
    • 1:27:02Well, let's make the cat more cat-like and do this.
    • 1:27:06Let me throw away all the say block and just let go there.
    • 1:27:09And let me introduce at bottom left a nice feature of scratch
    • 1:27:12whereby there's also these extensions that
    • 1:27:14tend to use the cloud, the internet, to give you even more functionality.
    • 1:27:17And in fact, I'm going to click on this extension up here, text to speech.
    • 1:27:20And if I click on that, I suddenly get a whole new category
    • 1:27:23of blocks at the bottom.
    • 1:27:24Text to speech.
    • 1:27:25They happen to be green.
    • 1:27:27But what's nice here is that I can actually now
    • 1:27:29have the cat say something audibly.
    • 1:27:32So let me drag the speak block here instead of the say block.
    • 1:27:36I don't want it to just say hello.
    • 1:27:38Let me stop that.
    • 1:27:39So let me go back under operators.
    • 1:27:41Let me grab another join block, because I threw the other one away.
    • 1:27:44Let me change apple to hello, space again.
    • 1:27:47Let me go to sensing.
    • 1:27:48Let me drag answer to banana again.
    • 1:27:51And now let me hit the green flag and let me type in my name, D-A-V-I-D.
    • 1:27:55And in a moment I'll hit enter and.
    • 1:27:58COMPUTER: Hello, David.
    • 1:27:59DAVID MALAN: All right.
    • 1:28:00It's not exactly cat-like, but it was synthesized.
    • 1:28:03But it turns out under these text to speech blocks, there are some others.
    • 1:28:06Set voice to alto, for instance, seems to be the default.
    • 1:28:10But let's change this.
    • 1:28:11So notice that some puzzle pieces don't just take white ovals.
    • 1:28:14They might even have drop downs.
    • 1:28:16So whoever created that puzzle piece decided
    • 1:28:18in advance what the available choices are for that input per the dropdown.
    • 1:28:23So I'm going to change it to squeak, which sounds--
    • 1:28:25or actually kitten sounds even more apt.
    • 1:28:27Let me zoom out, click the green flag, type my name.
    • 1:28:31D-A-V-I-D. Enter.
    • 1:28:33COMPUTER: Meow, meow.
    • 1:28:35DAVID MALAN: That's interesting.
    • 1:28:36So it doesn't seem to matter what I type.
    • 1:28:38So how about David Malan.
    • 1:28:40COMPUTER: Meow, meow, meow.
    • 1:28:42DAVID MALAN: So it seems to meow proportional to how long
    • 1:28:45the phrase is that I typed in.
    • 1:28:46It can get a little creepy quickly.
    • 1:28:48If I change kitten to giant.
    • 1:28:50Let me go ahead and hit Play.
    • 1:28:52D-A-V-I-D. Enter.
    • 1:28:54COMPUTER: Hello, David.
    • 1:28:56DAVID MALAN: So you can, for very non-academic ways,
    • 1:29:00start to have fun with this, but just playing around
    • 1:29:02with these various inputs and outputs.
    • 1:29:03But let's actually make the cat do something more cat-like and indeed meow
    • 1:29:06instead of saying any words at all.
    • 1:29:08So let me throw all of that away.
    • 1:29:10Let me go now under sound.
    • 1:29:11Let me drag the play sound until done.
    • 1:29:15And notice in the dropdown here, by default, you just get the cat sound.
    • 1:29:18You can record your own sounds.
    • 1:29:20There's a whole library of dogs and birds
    • 1:29:21and all sorts of sounds you can import into the program.
    • 1:29:24I'll keep it simple with cat.
    • 1:29:26And let me click the green flag.
    • 1:29:28COMPUTER: Meow.
    • 1:29:29DAVID MALAN: All right.
    • 1:29:30So the cat meowed once.
    • 1:29:31If I want the cat to meow again, I could do this.
    • 1:29:33COMPUTER: Meow.
    • 1:29:34DAVID MALAN: If I want the cat to meow a third time, I could again hit play.
    • 1:29:37COMPUTER: Meow.
    • 1:29:38DAVID MALAN: So this is kind of tedious if to play this game,
    • 1:29:40I have to keep clicking the button, keep clicking the button
    • 1:29:43to keep the cat alive virtually in this way.
    • 1:29:46So maybe I want this to happen again and again and again.
    • 1:29:48Well, let me just do that.
    • 1:29:50Let me sort of drag and drop.
    • 1:29:51Or I could right click or Control click and then
    • 1:29:54a little menu would let me Copy-Paste or duplicate blocks.
    • 1:29:56But I'll just keep dragging and dropping.
    • 1:29:58Let's do this.
    • 1:29:59COMPUTER: Meow.
    • 1:30:00Meow.
    • 1:30:00Meow.
    • 1:30:01DAVID MALAN: Cat's kind of hungry, unhappy.
    • 1:30:03So let's slow things down so it's adorable again.
    • 1:30:06So let me go under control.
    • 1:30:09Let me grab one of those wait one second, and I'll plop this here.
    • 1:30:13Another one.
    • 1:30:13Let me plop it here.
    • 1:30:14Click play again.
    • 1:30:15COMPUTER: Meow.
    • 1:30:17Meow.
    • 1:30:18DAVID MALAN: Cuter.
    • 1:30:19Less hungry.
    • 1:30:20Sure.
    • 1:30:21But this program is now, I daresay, correct
    • 1:30:23if my goal is to get the cat's meow three times.
    • 1:30:26But now, even if you've never programmed before, critique this program.
    • 1:30:31It is not well-designed, even though it is correct.
    • 1:30:35In other words, it could be better.
    • 1:30:38How, might you think?
    • 1:30:41Yeah?
    • 1:30:42AUDIENCE: A loop.
    • 1:30:42DAVID MALAN: So using a loop.
    • 1:30:43And why?
    • 1:30:44Why are you encouraging me to use a loop even though it works as is?
    • 1:30:47AUDIENCE: It's easier to plot.
    • 1:30:48DAVID MALAN: Yeah.
    • 1:30:49So to summarize, it's just easier to use a loop
    • 1:30:51because I could specify explicitly in one place how many times I want it
    • 1:30:55to loop.
    • 1:30:55And moreover, frankly, any time you are copying and pasting something in code
    • 1:31:00or dragging the same thing again and again, odds are you're
    • 1:31:02doing something foolish.
    • 1:31:03Why?
    • 1:31:04Because you're repeating yourself unnecessarily.
    • 1:31:07And this is a bit extreme, but suppose I want
    • 1:31:09to change this program later so that the cat pauses two seconds in between meows.
    • 1:31:13Well, obviously I can just go in here and do two.
    • 1:31:16But what if I forget?
    • 1:31:17And suppose this program isn't, like, five or six puzzle pieces.
    • 1:31:20Suppose it's 50 or 60 or 500 or 600.
    • 1:31:23Eventually I or a colleague I'm working with is going to screw up.
    • 1:31:26They're going to change a value in one place, forget to change it in another.
    • 1:31:29So why are you inviting the probability of making a mistake?
    • 1:31:32Just simplify things so that you only have to change inputs in one place.
    • 1:31:37So how can I do this?
    • 1:31:38Let me zoom out.
    • 1:31:39Let me throw most of this duplication away,
    • 1:31:41leaving me with just the play and the wait function.
    • 1:31:44Let me now, under control as well, grab one of these.
    • 1:31:48I could, for instance, repeat as follows.
    • 1:31:50Let me grab a repeat.
    • 1:31:51I'm going to have to move these in two parts.
    • 1:31:53So I'm going to move this down.
    • 1:31:54It's too small, but it will grow to fit the right shape.
    • 1:31:57Then let me reattach it up here.
    • 1:31:59Let me change the default 10 to a 3.
    • 1:32:01And now I think I've done exactly what you were encouraging, which is simplify.
    • 1:32:05And I click play now.
    • 1:32:06COMPUTER: Meow.
    • 1:32:09Meow.
    • 1:32:10DAVID MALAN: Now and.
    • 1:32:11COMPUTER: Meow.
    • 1:32:12DAVID MALAN: Yeah.
    • 1:32:13So still correct, but arguably better designed as a result.
    • 1:32:16I can keep things simple and change things now in just one place
    • 1:32:19and it will continue to work.
    • 1:32:21But this is getting a little tedious now, I claim.
    • 1:32:23Like, why am I implementing the idea of meowing?
    • 1:32:26Wouldn't MIT have been better to have just implemented
    • 1:32:30a meow puzzle piece for us?
    • 1:32:32Because the whole thing is themed around a cat.
    • 1:32:34Why is there not a meow puzzle piece?
    • 1:32:35Why do I need to go through all of this complexity to build that functionality?
    • 1:32:39Well, what's nice about Scratch and what's
    • 1:32:41nice about programming languages in general
    • 1:32:43is you can generally invent your own puzzle pieces, your own functions,
    • 1:32:47and then use and reuse them.
    • 1:32:49So let me go ahead and do this.
    • 1:32:50I'm going to go under my blocks in pink down here.
    • 1:32:54I'm going to go ahead and click make a block,
    • 1:32:56and I'm going to be prompted with this interface here.
    • 1:32:58And I'm going to call this block literally meow, because apparently MIT
    • 1:33:01forgot to implement it for us.
    • 1:33:03And I'm just going to go ahead and immediately click OK.
    • 1:33:05And what you'll see now is two things.
    • 1:33:07One, on the screen, I've been given this placeholder pink piece
    • 1:33:11that says define meow as follows.
    • 1:33:14So anything I attach to the bottom of that define block
    • 1:33:17is going to define the meaning of meowing.
    • 1:33:20And at top left, notice what I have under my blocks.
    • 1:33:23I now have a pink puzzle piece called meow
    • 1:33:27that is a new function that will do whatever that other block of code
    • 1:33:31tells the cat to do.
    • 1:33:33So what do I want to do here?
    • 1:33:34Well, I'm going to keep it simple for now.
    • 1:33:36I'm going to move the play sound meow until done and wait two seconds.
    • 1:33:40Though let's change it back to one second to move things along.
    • 1:33:42And now let me drag the meow puzzle piece
    • 1:33:45over to my loop such that now, what's it going to do?
    • 1:33:49It's going to meow three times.
    • 1:33:50And just to be dramatic, out of sight, out of mind.
    • 1:33:54Let me, for no technical reason, just drag
    • 1:33:57this all the way to the bottom of the screen and then scroll
    • 1:33:59back up just to make the point visually that now meowing exists.
    • 1:34:04That is an implementation detail that we can abstract away,
    • 1:34:07not caring how it exists, because I now know at a higher conceptual level,
    • 1:34:12if I want a meow, I just use the meow puzzle piece, and I or someone else
    • 1:34:16dealt with already how to implement meowing.
    • 1:34:18So now let me go ahead and hit play.
    • 1:34:20COMPUTER: Meow.
    • 1:34:22Meow.
    • 1:34:24Meow.
    • 1:34:25DAVID MALAN: OK, so same exact code, but arguably better
    • 1:34:27design because I've now given myself reusable code so I don't have
    • 1:34:31to Copy-Paste those several blocks.
    • 1:34:33I can just use meow again and again.
    • 1:34:35But let's make one refinement.
    • 1:34:37Let me actually scroll down to where I did in fact implement this.
    • 1:34:40Let me Control click or right click on it
    • 1:34:42and let me edit the pink block that I created
    • 1:34:45a moment ago, because I want to practice what I've been preaching about inputs.
    • 1:34:49So I don't want this function just to be called meow.
    • 1:34:51I want this function to also take an input,
    • 1:34:55and just for consistency with our use of n earlier, which in computer science
    • 1:34:58generally means number, let me meow n times.
    • 1:35:03And just so that this puzzle piece is even more programmer friendly,
    • 1:35:06let me add just a textual label that has no technical significance
    • 1:35:10other than to make this function read left to right
    • 1:35:13in a more English friendly way.
    • 1:35:15Meow n times.
    • 1:35:17Let me click OK.
    • 1:35:18And now notice this thing at the bottom has changed such
    • 1:35:22that it's not only called meow, there's explicit mention of n,
    • 1:35:26which is a circle, which is exactly the variable shape that we saw earlier
    • 1:35:30when it was called answer.
    • 1:35:32This is not a return value, though.
    • 1:35:34This is what, again, we're going to call an argument, an input to a function.
    • 1:35:38So let me do this.
    • 1:35:39I'm going to move this back up to the top
    • 1:35:41so I can see everything in one place, and I'm
    • 1:35:44going to make one modification, because my goal now
    • 1:35:47is to make a new and improved version of meowing that actually takes into account
    • 1:35:51how many times I want the cat to meow.
    • 1:35:54So instead of using a loop in my own program under when green flag clicked,
    • 1:35:59I'm going to detach this temporarily.
    • 1:36:01I'm going to move this away.
    • 1:36:03I'm going to move this code over here, and I'm going to reattach it here.
    • 1:36:07So focusing for the moment on just the left,
    • 1:36:10meow is now defined as repeating three times the following two functions.
    • 1:36:14Play sound and wait.
    • 1:36:16But that's not quite right.
    • 1:36:17I want to get rid of the three.
    • 1:36:19So what can I do?
    • 1:36:20Because I created this input to the meow function myself a moment ago,
    • 1:36:25I can actually drag a copy of it over right
    • 1:36:28that is change the three to be generally an n.
    • 1:36:31So now I have a function called meow that will meow any number of times.
    • 1:36:35And what's nice now is my actual program that is governed by that green flag,
    • 1:36:41I can type in three, I can type in 10, I can type in 100, and it will just work.
    • 1:36:45And henceforth, I can, again, dramatically
    • 1:36:48scroll this down so we don't know or care about it anymore.
    • 1:36:51Now my program is a single line whereby this notion of meowing
    • 1:36:55has been abstracted away by just defining my own function or custom
    • 1:37:00block.
    • 1:37:01Questions, then, about just this idea, this principle
    • 1:37:04of creating your own functions to hide implementation details once you've
    • 1:37:09solved a problem?
    • 1:37:10Therefore, you don't want to have to think about that same problem
    • 1:37:13ever again.
    • 1:37:13And that's the beauty of programming, typically.
    • 1:37:17Questions on what here we just did?
    • 1:37:22No?
    • 1:37:23All right.
    • 1:37:23Well, let's do this.
    • 1:37:24Let's now make this a little more interactive in code.
    • 1:37:27Let me go to this green flag.
    • 1:37:28Let me scroll down and just throw all of this hard work
    • 1:37:31away that we have copies on the courses website of all of these programs step
    • 1:37:34by step if you want to review them in slower detail.
    • 1:37:37Let's do this.
    • 1:37:37Under control, turns out there's other ways to loop.
    • 1:37:41There's this forever block that will just do something forever.
    • 1:37:44So in the forever block, there's some place for some other code.
    • 1:37:47And I'm going to move to the control section
    • 1:37:50here and grab one of these if blocks, so one of these conditionals.
    • 1:37:54Let's plug that in here.
    • 1:37:55And now notice if, and then there's this sort of trapezoid-like placeholder
    • 1:38:00that's going to probably fit what?
    • 1:38:03The if is a conditional.
    • 1:38:04Forever is a loop.
    • 1:38:06Say and so forth have been functions.
    • 1:38:09What was the other key term we used?
    • 1:38:11So a Boolean expression.
    • 1:38:12We need to put one of those yes, no or true, false questions here.
    • 1:38:15So what are those?
    • 1:38:16Well, I've been using Scratch for some years,
    • 1:38:18so I under sensing there's one of these shapes here.
    • 1:38:21Touching mouse pointer, question mark.
    • 1:38:23The question mark literally evokes the whole idea of a Boolean expression
    • 1:38:27being yes, no.
    • 1:38:27It's way too big to fit, but it is the right shape.
    • 1:38:30So let me drag it.
    • 1:38:31Let go.
    • 1:38:31It's going to grow to fill.
    • 1:38:33And now let me go to sound.
    • 1:38:35Let me grab that play sound, meow until done,
    • 1:38:37and put it inside that conditional such that what kind of program
    • 1:38:41have I just implemented here, arguably?
    • 1:38:44What will this program do when I click the green flag?
    • 1:38:50Well, nothing at the moment.
    • 1:38:53AUDIENCE: Not touching the cat.
    • 1:38:54DAVID MALAN: But I'm not touching the cat.
    • 1:38:55So if I move the mouse pointer to the cat.
    • 1:38:57COMPUTER: Meow.
    • 1:38:59DAVID MALAN: Again.
    • 1:39:00COMPUTER: Meow.
    • 1:39:01DAVID MALAN: Again.
    • 1:39:01COMPUTER: Meow.
    • 1:39:02DAVID MALAN: It's kind of implementing the idea of petting a cat, if you will,
    • 1:39:05because I'm forever just waiting and waiting and waiting.
    • 1:39:08Is the mouse pointer touching that sprite, touching that cat?
    • 1:39:12And only if so, go ahead and play that sound meow until done.
    • 1:39:15But now we can make things a little more interesting.
    • 1:39:17Let me stop this and let me do something actually completely different.
    • 1:39:21Let me throw all this hard work away.
    • 1:39:23Let me go under extensions.
    • 1:39:25Let me go to video sensing, because lots of laptops, my own included,
    • 1:39:28has a little webcam nowadays.
    • 1:39:30Let me approve use of that there.
    • 1:39:32And you can see me in the frame.
    • 1:39:34And let me do this.
    • 1:39:34Let me drag one of these when motion exceeds some measure.
    • 1:39:38And through trial and error, I figured out that 50 tends to work well.
    • 1:39:41Let me step out of frame here and program off to the side.
    • 1:39:45And if I go to play sound meow until done,
    • 1:39:48notice that this is an alternative to using when green flag clicked.
    • 1:39:53This is a category of block that's constantly
    • 1:39:55waiting for what we'll call an event.
    • 1:39:57An event is just something that can happen on the screen, a click, a drag,
    • 1:40:01a mouse movement, and so forth.
    • 1:40:03So let me zoom out here.
    • 1:40:05And now, if I can do this-- here we go.
    • 1:40:09No, too slow.
    • 1:40:12Still too slow.
    • 1:40:13Wait, did I click play?
    • 1:40:14Let's see.
    • 1:40:17Try again.
    • 1:40:20COMPUTER: Meow.
    • 1:40:21DAVID MALAN: There we go.
    • 1:40:22OK.
    • 1:40:2250 is a little too high, apparently.
    • 1:40:24So let's make this a little gentler.
    • 1:40:2610.
    • 1:40:27COMPUTER: Meow.
    • 1:40:27DAVID MALAN: OK, well.
    • 1:40:29COMPUTER: Meow.
    • 1:40:29DAVID MALAN: There we go.
    • 1:40:30COMPUTER: Meow.
    • 1:40:31DAVID MALAN: There we go.
    • 1:40:32COMPUTER: Meow.
    • 1:40:33DAVID MALAN: OK, so we've implemented now more physically the idea of actually
    • 1:40:36responding to petting a cat.
    • 1:40:38COMPUTER: Meow.
    • 1:40:39Meow.
    • 1:40:40DAVID MALAN: Oh, damn it.
    • 1:40:41OK.
    • 1:40:41COMPUTER: Meow.
    • 1:40:42Meow.
    • 1:40:43Meow.
    • 1:40:44DAVID MALAN: All right.
    • 1:40:44So this is a bug.
    • 1:40:45Like now-- this is MIT's fault. So it's not stopping in response
    • 1:40:49to the red stop sign.
    • 1:40:50So what do you do in doubt?
    • 1:40:52Most extreme, you reboot.
    • 1:40:53For now, I'm just going to close the window.
    • 1:40:56OK.
    • 1:40:56So now we've seen all of those primitives
    • 1:40:59that we saw in that pseudocode, but incarnated in this graphical programming
    • 1:41:03language, and again, without parentheses and semicolons and double quotes and all
    • 1:41:06that punctuation that we will introduce before long.
    • 1:41:09But for now, we have the mechanisms in place
    • 1:41:12where we can do some really interesting things.
    • 1:41:14So in fact, I thought, in the spirit of thinking back on olden times,
    • 1:41:18thought I'd open up the very first program I wrote when I actually took--
    • 1:41:21I was cross-registered in an MIT class and took
    • 1:41:24a class that introduced aspiring teachers to Scratch.
    • 1:41:27And I implemented this program here called Oscartime,
    • 1:41:30which was a game that used a childhood song that I was a fan of
    • 1:41:33and it allows you to drag trash into a trash can.
    • 1:41:37But to bring this to life and perhaps in exchange for one stress ball,
    • 1:41:40could I get one brave volunteer who wants to come up and control this here
    • 1:41:43keyboard?
    • 1:41:44I saw your hand first.
    • 1:41:45Come on up.
    • 1:41:46Come on up.
    • 1:41:49And you'll see, thanks to the team, we also have this amazing lamppost here,
    • 1:41:53being on Quincy Street as we are.
    • 1:41:54Do you want to introduce yourself to the group?
    • 1:41:56AUDIENCE: Hi, my name is Anna.
    • 1:41:58I'm from Richmond, Virginia, and I'm in Weld.
    • 1:42:01DAVID MALAN: Nice.
    • 1:42:02Weld.
    • 1:42:02AUDIENCE: Yes!
    • 1:42:03DAVID MALAN: All right, come on over.
    • 1:42:05So here, Anna, you'll have a chance to play
    • 1:42:06the very first game I wrote in Scratch, which admittedly
    • 1:42:09is more complicated typically than we would
    • 1:42:11expect of a student doing this for the very first time, as in problem set zero.
    • 1:42:14But what I'm going to do is full screen this here.
    • 1:42:16I'm going to click the green flag, and what you'll see on the screen
    • 1:42:18are these instructions.
    • 1:42:19Drag as much falling trash as you can to Oscar's trashcan before his song ends.
    • 1:42:23And here we go.
    • 1:42:26[OSCAR THE GROUCH, "I LOVE TRASH"]
    • 1:42:28Oh, I love trash
    • 1:42:32Anything dirty or dingy or dusty
    • 1:42:36Anything ragged or rotten or rusty
    • 1:42:40Yes, I love trash
    • 1:42:45DAVID MALAN: There we go.
    • 1:42:46So as Anna continues to play, let's tease this apart a little bit.
    • 1:42:49So one, there's some costumes on the stage.
    • 1:42:51Like that lamppost is actually never going to move.
    • 1:42:54But there's a couple of sprites.
    • 1:42:56There's the trash can, which seems to be a character unto itself.
    • 1:42:59There's this piece of trash that keeps coming back and back.
    • 1:43:01That is a sprite.
    • 1:43:02There's now this sneaker, which is another sprite.
    • 1:43:05And in fact, notice that Oscar, of course, keeps popping up from his sprite
    • 1:43:08once in a while.
    • 1:43:10So Oscar seems to have multiple costumes.
    • 1:43:12So I offer this as an example, as you keep playing, if you would.
    • 1:43:14Very good job so far.
    • 1:43:16The song goes on forever.
    • 1:43:17This was a nightmare to implement, to listen to this all day long.
    • 1:43:20But how do we implement the rest of this?
    • 1:43:23Well, notice that the trash, every time she throws into the trash can,
    • 1:43:26does reappear somewhere different.
    • 1:43:28So there's some kind of randomness involved.
    • 1:43:30And indeed, Scratch will let you pick random numbers in a range.
    • 1:43:34So maybe it could be negative 240, maybe it
    • 1:43:36could be positive 240, at the 180 point on the top of the screen.
    • 1:43:40So you can randomly put things on the screen.
    • 1:43:43There's apparently what kind of construct
    • 1:43:45that makes the trash fall again and again.
    • 1:43:47I think no one's listening to me.
    • 1:43:48They're all just watching you.
    • 1:43:51What's making the trash fall from top to bottom?
    • 1:43:54So it's actually some kind of loop because there's a motion block
    • 1:43:58inside of a forever loop, probably, that just
    • 1:44:00keeps moving the trash one pixel, one pixel, one pixel, one pixel, one pixel,
    • 1:44:04creating the illusion, therefore, of motion.
    • 1:44:06And if we can crank the song a little bit more,
    • 1:44:09you'll see that this is all synchronized now.
    • 1:44:11OSCAR THE GROUCH: (SINGING) Because they're trash
    • 1:44:15Oh, I love trash
    • 1:44:19Anything dirty or dingy or dusty
    • 1:44:23Anything ragged--
    • 1:44:24DAVID MALAN: The song keeps going forever, seemingly.
    • 1:44:27And now notice more and more sprites are appearing because they waited for--
    • 1:44:31here we go.
    • 1:44:32Climax.
    • 1:44:32OSCAR THE GROUCH: (SINGING) I love trash
    • 1:44:39DAVID MALAN: All right.
    • 1:44:40A big round of applause for Anna.
    • 1:44:42Nicely done.
    • 1:44:43OK, here you go.
    • 1:44:44Here you go.
    • 1:44:46All right.
    • 1:44:46So this is an interminable song.
    • 1:44:48And indeed, I spent hours building that, and just listening to that song on loop
    • 1:44:52was not the best way to program.
    • 1:44:53But the goal here is to really use it as just an intellectual exercise as to how
    • 1:44:58that was implemented.
    • 1:44:59And we won't do the entire thing in detail,
    • 1:45:01because I will say back in the day when I was younger,
    • 1:45:04I didn't necessarily write the cleanest code.
    • 1:45:06And in fact, if we see inside this and we poke around the bottom of the screen
    • 1:45:10here, you can see all of my different sprites.
    • 1:45:12And the code is kind of complex.
    • 1:45:14Like, things just kind of escalated quickly.
    • 1:45:16But I did not set out and write all of these programs
    • 1:45:19all at once for each sprite.
    • 1:45:20I pretty much took baby steps, so to speak.
    • 1:45:22And so, for instance, let me open up just a few sample building blocks here
    • 1:45:27that speak to this that are written in advance.
    • 1:45:29So here's version zero.
    • 1:45:31Computer scientists typically start counting at zero.
    • 1:45:33And let me show you this example here that only has two sprites on the screen.
    • 1:45:37We have Oscar the trashcan and we have the piece of trash.
    • 1:45:40And now notice, what does Oscar do?
    • 1:45:43Well, let me go ahead and zoom in on this script, as it's called.
    • 1:45:47A program is a script.
    • 1:45:49When the green flag is clicked, Oscar switches his costume to Oscar one.
    • 1:45:53That's his default costume where the lid is closed.
    • 1:45:55Then Oscar does this forever.
    • 1:45:57If Oscar is touching the mouse pointer, change the costume to Oscar two,
    • 1:46:03otherwise change it back to Oscar one.
    • 1:46:05So that whole idea of animation where Oscar is popping in and out
    • 1:46:09is just like a quick costume change based
    • 1:46:11on a loop inside of which is a conditional waiting for the cursor,
    • 1:46:15like Anna did, to get near the trash can.
    • 1:46:18Meanwhile, if we look at the piece of trash here,
    • 1:46:20notice that the trash is actually not doing anything in this first version
    • 1:46:24because I didn't even implement falling first.
    • 1:46:27So let me hit the green flag.
    • 1:46:28Nothing is happening in this very first version.
    • 1:46:30But notice, if I click on the trash and drag as soon as I'm touching Oscar,
    • 1:46:35there comes that trash can lid.
    • 1:46:37And it was just the result of making this one program respond to that input.
    • 1:46:42All right.
    • 1:46:42What did I do next?
    • 1:46:43Well, next, after taking that single baby step, I added one other feature.
    • 1:46:47Let's see inside this version one.
    • 1:46:49Again, Oscar is behaving the exact same way.
    • 1:46:52But notice this time the trash is designed to do the following.
    • 1:46:55First, I'm telling the program that the drag mode is draggable.
    • 1:46:59That is, I want the trash to be movable when the user clicks on it.
    • 1:47:02Then I tell the piece of trash to go to a random x location.
    • 1:47:06x is the horizontal, so it's going somewhere between 0 and 240,
    • 1:47:10but all the way at the top of the screen.
    • 1:47:12180.
    • 1:47:13Then forever, the piece of trash just changes by negative one.
    • 1:47:17So it just moves down and down and down.
    • 1:47:19And without looking at the second script yet, let me just hit play.
    • 1:47:22And notice, without even doing anything-- and eventually,
    • 1:47:25once there was lots of trash falling, like
    • 1:47:27Anna was struggling to keep up with this.
    • 1:47:28It's just moving one pixel at a time forever until, thankfully, MIT
    • 1:47:33does stop things automatically if they hit the bottom, lest a six-year-old get
    • 1:47:37upset that all of a sudden their sprite is gone forever.
    • 1:47:39So there is some special casing there.
    • 1:47:41But what else is this trash doing?
    • 1:47:44Let me zoom in here.
    • 1:47:45The piece of trash also, when the green flag is clicked,
    • 1:47:49is forever asking this question.
    • 1:47:51If you are touching Oscar, then pick a new random location between 0 and 240
    • 1:47:57at positive 180 and go back to the top.
    • 1:48:00So in other words, as soon as this piece of trash
    • 1:48:03is dragged over to Oscar like this and I let go, it recreates itself at the top.
    • 1:48:08It's just sort of teleporting to the top, and thus was born this feature.
    • 1:48:12And I won't slog through all of the individual features here,
    • 1:48:14but if we do just one more and see inside this one-- so now let me go ahead
    • 1:48:18and hit Play.
    • 1:48:19Notice at the top left of the screen, there's a score.
    • 1:48:21Currently zero.
    • 1:48:23But now when I click the trash and let go,
    • 1:48:25notice that the score is being incremented by one.
    • 1:48:28And this, in fact, is how, Anna, your score kept
    • 1:48:30going higher and higher and higher.
    • 1:48:31Every time I noticed, oh, the trash is touching Oscar, let's not only teleport,
    • 1:48:35let's also increment a variable.
    • 1:48:37And we didn't see this before, but if I go to this Oscar Scratch now,
    • 1:48:42you'll see that it is exactly the same.
    • 1:48:44But if I now go to the trash piece here and we go to when green flag clicked,
    • 1:48:50you'll see that I'm initializing a variable in orange called score to zero.
    • 1:48:54But if we scroll down to the bottom, Oscar
    • 1:48:57is also doing another thing in parallel at the same time.
    • 1:49:00When the green flag is clicked, Oscar is forever checking,
    • 1:49:03is the piece of trash touching Oscar?
    • 1:49:07If so, change the score by one and then go to top,
    • 1:49:11which is another location on there, that screen.
    • 1:49:14So in other words, even though at a glance something like Oscar
    • 1:49:16time might look very complicated and it did take me hours,
    • 1:49:20the goal, especially with problem set zero,
    • 1:49:21is not going to be to bite off all of that at once,
    • 1:49:24but to take proverbial baby steps.
    • 1:49:26Implement one tiny feature so that you feel like you're making progress.
    • 1:49:29Add another feature, another.
    • 1:49:31And invariably you might run out of time and not
    • 1:49:33get to the best version of your vision, but hopefully it'll be good.
    • 1:49:36Hopefully it'll be better, but you'll have these sort of mental milestones,
    • 1:49:39hoping that you at least get to that point.
    • 1:49:41Because as you will soon discover, everything in the world of programming
    • 1:49:45unfortunately takes longer than you might expect.
    • 1:49:48That was true for me 25 years ago and is still true today.
    • 1:49:52Well, let me introduce one final set of examples here.
    • 1:49:55This one written by one of your own predecessors, a former student.
    • 1:49:58Let me go ahead and open up three baby steps, if you will,
    • 1:50:02toward an end of implementing a game called Ivy's Hardest Game, whereby
    • 1:50:07it's now more interactive, quite like Oscartime.
    • 1:50:10So at top right here, notice-- and I'll zoom
    • 1:50:12in-- we have this world that's initially very simple.
    • 1:50:15Two black lines, two walls, if you will, and a Harvard sprite in the middle.
    • 1:50:19But when you click the green flag, notice
    • 1:50:21that nothing happens initially except that the sprite jumps to the middle.
    • 1:50:25But I can hit the up key or the down key or the left key or the right key.
    • 1:50:30But if I try to go too far, even though it's not the edge of the world,
    • 1:50:34it's only touching that there black line, it's still going to stop as well.
    • 1:50:39So intuitively, how could you implement that type of program?
    • 1:50:42How could you get a sprite from what we've seen to respond to up, down, left,
    • 1:50:47right, but actually move when I touch my arrow keys?
    • 1:50:51Like, what does it mean to move?
    • 1:50:53Yeah?
    • 1:50:54AUDIENCE: Maybe if then.
    • 1:50:55DAVID MALAN: Exactly.
    • 1:50:56So much like with representing information, at the end of the day,
    • 1:50:59all we've got is zeros and ones.
    • 1:51:00When it comes to algorithms, at the moment,
    • 1:51:02all we have are functions and loops and conditionals
    • 1:51:06and Boolean expressions and soon some more things too.
    • 1:51:08But there's not all that much we have at our disposal.
    • 1:51:11So let me zoom out from this and let me actually show you
    • 1:51:14what the Harvard sprite is doing.
    • 1:51:16It's doing this.
    • 1:51:17When I go up to the green flag here, the Harvard sprite is going to 0, 0.
    • 1:51:21So dead center in the middle.
    • 1:51:22And then it's forever doing two things, listening for the keyboard
    • 1:51:25and feeling for walls, left and right.
    • 1:51:27Now, those are not puzzle pieces that come with Scratch.
    • 1:51:30I created my own custom blocks, my own functions to implement those ideas.
    • 1:51:35Let's not abstract away for now.
    • 1:51:37Let's actually look at these features.
    • 1:51:38And indeed, to your instincts at left here,
    • 1:51:41what does it mean to listen for the keyboard?
    • 1:51:43Well, if the up arrow key is pressed, change y by one.
    • 1:51:47Move up.
    • 1:51:48If the down arrow key is pressed, change y by negative one.
    • 1:51:52If the right arrow key is pressed, change x by one.
    • 1:51:55If the left arrow key is pressed, change x by negative one.
    • 1:51:59So take all the magic out of moving up, down,
    • 1:52:01left, right by just quantizing it as plus, minus, this, and that.
    • 1:52:05It's all numbers, indeed, at the end of the day.
    • 1:52:07But what else is it doing?
    • 1:52:09Notice that it did, indeed, bounce off the wall.
    • 1:52:11So my other custom function, which I chose,
    • 1:52:14feel for walls to evoke this idea, it's asking two questions.
    • 1:52:17If you're touching the left wall, then change x by one,
    • 1:52:21so bounce in the other direction.
    • 1:52:23Else if you're touching the right wall, bounce in the negative one direction.
    • 1:52:27And so what are left wall and right wall?
    • 1:52:30I mean, I kind of cheated.
    • 1:52:31I just used two more sprites.
    • 1:52:32These sprites are literally nothing except black lines.
    • 1:52:35But because they exist, I can ask that question in my conditional saying,
    • 1:52:40are you touching those other sprites?
    • 1:52:42And I could have colored them any way I want, but this is enough, if I zoom in,
    • 1:52:46to implement this idea of going up, down, left, and right,
    • 1:52:49and preventing the sprite from leaving that little world.
    • 1:52:53All right.
    • 1:52:54So if you'll agree that there's a way now to implement motion up,
    • 1:52:58down, left, right, let's go ahead and implement this idea
    • 1:53:00by adding a rival into the mix, like a Yale sprite.
    • 1:53:03And what the Yale sprite is going to do, if I click the green flag, is this.
    • 1:53:07So Harvard at the moment is still going to be movable with the arrow keys,
    • 1:53:10up, down, left, right.
    • 1:53:11But Yale, for better or for worse, is just
    • 1:53:13going to mindlessly bounce back and forth from left to right forever,
    • 1:53:16it would seem.
    • 1:53:17The operative word being forever.
    • 1:53:18So how is that working?
    • 1:53:19Well, let's look.
    • 1:53:20Here's the Yale sprite at the bottom.
    • 1:53:22Let's zoom in on its actual code here.
    • 1:53:25The Yale sprite starts at 0, 0.
    • 1:53:27It points in direction 90 degrees, which means left, right, essentially.
    • 1:53:31And then it forever does this.
    • 1:53:32If touching the left wall or touching the right wall, turn around 180 degrees.
    • 1:53:38So I don't want the Yale sprite to just stop
    • 1:53:40by moving it one pixel to bounce off slightly.
    • 1:53:43I want it to wrap around and just keep going and going and going forever.
    • 1:53:47And that's it.
    • 1:53:48Everything else is the same.
    • 1:53:49So one final flourish.
    • 1:53:50Let's add a more formidable adversary, like MIT here,
    • 1:53:54whereby if I zoom in and hit play, notice
    • 1:53:57that if I move the Harvard sprite, MIT comes chasing me now.
    • 1:54:01Now, how is this actually working?
    • 1:54:03Yale is just kind of doing its thing, bouncing back and forth.
    • 1:54:05Now MIT has really latched on to me and it's following me up, down, left, right.
    • 1:54:10So how is that logic now working?
    • 1:54:12Well, again, it's probably doing something forever,
    • 1:54:14because that's why it's continually doing it.
    • 1:54:16Let's click on MIT.
    • 1:54:17This too is pretty simple, even though it's a pretty fancy idea.
    • 1:54:21Initially the MIT sprite goes to a random position,
    • 1:54:24but thereafter, it forever points toward the Harvard logo outline, which
    • 1:54:28is just the long name that your predecessor or former student
    • 1:54:30gave the name for that sprite.
    • 1:54:32And then it moves one step, one step, one step.
    • 1:54:35So suppose this were an actual game, and in games things
    • 1:54:38get harder and harder, the adversary moves faster and faster.
    • 1:54:41How could we make MIT even faster by changing just one thing here?
    • 1:54:48Like, how do we level up?
    • 1:54:51Change the one to two pixels at a time, two steps at a time.
    • 1:54:54So let's see that.
    • 1:54:55Let's go ahead and zoom out.
    • 1:54:56Let's hit play.
    • 1:54:57And now notice that MIT is coming in much faster this time.
    • 1:55:01All right.
    • 1:55:01So it wasn't noticeably faster.
    • 1:55:04Let's do this.
    • 1:55:04Let's move 10 steps at a time.
    • 1:55:06So 10 steps faster than originally.
    • 1:55:08I mean, now-- and now notice it's kind of twitching back and forth in this way.
    • 1:55:12Why?
    • 1:55:13Well, probably, if we worked out the math, probably
    • 1:55:15the MIT sprite is touching the sprite and it's bouncing off of it,
    • 1:55:18but then it's realizing, oh, I went too far.
    • 1:55:20Let me move back.
    • 1:55:20Wait a minute.
    • 1:55:21I'm still touching it.
    • 1:55:22Let me move down.
    • 1:55:22So you can get into these perverse situations
    • 1:55:24where there is actually a bug, be it logical or aesthetical.
    • 1:55:27But in this case, we probably want to fix that.
    • 1:55:29So 10 is probably too fast for this to work particularly well.
    • 1:55:32But the final flourish here really is to show you the actual version of a game
    • 1:55:37that one of your predecessors, a past classmate, actually implemented.
    • 1:55:40Before, thereafter, we will adjourn for cake
    • 1:55:43in the transept, which is the CS50 tradition.
    • 1:55:45But can we get one more final volunteer to come on
    • 1:55:49up to play Ivy's Hardest Game?
    • 1:55:51I'm seeing your hand most enthusiastically there.
    • 1:55:53Yeah, come on down.
    • 1:55:54Very happily.
    • 1:55:56[APPLAUSE]
    • 1:56:00In just a moment, we will indeed adjourn.
    • 1:56:03But the goal here now is going to be to navigate a maze that's
    • 1:56:06a little more difficult than the last.
    • 1:56:09Let's have you first, though, introduce yourselves to your classmates in front.
    • 1:56:13AUDIENCE: Hi, y'all.
    • 1:56:13I'm Eric.
    • 1:56:14I'm from Philadelphia and I'm also from Hollis Hall.
    • 1:56:17[CHEERS]
    • 1:56:18DAVID MALAN: One person from Hollis.
    • 1:56:20Nice.
    • 1:56:20OK.
    • 1:56:21Welcome.
    • 1:56:22All right.
    • 1:56:22Eric, go ahead and take the keyboard here.
    • 1:56:24It, too, will be all about up, down, left, right as soon
    • 1:56:26as you click the green flag.
    • 1:56:28And if we can crank the music.
    • 1:56:30[MC HAMMER, "U CAN'T TOUCH THIS"]
    • 1:56:32You Can't touch this
    • 1:56:33DAVID MALAN: So notice, the black walls are a little more involved
    • 1:56:36than last time.
    • 1:56:38But the goal is to get to the sprite all the way at right
    • 1:56:40and just touch it, at which point you move to the next level.
    • 1:56:44The next level, of course, has Yale doing its thing back and forth.
    • 1:56:49You've made it to level three.
    • 1:56:51But now there's two Yale.
    • 1:56:52So another sprite is in the mix that's randomly
    • 1:56:55moving a little different in terms of direction.
    • 1:57:00Three Yales.
    • 1:57:05Next level.
    • 1:57:06MIT is in.
    • 1:57:11Nice.
    • 1:57:17The walls are now gone.
    • 1:57:20Princeton's in the mix.
    • 1:57:31Nice.
    • 1:57:34Two Princetons.
    • 1:57:43OK.
    • 1:57:44New life.
    • 1:57:54OK, another life.
    • 1:57:55Nice.
    • 1:57:56Nice.
    • 1:57:56Oh.
    • 1:58:04Nice.
    • 1:58:04Second to last level.
    • 1:58:06Three Princetons.
    • 1:58:09Last level.
    • 1:58:15Yeah!
    • 1:58:18Congratulations.
    • 1:58:19[APPLAUSE]
    • 1:58:21Thank you.
    • 1:58:22All right.
    • 1:58:23This, then, was CS50.
    • 1:58:25Welcome aboard.
    • 1:58:26Cake is now served.
    • 1:58:29[MUSIC PLAYING]
  • CS50.ai
Shortcuts
Before using a shortcut, click at least once on the video itself (to give it "focus") after closing this window.
Play/Pause spacebar or k
Rewind 10 seconds left arrow or j
Fast forward 10 seconds right arrow or l
Previous frame (while paused) ,
Next frame (while paused) .
Decrease playback rate <
Increase playback rate >
Toggle captions on/off c
Toggle mute m
Toggle full screen f or double-click video