Harvard CS50 – Full Computer Science University Course

0:00 If you want to learn about computer science and the art of programming, this course is where to start. CS50 is considered by many to be one of the best computer science courses in the world. This is a Harvard University course taught by Dr. David Malan and we are proud to bring it to the freeCodeCamp YouTube channel. Throughout a series of lectures, Dr. Malan will teach you how to think algorithmically and solve problems efficiently. And make sure to check the description for a lot of extra resources that go along with the course. [MUSIC PLAYING] DAVID MALAN: All right, this is CS50, Harvard University's introduction to the intellectual enterprises of computer science and the art of programming, back here on campus in beautiful Sanders Theatre for the first time in quite a while. So welcome to the class. My name is David-- OK. [CHEERING AND APPLAUSE]

2:11 So my name is David Malan. And I took this class myself some time ago, but almost didn't. It was sophomore fall and I was sitting in on the class. And I was a little curious but, eh, it didn't really feel like the field for me. I was definitely a computer person, but computer science felt like something altogether. And I only got up the nerve to take the class, ultimately, because the professor at the time, Brian Kernighan, allowed me to take the class pass/fail, initially. And that is what made all the difference. I quickly found that computer science is not just about programming and working in isolation on your computer. It's really about problem solving more generally. And there was something about homework, frankly, that was, like, actually fun for perhaps the first time in, what, 19 years. And there was something about this ability that I discovered, along with all of my classmates, to actually create something and bring a computer to life to solve a problem,

3:00 and sort of bring to bear something that I'd been using every day but didn't really know how to harness, that's been gratifying ever since, and definitely challenging and frustrating. Like, to this day, all these years later, you're going to run up against mistakes, otherwise known as bugs, in programming, that just drive you nuts. And you feel like you've hit a wall. But the trick really is to give it enough time, to take a step back, take a break when you need to. And there's nothing better, I daresay, than that sense of gratification and pride, really, when you get something to work, and in a class like this, present, ultimately, at term's end, something like your very own final project. Now, this isn't to say that I took to it 100% perfectly. In fact, just this past week, I looked in my old CS50 binder, which I still have from some 25 years ago, and took a photo of what was apparently the very first program that I wrote and submitted,

3:47 and quickly received minus 2 points on. But this is a program that we'll soon see in the coming days that does something quite simply like print "Hello, CS50," in this case, to the screen. And to be fair, I technically hadn't really followed the directions, which is why I lost those couple of points. But if you just look at this, especially if you've never programmed before, you might have heard about programming language but you've never typed something like this out, undoubtedly it's going to look cryptic. But unlike human languages, frankly, which were a lot more sophisticated, a lot more vocabulary, a lot more grammatical rules, programming, once you start to wrap your mind around what it is and how it works and what these various languages are, it's so easy, you'll see, after a few months of a class like this, to start teaching yourself, subsequently, other languages, as they may come, in the coming years as well. So what ultimately matters in this particular course is not so much where you end up relative to your classmates but where you end up relative to yourself when you began. And indeed, you'll begin today. And the only experience that matters ultimately in this class is your own. And so, consider where you are today. Consider, perhaps, just how cryptic something like that looked a few seconds ago. And take comfort in knowing just some months from now all of that will be within your own grasp.

4:58 And if you're thinking that, OK, surely the person in front of me, to the left, to the right, behind me, knows more than me, that's statistically not the case. 2/3 of CS50 students have never taken a CS course before, which is to say, you're in very good company throughout this whole term. So then, what is computer science? I claim that it's problem solving. And the upside of that is that problem solving is something we sort of do all the time. But a computer science class, learning to program, I think kind of cleans up your thoughts. It helps you learn how to think more methodically, more carefully, more correctly, more precisely. Because, honestly, the computer is not going to do what you want unless you are correct and precise and methodical. And so, as such, there's these fringe benefits of just learning to think like a computer scientist and a programmer. And it doesn't take all that much to start doing so. This, for instance, is perhaps the simplest picture of computer science,

5:49 sure, but really problem solving in general. Problems are all about taking input, like the problem you want to solve. You want to get the solution, a.k.a. output. And so, something interesting has got to be happening in here, in here, when you're trying to get from those inputs to outputs. Now, in the world of computers specifically, we need to decide in advance how we represent these inputs and outputs. We all just need to decide, whether it's Macs or PCs or phones or something else, that we're all going to speak some common language, irrespective of our human languages as well. And you may very well know that computers tend to speak only what language, so to speak? Assembly, one, but binary, two, might be your go-to. And binary, by implying two, means that the world of computers has just two digits at its disposal, 0 and 1. And indeed, we humans have many more than that, certainly not just zeros and ones alone. But a computer indeed only has zeros and ones.

6:43 And yet, somehow they can do so much. They can crunch numbers in Excel, send text messages, create images and artwork and movies and more. And so, how do you get from something as simple as a few zeros, a few ones, to all of the stuff that we're doing today in our pockets and laptops and desktops? Well, it turns out that we can start quite simply. If a computer were to want to do something as simple as count, well, what could it do? Well, in our human world, we might count doing this, like 1, 2, 3, 4, 5, using so-called unitary notation, literally the digits on your fingers where one finger represents one person in the room, if I'm, for instance, taking attendance. Now, we humans would typically actually count 1, 2, 3, 4, 5, 6. And we'd go past just those five digits and count much higher, using zeros through nines. But computers, somehow, only have these zeros and ones. So if a computer only somehow speaks binary, zeros and ones, how does it even count past the number 1?

7:36 Well, here are 3 zeros, of course. And if you translate this number in binary, 000, to a more familiar number in decimal, we would just call this zero. Enough said. If we were to represent, with a computer, the number 1, it would actually be 001, which, not surprisingly, is exactly the same as we might do in our human world, but we might not bother writing out the two zeros at the beginning. But a computer, now, if it wants to count as high as two, it doesn't have the digit 2. And so it has to use a different pattern of zeros and ones. And that happens to be 010. So this is not 10 with a zero in front of it. It's indeed zero one zero in the context of binary. And if we want to count higher now than two, we're going to have to tweak these zeros and ones further to get 3. And then if we want 4 or 5 or 6 or 7, we're just kind of toggling these zeros and ones, a.k.a. bits, for binary digits that represent, via these different patterns,

8:31 different numbers that you and I, as humans, know, of course, as the so-called decimal system, 0 through 9, dec implying 10, 10 digits, those zeros through nine. So why that particular pattern? And why these particular zeros and ones? Well, it turns out that representing one thing or the other is just really simple for a computer. Why? At the end of the day, they're powered by electricity. And it's a really simple thing to just either store some electricity or don't store some electricity. Like, that's as simple as the world can get, on or off. 1 or 0, so to speak. So, in fact, inside of a computer, a phone, anything these days that's electronic, pretty much, is some number of switches, otherwise known as transistors. And they're tiny. You've got thousands, millions of them in your Mac or PC or phone these days. And these are just tiny little switches that can get turned on and off. And by turning those things on and off in patterns,

9:20 a computer can count from 0 on up to 7, and even higher than that. And so these switches, really, you can think of being as like switches like this. Let me just borrow one of our little stage lights here. Here's a light bulb. It's currently off. And so, I could just think of this as representing, in my laptop, a transistor, a switch, representing 0. But if I allow some electricity to flow, now I, in fact, have a 1. Well, how do I count higher than 1? I, of course, need another light bulb. So let me grab another one here. And if I put it in that same kind of pattern, I don't want to just do this. That's sort of the old finger counting way of unary, just 1, 2. I want to actually take into account the pattern of these things being on and off. So if this was one a moment ago, what I think I did earlier was I turned it off and let the next one over be on, a.k.a. 010. And let me get us a third bit, if you will. And that feels like enough.

10:16 Here is that same pattern now, starting at the beginning with 3. So here is 000. Here is 001. Here is 010, a.k.a., in our human world of decimal, 2. And then we could, of course, keep counting further. This now would be 3 and dot dot dot. If this other bulb now goes on, and that switch is turned and all three stay on-- this, again, was what number? AUDIENCE: Seven. DAVID MALAN: OK, so, seven. So it's just as simple, relatively, as that, if you will. But how is it that these patterns came to be? Well, these patterns actually follow something very familiar. You and I don't really think about it at this level anymore because we've probably been doing math and numbers since grade school or whatnot. But if we consider something in decimal, like the number 123, I immediately jump to that. This looks like 123 in decimal. But why? It's really just three symbols, a 1, a 2 with a bit of curve, a 3 with a couple of curves, that you and I now instinctively just assign meaning to.

11:22 But if we do rewind a few years, that is one hundred twenty-three because you're assigning meaning to each of these columns. The 3 is in the so-called ones place. The 2 is in the so-called tens place. And the 1 is in the so-called hundreds place. And then the math ensues quickly in your head. This is technically 100 times 1, plus 10 times 2, plus 1 times 3, a.k.a. 100 plus 20 plus 3. And there we get the sort of mathematical notion we know as 123. Well, nicely enough, in binary, it's actually the same thing. It's just these columns mean a little something different. If you use three digits in decimal, and you have the ones place, the tens place, and the hundreds place, well, why was that 1, 10, and 100? They're technically just powers of 10. So 10 to the 0, 10 to the 1, 10 to the 2. Why 10? Decimal system, "dec" meaning 10. You have 8 and 10 digits, 0 through 9. In the binary system, if you're going to use three digits,

12:21 just change the bases if you're using only zeros and ones. So now it's powers of 2, 2 to the 0, 2 to the 1, 2 to the 2, a.k.a. 1 and 2 and 4, respectively. And if you keep going, it's going to be 8s column, 16s column, 32, 64, and so forth. So, why did we get these patterns that we did? Here's your 000 because it's 4 times 0, 2 times 0, 1 times 0, obviously 0. This is why we got the decimal number 1 in binary. This is why we got the number 2 in binary, because it's 4 times 0, plus 2 times 1, plus 1 times 0, and now 3, and now 4, and now 5, and now 6, and now 7. And, of course, if you wanted to count as high as 8, to be clear, what do you have to do? What does a computer need to do to count even higher than 7? AUDIENCE: Add a bit. DAVID MALAN: Add a bit. Add another light bulb, another switch. And, indeed, computers have standardized just how many zeros and ones, or bits or switches, they throw at these kinds of problems.

13:19 And, in fact, most computers would typically use at least eight at a time. And even if you're only counting as high as three or seven, you would still use eight and have a whole bunch of zeros. But that's OK, because the computers these days certainly have so many more, thousands, millions of transistors and switches that that's quite OK. All right, so, with that said, if we can now count as high as seven or, frankly, as high as we want, that only seems to make computers useful for things like Excel, like number crunching. But computers, of course, let you send text messages, write documents, and so much more. So how would a computer represent something like a letter, like the letter A of the English alphabet, if, at the end of the day, all they have is switches? Any thoughts? Yeah. AUDIENCE: You can represent letters in numbers. DAVID MALAN: OK, so we could represent letters using numbers. OK, so what's a proposal?

14:10 What number should represent what? AUDIENCE: Say if you were starting at the beginning of the alphabet, you could say 1 is A, 2 is B, 3 is C. DAVID MALAN: Perfect. Yeah, we just all have to agree somehow that one number is going to represent one letter. So 1 is A, 2 is B, 3 is C, Z is 26, and so forth. Maybe we can even take into account uppercase and lowercase. We just have to agree and sort of write it down in some global standard. And humans, indeed, did just that. They didn't use 1, 2, 3. It turns out they started a little higher up. Capital A has been standardized as the number 65. And capital B has been standardized as the number 66. And you can kind of imagine how it goes up from there. And that's because whatever you're representing, ultimately, can only be stored, at the end of the day, as zeros and ones. And so, some humans in a room before, decided that capital A shall be 65, or, really, this pattern of zeros and ones inside of every computer in the world, 01000001.

15:08 So if that pattern of zeros and ones ever appears in a computer, it might be interpreted then as indeed a capital letter A, eight of those bits at a time. But I worry, just to be clear, we might have now created a problem. It might seem, if I play this naively, that, OK, how do I now actually do math with the number 65? If now Excel displays 65 is an A, let alone Bs and Cs. So how might a computer do as you've proposed, have this mapping from numbers to letters, but still support numbers? It feels like we've given something up. Yeah? AUDIENCE: By having a prefix for letters? DAVID MALAN: By having a prefix? AUDIENCE: You could have prefixes and suffixes. DAVID MALAN: OK, so we could perhaps have some kind of prefix, like some pattern of zeros and ones-- I like this-- that indicates to the computer here comes another pattern that represents a letter. Here comes another pattern that represents a number or a letter. So, not bad. I like that. Other thoughts?

16:05 How might a computer distinguish these two? Yeah. AUDIENCE: Have a different file format, so, like, odd text or just check the graphic or-- DAVID MALAN: Indeed, and that's spot-on. Nothing wrong with what you suggested, but the world generally does just that. The reason we have all of these different file formats in the world, like JPEG and GIF and PNGs and Word documents, .docx, and Excel files and so forth, is because a bunch of humans got in a room and decided, well, in the context of this type of file, or really, more specifically, in the context of this type of program, Excel versus Photoshop versus Google Docs or the like, we shall interpret any patterns of zeros and ones as being maybe numbers for Excel, maybe letters in, like, a text messaging program or Google Docs, or maybe even colors of the rainbow in something like Photoshop and more. So it's context dependent. And we'll see, when we ourselves start programming,

16:58 you the programmer will ultimately provide some hints to the computer that tells the computer, interpret it as follows. So, similar in spirit to that, but not quite a standardized with these prefixes. So this system here actually has a name ASCII, the American Standard Code for Information Interchange. And indeed, it began here in the US, and that's why it's actually a little biased toward A's through Z's and a bit of punctuation as well. And that quickly became a problem. But if we start simply now, in English, the mapping itself is fairly straightforward. So if A is 65, B it 66, and dot dot dot, suppose that you received a text message, an email, from a friend, and underneath the hood, so to speak, if you kind of looked inside the computer, what you technically received in this text or this email happened to be the numbers 72, 73, 33, or, really, the underlying pattern of zeros and ones. What might your friend have sent you as a message, if it's 72, 73, 33?

17:56 AUDIENCE: Hey. DAVID MALAN: Hey? Close. AUDIENCE: Hi. DAVID MALAN: Hi. It's indeed hi. Why? Well, apparently, according to this little cheat sheet, H is 72, I is 73. It's not obvious from this chart what the 33 is, but indeed, this pattern represents "hi." And anyone want to guess, or if you know, what 33 is? AUDIENCE: Exclamation point. DAVID MALAN: Exclamation point. And this is, frankly, not the kind of thing most people know. But it's easily accessible by a nice user-friendly chart like this. So this is an ASCII chart. When I said that we just need to write down this mapping earlier, this is what people did. They wrote it down in a book or in a chart. And, for instance, here is our 72 for H, here is our 73 for I, and here is our 33 for exclamation point. And computers, Macs, PCs, iPhones, Android devices, just know this mapping by heart, if you will. They've been designed to understand those letters.

18:46 So here, I might have received "hi." Technically, what I've received is these patterns of zeros and ones. But it's important to note that when you get these patterns of zeros and ones in any format, be it email or text or a file, they do tend to come in standard lengths, with a certain number of zeros and ones altogether. And this happens to be 8 plus 8, plus 8. So just to get the message "hi, exclamation point," you would have received at least, it would seem, some 24 bits. But frankly, bits are so tiny, literally and mathematically, that we don't tend to think or talk, generally, in terms of bits. You're probably more familiar with bytes. B-Y-T-E-S is a byte, is a byte, is a byte. A byte is just 8 bits. And even those, frankly, aren't that useful if we do out the math. How high can you count if you have eight bits? Anyone know? Say it again? Higher than that. Unless you want to go negative, that's fine. 256, technically 255.

19:45 Long story short, if we actually got into the weeds of all of these zeros and ones, and we figured out what 11111111 mathematically adds up to in decimal, it would indeed be 255, or less if you want to represent negative numbers as well. So this is useful because now we can speak, not just in terms of bytes but, if the files are bigger, kilobytes is thousands of bytes, megabytes is millions of bytes, gigabytes is billions of bytes, terabytes are trillions of bytes, and so forth. We have a vocabulary for these increasingly large quantities of data. The problem is that, if you're using ASCII and, therefore, eight bits or one byte per character, and originally, only seven, you can only represent 255 characters. And that's actually 256 total characters, including zero. And that's fine if you're using literally English, in this case, plus a bunch of punctuation. But there's many human languages in the world that need many more symbols and, therefore, many more bits.

20:45 So, thankfully, the world decided that we'll indeed support not just the US English keyboard, but all of the accented characters that you might want for some languages. And heck, if we use enough bits, zeros and ones, not only can we represent all human languages in written form, as well as some emotions along the way, we can capture the latter with these things called emojis. And indeed, these are very much in vogue these days. You probably send and/or receive many of these things any given day. These are just characters, like letters of an alphabet, patterns of zeros and ones that you're receiving, that the world has also standardized. For instance, there are certain emojis that are represented with certain patterns of bits. And when you receive them, your phone, your laptop, your desktop, displays them as such. And this newer standard is called Unicode. So it's a superset of what we called ASCII.

21:35 And Unicode is just a mapping of many more numbers to many more letters or characters, more generally, that might use eight bits for backwards compatibility with the old way of doing things with ASCII, but they might also use 16 bits. And if you have 16 bits, you can actually represent more than 65,000 possible letters. And that's getting up there. And heck, Unicode might even use 32 bits to represent letters and numbers and punctuation symbols and emojis. And that would give you up to 4 billion possibilities. And, I daresay, one of the reasons we see so many emojis these days is we have so much room. I mean, we've got room for billions more, literally. So, in fact, just as a little bit of trivia, has anyone ever received this decimal number, or if you prefer binary now, has anyone ever received this pattern of zeros and ones on your phone, in a text or an email, perhaps this past year?

22:29 Well, if you actually look this up, this esoteric sequence of zeros and ones happens to represent face with medical mask. And notice that if you've got an iPhone or an Android device, you might be seeing different things. In fact, this is the Android version of this, most recently. This is the iOS version of it, most recently. And there's bunches of other interpretations by other companies as well. So Unicode, as a consortium, if you will, has standardized the descriptions of what these things are. But the companies themselves, manufacturers out there, have generally interpreted it as you see fit. And this can lead to some human miscommunications. In fact, for like, literally, embarrassingly, like a year or two, I started being in the habit of using the emoji that kind of looks like this because I thought it was like woo, happy face, or whatever. I didn't realize this is the emoji for hug

23:19 because whatever device I was using sort of looks like this, not like this. And that's because of their interpretation of the data. This has happened too when what was a gun became a water pistol in some manufacturers' eyes. And so it's an interesting dichotomy between what information we all want to represent and how we choose, ultimately, to represent it. Questions, then, on these representations of formats, be it numbers or letters, or soon more. Yeah? AUDIENCE: Why is decimal popular for a computer if binary is the basis for everything? DAVID MALAN: Sorry, why is what so popular? AUDIENCE: Why is the decimal popular if binary is the fundamental-- DAVID MALAN: Yeah, so we'll come back to this in a few weeks, in fact. There are other ways to represent numbers. Binary is one. Decimal is another. Unary is another. And hexadecimal is yet a fourth that uses 16 total digits, literally 0 through 9 plus A, B, C, D, E, F. And somehow,

24:15 you can similarly count even higher with those. We'll see in a few weeks why this is compelling. But hexadecimal, long story short, uses four bits per digit. And so, four bits, if you have two digits in hex, that gives you eight. And it's just a very convenient unit of measure. And it's also human convention in the world of files and other things. But we'll come back to that soon. Other questions? AUDIENCE: Do the lights on the stage supposedly say that-- DAVID MALAN: Do the lights on the stage supposedly say anything? Well, if we had thought in advance to use maybe 64 light bulbs, that would seem to give us 8 total bytes on stage, 8 times 8, giving us just that. Maybe. Good question. Other questions on 0's and 1's? It's a little bright in here. No? Oh yes? Where everyone's pointing somewhere specific. There we go. Sorry. Very bright in this corner. AUDIENCE: I was just going to ask about the 255 bits, like with the maximum characters.

25:16 [INAUDIBLE] DAVID MALAN: Ah, sure, and we'll come back to this, in some form, in the coming days too, at a slower pace too, we have, with eight bits, two possible values for the first and then two for the next, two for the next, and so forth. So that's 2 times 2 times 2. That's 2 to the eighth power total, which means you can have 256 total possible patterns of zeros and ones. But as we'll see soon computer scientists, programmers, software often starts counting at 0 by convention and if you use one of those patterns, 00000000 to represent the decimal number we know is zero, you only have 255 other patterns left to count as high as therefore 255. That's all. Good question. All right, so what then might we have besides these emojis and letters and numbers? Well, we of course have things like colors and programs like Photoshop and pictures and photos. Well let me ask the question again.

26:11 How might a computer, do you think, knowing what you know now, represents something like a color? Like what are our options if all we've got are zeros and ones and switches? Yeah? AUDIENCE: RGB DAVID MALAN: RGB. RGB indeed is this acronym that represents some amount of red and some amount of green and blue and indeed computers can represent colors by just doing that. Remembering, for instance, this dot. This yellow dot on the screen that might be part of any of those emojis these days, well that's some amount of red, some amount of green, some amount of blue. And if you sort of mix those colors together, you can indeed get a very specific one. And we'll see you in just a moment just that. So indeed earlier on, humans only used seven bits total. And it was only once they decided, well, let's add an eighth bit that they got extended ASCII and that was initially in part a solution to the same problem of not having enough room, if you will,

27:00 in those patterns of zeros and ones to represent all of the characters that you might want. But even that wasn't enough and that's why we've now gone up to 16 and 32 and long past 7. So if we come back now to this one particular color. RGB was proposed as a scheme, but how might this work? Well, consider for instance this. If we do indeed decide as a group to represent any color of the rainbow with some mixture of some red, some green, and some blue, we have to decide how to represent the amount of red and green and blue. Well, it turns out if all we have are zeros and ones, ergo numbers, let's do just that. For instance, suppose a computer we're using, these three numbers 72, 73, 33, no longer in the context of an email or a text message, but now in the context of something like Photoshop, a program for editing and creating graphical files, maybe this first number could be interpreted as representing some amount of red, green, and blue,

28:00 respectively. And that's exactly what happens. You can think of the first digit as red, second as green, third as blue. And so ultimately when you combine that amount of red, that amount of green, that amount of blue, it turns out it's going to resemble the shade of yellow. And indeed, you can come up with a numbers between 0 and 255 for each of those colors to mix any other color that you might want. And you can actually see this in practice. Even though our screens, admittedly, are getting really good on our phones and laptops such that you barely see the dots, they are there. You might have heard the term pixel before. Pixel's just a dot on the screen and you've got thousands, millions of them these days horizontally and vertically. If I take even this emoji, which again happens to be one company's interpretation of a face with medical mask and zoom in a bit, maybe zoom in a bit more, you can actually start to see these pixels.

28:50 Things get pixelated because what you're seeing is each of the individual dots that compose this particular image. And apparently each of these individual dots are probably using 24 bits, eight bits for red, eight bits for green, eight bits for blue, in some pattern. This program or some other like Photoshop is interpreting one pattern and it's white or yellow or black or some brown in between. So if you look sort of awkwardly, but up close to your phone or your laptop or maybe your TV, you can see exactly this, too. All right, well, what about things that we also watch every day on YouTube or the like? Things like videos. How would a computer, knowing what we know now, represent something like a video? How might you represent a video using only zeros and ones? Yeah? AUDIENCE: As we can see here, they represent images, right? [INAUDIBLE] sounds of the 0 and 1s as well. [INAUDIBLE] DAVID MALAN: Yeah, exactly. To summarize, what video really adds is just some notion of time. It's not just one image, it's not just one letter or a number, it's presumably some kind of sequence because time is passing. So with a whole bunch of images, maybe 24 maybe 30 per second,

30:05 if you fly them by the human's eyes, we can interpret them using our eyes and brain that there is now movement and therefore video. Similarly with audio or music. If we just came up with some convention for representing those same notes on a musical instrument, could we have the computer synthesize them, too? And this might be actually pretty familiar. Let me pull up a quick video here, which happens to be an old school version of the same idea. You might remember from childhood. [MUSIC PLAYING] [CLICKING]

30:54 So granted that particular video is an actual video of a paper-based animation, but indeed, that's really all you need, is some sequence of these images, which themselves of course are just zeros and ones because they're just this grid of these pixels or dots. Now something like musical notes like these, those of you who are musicians might just naturally play these on physical devices, but computers can certainly represent those sounds, too. For instance, a popular format for audio is called MIDI and MIDI might just represent each note that you saw a moment ago essentially as a sequence of numbers. But more generally, you might think about music as having notes, for instance, A through G, maybe some flats and some sharps, you might have the duration like how long is the note being heard or played on a piano or some other device, and then just the volume like how hard does a human in the real world press down on that key and therefore how loud is that sound?

31:46 It would seem that just remembering little details like that quantitatively we can then represent really all of these otherwise analog human realities. So that then is really a laundry list of ways that we can just represent information. Again, computers or digital have all of these different formats, but at the end of the day and as fancy as those devices in years are, it's just zeros and ones, tiny little switches or light bulbs, if you will, represented in some way and it's up to the software that you and I and others write to use those zeros and ones in ways we want to get the computers to do something more powerfully. Questions, then, on this representation of information, which I daresay is ultimately what problem solving is all about, taking in information and producing new via some process in between. Any questions there? Yeah, in back. AUDIENCE: Yeah, so we talked about how different file formats kind of allow you to interpret information.

32:45 How does a file format like .mp4 discriminate between audio and video within itself as a value? DAVID MALAN: So a really good question. There are many other file formats out there. You allude to MP4 for video and more generally the use are these things called codecs and containers. It's not quite as simple when using larger files, for instance, in more modern formats that a video is just a sequence of images, for instance. Why? If you stored that many images for like a Hollywood movie, like 24 or 30 of them per second, that's a huge number of images. And if you've ever taken photos on your phone, you might know how many megabytes or larger even individual photographs might be. So humans have developed over the years a fancier software that uses much more math to represent the same information more minimally just using somehow shorter patterns of zeros and ones than are most simplistic representation here. And they use what might be called compression.

33:40 If you've ever used a zip file or something else, somehow your computer is using fewer zeros and ones to represent the same amount of information, ideally without losing any information. In the world of multimedia, which we'll touch on a little bit in a few weeks, there are both lossy and lossless formats out there. Lossless means you lose no information whatsoever. But more commonly as you're alluding to one is lossy compression, L-O-S-S-Y, where you're actually throwing away some amount of quality. You're getting some amount of pixelation that might not look perfect to the human, but heck it's a lot cheaper and a lot easier to distribute. And in the world of multimedia, you have containers like QuickTime and other MPEG containers that can combine different formats of video, different formats of audio in one file, but there, too, do designers have discretion. So more in a few weeks, too.

34:28 Other questions, then, on information here as well? Yeah? AUDIENCE: So I know computers used to be very big and taking up like a whole room and stuff. Is the reason they've gotten smaller because we can store this information piecemeal or what? DAVID MALAN: Exactly. I mean, back in the day you might have heard of the expression a vacuum tube, which is like some physically large device that might have only stored some 0 or 1. Yes, it is the miniaturization of hardware these days that has allowed us to store as many and many more zeros and ones much more closely together. And as we've built more fancy machines that can sort of design this hardware at an even smaller scale, we're just packing more and more into these devices. But there, too, is a trade off. For instance, you might know by using your phone or your laptop for quite a while, maybe on your lap, starts to get warm. So there are these literal physical side effects of this where now some of our devices run hot.

35:20 This is why like a data center in the real world might need more air conditioning than a typical place, because there are these physical artifacts as well. In fact, if you'd like to see one of the earliest computers from decades ago, across the river here in now Allston in the new engineering building is the Harvard Mark 1 computer that will give you a much better mental model of just that. Well if we come back now to this first picture being computer science or really problem solving, I daresay we have more than enough ways now to represent information, input and output, so long as we all just agree on something and thankfully all of those before us have given us things like ASCII and Unicode. Not to mention MP4s, word documents, and the like. But what's inside of this proverbial black box into which these inputs are going in the outputs are coming? Well that's where we get this term you might have heard, too.

36:09 An algorithm, which is just step-by-step instructions for solving some problem incarnated in the world of computers by software. When you write software aka programs, you are implementing one or more algorithms, one or more sets of instructions for solving some problem, and maybe you're using this language or that, but at the end of the day, no matter the language you use the computer is going to represent what you type using just zeros and ones. So what might be a representative algorithm? Nowadays you might use your phone quite a bit to make calls or send texts or emails and therefore you have a whole bunch of contacts in your address book. Nowadays, of course, this is very digital, but whether on iOS or Android or the like, you might have a whole bunch of names, first name and/or last, as well as numbers and emails and the like. You might be in the habit of like scrolling through on your phone all of those names to find the person you want to call.

37:05 It's probably sorted alphabetically by first name or last name, A through Z, or some other symbol. This is frankly quite the same as we used to do back in my day, CS50, when we just used a physical book. In this physical book might be a whole bunch of names alphabetically sorted from left to right corresponding to a whole bunch of numbers. So suppose that in this old Harvard phone book we want to search for John Harvard. We might of course start quite simply at the beginning here, looking at one page at a time, and this is an algorithm. This is like literally step-by-step looking for the solution to this problem. In that sense, if John Harvard's in the phone book, is this algorithm page-by-page correct, would you say? AUDIENCE: Yes. DAVID MALAN: Yes. Like if John Harvard's in the phone book, obviously I'm eventually going to get to him, so that's what we mean by correct. Is it efficient? Is it well designed, would you say? No.

37:58 I mean this is going to take forever even just to get to the Js or the Hs, depending how this thing's sorted. All right, well let me go a little faster. I'll start like two pages at a time. 2, 4, 6, 8, 10, 12, and so forth. Sounds faster, is faster, is it correct? AUDIENCE: No. DAVID MALAN: OK, why is it not correct? Yeah? AUDIENCE: So if you're starting on page 1, you're only going odd number of pages, so if it's on an even number page, you'll miss it. DAVID MALAN: Exactly. If I start on an odd number of pages and I'm going two at a time I might miss pages in between. And if I therefore conclude when I get to the back of the book there was no John Harvard, I might have just errored. This would be again one of these bugs. But if I try a little harder, I feel like there's a solution. We don't have to completely throw out this algorithm. I think we can probably go roughly twice as fast still. But what should we do instead to fix this? Yeah, in back.

38:48 AUDIENCE: [INAUDIBLE] DAVID MALAN: Nice. So I think what many of us, most of us, if we even use this technology any more these days, we might go roughly to the middle of the phone book just to kind of get us started. And now I'm looking down, I'm looking for J, assuming first name, J Harvard, and it looks like I'm in the M section. So just to be clear, what should I do next? AUDIENCE: [INAUDIBLE] DAVID MALAN: OK, and presumably it is John Harvard would be to the left of this. So here's an opportunity to figuratively and literally tear this particular problem in half, throw half of the problem away. It's actually pretty easy if you just do it that way. The hard way is this way. But I've now just decreased the size of this problem really in half. So if I started with 1,000 pages of phone numbers and names, now I'm down to 500. And already we haven't found John Harvard,

39:48 but that's a big bite out of this problem. I do think it's correct because if J is to the left of M, of course, he's definitely not going to be over there. I think if I repeat this again dividing and conquering, if you will, here I might have gone a little too far. Now I'm in like the E section. So let me tear the problem in half again, throw another 250 pages away, and again repeat, dividing and dividing and conquering until finally, presumably, I end up with just one page of a phone book on which John Harvard's name either is or is not, but because of the algorithm you proposed, step by step, I know that he's not in anything I discarded. So traumatic is that might have been made out to be, it's actually just harnessing pretty good human intuition. Indeed, this is what programming is all about, too. It's not about learning a completely new world, but really just how to harness intuition and ideas that you might already have and take naturally but learning how to express

40:43 them now more succinctly, more precisely, using things called programming languages. Why is an algorithm like that if I found John Harvard better than, ultimately, just doing the first one or even the second and maybe doubling back to check those even pages? Well let's just look at little charts here. Again, we don't have to get into the nuances of numbers, but if we've got like a chart here, xy plot, on the x-axis here I claim as the size of the problem. So measured in the numbers of pages in the phone book. So the farther you go out here, the more pages are in the phone book. And here we have time to solve on the y-axis. So the higher you go up, the more time it's going to be taking to solve that particular problem. So let's just arbitrarily say that the first algorithm, involving like n pages, might be represented graphically like this. No matter the slope, it's a straight line because there's presumably a one to one relationship

41:36 between numbers of pages and number of seconds or number of page turns. Why? If the phone company adds another page next year because some new people move to town, that's going to require one additional page for me. One to one. If, though, we use the second algorithm, flawed though it was, unless we double back a little bit to fix someone being in between, that's too going to be a straight line, but it's going to be a different slope because now there's a 2 to 1 or a 1 to 2 relationship because I'm going to pages at a time. So if the phone company adds another page or another two pages, that still only just one more step. You can see the difference if I kind of draw this. If this is the phone book in question, this number of pages, it might take this many seconds on the yellow line to represent or to find someone like John Harvard. But of course on the first algorithm, the red line, it's literally going to take twice as many steps.

42:29 And what do the n here mean? n is the go-to variable for computer scientist or programmer just generically representing a number. So if the number of pages in the phone book is n, the number of steps the second algorithm would have taken would be in the worst case n over 2. Half as many because you're going twice as fast. But the third algorithm, actually if you recall your logarithms, looks a little something like this. There's a fundamentally different relationship between the size of the problem and the amount of time required to solve it that technically is log-based, too, again, but it's really the shape that's different. The implication there is that if, for instance, Cambridge and Allston, two different towns here in Massachusetts, merge next year and there's just one phone book that's twice as big, no big deal for that third and final algorithm. Why? You just tear the problem one more time in half, taking one more byte, that's it, not another 1,000

43:21 bytes just to get to the solution. Put another way, you can walk it way, way, way out here to a much bigger phone book and ultimately that green line is barely going to have budged. So this then is just a way of now formalizing and thinking about what the performance or quality of these algorithms might be. Before we now make one more formalization of the algorithm itself, any questions then on this notion of efficiency or now performance of ideas? Yeah. AUDIENCE: How many phone books have you got? DAVID MALAN: (LAUGHING) A lot of phone books over the years and if you or your parents have any more still somewhere we could definitely use them because they're hard to find. Other questions? But thanks. Other questions here, too? No. Oh, was that a murmur? Yes, over here. AUDIENCE: You could get Harry Potter as a guest speaker. DAVID MALAN: Sorry, say again. AUDIENCE: You could get Harry Potter as a guest speaker. DAVID MALAN: (LAUGHING) Oh, yeah.

44:19 Hopefully. Then we'd have a little something more to use here. So now if we want to formalize further what it is we just did, we can go ahead and introduce this. A form of code aka pseudocode. Pseudocode is not a specific language, it's not like something we're about to start coding in, it's just a way of expressing yourself in English or any human language succinctly correctly toward an end of getting your idea for an algorithm across. So for instance, here might be how we could formalize the code, the pseudocode for that same algorithm. Step one was pick up the phone book, as I did. Step two might be open to the middle of the phone book, as you proposed that we do first. Step three was probably to look down at the pages, I did. And step four gets a little more interesting because I had to quickly make a decision and ask myself a question. If person is on page, then I should probably just go ahead and call that person.

45:13 But that probably wasn't the case at least for John Harvard, and I opened the M section. So there's this other question I should now ask else if the person is earlier in the book, then I should tear the problem in half as I did but go left, so to speak, and then not just open to the middle of the left half of the book, but really just go back to step three, repeat myself. Why? Because I can just repeat what I just did, but with a smaller problem having taken this big bite. But, if the person was later in the book, as might have happened with a different person than John Harvard, then I should open to the middle of the right half of the book, again go back to line three, but again, I'm not going to get sucked doing something forever like this because I keep shrinking the size of the problem. Lastly, the only possible scenario that's left, if John Harvard is not on the page and he's not to the left and he's not to the right, what should our conclusion be?

46:02 AUDIENCE: He's not there. DAVID MALAN: He's not there. He's not listed. So we need to quit in some other form. Now as an aside, it's kind of deliberate that I buried that last question at the end because this is what happens all too often in programming, whether you're new at it or professional, just not considering all possible cases, corner cases if you will, that might not happen that often, but if you don't anticipate them in your own code, pseudocode or otherwise, this is when and why programs might crash or you might say stupid little spinning beach balls or hourglasses or your computer might reboot. Why? It's doing something sort of unpredictable if a human, maybe myself, didn't anticipate this. Like what does this program do if John Harvard is not in the phone book if I had omitted lines 12 and 13? I don't know. Maybe it would behave differently on a Mac or PC because it's sort of undefined behavior.

46:53 These are the kinds of omissions that frankly you're invariably going to make, bugs you're going to introduce, mistakes you're going to make early on, and me, too, 25 years later. But you'll get better at thinking about those corner cases and handling anything that can possibly go wrong and as a result, your code will be all the better for it. Now the problem ultimately with learning how to program, especially if you've never had experience or even if you do but you learned one language only, is that they all look a little cryptic at first glance. But they do share certain commonalities. In fact, we'll use this pseudocode to define those first. Highlighted in yellow here are what henceforth we're going to start calling functions. Lots of different programming languages exist, but most of them have what we might call functions, which are actions or verbs that solve some smaller problem. That is to say, you might use a whole bunch of functions

47:46 to solve a bigger problem because each function tends to do something very specific or precise. These then in English might be translated in code, actual computer code, to these things called functions. Highlighted in yellow now are what we might call conditionals. Conditionals are things that you do conditionally based on the answer to some question. You can think of them kind of like forks in the road. Do you go left or go right or some other direction based on the answer to some question? Well, what are those questions? Highlighted now in yellow or what we would call Boolean expressions, named after a mathematician last name Bool, that simply have yes no answers. Or, if you prefer, true or false answers or, heck, if you prefer 1 or 0 answers. We just need to distinguish one scenario from another. The last thing manifests in this pseudocode is what I might highlight now and call loops. Some kind of cycle, some kind of directive that tells us to do something

48:43 again and again so that I don't need a 1,000-line program to search a 1,000-page phone book, I can get away with a 13-line program but sort of repeat myself inherently in order to solve some problem until I get to that last step. So this then is what we might call pseudocode and indeed there are other characteristics of programs that we'll touch on before long, things like arguments and return values, variables, and more, but unfortunately in most languages, including some we will very deliberately use in this class and that everyone in the real world these days still uses, its programs tend to look like this. This for instance, is a distillation of that very first program I wrote in 1996 in CS50 itself just to print something on the screen. In fact, this version here just tries to print quote unquote, "Hello, world." Which is, dare say, the most canonical first thing that most any programmer ever gets a computer to say just because,

49:41 but look at this mess. I mean, there's a hash symbol, these angled brackets, parentheses, words like int, curly braces, quotes, parentheses, semicolons, and back slashes. I mean there's more overhead and more syntax and clutter than there is an actual idea. Now that's not to say that you won't be able to understand this before long, because honestly there's not that many patterns, indeed programming languages have typically a much smaller vocabulary than any actual human language, but at first it might indeed look quite cryptic. But you can perhaps infer I have no idea what these other lines do yet, but "Hello, world." is presumably quote unquote what will be printed on the screen. But what we'll do today, after a short break, and set the stage for next week is introduce these exact same ideas in just a bit using Scratch, something that you yourselves might have used when you're quite younger but without the same vocabulary applied to those ideas.

50:34 The upside of what we'll soon do using Scratch, this graphical programming language from our friends down the road at MIT, it'll let us today start to drag and drop things that look like puzzle pieces that interlock together if it makes logical sense to do so, but without the distraction of hashes, parentheses, curly braces, angle brackets, semicolons, and things that are quite beside the point. But for now, let's go ahead and take a 10 minute break here and when we resume, we will start programming. So this on the screen is a language called C something that will dive into next week and thankfully this now on the screen is another language called Python that we'll also take a look at in a few weeks before long along with other languages along the way. Today though, and for this first week, week zero, so to speak, we use Scratch because again it will allow us to explore some of those programming fundamentals

51:23 that will be in C and in Python and in JavaScript and other languages, too, but in a way where we don't have to worry about the distractions of syntax. So the world of Scratch looks like this. It's a web-based or downloadable programming environment that has this layout here by default. On the left here we'll soon see is a palette of puzzle pieces, programming blocks that represent all of those ideas we just discussed. And by dragging and dropping these puzzle pieces or blocks over this big area and connecting them together, if it makes logical sense to do so, we'll start programming in this environment. The environment allows you to have multiple sprites, so to speak. Multiple characters, things like a cat or anything else, and those sprites exist in this rectangular world up here that you can full screen to make bigger and this here by default is Scratch, who can move up, down, left, right and do many more things, too.

52:16 Within its Scratch's world you can think of it as perhaps a familiar coordinate system with Xs and Ys which is helpful only when it comes time to position things on the screen. Right now Scratch is at the default, 0,0, where x equals 0 and y equals 0. If you were to move the cat way up to the top, x would stay zero, y would be positive 180. If you move the cat all the way to the bottom, x would stay zero, but y would now be negative 180. And if you went left, x would become negative 240 but y would stay 0, or to the right x would be 240 and y would stay zero. So those numbers generally don't so much matter because you can just move relatively in this world up, down, left, right, but when it comes time to precisely position some of these sprites or other imagery, it'll be helpful just to have that mental model off up, down, left, and right. Well let's go ahead and make perhaps the simplest of programs here.

53:10 I'm going to switch over to the same programming environment now for a tour of the left hand side. So by default selected here are the category in blue motion, which has a whole bunch of puzzle pieces or blocks that relate to motion. And whereas Scratch as a graphical language categorizes things by the type of things that these pieces do, we'll see that throughout this whole palette we'll have functions and variables and conditionals and Boolean expressions and more each in a different color and shape. So for instance, moving 10 steps or turning one way or the other would be functions categorized here as things like motion. Under looks in purple, you might have speech bubbles that you can create by dragging and dropping these that might say "hello" or whatever for some number of seconds. Or you could switch costumes, change the cat to look like a dog or a bird or anything else in between. Sounds too.

54:01 You can play sounds like "meow" or anything you might import or record, yourself. Then there's these things Scratch calls events and the most important of these is the first, when green flag clicked. Because if we look over to the right of Scratch's world here, this rectangular region has this green flag and red stop sign up above, one of which is for Play one of which is for Stop and so that's going to allow us to start and stop our actual programs when that green flag is initially clicked. But you can listen for other types of events when the spacebar is pressed or something else, when this sprite is clicked or something else. Here you already see like a programmer's incarnation of things you and I take for granted like every day now on our phones. Any time you tap an icon or drag your finger or hit a button on the side. These are what a programmer would call events, things that happen and are often triggered by us humans and things that a program be it in Scratch or Python

54:55 or C or anything else can listen for and respond to. Indeed, that's why when you tap the phone icon on your phone, the phone application starts up because someone wrote software that's listening for a finger press on that particular icon. So Scratch has these same things, too. Under Control in orange, you can see that we can wait for one second or repeat something some number of times, 10 by default, but we can change anything in these white circles to anything else. There's another puzzle piece here forever, which implies some kind of loop where we can do something again and again. Even though it seems a little tight, there's not much room to fit something there, Scratch is going to have these things grow and shrink however we want to fill similarly shaped pieces. Here are those conditionals. If something is true or false, then do this next thing. And that's how we can put in this little trapezoid-like shape.

55:42 Some form of Boolean expression, a question with a yes/no, true/false, or one/zero answer and decide whether to do something or not. You can combine these things, too. If something is true, do this, else do this other thing. And you can even tuck one inside of the other if you want to ask three or four or more questions. Sensing, too, is going to be a thing. You can ask questions aka Boolean expressions like is the sprite touching the mouse pointer, the arrow on the screen? So that you can start to interact with these programs. What is the distance between a sprite and a mouse pointer? You can do simple calculations just to figure out maybe if the enemy is getting close to the cat. Under Operator some lower level stuff like math, but also the ability to pick random numbers, which for a game is great because then you can kind of vary the difficulty or what's happening in a game without the same game playing the same way every time. And you can combine ideas.

56:33 Something and something must be true in order to make that kind of decision before. Or we can even join two words together. Says apple and banana by default, but you can type in or drag and drop whatever you want there to combine multiple words into full, larger sentences. Then lastly down here, there's in orange things called variables. In math we've obviously got x and y and whatnot. In programming we'll have the same ability to store in these named symbols, x or y, values that we care about. Numbers or letters or words or colors or anything, ultimately. But in programming you'll see that it's much more conventional not to just use simple letters like x and y and z, but to actually give variables full singular or plural words to describe what they are. Then lastly, if this isn't enough color blocks for you, you can create your own blocks. Indeed, this is going to be a programming principle we'll apply today

57:29 and with the first problem set whereby once you start to assemble these puzzle pieces and you realize, oh, would have been nice if those several pieces could have just been replaced by one had MIT thought to give me that one puzzle piece, you yourself can make your own blocks by connecting these all together, giving them a name, and boom, a new puzzle piece will exist. So let's do the simplest, most canonical programs here, starting up with control, and I'm going to click and drag and drop this thing here when green flag clicked. Then I'm going to grab one more, for instance under Looks, and under Looks I'm going to go ahead and just say something like initially not just Hello but the more canonical Hello comma world. Now you might guess that in this programming environment, I can go over here now and click the green flag and voila, Hello comma world. So that's my first program and obviously much

58:19 more user friendly than typing out the much more cryptic text that we saw on the screen that you, too, will type out next week. But for now, we'll just focus on these ideas, in this case, a function. So what it is that just happened? This purple block here is Say, that's the function, and it seems to take some form of input in the white oval, specifically Hello comma world. Well this actually fits the paradigm that we looked at earlier of just inputs and outputs.

…