CS50x 2024 - Lecture 0 - Scratch

0:00 [MUSIC PLAYING]

1:30 [AUDIENCE EXCLAIMING] [APPLAUSE] SPOT: Hello, world. This is CS50, Harvard University's introduction to the intellectual enterprises of computer science and the art of programming. Woof, woof. [LAUGHTER] I'm sorry, Dave. [PINK, "WHAT ABOUT US"] What about us? What about us?

2:16 La-da-da-da-da-da-da. We are searchlights. We can see in the dark. We are rockets pointed up at the stars. We are billions of beautiful hearts. And you sold us down the river too far. What about us? What about all the times you said you had the answers? What about us? What about all the broken happy ever-afters?

3:05 What about us? What about all the plans that ended in disaster? What about love? What about trust? What about us? La-da-da-da-da-da-da.

3:55 DAVID J. MALAN: All right. So-- [APPLAUSE, CHEERING] This is CS50, Harvard University's introduction to the intellectual enterprises of computer science and the art of programming. And this is Spot. And our thanks to our friends at 3D Cowboys for bringing him by class today. Perhaps a round of applause for our special Professor [INAUDIBLE].. [APPLAUSE] My name is David Malan. And I actually took this class, CS50, myself, some years ago. But I almost didn't. And I didn't because when I got to campus, as a first-year, I really gravitated toward things already familiar, things with which I was already comfortable, specifically, government. And I came in here thinking I was going to major or concentrate in government. And it was only once I got to sophomore year, fall semester,

4:41 that some friends of mine were coming to this class called CS50 that was very much to beware at the time, in that it was an unfamiliar field to so many of us, myself included. But I got up the nerve to go over the threshold, sit in on the first class, just shop it, so to speak. And I was hooked. I found that homework was, for the first time, fun. And this was after having enrolled only because the professor let me enroll pass/fail or [INAUDIBLE] because I didn't really think I could even cut it. But fast forward to five Mondays later in the semester, I actually switched to a letter grade, deciding, wow, this is actually something for me. And I say this because computer science, what I didn't realize about it at the time, really is this very general purpose way of thinking and way of solving problems. And even if this is the only CS class you ever take, even if this is the only formal training you have in programming

5:29 as a practical skill, it's just so darn applicable to so many other fields-- the arts, humanities, social sciences, natural sciences, and beyond, and certainly within the STEM fields, themselves. That said, it's going to often feel a little something like this. This is from our friends at MIT, down the road, which is one of their hacks whereby they connected a fire hydrant to a drinking fountain, with a little sign up there that says, "GETTING AN EDUCATION FROM MIT IS LIKE DRINKING FROM A FIRE HOSE," which is to say that it's going to feel, quite often, in this class, too, that there's just a lot of information. And you can't possibly absorb it all, but realize that's to be expected, especially in an introductory class. The whole point is for so much of it to feel new, but with practice, with time, with years, even, looking back, will you get all the more comfortable with the material.

6:15 But you're not meant to feel comfortable along the way. And so let me encourage you, invite you, expect you to get comfortable feeling uncomfortable along the way, whether you have or have not prior computer science or programming experience. Now, back in my day, the class' syllabus was a little bit different. And, really, when I and all of my classmates exited the class, we would say to friends that we learned how to program in C, which is a language that we, ourselves, will still learn in this class. But that was it for languages. But nowadays, as you'll see, we'll explore not just this older language called C, but a more modern language called Python that's very much in vogue for data science, and web applications, and much more. But we'll also introduce you, along the way, to another language called S-Q-L or SQL, which is specifically for databases.

7:01 And SQL is a different type of programming language that's just going to give you different ways of solving problems, different building blocks with which to express problems you want to solve. We'll introduce you, toward the end of the semester, yet another language, JavaScript, often used with markup languages called HTML and CSS, with which maybe you have some experience if you've made websites. But we'll do this because so many of today's actual real-world software is web-based. Or it's phone-based, mobile-based, but even then, it's using these same languages, like JavaScript. And so by the end of CS50, in particular, you won't know how to program in X, or Y, or Z, per se. But, period, you'll learn how to program. And, indeed, among the goals of this class is to equip you with enough of a set of concepts, enough practical skills and experience that after CS50, again, if you never take another CS class,

7:49 you can teach yourself new languages. And you won't feel-- you won't have been reliant on a class to, indeed, introduce you to each and one of those ideas. And what are we going to do, then, in this class? And, really, what are we going to start doing today? Well, we're going to learn how to solve problems. And that's really what computer science is all about. We'll, very specifically, today, knock off a few to-dos. We'll learn how to represent simple things, like numbers. We'll learn how to represent letters of an alphabet, like English. We'll learn how to represent colors-- red, green, blue, and everything in between. We'll learn how to represent, more interestingly, full-fledged images that you might see on the web or your phone. We'll talk about representing videos and even audio files. So, by the end of today, alone, you will exit here with a newfound mental model for how you can represent all of today's media and multimedia that we take for granted

8:36 and use most every day. But we'll also focus today, ultimately, on how to write algorithms, like step-by-step instructions for solving some problem, specifically, implementing algorithms with code. And that's what we'll find. An algorithm is just something you can express in English or any human language, but code is a translation of that to, presumably, the 0's and 1's that you've probably heard is all that computers ultimately speak. And if you're feeling like that's a lot for today, if you're feeling like that's a lot for the whole semester, realize and take comfort in knowing that -thirds of you have never taken a CS course before. So even if you think, like I did all those years ago, that, surely, my friends, the kids I didn't even in the class, must know more than I, have been programming since they were six years old. That's just not the case. You're in very much good company.

9:21 And within the class will you find different tracks, by way of the homework assignments, called "problem sets," by way of the sections or recitations. There will be different tracks for those of you less comfortable, more comfortable, somewhere in between. And if you really don't know why you are here today, we'll even have sections for those least comfortable, where you just don't necessarily feel ready to dive into CS or maybe STEM, more generally. But we'll get you there by way of the course's support structure. And it's very much grounded in this mindset. What ultimately matters in this class is not so much where you end up relative to your classmates, but where you end up relative to yourself, when you began. So whether you have or have not prior programming or CSS experience, it's not going to matter when it comes to evaluation, when it comes to the output, be it a grade, or a satisfactory mark, or the like. It's going to depend on, really, where you are today,

10:06 in this, what we call week zero, versus the very end of the semester, when you will have built something grand, of your very own, in software. But CS50 is also characterized, fairly uniquely, by its community, its culture. And along the way, you'll see that your experience is punctuated by a lot of social and academic events alike. CS50 lunches, most every Friday, we'll gather at a nearby restaurant called Changsho where we'll have Chinese lunch together. And as many of you as might want to attend that week will be able to join us, sit down, and chat casually with me, the course's teaching staff, friends of ours, alumni from industry, as well. CS50 Puzzle Day, coming up this weekend, will be an opportunity, even if you have no prior CS experience, just to solve problems, not jigsaw puzzles, but puzzles in the logical sense. We'll hand you a packet of puzzles--

10:52 logic problems, or riddles, or the like-- that you, as teams, can solve together. And at the very end, we'll walk you through. And along the way, there'll be not only these puzzles, but pizza, and prizes, and so much more, as well. Towards the end of the semester, we'll have a CS50 Hackathon whereby we'll get together around 7:00 PM, at the start of reading period, and we'll finish up around 7:00 AM the next morning. And it will be this opportunity to really bond with your classmates, your project partners, if you work in a team, on your very own final project, which is meant to be a capstone of the course, something you build, yourselves, that we don't hand you a specification for. But it's your final offboarding, so that when you exit CS50, you don't need CS50 anymore. You don't need me. You don't need your TF. You can actually write code and solve problems on your own. So this picture here is one of our past photos from earlier in the evening.

11:39 Things get a little quieter as we then, around 5:00 AM, drive anyone who's still awake and energetic to a nearby IHOP for pancakes, around then. But here is how most of the evenings tend to end for at least some of your classmates prior. But at the very end of the class is the so-called CS50 Fair, an exhibition of all of your final projects for friends, faculty, students, and staff across campus, whereby you'll be invited to a space like this. Bring your laptop. Bring your phone, whatever it is you have built and created. And we'll just show it off for a bit of the afternoon, complete with music, and friends from industry, and candy, and all what makes gathering together at term's end fond. And you'll wear, ultimately, very proudly, we hope, your very own "I took CS50," stating, very matter of factly, what I did some years ago; that, indeed, this was a course I, myself, took.

12:25 So, today, let's focus, then, on computer science, like what is it. Well, it's really the study of information. But, really, it's, more specifically, about solving problems, using certain ideas and techniques, all of which you'll exit the course with. So, as such, problem solving is a goal that we'll approach by way of something called "computational thinking." So computational thinking, you can oversimplistically think about it as thinking like a computer. But it's really the application of ideas that we'll dive into today and we'll finish some weeks from now, that you can apply to problems from this field or most any other, but in a computational, that is, a very methodical, very careful way. And that's what CS really did for me and does for a lot of people. It helps clean up your thought processes. Even if you go off into the real world and do nothing in tech,

13:12 you have an ability, after classes like this, to express yourself a little more correctly, more precisely and, generally, having better command of your own ideas and your language. So what's problem solving? Let me propose that this is it. This is as simple as we can make today's goals and the semester's goals. Problems to be solved look like this. You've got some input, the problem to be solved. You've got a goal being the output, like the solution there, too. And then somewhere in the middle is the secret sauce, where we'll spend the next several weeks figuring out how we can convert these inputs to outputs. But before we can do that, we all just have to agree on how to represent these inputs and outputs, whether it's with English or, really, any type of language. But, as I spoiled earlier, you probably came in here already with a general sense that, yeah, computers somehow only speak or know 0's and 1's, the so-called binary system.

14:00 But that's just one way of representing information. Even simpler than binary is unary. So if you've ever, at this age or any prior age, counted on your fingers, this is unary notation, whereby each of your digits, your fingers literally represent some piece of information; taking attendance, like 1, 2, 3, 4, 5. But on your one human hand, how high can you count in this unary notation? AUDIENCE: Five. DAVID J. MALAN: Five, I'm hearing five. Six, I heard one six. But I'm going to go further and say the answer, if you're clever about it, is actually-- AUDIENCE: 40? DAVID J. MALAN: Not quite 40. You overbid, but-- AUDIENCE: 31. DAVID J. MALAN: 31 is as high as I can actually count. And that's because if I actually-- and if you're thinking

14:46 this is weirdly painful now, it will be, but this is my hand representing the number 0. Normally, in unary, this is 1, 2, 3, 4, 5, of course, obviously. But what if I take into account the order in which I'm putting my fingers up and down? So maybe this is still 0. Maybe this is still 1. But maybe this is now 2, where it's just the single second finger up, not two of them, total. Maybe this is now 3. Maybe this is now-- often offensive, with just the middle finger up. This is now [LAUGHS] 5. This is now 6. This is now 7. And my hand just hurts too much if I try to count higher than seven. But, theoretically, because each of my fingers can be down or up and I've got five of them, that's actually 32 possible permutations,

15:32 up and down. But wait a minute. We said, 31, but if you start at 0. You have to subtract 1 from the biggest possible value. So this is to say you and I have been using unary because it's just simple, and it gets the job done. But if we just think about representation a little more cleverly, we can do exactly what computers do, using not what mathematicians call "base-1," where the finger is either there or it's not, but base-2. And in base-2, we just need two digits at our disposal. And we could call these digits 1 and 2, A and B, black or white. We just need two words to describe two pieces of information. Computers keep it simple. And just like we humans start counting 0, 1, 2, 3 on up, computers use 0 and 1, and that's it. But that's by convention. But why do they do that? Well, it turns out, when you use base-2, otherwise known as binary, well,

16:21 it just maps really readily to the real world. Because, at the end of the day, what do we all do, if you've got a laptop, or a phone, or any device? You plug it into the wall because it needs electricity at some point. And what if you have electricity or not? Well, there's your two possible values. Either it's there, or it's not. And because computers are electrical devices, this is why binary is just useful. It's nice and simple. Either electricity is there, or it's not. So when you plug this device in and you've got all these electrons or whatever flowing, maybe if we just hang on to some of that electricity, we can represent what we'll call a 1. And maybe if we let it dissipate or go away, that's a 0. So on and off maps very readily to this idea of just 0's and 1's. And if you've ever thought of this, now, as binary digits-- "bi" implying 2, 0 and 1-- well, if you've ever heard this term now,

17:10 "bit," it just means binary digit. A single bit is just a 0 or 1. But we could have called these things anything we want. Now how does this map to be clear to the real world? Well, we can't see the tiny little switches inside of our Macs, PCs, and our phones that are actually turning the electricity on or off, storing electricity or not. But they're called transistors. They've got millions of them in today's hardware. And they're just on or off, like a switch or a light bulb. So, for instance, if there's no electricity, the switch is off, we would call this, by convention, a 0. If, though, you throw the switch and it actually turns on, we would call this-- AUDIENCE: On. DAVID J. MALAN: --an "on," exactly, a 1. We could have reversed it. But this is just the way the world decided to standardize. And that's it. So you've either got something on or off, a 1 or a 0.

17:55 And this, then, is this thing we know now as a binary digit or a bit. So once we've got these values, what about how-- how can we go about, perhaps, representing things? Well, you know what? It turns out we've got a lot of light bulbs right here. Let me grab-- thanks. Excuse me, spot. Let me grab the little music stand here. Let me borrow a couple of these bulbs and see if we can't make clearer than my hand, alone, what's going on here. So I'm going to go ahead and grab two of these. And I'll just put them here. And I can turn these things on or off now. So if I've got two bits, two switches, two transistors, if you will, well, if I go ahead and turn on this one, I'm representing what number in binary, perhaps? AUDIENCE: 1. DAVID J. MALAN: So just 1.

18:41 Now, if I'm using unary, I would turn this one on and be done with it. And that's 2, but not in binary. Binary, it's the permutations, which ones are on and off, that matters. So what, now, am I representing here, perhaps? AUDIENCE: 2. DAVID J. MALAN: 2. So this is when I put my single pointer finger up. But then when I did this, in my human hand, this was like representing the number 3. How do I represent the number 4. Yeah, I need another light bulb, so I need more hardware, so to speak. So if I turn-- if I leave this one-- if I turn this one on, this one off, this one off, now I have the number 4. And someone tell me, saying the words "on" and "on" and "on," or "on," or "off," or "on,"

19:26 using combinations of "on," "off" and-- "on" and "off," how do I represent 5, from your left to your right? How about over here? AUDIENCE: On, off, on. DAVID J. MALAN: "On, off, on," I heard. And that's exactly right. And how do I represent, maybe, 6? Over here? AUDIENCE: Off, on, on. DAVID J. MALAN: Off, on, on, not quite. From left to right? AUDIENCE: Off-- the other way. DAVID J. MALAN: The-- [LAUGHS] OK, so from right to left. So I think we leave this one on. This one, I'm going to claim, represents, now, 6 and 7. AUDIENCE: On, off. DAVID J. MALAN: I'm just going to-- it's actually going to be "on, on, on." Now, if you're wondering, where are these people coming up with these combinations, there's actually a system here. It's actually hard for me to do it backwards. But it turns out there's actually a system that's not all that unfamiliar.

20:14 In fact, let me propose this. Let me propose that we consider what you and I all learned in grade school, which was something like the base-10 system, 10 meaning that you use 10 different digits, not two, 10. So 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, that's the base-10 system, otherwise known as decimal, "dec" implying 10. So that's what you and I use every day. Well, let's think about how we represent numbers in decimal, in the normal human way. Well, here is a number. It's what number, of course? AUDIENCE: 123. DAVID J. MALAN: 123. So we all just have an intuition for that, obviously. But it's not necessarily 123. You're just assigning meaning to the positions of these digits. This is really the pattern 1-2-3. But you immediately jump, mathematically, to 123, but why? Well, odds are, in grade school, you learned that the rightmost digit is

21:00 the ones place or the ones column. This is the tens place or the tens column. This is the hundreds place. And so why is this relevant? Well, this is like doing 100 times 1 plus 10 times 2 plus 1 times 3 or, if we multiply that out, 100 plus 20 plus 3, ergo, the number, now, that we just take for granted is 123. But that's in base-10, the so-called decimal system, whereby each of these digits is in a different column. And those columns are, again, ones place, tens, hundreds. If we keep going, thousand, ten thousand, and so forth. But where did these come from? Well, here's the base. If you remember exponents and all of that, this is just 10 to the 0, 10 to the 1, 10 to the 2, ad infinitum. And so, now, what if we just changed the base from 10, 0 through 9,

21:46 to just two digits, 0 and 1? Well, now the math is fundamentally the same. But it's 2 to the 0, 2 to the 1, 2 to the 2, which gives us the ones place, twos place, and fours place. Now, why is this relevant? If you've got three light bulbs or three bits that are off, off, off, what have I done? 4 times 0 plus 2 times 0 plus 1 times 0 is, obviously, the number you and I know, in decimal, as 0. This, though, represents the number you and I know as-- AUDIENCE: 1 DAVID J. MALAN: This represents-- AUDIENCE: 2. DAVID J. MALAN: --3, 4. And just to be clear, this is why, when I grabbed the additional light bulb, we claimed that this now was 4. Because we had "on, off, off," "on, off, off." This now is 5. This now is 6.

22:32 This now is 7. And if I wanted to count higher, what would the pattern of 0's and 1's be for the number 8? AUDIENCE: 1, 0-- DAVID J. MALAN: 1, 0, 0, 0. So we just need more hardware, more bits. So it wasn't arbitrary, even if it was non-obvious, what I was actually doing with turning these light bulbs on and off. Now, it turns out here we are talking about how to represent information, like numbers, but we could also use bits, 0's and 1's, light bulbs to represent instructions, as well. Because, at the end of the day, that's all computers do. They process data, information of some sort, whether it's files, or numbers, or images, or videos, or the like. And you do things with those files. You open them. You print them. You edit them and the like. So there's this notion of instructions, what the computer can actually do.

23:18 And I bet we could come up with some pattern of 0's and 1's or, equivalently, light bulbs that tell even Spot what to do. Maybe, go up, or down, or left, or right. And it could certainly do this autonomously by using various sensors. We need to keep things safe today. We're using Wi-Fi in sending Spot these very instructions. But what's happening, wirelessly, with our friend Andrew, here, is, essentially, he's sending Spot instructions just encoded, wirelessly, somehow, as patterns of 0's and 1's. And the folks at Boston Dynamics, who built this robot, programmed Spot to recognize certain patterns as meaning "up," a certain pattern as meaning "down," "left," "right," and any number of other things. So, in fact, Spot, come on over here, if you could. Come on, Spot. [FOOTSTEPS] OK.

24:05 So Spot, for instance, may very well have a pattern of 0's and 1's that represents shake. Shake, Spot. So he could do that and any number of other movements, as well. And maybe, especially with sensors here and also a little human help over here, for today, what if we went ahead and did something-- maybe ask Spot some questions? So let's go ahead, and we'll start simple. Spot, here we have some bits, "off, off, on." Spot, what [LAUGHS]-- OK. Spot, what is this representing, "off, off, on"? [SPOT TAPS STAGE] Correct? I think so. Very horse-like, OK. Thank you. All right, so a round of applause for Spot here. [APPLAUSE] All right.

24:51 So, Spot, what if we [LAUGHS] turn-- OK. We'll turn that one off here. How about if we turn this one on? So it's "off, on, off." Spot, what's this number? [SPOT TAPPING STAGE] Is that correct? Nice. OK. [APPLAUSE] [LAUGHS] How about one final flourish? How about, Spot, instead of "off, on, off," let's go ahead and do "off, on, on"? So think, in your mind's eye, what the answer should be. All right, Spot, "off, on, on." [SPOT LANDING ON THE STAGE] OK. And a round of applause for, Spot, as well. [LAUGHS] [APPLAUSE] So this is to say, no matter how--

25:36 thank you, Spot. No matter how fancy today's hardware or software is, it really just boils down to representing information and instructions. And computers, and phones, and the like really are just operating on those same pieces of information, whether implemented in 0's and 1's or with, really, anything else. All right. So, where can we take this, once we have this agreed-upon system for representing [LAUGHS] information? Well, it turns out that using three bits, three 0's and 1's, at a time, isn't actually all that useful. And you and I, even in conversation, don't often say the word "bit." We say the word "byte." And what is a byte, if familiar? Yeah? AUDIENCE: It's eight bits. DAVID J. MALAN: So it's just eight bits. It's just a more useful unit of measure. And it happens to be a power of 2, 2 to the third,

26:22 which just makes math work out cleanly. But it's just a convention, to have more interesting units of measure than individual bits. So a byte is eight bits. So, for instance, this represents, using eight bits, eight light bulbs, the number you and I know is 0. And this byte of all 1 bits-- now you've got to do some quick math-- represents what number, instead? So it's all 1's; eight of them, total. How about over here, on the end? AUDIENCE: 255. DAVID J. MALAN: So it's, indeed, 255. Now, that's not the kind of math that you need to do in your head for a class like this, but you could. This is the ones place, twos, fours, eight, 16, 32, 64, 128. And because they're all 1, you just have to add up all of those columns' values.

27:08 And you get 255. But a little mental trick, too, is that, if you've got eight bits and each of them can be two possible values, 0 or 1, that's like 2 possibilities here times 2 times 2 times 2 times 2, eight times. So that's 2 to the eighth, so that is maybe a little easier to do. That's 256. Or easier, in the sense that you get used to seeing these numbers in CS. That's 256. But wait a minute. How do I reconcile this with your 255? Because you start at 0. So you lose one on the high end because we started counting and representing the number, like 0. All right. Questions on how we've represented just numbers or, for instance, instructions to Spot, thus far? Any questions on binary, unary, or the like?

27:57 No? All right, so seeing none, let's let things escalate a bit. So how do you represent letters because, obviously, this makes our devices more useful, whether it's in English or any other human language. How could we go about representing the letter A, for instance? If, at the end of the day, all our computers, all our phones have access to is electricity; or, equivalently, switches; or, metaphorically, tiny little light bulbs inside of them that can be on and off-- that's it. There's no more building blocks to give you. How could we represent something like the letter A? Yeah, how about here? Yeah? AUDIENCE: You could assign a number. DAVID J. MALAN: Perfect. So we could just assign every letter a number. And we could do this super simply. Maybe 0 is A, and 1 is B. Or maybe 1 is A,

28:42 and 2 is B. It doesn't really matter, so long as we all agree and we all use the same types of computers, in some sense, ultimately. Well, for various reasons, the humans that designed this system, they went with the number 65. So, nowadays, anytime your computer is showing you the capital letter A on the screen, underneath the hood, so to speak, it's actually storing a pattern of 0's and 1's that represents the number 65. And it tends to use seven bits or, typically, eight bits, total, even if it doesn't need all of those bits in total. So how do we get there? Well, here, for instance, is that same pattern. Here is that pattern of bits that represents 65. And why? Well, quick check here. This is the ones place, twos, fours, eights, 16, 32, 64's place.

29:29 OK, so 64 plus 1 gives me 65. So that is to say here's how a computer, using some light switches, so to speak, would represent the number 65. And our Macs, our PCs, our phones just all know this. So whenever they see that in their memory, so to speak, they show a capital letter A on the screen. So that's it. That's the system known as ASCII, the American Standard Code for Information Interchange. And the A is actually operative there because we're only talking, thus far, about English letters in our alphabet. And, in fact, I claimed, a moment ago, that we only use seven, maybe eight bits to represent letters of an alphabet. So, just to come back to you, if I may, how many possible letters of the alphabet could-- how many possible letters of any alphabet could we represent with eight bits?

30:14 AUDIENCE: 256. DAVID J. MALAN: 256, the numbers 0 through 255. Now, that's more than enough for English because we've got A through Z, uppercase, lowercase, a bunch of numbers, a bunch of punctuation symbols. But in a lot of languages, with accented characters, a lot of Asian characters, this is not nearly enough memory or bits with which to represent all of those possible values. So we need to do a little better than ASCII, but we can build on top of what they did years ago. So here is a chart of ASCII codes. It's just a bunch of columns showing us the mapping between letters and numbers. So, for instance, up here is the capital letter A, 65; capital B, 66; capital C, 67; dot, dot, dot. 72 is H. 73 is I and so forth. There's some weird things over here, like special symbols, that we'll learn about over time.

31:00 But there's a mapping between every English letter of the alphabet and some number, just as you'd propose, both for uppercase and lowercase. So, for instance, if we highlight just a few of these for now and I say that I've just received a text message or an email that, underneath the hood, so to speak, if I have the ability to look at what switches are on and off, I received this message here. Well, first-- and this is not what CS is about, but just fun fact. Does anyone know what number this would represent in decimal, if this is the binary pattern, like ones place, twos place? AUDIENCE: 72? DAVID J. MALAN: 72 is correct. And again, not, intellectually, all that interesting and this is not the kind of math that we spend all day as CS-- a computer scientist doing. But it's just following the same darn pattern, which

31:45 is to say it might look cryptic, but, conceptually, intellectually, it ultimately is exactly as we did before. So, yes, I'll spoil the rest of the math. It's 72, 73, 33. Now, anyone remember, in your mind's eye, what message we just spelled? AUDIENCE: Hi. DAVID J. MALAN: Yeah, so it is, in fact, "Hi!" Though, no one really said that excitedly. What's the 33, if you noticed? AUDIENCE: Exclamation point. DAVID J. MALAN: OK, so a lot of people noticed. Yes, it's an exclamation point. And that's, indeed, noticeable right here. 33 is the exclamation point. And that's just something, eventually, that might sink in. But, for the most part, if you remember capital A is 65, you can figure out at least 25 other answers to these kinds of questions because they're all contiguous like that. So there's the exclamation point. But at the end of the day, we might just have this mapping known as ASCII. And it's how our phones, and computers, and devices, more

32:33 generally, actually store information. So we thought we'd make-- maybe take a little pressure off of me here. And could we maybe flip things around? How about we try applying this newfound knowledge-- if it's, indeed, new to you-- with seven volunteers, seven bits, if we could? OK. I saw your hand first. Come on down. Maybe your hand, there. OK, three, come on down over here. How about four and five? Yep, come on down. Yep, in the black shirt, yep. How about let me go farther back? How about in the green, over there? And how about you, seven, over here? All right. Come on down. [CHATTER] Come on down. So a round of applause for our brave volunteers. [APPLAUSE] All right. So if you'd like to stand, roughly, side by side, here in the middle of the stage.

33:20 First of all, thank you. Let's see. 1, 2, 3, 4, 5, 6, 7, perfect. OK. And let's go all the way over to this place, here. If you would like to introduce yourself to the class. RACHEL RICHEY: I'm Rachel Richey. DAVID J. MALAN: OK. And what year? Anything about you? RACHEL RICHEY: Oh, first year, concentrating in CS. DAVID J. MALAN: OK. Welcome to the stage. Next. SPEAKER: Hi. I'm [? Kang. ?] Also a first-year concentrating in CS. SPEAKER: Hello. My name is [? Lam. ?] I'm a [INAUDIBLE] student from education department. DAVID J. MALAN: Nice. OK. Next. JORDAN MITTLER: Hi. I'm Jordan Mittler, concentrating in economics and maybe some CS. SPEAKER: So, hi. I'm [? Natalia. ?] First year, and I want to do CS. SPEAKER: Hi. I'm [? Khadija. ?] I'm a first-year, and I want to do CS.

34:05 DAVID J. MALAN: [LAUGHS]. SPEAKER: Hello. I'm [? Caleb. ?] And, once again, first year, concentrating in CS. DAVID J. MALAN: OK. Wonderful. A pattern, yes. Thank you. [APPLAUSE] So, if you haven't guessed already, each of these volunteers is going to represent a bit, from left to right, or right to left, in this case. So let's see. If you want to represent-- how about the twos place? How about the fours place, the eighths place, 16ths place, 32's, 64, and 128? Although, wait a-- I think I screwed up. We needed one-- eighth volunteer. I think you know-- well, I think-- [CLEARS THROAT] Spot? OK. Come on over. If you guys could step forward a little bit, and then scooch this way, just to give Spot some room.

34:51 [FOOTSTEPS] So Spot will represent the ones place. Now, what our volunteers have on the back of their sheets of paper are little instructions. We're going to spell out a three-letter word in English by using three bytes, from left to right, because now we have eight volunteers. I'm going to propose that you raise your hand, if you're supposed to represent a 1. Or you just stand there, without raising your hand, if you're meant to represent a 0. And what we'll have the audience do is do the quick math to figure out-- one, two, three-- each letter, what number is it. What letter is it? And we'll see what word that we have finally spelled. All right. So, in round one-- you have instructions on your back of your sheet that will tell you to-- what your number is. If you're 0, stand there. If you're a 1, raise your hand.

35:37 [PAPER RUSTLING] What number do these guys seem to be representing? AUDIENCE: 68. DAVID J. MALAN: 66, I think. 64 plus 2, so 66, which is the letter-- AUDIENCE: B. DAVID J. MALAN: OK, so, B. OK, so, B. All right. Hands down. Second letter is going to be spelled how? [SPOT LANDS ON THE STAGE] AUDIENCE: Whoa. DAVID J. MALAN: [LAUGHS] All right. What are we spelling now? [INDISTINCT CHATTER] I think-- psst, yep, OK. Yeah, I think you're one. [LAUGHTER] OK. Now what number are we spelling?

36:23 AUDIENCE: 79 DAVID J. MALAN: 79, I heard, which is the letter? AUDIENCE: O. DAVID J. MALAN: O. OK. So hands down. Thank you, Spot. One final flourish. So we've spelled B-O-- third letter, go ahead. [SPOT LANDS ON THE STAGE] What number, now, is this? AUDIENCE: 87. DAVID J. MALAN: I heard it here, 80-- AUDIENCE: Seven. DAVID J. MALAN: --seven, which is? AUDIENCE: W. DAVID J. MALAN: W, which, of course, spells "bow." So if our volunteers could take a bow, Spot included. [APPLAUSE] So this will make more sense in week one, when we have an assignment involving a certain someone from the Nintendo World. But we have a lovely parting gift for each of you. SPEAKER: Thank you. [LAUGHS] DAVID J. MALAN: Thank you for volunteering. SPEAKER: Thanks.

37:08 DAVID J. MALAN: You might need to share it with the folks next to you. [CHATTER] Oop, here we go. There we go. Thank you-- SPEAKER: Thank you. RACHEL RICHEY: Thank you. DAVID J. MALAN: --so much. One more round of applause, if we could, for our volunteers. Thank you. [APPLAUSE] Did you lose something? OK. All right. So, [LAUGHS] Spot's had it. So let's see, then, if we've solved, now, the problem of representing English letters of the alphabet, being able to spell out words like "bow," B-O-W. What if we actually do have accented characters? What if we do have other glyphs that we want to represent? Well, here, of course, is a standard US English keyboard, which a lot of you might have. But there's also characters that you can type much more easily if you have a foreign keyboard, relative to the US, or with certain keystrokes on your own Mac, PC, and phone.

37:55 But, nowadays, too, there's this menu that, probably, you've used in the past hour or two to actually send some emoji. An emoji, even though they look like pictures and they actually are pictures on the screen, they're, technically, just characters, characters of an emoji alphabet that happened to use a certain pattern of 0's and 1's to represent each of these faces, each of these people, and places, and things. And it turns out that one of the reasons that we have just so many [LAUGHS] such characters nowadays is because we now use Unicode instead of ASCII. So Unicode is a superset, so to speak, of ASCII, which is to say that we, humans, realized, some time ago, that just using eight bits to represent letters of the alphabet certainly isn't very good when we want to represent

38:43 other, non-English languages. So Unicode doesn't just use eight bits. It sometimes uses 16 bits per character, sometimes 24 bits per character, and sometimes even 32 bits per character. Now, why those numbers? That's just one byte, two bytes, three bytes, or four bytes. And that gives us-- does anyone know? That gives us the ability to represent as many as 4 billion possible characters. Because if the longest one is 32 bits, that's 2 to the 32, which, if you do out the math, trust me, is roughly 4 billion. So that's a lot of characters. And we've got a lot of room, then, for these emoji. But it's not just about having fun, pictorially, on the screen. Unicode's mission really is to represent and to preserve all human languages digitally, both past, present, and future.

39:31 So it is really about capturing the entirety of human knowledge, as we've expressed it in language, but also giving this newfound ability that's been used centuries ago, too-- in writings, on walls, and the like-- pictograms via which we can still communicate, even independently of our own human language. So we'll reduce it, today, to just patterns of 0's and 1's, but the problem being solved is much greater and well-beyond CS, itself, there. So here is a pattern of 0's and 1's using Unicode, so more than eight bits, that represents a very popular emoji, which might be a bit of a hint. This is the most popular emoji, as of last year, at least, statistically, internationally. [INTERPOSING VOICES] DAVID J. MALAN: Does this help? It's, roughly, this number here. No?

40:17 It's this one here. So this is the most popular emoji, by most measures, as of last year. But it doesn't always look like this. Those of you who have a Mac or an iPhone recognize this symbol, perhaps, immediately. Those of you with Android devices or other platforms might notice that it's the same idea, but it's a little bit different. And this is because, too, emojis, at the end of the day, just represent character, but those characters can be drawn, can be painted in different ways. And reasonable people will interpret differently this emoji, whose official name is "face with tears of joy." And, indeed, Google interprets it a little differently from Apple, versus Microsoft, versus Meta, versus other companies, as well. So you can almost think of those different companies as having different fonts for emoji. And that really starts to connect things to the world of text and characters.

41:04 So, just so you've seen it. More on this, another time. It turns out that emoji and, really, characters, in general, we don't use binary 0's and 1's to represent them because no one, myself included, is going to recognize what's what. It's just too much math. It's not interesting. And even decimal numbers-- that was 4 billion or some-- I don't remember which number is which. So we represent things a little more compactly. And this, too, admittedly, still looks cryptic, but this is a Unicode code point that uses another system, mathematically, called base-16 or hexadecimal. More on that, another time. But it's just a way of representing numbers even more succinctly, writing less on the screen, because you're using not just 0 through 9, as in decimal. But you're using A through F, as well, so a few letters of the English alphabet come into play. But, for now, that's just a little easier

41:49 to remember, too, for people who care, that that is the number that represents "face with tears of joy." But what if we want a customized emoji? And this, increasingly, is the case. Here, for instance, are the five skin tones that phones, and laptops, and desktops, nowadays, support. It's based on something called the "Fitzpatrick scale," which essentially categorizes human skin tone into six or, in this case, five different categories, from lighter to darker. But this suggests that, wow, if we want to represent people with five different skin tones, like this, that could significantly increase how many unique patterns of 0's and 1's we need for every possible face. But if we think about it from an engineering perspective, we can actually just think of skin tone as modifying some default color, for better or for worse. And yellow is the de facto default, Simpson style.

42:37 But to modify it to look more genuinely human-like, from lighter to darker, well, maybe we just use the same pattern of bits to represent a human thumb, for instance, thumbs up or thumbs down. And we just, then, modify that character to be displayed with a different skin tone. So, for instance, here, then, is the "thumbs up" that you might use on various platforms. And let me just stipulate that this is the Unicode code point. That is the number that Macs, PCs, and phones use underneath the hood to represent the default yellow "thumbs up." But if you want to give it a medium skin tone, you still use that same number, that same pattern of 0's and 1's, or switches, underneath the hood. But you use a few more switches that the computer or phone will interpret as, "Oh, you don't want to see the default in yellow because of this second number that's in the computer's memory somewhere.

43:23 You want me to adjust it to be the medium skin tone or any of the other values, instead." So that's the engineering solution to this problem of just trying to represent different ranges of emoji here. Well, what about something like this? There's a lot more combinatorics, nowadays, on your keyboard for relationships, for instance. So here is a "couple with heart" here. So the couple, here, of course, is represented with, apparently, this number here. But that's it. But if you want to be more specific-- like man and woman, or man-man, woman-woman-- it's the same idea, but we just need to express ourselves a little-- with a little more information. So, for instance, the way the Unicode folks came up with, years ago, to represent, for instance, a woman with a heart and a man, from left to right, would be using these values. So things just escalated quickly, but only

44:08 in the sense that we're using more bits, more 0's and 1's, to represent, more expressively, this particular combination. So this happens to be the number in Unicode that represents the woman at left. This is the number that represents the man at right. And this is the pair of numbers that represents the heart in the middle, sometimes red, sometimes pink, displayed here as pink. But if we want to change the combination, for instance, to be, say, woman-- if we want to change the combination to be woman-woman, notice that, now, the left and the rightmost numbers match. Or if we flip it back to man-man, it's just using different numbers on the tail end again. And meanwhile, if I rewind, there's these two identical values here. These are called zero-width joiners or ZWNJ characters. It just is a special number that humans reserve to say,

44:55 glue the emoji at the left to the emoji on the right and so forth. So it connects ideas in this way. So there's actually a lot of emojis, nowadays, that are a combination of different things. "Heart on fire" is one that's, technically, the combination of a heart emoji, the fire emoji, joined together, numerically, in this way. So computer scientists who come up with these things are just reducing things to representations. All we have at our disposal are 0's and 1's. So we all just need to agree, ultimately-- whether we're Google, Microsoft, or the like-- how we're going to standardize these kinds of things as information. Questions, then, on how characters are represented in a computer, be it English or any other language? Yeah. AUDIENCE: How is the plus a number?

45:40 DAVID J. MALAN: How is the what? AUDIENCE: The plus, the U+. DAVID J. MALAN: Oh, the U+ is just a convention, really. So U+ represents a special Unicode character, which is a U with a plus in the middle. And this is just the convention for saying, hey, everyone, here comes a number that represents a Unicode code point. The U and the 1 have no-- sorry. The U and the plus have no mathematical significance. It's just a visual clue to folks. Other questions on representing text in this way? All right. So what about colors? We've already started looking at pictures. Well, how are those pictures, be it emojis or anything else, represented? One of the most common ways is just with RGB-- red, green, and blue. It turns out that if we just keep track of how much red should be on the screen, and how much green, and how much blue, combined together,

46:27 that gives us every color of the rainbow, from white to black and everything in between. So how do we represent an amount of red, and green, and blue? Well, frankly, just with three different numbers. And this is how computers typically represent colors. Every one of the dots on your computer screen or your phone screen is called a pixel. And every single dot underneath the hood has three numbers associated with it, so three numbers, three numbers, three numbers for every little dot. And those three numbers, together, say how much red, green, and blue should the device display at that location. So, for instance, if you had a dot on your screen that said, "use this much red, this much green this much blue," because each of these numbers, I'll tell you, are one byte or eight bits, which means the total possible values is 0 to 255--

47:15 let me just ballpark that the 72, it feels like a medium amount of red because it's in between 0 and 255. 73 is a medium amount of green, and 33 of blue is just a little bit. So if you combine a medium amount of red, green, and a little bit of blue, anyone want to guess what color of the rainbow this is? AUDIENCE: Brown. DAVID J. MALAN: Sorry? AUDIENCE: Brown. DAVID J. MALAN: Brown? So, close. It's a little more yellow than it is brown. But if we combine them, it looks a little something like this. This is just CS trivia, not something that even I would be able to eyeball, unless I came up with that particular example. But wait a minute. We've seen these numbers before. 72, 73, 33 represented what-- AUDIENCE: Hi! DAVID J. MALAN: --a few minutes ago? So it meant "Hi!" but here I am, claiming, no, no, no, no, that means yellow. How do you reconcile this? Well, at the end of the day, this is all we have,

48:01 0's and 1's, whether you think of them as numbers, or letters, or even colors now. But it depends on the context. So if you've received a text message or an email, odds are the pattern of 0's and 1's that the computer is showing you are going to be interpreted as text because that's the whole point of a text message or an email. If, though, you opened up MacOS's or iOS's or Windows's or Android's calculator app, the same pattern of 0's and 1's might be interpreted as numbers for some addition, or subtraction, or whatever. If you open the same pattern of 0's and 1's in Photoshop, like a graphics program, they're going to be interpreted, in that context, as colors. So context matters. And, indeed, as soon as next week, when you start writing code in that language called C, the onus will be on you, the programmer, to tell the computer, interpret

48:47 the following sequence of bits as a number, or a letter, or something else. And you won't have to even worry about what the 0's and 1's are, but you need to give the computer a hint as to what type of file or piece of data you're representing. So that gives us bits. And you can actually see these dots, these pixels on the screen. Let me zoom in, zoom in. And here we have it, just with this emoji, which, at the end of the day, is a picture that someone at Apple, in this case, drew. And you can see-- if you really zoom in, or take your phone or TV and really put it close to your face, you'll see all of these dots, depending on the hardware. And each of these dots, these squares, is storing 24 bits or three bytes, 24 bits, 24 bits, 24 bits. And that's whey, dot, dot, dot, if you've got a photograph, for instance, that's three megabytes, which

49:35 is 3 million bytes, well, odds are there's 1 million pixels therein because you're using three bytes per pixel to represent each of those colors. That's a bit of an oversimplification, but that's why images and photos are getting bigger and bigger nowadays. Because we're throwing even more pixels into the file. Music-- [MUSIC PLAYING] --how could you represent music, digitally, using just 0's and 1's, or numbers, really? Any instinct, whether a musician or not? Yeah. AUDIENCE: The notes could be represented by a number. DAVID J. MALAN: Yeah, so we can just represent notes by a number. So A is some number, and B. And maybe sharp or flat is some other number. But note might not be quite enough for some--

50:21 yeah? AUDIENCE: [INAUDIBLE]. DAVID J. MALAN: Ah, OK. So one note-- one number to represent the note, itself, the sound or the pitch; one other number to represent the duration. In the context of piano, how long is the human holding the key down? And maybe I can think of a third, the loudness. How hard has the person played that note? So, minimally, with three numbers, you could imagine representing music, as well. And, indeed, that's very well might be what computers are doing when you listen to sound. What about video? How could you represent videos, as well? Yeah? AUDIENCE: Through many images. DAVID J. MALAN: Yeah, many images. So if you've ever produced a film or looked at some of the fine print, 30 frames per second, FPS, or 29 frames per second is just how many pictures are flying across the screen. But that's really all a video file is on a computer,

51:06 lots of pictures moving so quickly in front of us that you and I, our brains, interpolate that as being actual motion. And, in fact, from yesteryear, motion pictures, it's like pictures that are giving the illusion of motion, even though there's only 30 or so of them flying across the screen. So we have a way, now, to represent information, both as input and output, whether it's numbers, letters, images, anything else. Let's now focus on what's inside of that black box, so to speak, wherein we have algorithms, step-by-step instructions for solving some problem. Now, what do I mean by "algorithms" or "step-by-step instructions"? Well, maybe, if we were to turn this into code-- and that's how we'll connect the dots, ultimately, today. Code is just the implementation, in computers, of algorithms. An algorithm can be something we do in the physical world.

51:53 Code is how we implement that exact same idea, in the context of a computer, instead. And here, for instance, is a very common application inside of a computer, for your context. This is the iOS version of the icon. And, typically, if you click on that icon, you'll see something like all of your contacts here, typically, alphabetical, by first name or last name. And your phone or your computer lets you often search for someone's name at the very top. And it will autocomplete, and it'll be pretty darn fast. But it'll be pretty darn fast because the programmers who implemented that application are looking for someone quickly for you. Now, I can do this old school style, whereby we have one of these things from yesteryear, an actual phone book. So, in a physical phone book like this, you might have 1,000 pages.

52:39 And on every page are a bunch of names and a bunch of numbers. And as I flip through this, I could look for someone specific. So suppose I want to call John Harvard, who's-- the first name, of course, starts with a J. Well, I could just turn, page by page, looking for John Harvard. And if he's not there, I keep turning and turning. So this is an algorithm. I'm stepping through the phone book, one page at a time. Is it correct, this algorithm, assuming I'm looking down? So, yeah. I mean, it's stupidly slow because why am I wasting my time with the A's, and the B's, and the so forth? I could probably take bigger bites out of it. But it is correct. And that's going to be one of the goals of writing code, is to, of course, solve the problem you care about correctly. So correctness goes without saying, or else what's the point of writing the code or solving-- or implementing the algorithm? All right. Well, let me at least speed things up.

53:25 So, instead of one page at a time, so, two, four, six, eight-- no, ignore that-- 10, 12, 14, 16, and so forth. It's a little hard to do, physically, but it sounded faster. It was twice as fast, theoretically, but is it correct? AUDIENCE: No. DAVID J. MALAN: So, no. Why? Yeah? AUDIENCE: Yeah, you might [INAUDIBLE]. DAVID J. MALAN: Yeah, I might miss John Harvard because, just by accident, he might get sandwiched between two pages. But do I have to throw the algorithm out altogether? Probably not. Once I reach the K section, which is past the J section, I could double back at least one page, at least, [PATS TELEPHONE BOOK] and just make sure I didn't blow past him completely. So that is twice as fast, because I'm going two pages at a time, plus one extra step. So it's still an improvement. So the first algorithm, worst case, if it's not John, but someone whose name starts with Z,

54:10 that might take me a full 1,000 steps. The second algorithm is just 500 steps because I'm going two pages at a time plus one, in case I have to double back, but that's in the worst case. But most of us in the-- in yesteryear, and what Apple, and Google, and others are actually doing is, in software or here, physically, we're typically going, roughly, to the middle. Especially if there's no cheat sheet on the side, like A through Z, I'm just going to go to, roughly, the middle. And, oh, here I am, not surprisingly, in the M section. But what do I now know. If this is the M section, where is John Harvard? So, clearly, to the left, alphabetically. And so here is where we can take a much bigger bite out of the problem. We can really divide and conquer this problem by tearing [TEARS BOOK] the problem in half, throwing half of it

54:56 away, 500 pages away, leaving me with a smaller problem, half as big, that I can really just now repeat. So I go, roughly, here, and now I'm in the E section. So I went a little too far back. But what do I now know? If this is the E pages, where's John? AUDIENCE: To the right. DAVID J. MALAN: So now he's to the right. So I can-- again, hopefully, he's not on that page. I can tear the problem in half again, throw that 250 pages away. And now I've gone from 1,000 to 500 to 250 pages. Now I'm moving because the first algorithm was one page at a time, second was two. This is hundreds of pages at a time. And if I go, roughly, again, to the middle; roughly, to the middle; roughly, to the middle, hopefully, I'll find John Harvard on one final page. Can only do this once, but one final page. So that invites the question, I would think,

55:42 if the phone book does have 1,000 or so pages, how many times can I divide the problem in half to get down to one last page? So it's, roughly, 10. And the quick math is 1,000 goes to 500 to 250 to 125 to 67 something. So we have to deal with rounding issues, eventually. But assuming we work out the math, it's, roughly, 10 page tears. And that's crazy faster than 1,000 pages and still faster than 500 pages. So it's fundamentally better. And, indeed, if I finally get to that final page, in the software world, you'd see something like this, John Harvard and his number, which you're welcome to call or text. But that's how we now have our answer, much like the single page there. But let's consider just how efficient that actually is.

56:27 So here's a very rough, broad-- with broad strokes, a chart. So here's an xy plot. So here, on the horizontal, is going to be the size of the problem. And, by that, I mean, how many pages are we trying to go through? This would be zero pages. This would be a lot of pages. How much time does it take to solve the problem? How long does it take to find John Harvard or anyone else? This means no time. This means a lot of time. So what's the relationship among these algorithms? Well, the first one is actually just a straight line. If there's n pages in the phone book, well, I claim that it's a one-to-one relationship. Because if Verizon or the phone company adds another page next year, that just means I might have one more step next year, as well, to find John Harvard or anyone else. But the second algorithm, it's also a straight line,

57:12 but it's lower, even though it might not look obvious. And what do I mean by that? Well, let me just draw some temporary lines. If this is how many pages are in the phone book-- dot, dot, dot-- notice that it takes this much time, on the red line, to solve the problem. But if I, instead, use the second algorithm, it takes me half as much time. So, even though they're both straight lines, one is strictly lower than the other, which means it's faster. It's better. But the third algorithm is a fundamentally different shape, and it looks a little something like this. And it looks like it's going to flatten, flatten, flatten out, but it never does. It just rises ever so slowly. And what this means is that if maybe Cambridge and Allston, here in Massachusetts, merge next year, so we go from 1,000 page phone book to a 2,000 page phone book, that means, if we're here this year,

57:58 we're over here next year. It's not all that much higher. But it would be much higher if we were using the first two algorithms. Why? It'd be an extra 1,000 steps to find someone in that combined phone book or maybe another 500 steps. But, to be clear, if we're using my third and final algorithm, how many more steps will it take me next year, when Cambridge and Allston merge into one 2,000-page phone book? Just one more step, no big deal. It's one more page tear. And this is what we mean, ultimately, about not just writing code or implementing algorithms that are correct, but, now, that are well-designed or efficient, specifically. And this is what makes someone a better programmer, perhaps, than someone else, or a better problem-solver than someone else, is acquiring, over time, these skills. So that, sure, you could solve the problem quickly and dirtily,

58:43 so to speak, but if you're going to have a lot of data eventually, be it in your phone book or maybe your Google website index, if you're searching the web, you're going to want to try to think about how to design algorithms that look like this. Mathematically, this is called a logarithm. And it's log base 2 because I'm halving, halving, halving, again and again. But, for now, just know that it's a fundamentally faster and different shape. So, among our goals in CS50, ultimately, is not just to write and solve problems correctly, but, ultimately, ever more efficiently, as well. Any questions, then, on these ideas of efficiency and design? Any questions here? Yeah, in back? AUDIENCE: [INAUDIBLE]. DAVID J. MALAN: A good question. Just to repeat it, can a graph like this capture the accuracy of the algorithm? Short answer, no.

59:28 For instance, if I drew a straight line that is super low on this graph, which would imply that the algorithm takes the same amount of time, no matter how many pages there are, my algorithm might actually be to just pull a random page from the phone book, one step, and say, here it is. But that's not necessarily going to be accurate, unless I get really, really lucky. So the graph really only speaks to efficiency and the design of the algorithm, not the correctness of it. To analyze the correctness, you need to use another mechanism altogether, namely, logic. Other questions now, on efficiency, in this way? No? All right. So, with that in mind, let's begin to translate this to some actual code. And, in fact, before we look at, today, one actual programming language, albeit a graphical one, let's consider something called pseudocode.

1:00:14 So pseudocode has no formal meaning. Generally, you write it in English or whatever your own human language is. But you write your thoughts down tersely, succinct, but precisely. You try to really convey your thoughts, not with a wave of the hand, metaphorically, but step by step, precisely. So what do I mean by this?

…