CS50 2019 - Lecture 0 - Computational Thinking, Scratch
CS50
0:00 [MUSIC PLAYING] DAVID MALAN: This is CS50,
1:25 Harvard University's introduction for the intellectual enterprises
1:27 of computer science and the art of programming.
1:30 My name is David Malan,
1:31 and I actually took this course myself sophomore year some years ago.
1:35 But I almost didn't.
1:36 At the time, I was quite uneasy with the idea,
1:39 frankly, of taking a computer science course, let alone this course.
1:42 And so my freshman year, at least,
1:44 I really gravitated toward courses and departments
1:46 with which I was much more familiar.
1:48 Computer science was well beyond my comfort zone at the time,
1:52 and it was really these unfamiliar waters that I
1:54 wasn't quite ready to shop, even my first year.
1:57 But sophomore year, I finally got up the nerve to come through the door of CS50,
2:01 and only because the professor at the time let me take the course pass/fail.
2:05 I was that uneasy.
2:06 And if only I had known at the time what I now know,
2:09 which is that 2/3 of CS50 students
2:11 have never taken a computer science course before.
2:14 So if you are feeling similarly uneasy with the idea of trying something new,
2:18 or even if you have prior background but are
2:20 looking to fill in gaps in your knowledge,
2:21 or if you're particularly self-taught,
2:23 realize you are very much in good company.
2:25 And ultimately, what matters in this course is not
2:28 so much where you end up relative to your classmates,
2:30 but where you end up relative to yourself when you began,
2:33 which is, of course, today.
2:35 So what, then, is computer science?
2:37 And what was it that I was so uneasy with?
2:39 Well, I dare say we can describe computer science as this.
2:42 It's just the process of solving problems.
2:44 And what does it mean to solve a problem?
2:46 You've got some input.
2:47 And the goal is to get some output, the solution, to that particular problem.
2:52 And in between, really, is computer science.
2:54 And we'll see what's in this literal black box on the screen
2:57 as we begin to fill in some of those blanks.
2:59 But when we consider a problem to be solved,
3:02 we have to all agree from the get-go, especially if we're using machines,
3:05 how are we going to represent these inputs and outputs?
3:08 And so one of the first concepts we explore
3:10 in computer science is how you represent information itself.
3:14 And odds are you probably know coming into this course
3:16 that computers only speak what language, so to speak?
3:19 AUDIENCE: Binary.
3:20 DAVID MALAN: Yeah.
3:20 So binary.
3:21 And if you've never heard that term before, fine, as well.
3:23 But zeros and ones, somehow.
3:25 But how do we get to that point?
3:26 Well, even if you kind of know that computers speak binary,
3:29 whatever that means, but you haven't necessarily thought about how that works,
3:33 well, consider how most of us learn how to count maybe first on our hands.
3:37 If I want to count the number of people in the room, I might do 1,
3:40 2, 3, 4, 5, putting up one finger for every person in the room.
3:45 So that's what's known as unary notation.
3:47 U,?] or uno, implying 1 because I'm just putting up
3:50 a finger or not to count people in the room.
3:52 Of course, I can only count so high on just one hand.
3:55 But thankfully, we have many symbols in our so-called human world of decimal.
4:00 Dec meaning 10, we have digits 0 through 9.
4:03 And from there, we can express any numbers with which we're all familiar.
4:07 But computers don't have that many digits.
4:10 They only have zeros and ones.
4:12 And yet somehow, they're able to store not only numbers,
4:14 but letters and images and videos and sounds and so much more.
4:18 So how does that work?
4:19 Well, let's take a quick look at just this to get everyone
4:21 on the same page as to how you can build the phones in our pockets,
4:24 the laptops on our desk today, using just zeros and ones.
4:28 Well, these are just symbols on the screen here.
4:31 What does this, of course, represent?
4:34 123, but why?
4:36 I mean, these literally are just symbols or glyphs on the screen,
4:39 sort of strokes of a pen that we all ascribe meaning to.
4:41 We just see this as 123.
4:43 But why is that?
4:44 Well, if you're like me,
4:45 you probably learned way back when to think of the rightmost
4:48 digit as being in the ones place or the ones column,
4:50 the middle digit as being in the tens place,
4:52 and the leftmost digit as being in the hundreds place.
4:55 So how do we get from this pattern of 1, 2, 3 to the number 123?
4:59 Well, it's some quick mental math that we all just do instinctively.
5:02 It's 100 times 1, plus 10 times 2, plus 1 times 3.
5:08 That, of course, gives us 100 plus 20 plus three, or 123.
5:13 So all of us just kind of take that process for granted now.
5:16 But it turns out that there's a system at play here,
5:19 a system such that we can figure out any number in the same way.
5:23 So if we've got our ones place, tens place,
5:25 and hundreds place, of course, in the decimal world,
5:27 this is the number 1, this is the number 2, 3, 4, 5, 6, 7, 8, 9.
5:33 Something interesting happens, of course, after 9.
5:35 You sort of carry the 1.
5:36 And why then does 010, or if we ignore the leading zeros as being insignificant,
5:41 why does one 0 represent the number we all know obviously as 10?
5:45 Well, just because it's 10 times 1 plus 1 times 0.
5:48 So that's the system we've been using for years.
5:51 And it turns out that these columns, realize, are just powers of 10.
5:54 So 10 to the 0 is 1, 10 to the 1 is 10, and 10 to the 2 is 100.
5:59 That's how we got ones, tens, and hundreds place.
6:02 Now in the computer world, you don't have 10 digits, 0 through 9.
6:05 You have just two digits, 0 and 1.
6:08 So we can just make a little tweak to our mental model here,
6:11 so to speak, and just now use 2, powers of 2, instead of powers of 10.
6:15 So that means the right hand column is going to be 1,
6:18 the middle column is going to be 2,
6:19 the left column is going to be 4, and if we kept going,
6:23 it'd be 8, 16, 32 instead of 1,000, 10,000, 100,000.
6:27 But the idea is exactly the same.
6:29 So I propose that computers only speak zeros and ones, of course.
6:32 But how do they represent larger numbers than 0 and 1?
6:37 Well, this is representing 0.
6:39 This is representing 1.
6:40 What pattern of symbols on the screen would
6:42 represent the number we humans know as 2?
6:45 Yeah.
6:46 So 010.
6:47 So you just spoke binary.
6:49 So even if you just generally knew that binary is spoken by computers,
6:53 it just means that a computer, to represent the number we know as 2,
6:56 somehow stores a pattern of symbols of 010.
6:59 How do they represent 3?
7:01 011, for the same reason.
7:03 It's 2 times 1, plus 1 times 1, gives us, of course, three.
7:07 And now, just as before when we meant 9 to 10,
7:10 now we actually go from 3 to 4 by carrying the 1 now.
7:13 So in binary, bi meaning two, hence the 0 and 1,
7:18 100 is not 100, per se, it is literally the number we know as 4.
7:23 And we can keep going on up.
7:24 This of course, now is 5.
7:26 This would be 6.
7:27 This would be 7.
7:28 And what happens if we want to represent eight?
7:31 Yeah.
7:32 So we kind of have to solve this somehow.
7:33 We need another digit.
7:34 And that's fine, right?
7:35 In math class, you would just add another place, another column,
7:39 in order to get back the value that you want.
7:42 So we need more zeros or ones, otherwise, now known as bit.
7:47 If you've ever heard of the phrase bit, it just means binary digit,
7:50 and a 0 or a 1 is just something we know as a bit.
7:53 And why is this germane to computers?
7:55 Well, as fancy as our Macs and PCs and phones are today,
7:58 consider, after all, that at the end of the day,
8:00 what do you have to do, typically,
8:02 with your laptop, your desktop, your phone these days?
8:07 What do you do at the very end of the day?
8:09 Yeah, so you charge it, right?
8:10 You plug it into some physical resource.
8:12 That is the only physical resource into these computers that we use today.
8:16 And that's kind of nice, because, of course,
8:18 the core can either be plugged in or not plugged in.
8:21 Or maybe we could call that a 1 or a 0, true or false, on or off,
8:27 which is to say if electricity is our only
8:29 input and there's either yes electricity or no electricity,
8:32 well, that actually maps quite nicely to the idea
8:35 of binary because we need just two symbols,
8:38 0 and 1, off and on, to represent that idea.
8:41 Of course with a single bit, you can't do all that much.
8:43 You can only count from 0 to 1, and that's it.
8:46 So computers tend to use larger numbers of bits to represent information.
8:50 And they do this ultimately physically.
8:53 So it turns out that with both plug-in the wall,
8:55 or even a light bulb or a switch thereof, you can represent a 0 or 1.
9:00 But if you want to represent more zeros and ones,
9:02 well, we just need, maybe, 8 bits at a time.
9:05 And if you've ever heard of the expression byte,
9:08 a byte is just a term describing eight bits,
9:11 eight zeros and ones, a more useful measure instead.
9:15 So given that, I think it's time, perhaps,
9:19 to see if we can't solve the problem ourselves.
9:22 Perhaps we could get, say, two volunteers to come on?
9:25 OK.
9:25 Saw one hand here and one hand over here.
9:28 Come on down, if you want to meet me on the other end of the stage.
9:32 Come on over here.
9:36 Come on down.
9:37 What's your name?
9:37 PRIYANKA: Priyanka.
9:38 DAVID MALAN: Priyanka, nice to meet you.
9:39 David.
9:40 Come on over and if you want to wait right here.
9:42 And what's your name?
9:43 CALVIN: Calvin.
9:44 DAVID MALAN: Calvin?
9:44 CALVIN: Yeah.
9:45 DAVID MALAN: David.
9:45 Nice to meet you.
9:46 Come on over here where Priyanka is.
9:47 So Priyanka, you raised your hand first, so you get to choose.
9:50 Do you want to go first or second in this little challenge ahead?
9:53 PRIYANKA: Uh, I'll go first.
9:54 DAVID MALAN: OK.
9:54 So Priyanka is going to go first.
9:56 If you want to stand over there, Calvin.
9:57 So the challenge at head here is could
9:59 you go ahead and represent for us in binary,
10:02 using each of these light bulbs and, in turn,
10:05 switches, as zeros and ones, say, the number 50?
10:10 So you might turn one light bulb on representing the 32s place.
10:18 Might turn a light bulb on representing the eighth place.
10:21 Our total count now is 32 plus not 8 plus 16, I think,
10:28 which is going to give us 32 plus 16, which is 48.
10:33 And so we get now a round of applause, if we could, for Priyanka.
10:38 Thanks very much.
10:40 Give us just a moment.
10:41 So each of these light bulbs, then, represents just a switch or a bit.
10:44 And inside of your computer, if you've ever heard the phrase transistor,
10:48 a transistor is just a tiny little switch in our computers.
10:50 So they have millions or billions of these switches
10:53 that they use physically to represent information and store values,
10:57 just like Priyanka did here.
10:58 So if a computer were to represent the number 50,
11:01 it would literally turn on three switches of sorts,
11:03 store a little bit of electricity here,
11:05 here, and here to represent the number 50,
11:08 and it would leave off all of the other switches.
11:11 The other five, in this case, if we're using eight bits or one byte.
11:14 Calvin you raised your hand second, and so we have one other challenge ahead.
11:19 Fortunately, these things are magnetic, so let's take things up a notch.
11:25 And if you would, Calvin— [LAUGHTER] --how about the number 13, if you will.
11:33 How would a computer represent the number 13 where each
11:36 of these light bulbs from 1 to 128 represents a bit?
11:44 We had, of course, the ones place over here,
11:49 the twos place, four, eight, 16, and so forth.
11:55 So we can ask the audience, should we turn on, for instance, this bulb here?
12:00 AUDIENCE: No.
12:01 DAVID MALAN: No.
12:02 Way too big.
12:02 How about this one?
12:03 CALVIN: No, too big.
12:04 DAVID MALAN: OK.
12:04 And you're in charge.
12:05 Ask the audience.
12:06 CALVIN: This one?
12:07 AUDIENCE: Yeah.
12:08 CALVIN: Yeah.
12:09 DAVID MALAN: OK.
12:09 So we have 1, 2, 4, 8.
12:12 CALVIN: 4.
12:13 DAVID MALAN: 4 gives us 8 plus 4 is 12.
12:15 And another round of applause, if we could.
12:20 Thank you.
12:20 You got the tougher job.
12:21 Thanks to you both.
12:22 So at the end of the day,
12:24 while this is a very large physical incarnation of the notion of binary,
12:28 that's all that's going on inside
12:29 of our computers every day when they represent information.
12:32 But we only, thus far, have the ability to represent numbers, it seems.
12:36 So how then does a computer allow you to send
12:38 text messages and emails and compose documents and so forth?
12:41 We need to all agree how we're going
12:43 to go about representing characters or letters of an alphabet,
12:46 be it English or something else, instead.
12:48 And any intuition for how, if a computer only has millions or billions
12:52 of switches that can be turned on and off, thereby representing numbers,
12:56 we could possibly go about representing something
12:58 other than numbers, like the letter A?
13:02 Say it again?
13:04 By a digit.
13:04 So we maybe just need to agree as a group, you know what?
13:07 Let's all agree that the letter A, in the context
13:10 of a word processing program or a text message or email,
13:12 just needs to be represented by a number,
13:14 and we all need to agree what that number is.
13:17 So maybe super simply, let's just say A is 1, B is 2, C is 3 and so forth.
13:22 And you could imagine then having a computer turn on lots
13:25 of little transistors to represent A and B and C,
13:28 so long as the software on that computer,
13:30 as we'll see, knows that it's a word processing program and not,
13:34 say, a calculator or something that's meant to use numbers alone.
13:37 So it turns out that computers don't actually use the number 1 for A or 2 for B.
13:41 It's a little bigger than that.
13:43 The world decided decades ago that the capital letter
13:45 A is going to be represented by the number 65.
13:50 65, which is to say, if you have a byte of information in the computer,
13:53 and this is the ones place, twos, four, eight, 16, 32, 64.
13:59 If a computer were to store the capital letter A using eight bits or switches,
14:04 it would just turn on those two, the 64s place and the ones place.
14:09 And so when you have actually received a message in a text message or an email
14:12 with a capital letter A, you have just
14:14 received a pattern of zeros and ones somehow,
14:17 wirelessly or via wires, representing that pattern.
14:20 Specifically, this pattern here, if we draw it not as light bulbs,
14:23 but as zeros and ones.
14:25 So it turns out there are certainly more numbers than just A's and B's and C's.
14:30 We have the whole alphabet plus punctuation, thanks to a system called ASCII,
14:34 the American Standard Code for Information Interchange,
14:36 which is just a fancy way of saying that there is a well-defined map
14:39 that humans around the world agreed on years
14:42 ago that looks a little something like this.
14:44 So A is 65, an I is 73, and dot dot dot to both ends.
14:50 So that is to say if you were to receive
14:52 a message from a computer or from a friend saying 72,
14:56 73, 33, or the pattern of zeros and ones representing those digits,
15:01 what message did you perhaps just receive?
15:04 72, 73, 33.
15:08 Yeah.
15:09 So, hi.
15:09 So quite literally, if you were to text a friend, hi,
15:12 they would receive a message that's essentially a pattern of zeros and ones,
15:16 72, 73, then something.
15:17 It's actually not obvious from the chart what they are,
15:20 but it turns out 33 was the number humans
15:22 gave years ago to represent an exclamation point instead.
15:25 And so any of the other punctuation symbols you might see on your keyboard,
15:28 similarly have numbers that a computer would use,
15:31 that all of us agreed on years ago, to represent that value.
15:35 But of course, this is very American-centric at the moment.
15:37 And indeed, the acronym ASCII has American in it.
15:40 So it was biased early on to American English, for instance.
15:44 But there's so many more characters in the world,
15:46 of course, such as accented characters and other languages altogether.
15:50 And frankly, there's also these things these days,
15:53 which even though they look like pictures,
15:55 you access them via your keyboard because
15:57 they are indeed just symbols in an alphabet.
16:01 There are zeros and ones, patterns of zeros and ones,
16:05 that represent those characters, as well.
16:07 That's what's known as Unicode, and that's, like, a superset of ASCII.
16:11 Because ASCII, way back when, used only eight bits,
16:13 which is not terribly many, to represent characters.
16:16 Unicode uses 8 or 16 or 24 or even 32,
16:19 which means we have a way many more possible patterns
16:23 of zeros and ones with which to represent things like this.
16:26 So this is face with tears of joy.
16:29 As of 2019, it is the most popular emoji sent on iOS devices, at least.
16:34 Does anyone want to hazard a guess as to what
16:37 the decimal number is that represents a face with tears of joy?
16:45 Not 65.
16:46 Not 72.
16:46 Not 73.
16:49 800.
16:50 Higher than that.
16:52 10,000.
16:53 Higher than that.
16:54 It's 128,514.
16:57 That's how many emojis await us down the road
17:00 because the numbers are now getting this big.
17:02 Or equivalently, this pattern of zeros and ones.
17:05 So at the risk of taking all of the fun out of ever sending someone an emoji,
17:09 when you send that face with tears of joy,
17:11 you're literally just somehow having your phone send
17:13 a friend's phone this pattern of zeros and ones.
17:16 And Android or iOS are presenting it as that yellow picture.
17:21 But that yellow picture, of course, itself is an image.
17:24 And it's composed of lots of little dots.
17:26 And odds are coming into this class,
17:27 you're generally familiar with using images,
17:29 certainly, and seeing the little dots that compose an image.
17:32 Especially if they're of low quality, you can really see those dots.
17:34 And so in a face like the emoji, we have lots of yellow dots.
17:38 How does the computer represent each of those dots?
17:40 Well, according to a system called RGB.
17:42 Red, green, blue.
17:44 So again, decades ago, people in a room decided, you know what?
17:47 To represent colors,
17:48 we still have to use just zeros and ones, little switches, mechanically.
17:53 But let's just all agree what numbers represent what colors.
17:56 So we just need another system for that.
17:59 Now it turns out that RGB essentially composes any
18:02 color of the rainbow by mixing together some red, some green, some blue.
18:08 And by combining those colors one on top of the other,
18:11 you can get any color of the rainbow you want.
18:13 So this is to say to store any dot on the screen, one pixel, so to speak,
18:18 in an image that you might take as a photo or send to a friend,
18:22 you are actually storing three values.
18:24 One, two, three.
18:24 Three numbers, really, that, of course,
18:26 at the end of the day, are zeros and ones.
18:29 Those three numbers just tell the computer how much red, how much green,
18:32 and how much blue to use to represent some dot on a screen.
18:36 So suppose that coincidentally, a computer were storing the pattern 72, 73,
18:42 33, albeit with zeros and ones or light bulbs, back-to-back-to-back like this.
18:47 Well, in the context of Photoshop or a browser or Apple photos or the like,
18:52 in the context of a graphical program,
18:54 your computer is going to interpret this same pattern of digits,
18:59 and in turn, bits, not as high, exclamation point,
19:02 but as some amount of red, some amount of green, some amount of blue.
19:05 And it turns out if you combine this much red,
19:08 72, this much green, 73, followed by this much blue,
19:11 33, what you get when you combine all three of those is a shade of yellow.
19:17 So for every single dot in that emoji, that face with tears of joy,
19:22 every dot in this image— and we can see it
19:25 if we really zoom in— is stored using three values.
19:28 Some amount of red, some amount of green,
19:30 some amount of blue that we can bind give
19:32 you yellow or black or gray or anything else,
19:35 depending on how you encode those values.
19:38 Meanwhile, images or videos, things like this that you might see on the internet
19:43 these days in the form of memes or anything else,
19:45 are actually just images, but they're multiple images in the same file.
19:49 If you've ever seen what's called an animated GIF,
19:52 which this happens to be that happens to be looping,
19:54 all our human eyes are seeing is one
19:56 image after another after another after another really quickly,
19:59 creating the illusion, therefore, of movement.
20:02 But this cat is not actually moving.
20:04 These are like five or 10 photographs
20:06 of a cat in different positions just being looped endlessly.
20:09 And that, too, is all a video is.
20:11 A video is just a sequence of images flying past your eyes so quickly,
20:15 we humans perceive it as actual movement.
20:18 And so that's almost everything we use
20:20 to represent information today in our computers.
20:22 We have zeros and ones from which we
20:23 get binary to which we then get decimal digits,
20:26 but we can use those digits to represent,
20:28 say, characters on the screen or colors on the screen and, in turn,
20:32 now even the more interactive.
20:33 Now what about something like music in a computer?
20:36 Another type of information you might want to represent?
20:38 Well, if we had a piano on the stage here,
20:40 we could quantize the notes you're playing using just numbers, as well.
20:45 What note you're playing, maybe it's A, B, C,
20:47 D, E, F or G or some variant thereof.
20:50 Maybe how long you hold the key down for, and if you hit it really hard,
20:53 maybe how loud it is.
20:54 So you could imagine using three values, the note, the duration,
20:58 and the volume just to represent something like a piano song.
21:02 [PIANO PLAYING] Might be one encoding of a song.
21:06 And I might use different values if I want to play it even louder and longer.
21:10 [PIANO PLAYING] And so forth.
21:14 Which is to say that at the end of the day,
21:16 no matter what media we use to represent information,
21:19 it all reduces to zeros and ones.
21:21 So once we have the ability to represent inputs,
21:23 be it numbers or letters or colors or videos, now we can talk about outputs.
21:29 So how do we get from inputs to outputs?
21:31 That's what's inside this so-called black box,
21:34 and this is where computer science comes in.
21:36 An algorithm.
21:37 Anyone know what this term is?
21:40 What's an algorithm?
21:41 You sort of read about it all the time these days,
21:43 especially in the context of self-driving cars and Siri and Alexa and so forth.
21:47 Yeah?
21:49 A set way to do something, yeah.
21:51 In the context of problem solving,
21:53 an algorithm is just step-by-step instructions for solving some problem.
21:57 So what might an algorithm be for a problem that we might want to solve?
22:00 Well, consider this.
22:01 This is an old school problem where you might have
22:03 lots and lots of names and lots of lots of numbers,
22:06 and those names are hopefully sorted alphabetically
22:08 from A through Z in a book like this.
22:11 And even though most of us don't really reach for this technology anymore,
22:14 consider that it's really the same
22:15 as your iPhone or Android phone or other device,
22:18 which has all of your contacts top to bottom
22:20 and you can scroll through them from A to Z,
22:23 or you can search for them by typing into the little autocomplete box.
22:26 How is even your phone solving this problem?
22:29 Well let's consider a simple approach.
22:31 I'm going to look at the first page and look for someone on the phone book.
22:35 Suppose that person's name is Mike Smith, last name starting with S.
22:37 Let me go ahead and look down.
22:39 He's not here.
22:40 Let me turn the page.
22:41 Let me turn the page.
22:43 Let me turn the page.
22:44 This is an algorithm.
22:45 It's a step-by-step process for solving a problem, finding Mike Smith.
22:48 Is this algorithm correct, would you say?
22:52 Yeah.
22:52 I mean, it's pretty slow, it's pretty stupid, in that it's going to take,
22:55 my God, forever, like, hundreds of page turns to find Mike Smith.
22:59 But if he's there, I will find him according to this step-by-step approach.
23:03 What if I speed things up a bit just because it's tedious, otherwise?
23:05 So I do two, four, six, eight, 10, 12, 14, 16 and so forth.
23:11 Is that algorithm faster?
23:13 Absolutely.
23:14 Literally twice as fast.
23:15 Is it correct?
23:16 AUDIENCE: No.
23:17 DAVID MALAN: No.
23:17 Why?
23:18 [INTERPOSING VOICES] DAVID MALAN: Yeah, we might skip them.
23:21 I might get unlucky and eventually, I might get to the S's.
23:23 But darn it if Mike wasn't in between two pages as I turn them at once.
23:28 So it's not a fatal flaw.
23:29 That algorithm, I could fix by just saying if you
23:32 hit the T section or maybe Sn instead of Sm,
23:35 just back up one or so pages just to fix that bug or mistake, so to speak.
23:40 But it, at least, is twice as fast.
23:43 But if this phone book has 1,000 something pages,
23:45 it's still going to take me maybe 500 pairwise turns just to find Mike Smith.
23:51 That's a while just to look someone up.
23:53 But most of us, if you've used this technology,
23:55 instead, did what, back in the day?
23:58 Go roughly to the middle if there aren't
24:00 little letters on the side off which to cheat.
24:03 So roughly into the middle.
24:04 I'm in the M section.
24:05 Now the M's, of course, mean that Mike is not this way, which would be the A's.
24:09 He's probably this way toward the Z's because S,
24:12 of course, is between the M and the Z.
24:14 So at this point, I can literally tear the problem in half,
24:18 throw half of the problem away very dramatically and unnecessarily,
24:24 making the point that we've now gone from 1,000 some odd pages to what?
24:27 500.
24:28 And I can do it again.
24:29 Ah, I went a little too far.
24:30 I'm now in the T section,
24:32 so I can tear the problem in half again, throw that half away,
24:35 and now I'm down from 1,000 to 500 to 250 pages only,
24:40 after just two steps in this step-by-step process.
24:44 And if I repeat this again and again and again, hopefully, I'll be left,
24:47 ultimately, with, say, just one page on which Mike Smith either is or is not.
24:53 And I can call him or quit.
24:55 So that algorithm would get me to the solution so much faster.
24:58 And we can appreciate this even if we just look at some of the numbers,
25:01 ultimately, as follows.
25:03 So if I start with, say, 1,024 pages total in the phone book,
25:08 and I'm looking for Mike Smith, and I divide and conquer this problem,
25:11 splitting the problem in half and in half and in half, I go to 512,
25:14 I go to 256, 128, 64, 32, 16, eight, four, two, and one.
25:21 After just 10 steps, I have found Mike Smith's page.
25:25 By contrast, that first algorithm where I just did one page at a time,
25:29 how many steps, maybe, might it have taken me to find Mike Smith?
25:33 Yeah, like, 700, 800, roughly where the S's might be.
25:36 So in the worst case, 1,000 pages, if I look through the whole thing.
25:39 The second algorithm, maybe, 500 pages because I'm going twice at a time.
25:43 But my God, 10 steps with this algorithm here.
25:47 And odds are that would be the algorithm most
25:49 of us in this room would reach for by default,
25:51 which is to say that a lot of problem solving really,
25:53 as we'll find, is just about harnessing
25:56 your existing intuition and comfort with ideas that now
25:59 you just need to translate in such
26:00 a way that machines and other humans can understand.
26:04 So how might we just think about how much better that algorithm is?
26:08 Well, consider this first line here.
26:10 On this y-axis, or vertical axis,
26:13 let me describe this as the time to solve some problem.
26:16 And on the horizontal, or x-axis, the size of the problem.
26:19 So the number of pages in the phone book would get bigger as you go to the right
26:23 and the number of seconds or page turns
26:26 required would go up along the y-axis here.
26:28 So that first algorithm, depicted here in red,
26:31 suggests a one-to-one relationship between the number of pages
26:34 in the book and the number of seconds to find someone.
26:37 So you have this straight line.
26:39 A slope of 1 over 1, if you will.
26:41 And so if we consider the second algorithm,
26:44 the second algorithm is also going to be a straight line,
26:47 but that straight line is going to be lower on the graph.
26:49 Why?
26:50 Because for any size problem,
26:51 it's going to take me half as much time to search that phone book because,
26:55 of course, I'm going two pages at a time.
26:57 So if we see this, for instance, if this dashed line represents some number
27:00 of pages in the phone book, maybe 1,024,
27:02 well, you can see that it might take this many seconds
27:05 or page turns to actually find Mike Smith with that second algorithm.
27:09 But in the first algorithm,
27:11 that same number of pages would take way more time to solve,
27:15 literally twice as much time in this case.
27:17 Well what about the third algorithm?
27:19 Well, even if your memory of what a logarithm is a little hazy,
27:22 it just describes a fundamentally different shape.
27:24 The green line describes that third and final algorithm whereby you divided
27:28 the problem not one page at a time or two pages at a time,
27:31 but 50% again and again and again.
27:35 You have it again and again and again.
27:37 And notice that as the number of pages in the phone book gets really large,
27:41 you barely make an impact on how much time it takes to solve that problem.
27:47 For instance, if Cambridge and Allston, two towns here in Massachusetts,
27:50 merge next year and their phone books become one phone book that's twice as big,
27:54 so not 1,000 pages each, but 2000 pages total,
27:57 how many more steps might it take us to find Mike Smith
28:00 in next year's phone book if it's got 2000 pages instead of 1,000?
28:04 Just one more step.
28:06 But the first two algorithms, that's another 1,000 steps, maybe, or another 500.
28:10 These are fundamentally big differences in efficiency, so to speak.
28:15 So let's translate this idea, this intuition, into the first example of code.
28:20 There's a pseudo code.
28:21 And there's no one formal definition of this.
28:23 Pseudocode is code-like syntax that you write in English
28:25 or your own spoken language that represents your ideas, but in a succinct way.
28:30 And so I might propose that this algorithm for finding
28:32 Mike Smith might be written in pseudocode English-like syntax as follows.
28:37 Step one, pick up phone book, which was indeed the first thing I did.
28:40 Step two, open to the middle of phone book, which is the next thing I did.
28:43 Step three might be look at the page to see
28:46 if someone's there and if Smith is on that page, what do I want to do?
28:50 Well, my code is going to look a little different now,
28:52 and I'm going to deliberately indent to make
28:54 clear that there's a dependency here of some sort.
28:57 I'm going to go ahead and step five and call Mike only if line four is true,
29:02 that he's on the page.
29:04 Else if Smith is earlier in the book, to the left, so to speak,
29:08 I'm going to go ahead and open to the middle of the left half of the book,
29:11 and then what am I probably going to want to do next?
29:14 AUDIENCE: [INAUDIBLE] DAVID MALAN: So, yeah, this, ultimately.
29:16 How do I do this again and again?
29:18 Well, I already have some code, if you will, on line three that does that.
29:22 Look at page and then make a decision to go left or go right.
29:26 So I'll just say go back to line three after going to the middle
29:29 of the left half of the book if Smith is indeed earlier in the book.
29:33 The other scenario, of course, is the opposite.
29:35 So else if Smith is later in book,
29:37 let's open to the middle of the right half of the book,
29:40 and then let's go to line three.
29:42 Else, there's a fourth possible scenario or case.
29:45 What else might happen in this algorithm?
29:49 AUDIENCE: [INAUDIBLE] DAVID MALAN: He's not there.
29:51 And so I probably want to anticipate that and just say quit if, indeed,
29:54 he's not on the page, to the left of the page, or to the right of the page.
29:59 So there is one way of expressing
30:01 this pseudocode albeit now in just this English-like syntax.
30:05 But in this syntax alone, there's some commonalities,
30:08 some features we're going to see over
30:09 the next several weeks not only in pseudocode, but in a language called Scratch,
30:13 a language called C, a language called Python and more.
30:16 There are certain constructs in programming,
30:19 procedural programming, so to speak,
30:20 that are going to be common among all of these languages.
30:23 Highlighted in yellow here are what, henceforth,
30:25 today and onward, we're just going to call functions.
30:27 These are verbs or actions that just tell the computer,
30:30 or in this case, the human, what to do.
30:33 So those are functions.
30:34 Now highlighted in yellow instead are what we're going to call conditions.
30:37 These are branches, sort of forks in the road so you can either
30:40 do this or you can do that or maybe this other thing as well.
30:43 But to make those decisions, you have to ask yourself a question.
30:47 And those questions, in computer science,
30:49 are called Boolean expressions, after a mathematician named Boole.
30:52 And a Boolean expression, highlighted now in yellow,
30:55 are just questions that have yes or no answers or, if you will,
30:59 true or false answers or, heck, now that we know binary, one or zero answers.
31:04 So even in code, we see a hint of why ones and zeros are helpful.
31:08 Lastly, there's this thing here.
31:10 Go back to line three.
31:11 We've used it in two places.
31:12 That refers to something we'll call a loop.
31:14 It's a cycle that does something again and again.
31:18 So beyond those four ideas,
31:20 functions, conditions, Boolean expressions, and loops,
31:22 we're about to see a bunch of others, as well.
31:24 Variables, reminiscent of what you might recall from algebra,
31:27 but more powerful now in this context of programming.
31:30 Something called threads and events.
31:31 And we're going to do this by way of an actual programming language.
31:35 But it's not yet going to be this one.
31:36 Indeed, just a week from now will you actually understand what this means.
31:41 Odds are 2/3 of you have no idea what this actually is, and that's OK.
31:46 But it's a program written in a language called C— more
31:49 on that next time— that quite simply says hello to the world.
31:53 But we're going to do it today in the context
31:55 of a graphical language from my MIT's Media Lab called Scratch.
31:58 This is a language via which you can program
32:01 a computer by dragging and dropping blocks or things
32:03 that look like puzzle pieces that interlock together so
32:06 that you can tell the computer exactly what to do, step-by-step.
32:10 And we'll see in this language today,
32:12 and for the first problem set or programming assignment,
32:14 that you can express all of these ideas
32:16 from pseudocode in an actual language like Scratch.
32:20 So what lies ahead?
32:21 Well at scratch.MIT.edu, which I'm about to pull up myself,
32:26 is going to be where you spend time in the first problem set.
32:28 And it's going to look quite like this when you open it up.
32:31 On the left hand side of this website,
32:33 this web-based programming environment from MIT,
32:35 you're going to see on the left hand side
32:37 a whole bunch of puzzle pieces, so to speak.
32:39 And they're categorized according to some different colors there on the left.
32:43 In the middle, there's just going to be a big white canvas, initially,
32:46 onto which you can drag and drop those puzzle pieces
32:48 and lock them together to make the program do something.
32:52 What can you make it do?
32:53 Well, on the top right here is the so-called stage in Scratch.
32:56 By default, there's only one character, or sprite, on that stage.
33:00 Scratch himself, and he can move up, down, left,
33:02 right and do any number of other things if you tell
33:05 him what to do by dragging and dropping those puzzle pieces.
33:08 If you don't like that cat or you want many others,
33:11 you can also add multiple sprites, or characters, by creating them in that area.
33:16 So let's actually do this now with some sample programs
33:19 such that we can actually begin programming using this environment.
33:24 I'm going to go ahead now and open up a browser here.
33:27 And in just a moment, you'll see on the screen scratch.MIT.edu itself.
33:34 So if I go ahead and create by simply clicking up there, we'll see this editor,
33:38 ultimately, that, by default,
33:40 has this tutorial that I'm going to go ahead and dismiss.
33:43 But now we see that same environment.
33:45 And you'll see that above Scratch here over at top right,
33:47 there's this green flag and this stop sign.
33:49 The green flag is what you can click as the human to make the program go.
33:53 The stop sign will make any program stop.
33:56 So it turns out among all of these categories here,
33:59 there's, for instance, some orange ones called Control.
34:02 There's some yellow ones called Events.
34:04 And we'll focus on this latter one first.
34:06 If I go ahead and drag from events this puzzle piece here,
34:10 this is how I can begin programming.
34:11 When the green flag is clicked, do the following.
34:14 What do I want to do?
34:15 Well, let's have this cat just say hello.
34:17 And from having used this program before, I know that under Looks,
34:20 I can go ahead and say something like, say hello.
34:23 And notice not only does the shape match
34:25 the orange puzzle piece or yellow puzzle piece,
34:28 notice that it magnetically wants to snap together, and if I let go, it will.
34:31 And I'm going to say perhaps one of the most
34:33 canonical things to say in your very first program,
34:36 which is just, conventionally, hello world, and leave it at that.
34:39 I'm going to now go ahead and click the green flag.
34:41 And voila, our very first program.
34:45 The same effect.
34:46 [APPLAUSE] Thank you.
34:50 Thank you.
34:51 Very low bar so far, but we'll improve upon this next because this cat
34:55 is pretty inanimate and is just now saying hello.
34:58 What if we wanted him to do more than that and say not hello,
35:01 but hello to me or hello to you?
35:03 Well, it turns out we can do this a little differently, as well.
35:05 I'm going to go ahead and throw this away by just dragging it over on the left.
35:09 And the puzzle piece just goes away.
35:11 And if I poke around a little further under these blue blocks,
35:13 for instance, Sensing,
35:14 there's a bunch of puzzle pieces related to Scratch's environment.
35:18 And one of those is this one here, ask, what's your name?
35:21 And wait.
35:22 But that what's your name expression is
35:23 in a white box that I can actually change.
35:25 So you can ask any questions you want, but I'll go ahead and use that default.
35:29 And now notice also over here in blue is Answer,
35:32 which is another circular shape which represents
35:34 what we're going to start calling a variable.
35:36 That variable is going to store whatever the human
35:39 types in when asked for his or her name.
35:41 So what do I want to do when I actually get the person's name?
35:44 Well, let me go back to Looks.
35:46 Let me go ahead and say hello.
35:48 And I'll go ahead and say hello and then another one, say hello again.
35:53 But instead of this, I want it to say my name.
35:56 But it would be incorrect to just type my name because then my name is
36:00 always going to be David no matter who plays this game or is asked the question.
36:04 So I don't want to do that.
36:05 If I go instead to Sensing and then
36:07 drag and drop this puzzle piece, notice this.
36:09 It wants to magnetically snap in there.
36:11 And it will grow to fit it.
36:12 So now I can say hello and then I can say name.
36:16 So let me go ahead and hit stop and play again.
36:18 What's your name?
36:19 I'll go ahead and type in David.
36:20 Enter.
36:21 And now David.
36:24 Huh, I feel like we forgot the hello.
36:27 This is my first bug.
36:30 Any thoughts as to why?
36:31 What did I do wrong?
36:32 Yeah?
36:33 AUDIENCE: [INAUDIBLE] DAVID MALAN: Yeah.
36:38 I mean, I told the computer via this algorithm to do three things,
36:42 ask what's your name and wait,
36:43 but then I just say said hello, say answer in such rapid succession.
36:47 And my God, our Macs and PCs and phones these days are so fast,
36:50 they're going to do so many things so quickly that it did say hello,
36:53 it's just none of us really saw it because my name immediately overrode it.
36:57 So I can fix this in a couple of ways.
36:59 Let me go ahead and go back to Looks for just a moment,
37:01 get rid of this puzzle piece, and maybe say hello for two seconds.
37:05 Then let me go ahead and say my name or the user's
37:08 name for two seconds as by dragging answer now into here.
37:11 So that was my first bug in code, so to speak.
37:14 Let me go ahead and play again, type in David, and now it's hello, David.
37:19 All right.
37:20 So better.
37:20 It's a little weird because you typically don't greet someone by saying hello,
37:25 David, two seconds later.
37:27 So what if we kind of combine this expressions and say not hello world,
37:31 but hello comma David?
37:32 Well, we can do this in a different way.
37:34 Let me go back over here and, for instance,
37:37 get just one of those say blocks like this.
37:39 I'm not going to worry about saying it for some number
37:42 of seconds because I'm only going to say one thing now.
37:44 But I somehow want to say hello comma and then the user's name.
37:49 Well, if I poke around further,
37:50 and you would only know this by having seen it before,
37:52 it turns out there's this puzzle piece down here called Join.
37:55 And it's a little weird that the default words are apple and banana,
37:58 but those are just placeholders.
38:00 If I go ahead and drag this over here,
38:03 it grows to fill and it overwrites what was there.
38:06 I can say hello comma and then instead of hello banana,
38:10 let me go back to Sensing,
38:12 drag the user's answer, and now we say hello comma so and so.
38:16 So let's try this now instead.
38:18 Green flag, type in my name, Enter.
38:21 Hello comma David.
38:23 So now the program isn't all that much more complicated,
38:25 but notice that we're starting to nest these verbs, these functions.
38:28 We're asking for a name and then we're
38:30 saying the result of joining the following two things.
38:34 So there's a few ideas to keep track of at a time.
38:36 But this is actually quite like what we
38:38 were doing from the get-go earlier as follows.
38:41 For instance, if we want to just say hello world with this puzzle piece here,
38:44 this actually maps perfectly to our fundamental
38:48 definition of what problem solving is.
38:50 The input to that puzzle piece is, of course, just hello world.
38:53 The function or algorithm that you want to execute,
38:57 step-by-step instructions for saying something,
38:59 Scratch calls Say in purple, and the output you want,
39:02 of course, is Scratch saying hello world.
39:05 Now in the more sophisticated example, consider this.
39:07 We asked what's your name?
39:08 And then we waited.
39:09 Well, that picture would look like this instead.
39:12 The input to that question is, of course, what's your name?
39:15 The algorithm, or in this case, function,
39:17 via which we're solving that problem is to ask and wait, taking in that input.
39:22 And the output we get back is now answer.
39:25 And then lastly in that third example,
39:26 where things got a little fancier and you had
39:28 to start dragging and dropping and nesting these puzzle pieces,
39:31 notice that this is the same idea.
39:33 The input now is two things, hello and answer.
39:36 Those go into a function called Join,
39:38 the output of which should be hello comma David.
39:41 But now we want to pass that output as the input
39:46 to the Say block so that the final result is hello,
39:50 David right out of the cat's mouth.
39:52 So in this way, even with the simplest of puzzle pieces,
39:54 does everything fit into this same model of problem solving.
39:59 But let's now make things a little more interesting.
40:01 Rather than just talk and text with this cat,
40:03 let's go ahead and have it do some other things instead.
40:06 Let me go ahead under Sound, for instance, and it looks like there's a block
40:10 in pink here called Play Sound Meow until done.
40:12 And now let me stop the old program and start the new.
40:15 [CAT MEOWING] OK.
40:17 A little piercing, but adorable.
40:19 And if you want to hear it again— [CAT MEOWING] --I can
40:22 click the green flag— [CAT MEOWING] --and I can click the green flag.
40:26 Of course, this is a pretty boring cat if
40:29 it goes lifeless after it said just one meow.
40:32 How would we get it to perpetuate that sound and just meow every few seconds?
40:37 What constructor idea might we want to use here?
40:39 AUDIENCE: [INAUDIBLE] DAVID MALAN: Yeah, so some kind of loop.
40:41 So it turns out in Scratch, there's a few ways to do this.
40:44 But if I go down to Control, you'll see a couple of blocks here.
40:47 Repeat some number of times, by default, 10, or forever.
40:50 I'm going to go ahead and maybe do this forever.
40:53 [LAUGHTER] And I'm going to drag and drop this now into here.
40:56 Notice I can move things around wherever I want.
40:58 And now I can reattach this up here.
41:01 And now play.
41:02 [CAT MEOWING REPEATEDLY] It's a very agitated cat at the moment.
41:08 I can calm him down, perhaps, by dragging and dropping this.
41:11 And notice even if there's no room, it will grow to fill.
41:15 [CAT MEOWING SLOWED DOWN] One second.
41:17 Now it's a happier cat, if you will.
41:20 But now that we have the ability to have the cat do something forever,
41:23 it doesn't have to just do the same thing again and again.
41:26 It can interact with me or its environment.
41:29 So instead of playing the sound here— someone following along at home?
41:33 So instead of playing the sound here, let me go ahead and try this.
41:37 Let me go to Sensing and go ahead to— what might I want to do here?
41:43 Let's go ahead and under Motion, rather, under here, point toward mouse pointer.
41:50 So point towards mouse pointer and then go ahead and move some number of steps.
41:54 And I'm going to have it move one step or dot or pixel at a time.
41:57 And here now we'll get this effect.
42:00 It looks as though now he'll kind of follow me, right?
42:03 And as I move my cursor,
42:04 he is forever pointing toward the cursor then moving one step.
42:08 Of course, he's a little slow.
42:09 And let me go ahead and stop.
42:10 If I make him take 10 steps at a time,
42:13 or 10 dots or pixels on the screen, now it seems a little harder to avoid.
42:17 And you can sort of— he'll literally do as you move your cursor here.
42:22 All right.
42:23 So now that we have the ability to do something again and again,
42:26 let's have something count up.
42:27 For this one, let me go ahead and grab something from online.
42:32 So on CS50's website,
42:33 we'll always make available the examples and source code from each class.
42:37 And this time, I want to go ahead and get this sheep here.
42:41 So it turns out you don't have to just use a cat.
42:43 You can use a sheep if you prefer.
42:44 And let's see.
42:45 By looking at this code first, what is this sheep going to do?
42:49 When the green flag is clicked,
42:51 there's this orange puzzle piece called Counter to one.
42:54 What is that?
42:54 That's an example of— what might we call this?
42:58 Yeah.
42:59 It's called a variable.
43:00 Now in algebra, we typically use x and y and z for variables.
43:04 In programming, when you want to store
43:06 some value in a placeholder like a variable,
43:08 you typically give it more descriptive words because x, y,
43:11 and z don't really tell the programmer or someone reading it what it's doing.
43:14 So we call this variable Counter and we set it equal to 1.
43:17 Now forever, the sheep is going to do what?
43:19 It's going to say the counter for one second,
43:21 it's going to then wait for one second,
43:23 and then it's going to change, or add 1 to, the counter as its final step.
43:28 So here we have, if you will,
43:30 counting sheep whereby it will now just perpetually count up from 1 to 2 to 3.
43:39 And probably, if we let this thing go, up to infinity.
43:43 So once we have the ability now to do variables,
43:45 what if we start to make our programs
43:47 more interactive and start to remember information?
43:50 Let me go ahead and into our examples from before,
43:54 and grab another example here now instead.
43:56 I'm going to go back to what's called a Studio in Scratch,
43:59 where all of these examples currently are.
44:02 And I'm going to go and open up an example called pet 0.
44:05 Computer scientists typically start counting from zero because that's
44:08 symbolic of all of the light bulbs being off.
44:10 And so here's a program now that if I
44:12 hit Play does not seem to do anything at first,
44:16 but notice as I move my cursor over— [CAT MEOWING]
44:20 --I'm kind of petting the cat now, if you will.
44:24 So how is this working?
44:25 Well, he, too, is just forever listening or waiting for something to happen.
44:29 It's forever doing this if Touching Mouse
44:32 Pointer then Play Sound Meow until done.
44:35 So now the cat is being responsive to the user input not following my cursor,
44:38 but responding just if I'm actually hovering over him.
44:42 We can, of course, change this up a little bit in version two
44:45 of this, otherwise known as pet one because we started counting at 0.
44:50 What should I not do with this program?
44:52 [CAT MEOWING] Maybe don't pet this cat.
45:00 Why?
45:00 Well, this time it is forever checking if I'm touching the mouse pointer.
45:05 And if so, it's going to apparently play a sound roar,
45:08 else it plays the sound Meow, which seems to be happening.
45:12 So here we go.
45:13 [CAT MEOWING] [CAT ROARING] So don't pet the cat.
45:19 And so that's just a condition asking a question,
45:22 a so-called Boolean expression if Touching Mouse Pointer.
45:26 Well, now let's do something a little fancier still.
45:28 Let me go ahead here and do this.
45:30 Let me go ahead and make this one from scratch, no pun intended.
45:34 And I'm going to go ahead and start with an event.
45:36 When the green flag is clicked, let me go ahead and grab some motion here.
45:41 Let me go ahead and grab Set Rotation Style to left right
45:45 just because this will make sure that he ultimately does as we intend.
45:49 I'm going to go to Control.
45:50 I'm going to do the following forever.
45:52 Suppose I want the cat to just bounce back and forth on the screen.
45:56 Well, the first thing I need to do
45:57 is animate him and actually make him start moving.
46:00 And the best way to do that, frankly,
46:02 would just be to go to Motion and move some number of steps,
46:05 maybe 10 steps to go quickly or one step to go slowly.
46:08 But I can ask a question every time the cat moves.
46:11 I can go and ask something like this.
46:14 If something is true, go ahead and maybe do something else.
46:18 So maybe bounce off the wall.
46:19 So how do I say if you're touching the edge, go ahead and bounce backwards?
46:24 Well, it turns out if you poke around, you'll see something like this.
46:27 If touching Not Mouse Pointer, but notice this edge,
46:32 I can use the little dropdown, change what the puzzle piece says.
46:35 I can now move this Boolean expression into place.
46:38 The condition will grow to fill.
46:40 And what do I want to now do?
46:41 Well, if he touches the edge, I'm going to go ahead and say turn not 15 degrees,
46:46 which is the default, but I'll do it 180 instead.
46:50 And now we have our own little animation where
46:54 he's going back and forth and back and forth.
46:57 Of course, this seems a little unrealistic that he's just bouncing happily so,
47:01 so there is a non-academic feature we can now introduce.
47:05 For instance, you can turn on your computer's microphone and say ouch.
47:11 That is what Ouch looks like.
47:13 If I go ahead and save this, call this Ouch, go back now to my code.
47:18 Let's go ahead and into sound here and maybe play not the sound Meow,
47:23 but maybe the sound Ouch,
47:25 such that now this cat— [OUCH SOUND PLAYING REPEATEDLY] OK.
47:33 So maybe a little more dynamic.
47:36 But it turns out he's really not walking or running.
47:39 He's really just— [OUCH SOUND] --sliding across the screen, right?
47:42 His legs are never actually moving.
47:44 Now, why is that?
47:45 Well, it turns out that the costume that this sprite is wearing,
47:48 that the cat is, it's just a picture.
47:49 It's an image composed of lots of little dots.
47:51 And you know what?
47:52 To animate a character and bring some life to it,
47:55 so to speak, all we really need is at least one more picture.
47:58 After all, that's all an animated GIF or a video is, multiple pictures.
48:01 So here's one, here's two.
48:04 Here's one, here's two.
48:06 And even though he's definitely making some leaps with each stride,
48:09 if you do this fast enough, it would seem that the cat is actually
48:12 making some motion and walking instead of just sliding.
48:15 So how might I go ahead and do this?
48:18 Let me go ahead and open up this example, which I've made in advance.
48:21 This one's called bounce one.
48:22 And in bounce one here, I have the following second costume.
48:28 If I go ahead and click See Inside and click Play Now,
48:31 you'll notice now he's kind of moving.
48:34 It's a little jaggy because he's moving
48:36 from one position to another really quickly,
48:38 but now it's the illusion of movement.
48:41 So if you've ever played a game or you've
48:43 ever created some animation yourself or even a film,
48:45 this really is what's been happening underneath the hood all this time.
48:49 But you don't have to have just one cat or one sprite in a program.
48:52 We can actually have multiple.
48:53 Let me go ahead and open up another animal here.
48:56 This one, a sea lion.
48:58 So in this sea lion here,
48:59 if I See Inside and see its code, there's a lot going on here.
49:03 So let's see what this thing does first.
49:04 If I go ahead and click the green
49:06 flag— [SEA LION BARKING] --it's really, really annoying.
49:09 [SEA LION BARKING] Now, why is that?
49:12 There's some loop in here, clearly,
49:14 that's just doing the same thing again and again and again.
49:18 How might, based on this code, I stop the sea lion from barking?
49:24 Yeah.
49:25 So that's the solution.
49:26 Let's go ahead and hit the space bar.
49:31 Why did that actually get him to stop barking?
49:34 Well, notice this.
49:35 There's two scripts in this program, which is a little different from before.
49:38 Each of these represents a script or a program.
49:40 Notice here there's a variable called muted, and by default, it's false.
49:43 That is off.
49:44 So muted is false, or off, which means it's not muted, which is why we hear it.
49:48 Then it does forever the following.
49:50 If the key space is pressed, go ahead and check the following question.
49:55 If muted is true, change muted to false, else change muted to true.
50:00 So this is a very common approach in programming where if you have a variable,
50:03 like something called muted that's either true or false,
50:06 1 or 0, on or off, you can change its value by just asking that question.
50:10 If muted is true, change it to false, else set it to true.
50:15 Meanwhile, if we scroll up,
50:17 there's another script here that was doing something again and again.
50:21 And I'll zoom in on this one.
50:22 When the green flag was clicked, the sea lion was also forever doing this.
50:26 If muted is false, that is, if it's not muted,
50:29 go ahead and play the sound sea lion and go ahead and say hi,
50:32 hi, hi for two seconds and then wait for one second.
50:35 And do that again and again and again.
50:38 So in programming, as in Scratch here,
50:40 you can do multiple things at a time sometimes with languages,
50:43 such that they're both running together in parallel,
50:45 if you will, or looping again.
50:47 And they can somehow intercommunicate by using something like a variable.
50:52 Let's look at one final example involving two different sprites,
50:55 this one an old school game that you might recall growing up called Marco Polo.
50:59 In this game of Marco Polo,
51:01 one person yells out Marco and one or more other people yell out Polo.
51:05 And the first of them is typically blindfolded,
51:07 so you're trying to find that person based only on his or her voice's response.
51:12 So in this program here, if I go ahead and click the green flag,
51:16 notice that nothing happens yet until I hit the space bar.
51:20 And we'll see that the orange puppet says Marco and the blue puppet says Polo.
51:26 But how does that work?
51:27 Well, here is the code for the orange puppet.
51:30 Forever, he is doing the following.
51:33 If the key space is pressed, that is the space bar,
51:36 say Marco for two seconds, but then one other feature.
51:39 And this is new.
51:40 It broadcasts what's called an event.
51:41 So it turns out that computers can't just
51:43 see what another program or sprite is doing,
51:46 but they can listen for something called an event.
51:48 It's sort of a secret message from one program to another.
51:51 So broadcast event is this other puzzle piece that can just say event.
51:56 And now notice if I click not on the orange puppet down here, but on the blue,
52:00 the blue puppet has even less code,
52:02 but it is not waiting for the green flag to be clicked.
52:05 Instead, it is waiting until it receives this so-called an event,
52:09 a sort of invisible message from one sprite to another.
52:12 And once he receives that event, it says Polo for two seconds.
52:19 All right.
52:20 So along the way, it turns out that there
52:22 are better ways to solve some of these problems.
52:25 And we can actually start to think now a little more in terms of design,
52:30 the design of the quality of your code.
52:32 I'm going to go ahead and do this.
52:35 Under events, I'm going to go ahead and grab when green flag is clicked,
52:38 and I'm going to go ahead and say something this time.
52:40 Let's go ahead and say cough for one second like this.
52:45 And then let me go ahead and wait for some number of seconds, like one.
52:49 And then you know what?
52:50 Let me go ahead and cough three times.
52:51 It's not uncommon when you're coughing, in the real world, to cough three times.
52:54 So I'm going to right click or Control click,
52:56 I'm going to go ahead and duplicate, and just attach another one of those.
52:59 And I'm going to right click or Duplicate and give me one of these.
53:02 And now, of course, the cat is going to cough,
53:07 cough, cough or meow, and three times in a row.
53:10 Now this code is correct.
53:12 It does cough three times and it waits one second after each,
53:15 but it's not very good code.
53:17 It's not well-designed, as a computer scientist would say.
53:20 What could we do better with this code based on the ideas we've seen thus far?
53:23 AUDIENCE: [INAUDIBLE] DAVID MALAN: Yeah.
53:25 So we can loop instead, right?
53:26 And Copy Paste is rarely the solution when programming,
53:29 be it in Scratch or in C or in Python or other languages.
53:33 So I'm actually going to throw all of this away.
53:35 Let me go ahead and just grab a repeat block, change that default ten to three.
53:39 Let me grab these pairs of blocks and put them in here,
53:42 drag and drop this up here.
53:43 So now I'm going to go ahead and repeat three times,
53:46 say cough for a second, and then wait one second.
53:49 And now the program is just better designed.
53:52 It is no different from before,
53:53 but it's a little easier to maintain now for me or someone else
53:56 because if I want to change how long something's happening or what's being said,
54:00 I can change it now in one place instead of multiple.
54:04 But there's this other idea in computer science, this notion of abstraction.
54:07 Right now, this is a program that just
54:10 so happens to implement the notion of coughing.
54:12 But what if I want to use the same idea in multiple programs and I
54:17 want to give myself a custom puzzle piece
54:18 that does not come with Scratch called cough?
54:22 Well, there's this one other feature up here I can do like my blocks,
54:25 and I can make a block.
54:27 And I'm going to go ahead and call this cough.
54:29 And that puzzle piece, once I click OK,
54:31 is going to give me this pink block here.
54:35 I'm going to go ahead now, for instance,
54:37 and move all of this down to the custom puzzle piece.
54:40 And now notice because I've made a new block, I have this pink piece here.
54:44 I can now move this over here.
54:46 And frankly, out of sight, out of mind.
54:48 I can literally ignore those puzzle pieces I created because now I
54:53 have a new puzzle piece just called cough that says what it does.
54:57 This is an abstraction in the sense
54:58 that I don't care how you implement coughing,
55:01 I just care that your program can cough.
55:04 And so we have this notion of reusability
55:05 that starts to make our code no less sophisticated,
55:08 but much, much smaller and much less prone, potentially, to mistakes.
55:12 And I can take this one step further.
55:13 Let me go ahead and open up a different variant of this one altogether,
55:17 this one in cough three.
55:19 You can have these custom puzzle pieces even take arguments.
55:23 You can have this puzzle piece called cough say, well,
55:25 how many times do you want to cough, thereby taking an input.
55:28 Then you can repeat that number of times cough for a second and wait one second.
55:34 So if you want to now use this fancier puzzle piece up here,
55:37 notice this now looks even simpler.
55:40 Go ahead and cough three times.
55:42 And everything has been abstracted away.
55:44 If I scroll up and out of the way,
55:46 you don't even know or have to care how or why cough was implemented.
55:51 And so whereas we began this whole conversation just looking for Mike
55:54 Smith and trying to find an answer to a problem correctly,
55:57 we talked then about efficiency and finding
56:00 that solution not only for sure, but also quicker.
56:03 And now we've spoken a little bit to ideas that lie ahead
56:06 when it comes to the design of the quality of your code.
56:10 So where does that actually leave us?
56:12 Well, let me go ahead and open up a couple of final examples here,
56:15 one of them that I actually made back in my day.
56:18 And so this, when I actually started using Scratch for the first time,
56:23 it gave me this program here called Oscar Time.
56:26 And Oscar Time, reminiscent of an old
56:28 song from Oscar the Grouch singing, does this.
56:31 [SINGING] There's this stage.
56:33 Notice the lamp post here and the trashcan.
56:35 And apparently, something falling from the sky that looks like a piece of trash,
56:38 but it's just a sprite.
56:39 It's what could have been a cat,
56:41 but I changed the costume on the cat to be a piece of trash.
56:44 But notice if I move my cursor and click and drag,
56:47 notice that this piece of trash follows the cursor
56:50 just like Scratch followed my cursor before on the screen.
56:54 And notice if I move it over to the trash can,
56:56 the trash can opens up, which is a Sensing question.
57:00 If touching trash can, then open up.
57:03 And open up probably just means change the costume
57:06 to show a different image instead of the original,
57:08 thereby a very simple idea of animation.
57:11 And now notice when I let go, if touching trash can and let go,
57:17 Oscar should come out of the trash can, count up to one,
57:20 which is my score, and then the game continues.
57:22 Now there's more trash falling.
57:23 Let me go ahead and do this.
57:25 And you'll see that these basic ideas of conditions and loops
57:28 and variables and Boolean expressions together
57:31 can compose a pretty interactive game.
57:34 This game took me eight or more hours to make,
57:36 and it's because I did not sit down and just make the whole thing at once.
57:39 I took baby steps, so to speak.
57:41 I first, frankly, did the easy part and I just found an image of Sesame Street,
57:44 put it on the stage, and boom.
57:45 At least version one, all it did was say Sesame Street.
57:48 And it's not interactive at all.
57:49 Then I added a sprite, which instead of being a cat,
57:52 I changed the costume to be the trash icon.
57:54 And I just figured out the code, the puzzle pieces,
57:57 to make that puzzle piece fall from the sky and then stop when it's on the edge,
58:02 just like the cat was able to make
58:03 a decision to bounce when it touched the edge.
58:05 And now things get a little crazy.
58:07 The song gets more sophisticated.
58:08 I added more and more sprites that just fall in lockstep with the music.
58:13 So this was quite a few hours of effort,
58:15 but it boils down to really the same principle,
58:18 just as this other program here does, too.
58:21 And for this, rather than me play it,
58:23 let me invite one other volunteer to come on up who's got to be— OK,
58:28 I see your hand here.
58:28 What's your name?
58:29 MEGAN: Megan.
58:30 DAVID MALAN: Megan.
58:30 All right, Megan, we have a game for you called— maybe I mentioned this—[?
58:35 IB's?] hardest game.
58:36 OK, come on up.
58:38 Nice to meet you.
58:39 This is a game by one of your former predecessors,
58:42 who their problems said zero, implemented this.
58:45 You'll see the instructions in just a moment on the screen.
58:49 We'll see if we can't inspire some folks to root for you here.
58:54 And after this, as is the tradition in CS50, we will adjourn for some cake.
59:00 So Megan, we have here for you,[?
59:02 IB's?] hardest game.
59:03 I'm going to go ahead and maximize the window.
59:05 I'm going to go ahead and click Begin and we'll see the instructions.
59:07 MEGAN: OK.
59:07 DAVID MALAN: Good luck.
59:08 MEGAN: Thanks.
59:10 [MUSIC -MC HAMMER, "U CAN'T TOUCH THIS"] DAVID MALAN:
59:13 Let's go ahead and raise the volume.
59:15 Here we go.
59:16 [MUSIC -MC HAMMER, "U CAN'T TOUCH THIS"] (SINGING) Can't touch this.
59:20 DAVID MALAN: So you're going to move the arrow keys and navigate your way,
59:24 essentially— oh, yep— through a maze.
59:26 Notice Megan's not able to go beyond
59:28 the black borders because if touching edge, logic.
59:33 Now when you touch the other sprite, you advance to the next level.
59:39 Two sprites now.
59:42 Another Yale icon.
59:44 (SINGING) From the Oaktown and I'm known as such.
59:46 And this is a beat you can't touch.
59:49 I told you, homeboy.
59:50 DAVID MALAN: Nice.
59:51 OK.
59:51 [LAUGHTER] (SINGING) Yeah, that's how we living and you know.
59:54 Can't touch this.
59:56 Look in my eyes, man.
59:58 DAVID MALAN: Nice.
1:00:00 (SINGING) Yo, let me but the funky lyrics.
1:00:02 Can't touch this.
1:00:03 [LAUGHTER] DAVID MALAN: Nice.
1:00:09 [AUDIENCE GASPING] [APPLAUSE] (SINGING) Cold on a mission, so pull them on back.
1:00:17 Let them know that you're too much and this is a beat, uh, they can't touch.
1:00:22 Yo, I told you.
1:00:23 [LAUGHTER] Why you standing there, man?
1:00:27 Can't touch this.
1:00:28 Yo, sounds the bells.
1:00:29 School is in, sucker.
1:00:31 Can't touch this.
1:00:32 DAVID MALAN: OK.
1:00:34 Good.
1:00:35 Nice.
1:00:39 [AUDIENCE GASPING] [LAUGHTER] (SINGING) Or a tape
1:00:43 to learn what's it going to take?
1:00:45 And now he's going to burn the charts.
1:00:47 DAVID MALAN: Oh!
1:00:48 (SINGING) And you might as well quit.
1:00:50 That's word because you know— DAVID MALAN: No!
1:00:53 That's OK.
1:00:59 Oh.
1:00:59 It's OK.
1:01:03 Nice.
1:01:09 Ah!
1:01:15 [INAUDIBLE] Oh!
1:01:20 Couple more lives.
1:01:22 Nice.
1:01:22 Oh!
1:01:23 [AUDIENCE GASPING] OK.
1:01:29 Yeah, you got it.
1:01:30 MEGAN: Yes.
1:01:31 Yep.
1:01:32 Oh my God.
1:01:33 DAVID MALAN: All right.
1:01:34 One more life— two more lives!
1:01:37 Three more lives!
1:01:40 Come on.
1:01:41 (SINGING) Bring the bill.
1:01:42 School's back in.
1:01:43 Break it down.
1:01:45 DAVID MALAN: Yes!
1:01:46 [APPLAUSE] MEGAN: Up, up, up.
1:01:56 (SINGING) Stop.
1:01:57 Hammer time.
1:01:58 DAVID MALAN: All right.
1:01:59 Last life.
1:02:00 Last life.
1:02:00 Go, go!
1:02:02 Here we go.
1:02:05 All right.
1:02:06 Nice, nice.
1:02:07 Yes, yes.
1:02:08 Ah!
1:02:10 All right.
1:02:11 A round of applause for Megan, if we could.
1:02:13 Check her out.
1:02:14 Here you go.
1:02:15 [APPLAUSE] This, then, is CS50.
1:02:20 Welcome aboard.
1:02:21 Cake is now served.