1 00:00:00,000 --> 00:00:00,479 2 00:00:00,479 --> 00:00:10,830 >> [MUSIC PLAYING] 3 00:00:10,830 --> 00:00:12,080 [MUSIC - ROSSINI, "RANZ DES VACHES" FROM WILLIAM TELL] 4 00:00:12,080 --> 00:00:24,222 5 00:00:24,222 --> 00:00:25,472 >> [MUSIC - THE ENGLISH BEAT, "MARCH OF THE SWIVEL HEADS"] 6 00:00:25,472 --> 00:02:24,538 7 00:02:24,538 --> 00:02:31,510 >> [APPLAUSE AND CHEERING] 8 00:02:31,510 --> 00:02:33,520 >> DAVID MALAN: So this is CS50. 9 00:02:33,520 --> 00:02:34,730 My name is David Malan. 10 00:02:34,730 --> 00:02:39,250 And 73% of you have no prior experience with computer science, 11 00:02:39,250 --> 00:02:41,300 contrary to what you might think. 12 00:02:41,300 --> 00:02:45,290 So today we thought we would chip away at that lack of familiarity, but also 13 00:02:45,290 --> 00:02:48,970 give you a sense of, for those of you with more comfort, which directions 14 00:02:48,970 --> 00:02:50,550 you can go this semester. 15 00:02:50,550 --> 00:02:51,890 >> So let's start with this. 16 00:02:51,890 --> 00:02:55,490 I really have no idea what's inside of a computer, even though, like you, I 17 00:02:55,490 --> 00:02:56,780 use it every day. 18 00:02:56,780 --> 00:03:00,000 But it's some kind of box, and there's not many inputs into it. 19 00:03:00,000 --> 00:03:01,350 Minimally, there's, what? 20 00:03:01,350 --> 00:03:03,120 Probably a power cord. 21 00:03:03,120 --> 00:03:06,640 >> And indeed with this one ingredient, electricity, we seem to be capable of 22 00:03:06,640 --> 00:03:09,490 doing quite a bit these days. 23 00:03:09,490 --> 00:03:12,130 But at the end of the day, we have to represent the things 24 00:03:12,130 --> 00:03:12,860 that we care about. 25 00:03:12,860 --> 00:03:15,240 We have to represent information in some form. 26 00:03:15,240 --> 00:03:18,365 And you're probably at least vaguely familiar with the idea by binary or 27 00:03:18,365 --> 00:03:21,370 bits somehow or other, computers reduced to zeros and ones. 28 00:03:21,370 --> 00:03:26,320 But can we embrace that and at least put a bit of light to that? 29 00:03:26,320 --> 00:03:28,880 >> So I have these little desk lamps here. 30 00:03:28,880 --> 00:03:30,450 I have an electrical outlet here. 31 00:03:30,450 --> 00:03:33,930 And I'm going to propose that inside of my computer is at least one of 32 00:03:33,930 --> 00:03:37,300 these things, something capable of being switched on or off. 33 00:03:37,300 --> 00:03:40,200 In this case, it's indeed a desk lamp, but at the lower level, it's something 34 00:03:40,200 --> 00:03:41,500 called a transistor. 35 00:03:41,500 --> 00:03:44,730 >> But in our world, it's a desk lamp, so I'm going to go ahead and plug this 36 00:03:44,730 --> 00:03:47,990 into my electricity here. 37 00:03:47,990 --> 00:03:52,970 And I claim that using this simple, simple device, this simple switch, I 38 00:03:52,970 --> 00:03:54,850 can represent information. 39 00:03:54,850 --> 00:03:58,090 For instance, right now, I am representing nothing, right? 40 00:03:58,090 --> 00:04:01,820 I'm representing what I'll call 0 or false, the opposite of something 41 00:04:01,820 --> 00:04:03,130 actually being present. 42 00:04:03,130 --> 00:04:07,050 But if I simply turn this switch, now I've represented a 1. 43 00:04:07,050 --> 00:04:10,720 So using this very simple piece of memory, if you will, I can represent 44 00:04:10,720 --> 00:04:11,450 information. 45 00:04:11,450 --> 00:04:14,350 >> Now unfortunately, my computer can't do all that much. 46 00:04:14,350 --> 00:04:17,430 It can only represent two values in the whole world-- 47 00:04:17,430 --> 00:04:18,620 0 or 1. 48 00:04:18,620 --> 00:04:21,839 But what's an obvious solution, now, if we want to expand our computer's 49 00:04:21,839 --> 00:04:25,120 memory and represent more than just 0 and 1? 50 00:04:25,120 --> 00:04:27,060 >> Well, let's grab another such bit. 51 00:04:27,060 --> 00:04:30,260 Let's grab another switch, another transistor, however you'd like to 52 00:04:30,260 --> 00:04:31,130 think about it. 53 00:04:31,130 --> 00:04:34,170 Let me go ahead and plug this into my computer as well. 54 00:04:34,170 --> 00:04:38,270 And I'm going to claim, now, that by using a bit more electricity and 55 00:04:38,270 --> 00:04:42,290 turning more of these switches on and off, I can represent more such 56 00:04:42,290 --> 00:04:43,020 information. 57 00:04:43,020 --> 00:04:44,660 >> So right now, this is 1. 58 00:04:44,660 --> 00:04:48,120 If I want to now represent 2, I could do this. 59 00:04:48,120 --> 00:04:51,510 But typically, convention, as we'll eventually see, will have me do this. 60 00:04:51,510 --> 00:04:55,260 So this is 0, this is 1. 61 00:04:55,260 --> 00:04:56,720 This would be 2. 62 00:04:56,720 --> 00:04:59,920 And not surprisingly, this would be 3. 63 00:04:59,920 --> 00:05:02,610 >> So in this way, still, can we count up even further? 64 00:05:02,610 --> 00:05:06,500 If I get a third bit, a third switch, what's the highest number I can now 65 00:05:06,500 --> 00:05:09,720 count up to from 0? 66 00:05:09,720 --> 00:05:12,020 So 7 if I'm starting at 0, right? 67 00:05:12,020 --> 00:05:15,980 Because if I turn this light on and actually plug this third and final 68 00:05:15,980 --> 00:05:20,090 light into my electrical socket here, then I have the ability to represent 69 00:05:20,090 --> 00:05:24,930 any of two values here, two values here, two values here-- 70 00:05:24,930 --> 00:05:32,610 and so I can represent 2 times 2 times 2, or eight possible values. 71 00:05:32,610 --> 00:05:36,340 And if I start accounting at 0, so that's 0, 1, 2, 3, 4, 5, 6, 7. 72 00:05:36,340 --> 00:05:37,480 >> So this binary. 73 00:05:37,480 --> 00:05:39,420 It really is as simple as that. 74 00:05:39,420 --> 00:05:41,930 And I'd argue that this is actually quite familiar to most 75 00:05:41,930 --> 00:05:43,180 everyone in this room. 76 00:05:43,180 --> 00:05:45,710 Let me go ahead and open a little text editor here. 77 00:05:45,710 --> 00:05:49,040 >> And you might recall from grade school that we had things like the hundreds 78 00:05:49,040 --> 00:05:51,970 place, the tens place, and the ones place. 79 00:05:51,970 --> 00:05:55,040 And recall that if you had some decimal number, like something random 80 00:05:55,040 --> 00:05:59,470 like 123, you would essentially write that out in the form 81 00:05:59,470 --> 00:06:00,450 of these three columns. 82 00:06:00,450 --> 00:06:04,070 And why is 1, 2, 3 what we know as 123? 83 00:06:04,070 --> 00:06:11,220 Well, in the leftmost column, we have one 100 plus two 10s, so that's 120, 84 00:06:11,220 --> 00:06:14,250 plus three 1s, so that's 123. 85 00:06:14,250 --> 00:06:17,990 >> Now this world that we just illuminated is exactly the same as 86 00:06:17,990 --> 00:06:21,150 you've been familiar with for years, except now, our columns 87 00:06:21,150 --> 00:06:22,060 aren't powers of 10. 88 00:06:22,060 --> 00:06:23,780 They're just powers of 2. 89 00:06:23,780 --> 00:06:27,830 So whereas that's the ones place, this is going to be the twos place, this is 90 00:06:27,830 --> 00:06:29,540 going to be the fours place. 91 00:06:29,540 --> 00:06:33,260 >> And because I am only using the simplest of mechanisms to turn things 92 00:06:33,260 --> 00:06:37,100 on and off-- electricity is flowing or electricity is not flowing-- 93 00:06:37,100 --> 00:06:40,880 I don't quite have the same expressive range as 0 through nine. 94 00:06:40,880 --> 00:06:43,270 We're going to keep it super simple in this world of computers. 95 00:06:43,270 --> 00:06:45,060 I only have 0 or 1-- 96 00:06:45,060 --> 00:06:47,890 off or on, false or true. 97 00:06:47,890 --> 00:06:52,610 >> And so what I'm representing right now is 1, 1, 1, because each of these 98 00:06:52,610 --> 00:06:54,000 lights is illuminated. 99 00:06:54,000 --> 00:06:59,600 Well, that gives me one 4 plus one 2, so that's 6, plus one 1, and that's 7. 100 00:06:59,600 --> 00:07:03,450 And ergo does this sequence of three bits represent the number 7. 101 00:07:03,450 --> 00:07:06,330 >> So all this time, inside of your computer, have been any number of 102 00:07:06,330 --> 00:07:08,090 transistors, any number of bits. 103 00:07:08,090 --> 00:07:10,380 But at the end of the day, we can represent information 104 00:07:10,380 --> 00:07:12,560 as simply as that. 105 00:07:12,560 --> 00:07:16,770 Now unfortunately, we've only counted up to 7 in CS50 thus far, but 106 00:07:16,770 --> 00:07:18,550 hopefully we can do a bit better than that. 107 00:07:18,550 --> 00:07:19,550 And indeed we can. 108 00:07:19,550 --> 00:07:23,570 >> Suppose that we as humans just arbitrarily decided that we are going 109 00:07:23,570 --> 00:07:28,750 to associate numbers like 1 and 2, 3, 4, 5, 6, 7, with specific letters of 110 00:07:28,750 --> 00:07:29,410 the alphabet. 111 00:07:29,410 --> 00:07:32,350 And for historical reasons, I'm going to start somewhat arbitrarily, but I'm 112 00:07:32,350 --> 00:07:36,880 going to say, humans, we are going to decide as a standard, globally, that 113 00:07:36,880 --> 00:07:43,200 65 represents the number the letter A. 66 will represent B. Dot, dot, dot. 114 00:07:43,200 --> 00:07:45,140 90 will represent the letter Z. 115 00:07:45,140 --> 00:07:48,000 >> And let's suppose, if we really put some thought into it, we could come up 116 00:07:48,000 --> 00:07:50,860 with numbers for exclamation points and lowercase letters, and indeed, 117 00:07:50,860 --> 00:07:52,710 other people have done that for us. 118 00:07:52,710 --> 00:07:56,410 So now we had bits with which we can represent numbers, numbers with which 119 00:07:56,410 --> 00:08:00,130 we can represent letters, and with letters can we now start composing 120 00:08:00,130 --> 00:08:02,650 emails and printing characters on the screen. 121 00:08:02,650 --> 00:08:05,850 >> So let me invite, if I could, eight brave volunteers-- 122 00:08:05,850 --> 00:08:09,200 who don't mind appearing not only on camera but on the internet-- 123 00:08:09,200 --> 00:08:13,130 to come up here and represent eight such bits, rather than these three. 124 00:08:13,130 --> 00:08:14,380 So how about one, two? 125 00:08:14,380 --> 00:08:16,290 How about three? 126 00:08:16,290 --> 00:08:20,230 How about four in light blue, five on the end? 127 00:08:20,230 --> 00:08:21,250 About someone over here? 128 00:08:21,250 --> 00:08:25,320 Six in front, seven in front, and eight in front, as well. 129 00:08:25,320 --> 00:08:29,050 >> So I just so happened to come prepared with a whole bunch of slips of paper. 130 00:08:29,050 --> 00:08:34,150 And on these pieces of paper are numbers that represent what columns 131 00:08:34,150 --> 00:08:35,809 you guys are going to represent. 132 00:08:35,809 --> 00:08:36,740 So you will be-- what's your name? 133 00:08:36,740 --> 00:08:37,570 >> STUDENT: Anna Leah. 134 00:08:37,570 --> 00:08:40,370 >> DAVID MALAN: Anna Leah, you will be the 128s column. 135 00:08:40,370 --> 00:08:41,059 You are? 136 00:08:41,059 --> 00:08:41,510 >> STUDENT: Chris. 137 00:08:41,510 --> 00:08:43,620 >> DAVID MALAN: Chris will be the 64s column. 138 00:08:43,620 --> 00:08:44,070 You are? 139 00:08:44,070 --> 00:08:44,540 >> STUDENT: Dan. 140 00:08:44,540 --> 00:08:46,970 >> DAVID MALAN: Dan will be the 32s column. 141 00:08:46,970 --> 00:08:47,470 >> STUDENT: Pramit. 142 00:08:47,470 --> 00:08:49,430 >> DAVID MALAN: Pramit will be the 16s column. 143 00:08:49,430 --> 00:08:50,290 >> STUDENT: Lillian. 144 00:08:50,290 --> 00:08:51,904 >> DAVID MALAN: Lillian will be the 8s. 145 00:08:51,904 --> 00:08:52,768 >> STUDENT: Jill. 146 00:08:52,768 --> 00:08:55,025 >> DAVID MALAN: Jill will be the 4s column. 147 00:08:55,025 --> 00:08:55,400 >> STUDENT: Mary. 148 00:08:55,400 --> 00:08:57,000 >> DAVID MALAN: Mary will be the 2s, and? 149 00:08:57,000 --> 00:08:57,470 >> STUDENT: David. 150 00:08:57,470 --> 00:08:59,220 >> DAVID MALAN: David will be the 1s column. 151 00:08:59,220 --> 00:09:02,030 So if you guys could step a little forward so that everyone can see. 152 00:09:02,030 --> 00:09:05,370 What you guys don't see is that on the back of these slips of paper is a 153 00:09:05,370 --> 00:09:09,760 little cheat sheet that's about to instruct these eight bits to either 154 00:09:09,760 --> 00:09:12,380 raise their hand or not raise their hand. 155 00:09:12,380 --> 00:09:14,100 If their hand goes up, they're representing a 1. 156 00:09:14,100 --> 00:09:17,120 If their hand stays down, they're representing a 0. 157 00:09:17,120 --> 00:09:21,410 >> Meanwhile, we the audience should be able to figure out, based on this 158 00:09:21,410 --> 00:09:26,490 mapping, what three-letter word these folks are about to spell out. 159 00:09:26,490 --> 00:09:29,700 So in just a moment, you're going to read the first line off the back of 160 00:09:29,700 --> 00:09:32,880 your cheat sheet, and you're either going to raise or not raise your hand. 161 00:09:32,880 --> 00:09:35,710 If you're a 1, you raise, if you're a 0, you stand there 162 00:09:35,710 --> 00:09:38,594 awkwardly, just like that. 163 00:09:38,594 --> 00:09:40,386 Go. 164 00:09:40,386 --> 00:09:43,945 What number, first and foremost, are these guys representing? 165 00:09:43,945 --> 00:09:47,140 166 00:09:47,140 --> 00:09:48,860 >> 66. 167 00:09:48,860 --> 00:09:49,560 66, right? 168 00:09:49,560 --> 00:09:52,400 We have a 1 in the 64s column, a 1 in the 2s column. 169 00:09:52,400 --> 00:09:56,340 That gives me 66, so that appears to be representing B. So 170 00:09:56,340 --> 00:09:57,075 you guys have spelled-- 171 00:09:57,075 --> 00:09:58,300 OK, that's enough. 172 00:09:58,300 --> 00:09:59,430 B. 173 00:09:59,430 --> 00:10:01,610 >> So now let's move onto our second letter. 174 00:10:01,610 --> 00:10:03,530 Go. 175 00:10:03,530 --> 00:10:06,860 Who's quickest at math here? 176 00:10:06,860 --> 00:10:07,750 So 79. 177 00:10:07,750 --> 00:10:11,840 Again, if we add up all of the columns in which there's a 1, currently, just 178 00:10:11,840 --> 00:10:14,840 like we did before with the simplest of examples of 7, we now 179 00:10:14,840 --> 00:10:16,140 get the number 79. 180 00:10:16,140 --> 00:10:19,910 Which according to our mapping is the letter O. So we're almost there. 181 00:10:19,910 --> 00:10:22,590 B, O. And lastly, go. 182 00:10:22,590 --> 00:10:26,420 183 00:10:26,420 --> 00:10:30,120 >> What are they representing now? 184 00:10:30,120 --> 00:10:31,370 Less consensus. 185 00:10:31,370 --> 00:10:34,660 186 00:10:34,660 --> 00:10:36,460 That's just an absolute murmur. 187 00:10:36,460 --> 00:10:40,090 Yes, it's in fact 87. 188 00:10:40,090 --> 00:10:40,490 Good. 189 00:10:40,490 --> 00:10:44,480 >> So if we now map that back up to-- let's start calling our ASCII chart, 190 00:10:44,480 --> 00:10:46,450 American Standard Code for Information Interchange. 191 00:10:46,450 --> 00:10:47,700 That gives us the letter-- 192 00:10:47,700 --> 00:10:51,260 193 00:10:51,260 --> 00:10:54,810 not "bo" but "bow." And that's a perfect cue for you guys to take a bow 194 00:10:54,810 --> 00:10:56,100 and head on back. 195 00:10:56,100 --> 00:10:56,980 Thank you very much. 196 00:10:56,980 --> 00:10:57,886 >> [APPLAUSE] 197 00:10:57,886 --> 00:10:59,136 >> DAVID MALAN: You can keep them. 198 00:10:59,136 --> 00:11:01,850 199 00:11:01,850 --> 00:11:05,942 Though actually, would anyone like a desk lamp, also? 200 00:11:05,942 --> 00:11:07,300 >> [HOOT FROM AUDIENCE] 201 00:11:07,300 --> 00:11:08,390 >> DAVID MALAN: Desk lamp? 202 00:11:08,390 --> 00:11:10,850 >> [LAUGHTER] 203 00:11:10,850 --> 00:11:11,860 >> DAVID MALAN: Really? 204 00:11:11,860 --> 00:11:13,230 Desk lamps for everyone? 205 00:11:13,230 --> 00:11:14,310 All right. 206 00:11:14,310 --> 00:11:20,990 So starting with the very simplest of principles, we've now not only counted 207 00:11:20,990 --> 00:11:24,750 up from 0 all the way up to 7, we've assumed that just by throwing more 208 00:11:24,750 --> 00:11:28,080 bits or more lights or more transistors at this problem, we can 209 00:11:28,080 --> 00:11:32,680 represent bigger and bigger numbers, and ergo, bigger and bigger ranges of 210 00:11:32,680 --> 00:11:33,780 alphabets, like English. 211 00:11:33,780 --> 00:11:37,770 And just let's take on faith for today that similarly could we start to 212 00:11:37,770 --> 00:11:42,220 represent graphics and video and any number of other media with which we're 213 00:11:42,220 --> 00:11:43,610 familiar today. 214 00:11:43,610 --> 00:11:49,240 >> So this is CS50, and in this class alongside of you are, again, very many 215 00:11:49,240 --> 00:11:53,050 classmates who have as little experience as you. 216 00:11:53,050 --> 00:11:57,730 And I mention this only because quite often, including as recently as one of 217 00:11:57,730 --> 00:12:01,860 the freshman advising events and at last spring's sophomore advising 218 00:12:01,860 --> 00:12:06,420 event, we often hear students disclaim when coming up to the CS table, well, 219 00:12:06,420 --> 00:12:10,070 I've been thinking about taking this intro class, but I'm not really a 220 00:12:10,070 --> 00:12:11,120 computer person. 221 00:12:11,120 --> 00:12:13,220 Or, but everyone surely knows more than me. 222 00:12:13,220 --> 00:12:17,340 And I put this in the biggest font possible, to convey this message that 223 00:12:17,340 --> 00:12:18,730 that's not in fact the case. 224 00:12:18,730 --> 00:12:21,100 >> And if you're wondering, should I, in fact, be here? 225 00:12:21,100 --> 00:12:25,950 Realize that not only is this course's title Introduction to Computer 226 00:12:25,950 --> 00:12:31,740 Science, it is Introduction to Computer Science I. So there is indeed 227 00:12:31,740 --> 00:12:33,170 a second such introduction. 228 00:12:33,170 --> 00:12:35,390 So you're not, in fact, in the wrong place. 229 00:12:35,390 --> 00:12:39,000 And among the goals I have for today are to assuage any such concerns you 230 00:12:39,000 --> 00:12:42,430 might have, but also to paint a picture of what's in store for 231 00:12:42,430 --> 00:12:45,720 students less and more comfortable alike in this course. 232 00:12:45,720 --> 00:12:49,320 >> But first, a word on one of the handouts you have today, among which 233 00:12:49,320 --> 00:12:50,780 are a number of FAQs. 234 00:12:50,780 --> 00:12:54,290 It's been a vision of ours for some time now to introduce a new grading 235 00:12:54,290 --> 00:12:57,010 option into this course-- namely, SAT/UNSAT. 236 00:12:57,010 --> 00:13:01,930 Philosophically for me, it is much much, much more important that the 237 00:13:01,930 --> 00:13:05,050 students in this class engage with the material, be challenged by the 238 00:13:05,050 --> 00:13:09,800 material, and worry far, far less about the mechanics of actual scores 239 00:13:09,800 --> 00:13:12,590 and letter grades at semester's end, but truly embrace the 240 00:13:12,590 --> 00:13:13,970 course and its material. 241 00:13:13,970 --> 00:13:18,140 And really this feels, more generally, for what's interesting to them, to 242 00:13:18,140 --> 00:13:21,390 feel challenged and rewarded but without fear of failure. 243 00:13:21,390 --> 00:13:25,030 >> And indeed, this too is a recurring theme in this and other introductory 244 00:13:25,030 --> 00:13:28,680 courses in other fields, that you have this trepidation when it comes to 245 00:13:28,680 --> 00:13:31,040 putting one's toes in unfamiliar waters. 246 00:13:31,040 --> 00:13:34,880 I myself, back in 1995, was a freshman. 247 00:13:34,880 --> 00:13:37,990 I was very much focused on being a Gov concentrator here. 248 00:13:37,990 --> 00:13:41,060 And yet I'd always grown up with a bit of an interest in computer science. 249 00:13:41,060 --> 00:13:42,180 I was always curious. 250 00:13:42,180 --> 00:13:47,610 >> But back then, even, I had this fear of even stepping foot in CS50, so much 251 00:13:47,610 --> 00:13:49,420 so that I didn't even shop it freshman year. 252 00:13:49,420 --> 00:13:53,460 And the only reason I put a foot in the door sophomore year was because I 253 00:13:53,460 --> 00:13:55,340 was allowed to take it pass/fail. 254 00:13:55,340 --> 00:13:58,920 But even pass/fail required that I get up the nerve to make an appointment 255 00:13:58,920 --> 00:14:01,970 with Professor Kernehan at the time, bring this big sheet of paper, and ask 256 00:14:01,970 --> 00:14:04,470 him for his signature and his permission to explore 257 00:14:04,470 --> 00:14:05,700 these unfamiliar waters. 258 00:14:05,700 --> 00:14:09,030 >> And it hasn't helped in recent years that when doing this in CS50, when we 259 00:14:09,030 --> 00:14:12,500 used to be pass/fail, similarly would dozens or hundreds of your classmates 260 00:14:12,500 --> 00:14:15,970 have to come up, God forbid, at the front of Sanders with this form, that 261 00:14:15,970 --> 00:14:19,520 in some minds represents an inability, I dare say, to perform 262 00:14:19,520 --> 00:14:20,800 are your peers' level. 263 00:14:20,800 --> 00:14:23,410 Which is ridiculous, but I do think there's that mentality. 264 00:14:23,410 --> 00:14:27,210 And there's never been in this culture of SAT/UNSAT, or pass/fail more 265 00:14:27,210 --> 00:14:30,610 generally, in this course, or really on this campus. 266 00:14:30,610 --> 00:14:32,310 >> So this year we changed that. 267 00:14:32,310 --> 00:14:35,630 I would be ecstatic half of this class or more ended 268 00:14:35,630 --> 00:14:38,700 up taking CS50 SAT/UNSAT. 269 00:14:38,700 --> 00:14:42,130 In a year's time, it would be wonderful if almost everyone is. 270 00:14:42,130 --> 00:14:44,410 Thereafter perhaps we'll work on letter grades at Harvard 271 00:14:44,410 --> 00:14:45,480 College more generally. 272 00:14:45,480 --> 00:14:48,900 But for now, we'll do this within our own sphere, and I would heartily 273 00:14:48,900 --> 00:14:53,400 encourage you to review those FAQs and ask questions as you see fit, so that 274 00:14:53,400 --> 00:14:58,000 hopefully you, unlike me, won't quite have that same fear factor when 275 00:14:58,000 --> 00:15:01,040 exploring what's probably an unfamiliar place. 276 00:15:01,040 --> 00:15:02,786 >> So what is CS50? 277 00:15:02,786 --> 00:15:06,150 It is an introduction to the intellectual enterprises of computer 278 00:15:06,150 --> 00:15:07,700 science and the art of programming. 279 00:15:07,700 --> 00:15:08,770 But what does that really mean? 280 00:15:08,770 --> 00:15:12,510 >> Well, thus far, we talked very briefly about representing information. 281 00:15:12,510 --> 00:15:15,070 But suppose that we actually want to do something with it. 282 00:15:15,070 --> 00:15:17,890 We need to introduce the notion of what we'll call an algorithm. 283 00:15:17,890 --> 00:15:21,540 An algorithm is a procedure, a process, a set of instructions for 284 00:15:21,540 --> 00:15:22,780 doing something. 285 00:15:22,780 --> 00:15:25,620 >> And an algorithm can be something super simple. 286 00:15:25,620 --> 00:15:28,660 For instance, an example with which some of you might be familiar is this 287 00:15:28,660 --> 00:15:29,350 thing here. 288 00:15:29,350 --> 00:15:32,510 So this book here is increasingly dated, but once upon a time, it 289 00:15:32,510 --> 00:15:34,720 contained a whole lot of names and phone numbers. 290 00:15:34,720 --> 00:15:37,710 And indeed, if I wanted to find someone in this phone book-- 291 00:15:37,710 --> 00:15:39,800 say, someone named Mike Smith-- 292 00:15:39,800 --> 00:15:43,810 I could find Mike Smith in any number of fairly straightforward ways. 293 00:15:43,810 --> 00:15:47,700 I could start at the beginning and move on to page 1, not there. 294 00:15:47,700 --> 00:15:49,240 Page 2, not there. 295 00:15:49,240 --> 00:15:49,960 Page 3. 296 00:15:49,960 --> 00:15:53,430 Is that algorithm, is that process, correct? 297 00:15:53,430 --> 00:15:54,620 >> So it is correct, right? 298 00:15:54,620 --> 00:15:58,070 I'm kind of an idiot for doing it in that manner, but eventually I will 299 00:15:58,070 --> 00:16:02,670 find the surname S, and hopefully Mike is in that section, and I will become 300 00:16:02,670 --> 00:16:04,100 done with my algorithm. 301 00:16:04,100 --> 00:16:05,440 But surely it's not intuitive. 302 00:16:05,440 --> 00:16:08,020 Most every reasonable human in this room would not have done that. 303 00:16:08,020 --> 00:16:10,180 What would you have done? 304 00:16:10,180 --> 00:16:11,480 >> You'd have gone straight to the middle, right? 305 00:16:11,480 --> 00:16:12,000 Roughly to the middle. 306 00:16:12,000 --> 00:16:16,310 And you realize, oh, these are the Ms. So Mike Smith, last name being Smith, 307 00:16:16,310 --> 00:16:19,050 is not, clearly, then in the left half of the book. 308 00:16:19,050 --> 00:16:21,040 He must be toward the S's in the right. 309 00:16:21,040 --> 00:16:24,090 And at this point, though most of us don't do this in reality, we can 310 00:16:24,090 --> 00:16:27,125 literally tear this problem in half. 311 00:16:27,125 --> 00:16:27,640 >> [CHEERING AND APPLAUSE] 312 00:16:27,640 --> 00:16:28,950 >> DAVID MALAN: Thank you. 313 00:16:28,950 --> 00:16:30,150 >> [CHEERING AND APPLAUSE] 314 00:16:30,150 --> 00:16:34,660 >> DAVID MALAN: You can literally tear this problem in half, leaving me with, 315 00:16:34,660 --> 00:16:36,120 literally, a problem half as big. 316 00:16:36,120 --> 00:16:39,750 So if this phone book was-- and it probably was-- about 1,000 pages, now 317 00:16:39,750 --> 00:16:40,840 it's only 500. 318 00:16:40,840 --> 00:16:44,710 If I do this again and I realize, oh, damn, I went too far, I'm in the Ts 319 00:16:44,710 --> 00:16:46,480 section, I can similarly-- 320 00:16:46,480 --> 00:16:48,030 figuratively or literally-- 321 00:16:48,030 --> 00:16:50,260 rip the phone book-- it was actually much easier that time. 322 00:16:50,260 --> 00:16:53,610 I can literally rip the phone book in half, leaving me now with 323 00:16:53,610 --> 00:16:55,186 not 1,000, not 500-- 324 00:16:55,186 --> 00:16:56,680 250 pages. 325 00:16:56,680 --> 00:17:00,210 And I can go 125, and half of that, and half of that, and half of that, 326 00:17:00,210 --> 00:17:04,760 until finally I'll be left with just one single page. 327 00:17:04,760 --> 00:17:06,430 >> [LAUGHTER] 328 00:17:06,430 --> 00:17:07,589 >> DAVID MALAN: That's the part I fail on. 329 00:17:07,589 --> 00:17:10,400 One single page on which Mike hopefully is. 330 00:17:10,400 --> 00:17:14,630 Now those different algorithms can be sort of assessed or evaluated in 331 00:17:14,630 --> 00:17:15,270 different ways. 332 00:17:15,270 --> 00:17:17,300 The first one was very linear, right? 333 00:17:17,300 --> 00:17:18,500 Turn page, look for Mike. 334 00:17:18,500 --> 00:17:19,630 Turn page, look for Mike. 335 00:17:19,630 --> 00:17:20,560 It's very linear. 336 00:17:20,560 --> 00:17:23,339 If there's one more page in the phone book, it's probably going to take me 337 00:17:23,339 --> 00:17:27,380 one more second, one more unit of time, however we're computing time. 338 00:17:27,380 --> 00:17:32,470 >> So I might draw like this this line here, whereby as the size of the 339 00:17:32,470 --> 00:17:34,700 problem increases from left to right-- 340 00:17:34,700 --> 00:17:37,480 phone book gets smaller to bigger-- 341 00:17:37,480 --> 00:17:41,080 and time is going to increase on the vertical axis, the bigger 342 00:17:41,080 --> 00:17:42,030 the phone book is. 343 00:17:42,030 --> 00:17:46,180 So n is just a general variable that computer scientists use to represent 344 00:17:46,180 --> 00:17:48,210 some value, some number. 345 00:17:48,210 --> 00:17:50,740 So n is going to increase linearly. 346 00:17:50,740 --> 00:17:53,040 Double the size of the phone book, it's going to take me twice as much 347 00:17:53,040 --> 00:17:54,780 time, most likely, to find Mike. 348 00:17:54,780 --> 00:17:56,390 >> Now I could have been smart about this, right? 349 00:17:56,390 --> 00:17:57,800 I was getting bored quickly. 350 00:17:57,800 --> 00:17:58,910 Could have done this by twos. 351 00:17:58,910 --> 00:18:01,870 So two pages, then four, then six, then eight. 352 00:18:01,870 --> 00:18:05,220 And I could start flying through it a little faster, albeit at minor risk of 353 00:18:05,220 --> 00:18:09,210 overshooting Mike, but that curve isn't going to be all that different. 354 00:18:09,210 --> 00:18:12,550 It's still going to be a straight line, but slightly faster. 355 00:18:12,550 --> 00:18:13,710 >> But what did I do? 356 00:18:13,710 --> 00:18:15,845 I actually did something fundamentally better. 357 00:18:15,845 --> 00:18:21,990 I achieved what we'll call logarithmic time, log of n, whereby this green 358 00:18:21,990 --> 00:18:27,730 line has a much, much, much less straight edge to it. 359 00:18:27,730 --> 00:18:33,050 And rather, it suggests, as it sort of approaches infinity ever so gradually, 360 00:18:33,050 --> 00:18:36,700 that I could actually take a 1,000-page phone book, double its size 361 00:18:36,700 --> 00:18:39,610 next year-- because suppose a lot more people move into town. 362 00:18:39,610 --> 00:18:43,250 >> So now I've got 2,000 pages, but how many more steps is that smarter 363 00:18:43,250 --> 00:18:45,200 algorithm going to take? 364 00:18:45,200 --> 00:18:46,060 Just one. 365 00:18:46,060 --> 00:18:48,060 I mean, that's a powerful thing. 366 00:18:48,060 --> 00:18:51,400 If we go to 4,000 pages next year, that's going to take me 367 00:18:51,400 --> 00:18:53,020 only two more steps. 368 00:18:53,020 --> 00:18:56,500 So you can throw bigger and bigger problems at me, not unlike the web is 369 00:18:56,500 --> 00:18:59,560 throwing bigger and bigger problems every day at Googles and Facebooks of 370 00:18:59,560 --> 00:19:01,590 the world, and it's not such a big deal. 371 00:19:01,590 --> 00:19:05,840 Because I put more thought and care into my algorithm with which to solve 372 00:19:05,840 --> 00:19:07,020 problems efficiently. 373 00:19:07,020 --> 00:19:09,260 >> And indeed, that will be one of the goals of this course. 374 00:19:09,260 --> 00:19:11,230 You will, along the way, learn how to program. 375 00:19:11,230 --> 00:19:13,360 You'll learn how to program in any number of languages. 376 00:19:13,360 --> 00:19:16,670 But at the end of the day, the course is about solving problems and getting 377 00:19:16,670 --> 00:19:20,490 better at solving problems-- and, as in cases like this, solving problems 378 00:19:20,490 --> 00:19:22,030 more efficiently. 379 00:19:22,030 --> 00:19:23,990 >> Now thus far, we've done this fairly intuitively. 380 00:19:23,990 --> 00:19:27,420 Let's introduce something fairly generic called pseudocode. 381 00:19:27,420 --> 00:19:29,150 So we'll eventually get, in this course, to 382 00:19:29,150 --> 00:19:30,570 various programming languages. 383 00:19:30,570 --> 00:19:34,280 But today we'll do it in English-like syntax, where you just kind of say 384 00:19:34,280 --> 00:19:37,330 what you mean, but you're ever so succinct and you don't worry about 385 00:19:37,330 --> 00:19:38,960 grammar and complete sentences. 386 00:19:38,960 --> 00:19:41,600 You just express yourself as concisely as possible. 387 00:19:41,600 --> 00:19:45,400 >> So pseudocode is English-like syntax that represents 388 00:19:45,400 --> 00:19:46,750 a programming language. 389 00:19:46,750 --> 00:19:51,170 And toward that end, let me propose that we now model the process we just 390 00:19:51,170 --> 00:19:54,990 described of counting something a little differently, this time taking a 391 00:19:54,990 --> 00:19:59,040 look at this five-minute video produced by our friends at TED that 392 00:19:59,040 --> 00:20:03,170 defines what pseudocode is, defines what algorithmic thinking is, and even 393 00:20:03,170 --> 00:20:07,030 though the example you're about to see is, in of itself, super simple, it's 394 00:20:07,030 --> 00:20:09,820 going to start to give us the mental model, the vocabulary, with which to 395 00:20:09,820 --> 00:20:14,588 do much, much more complex algorithms quite quickly. 396 00:20:14,588 --> 00:20:15,576 >> [BEGIN VIDEO PLAYBACK] 397 00:20:15,576 --> 00:20:29,920 >> [MUSIC PLAYING] 398 00:20:29,920 --> 00:20:31,100 >> NARRATOR: What's an algorithm? 399 00:20:31,100 --> 00:20:34,730 In computer science, an algorithm is a set of instructions for solving some 400 00:20:34,730 --> 00:20:36,620 problem step by step. 401 00:20:36,620 --> 00:20:39,650 Typically, algorithms are executed by computers, but we humans have 402 00:20:39,650 --> 00:20:41,230 algorithms, as well. 403 00:20:41,230 --> 00:20:43,290 For instance, how would you go about counting the number 404 00:20:43,290 --> 00:20:44,750 of people in a room? 405 00:20:44,750 --> 00:20:47,980 Well, if you're like me, you'd probably point at each person, one at 406 00:20:47,980 --> 00:20:50,120 a time, and count up from 0. 407 00:20:50,120 --> 00:20:52,970 1, 2, 3, 4, and so forth. 408 00:20:52,970 --> 00:20:54,140 >> Well, that's an algorithm. 409 00:20:54,140 --> 00:20:57,600 In fact, let's try to express it a bit more formally in pseudocode-- 410 00:20:57,600 --> 00:21:00,700 English-like syntax that resembles a programming language. 411 00:21:00,700 --> 00:21:02,580 Let N equal 0. 412 00:21:02,580 --> 00:21:06,970 For each person in room, set N equal to N plus 1. 413 00:21:06,970 --> 00:21:08,400 >> How to interpret this pseudocode? 414 00:21:08,400 --> 00:21:12,840 Well, line one declares, so to speak, a variable called N and initializes 415 00:21:12,840 --> 00:21:14,250 its value to 0. 416 00:21:14,250 --> 00:21:17,550 This just means that at the beginning of our algorithm, the thing with which 417 00:21:17,550 --> 00:21:19,650 we're counting has a value of 0. 418 00:21:19,650 --> 00:21:22,620 After all, before we start counting, we haven't counted anything yet. 419 00:21:22,620 --> 00:21:25,340 Calling this variable N is just a convention. 420 00:21:25,340 --> 00:21:26,890 I could have called it most anything. 421 00:21:26,890 --> 00:21:30,560 >> Now line two demarks the start of a loop, a sequence of steps that will 422 00:21:30,560 --> 00:21:32,310 repeat some number of times. 423 00:21:32,310 --> 00:21:35,910 So in our example, the step we're taking is counting people in the room. 424 00:21:35,910 --> 00:21:38,730 Beneath line two is line three, which describes exactly how 425 00:21:38,730 --> 00:21:40,160 we'll go about counting. 426 00:21:40,160 --> 00:21:43,440 The indentation implies that it's line three that will repeat. 427 00:21:43,440 --> 00:21:47,380 >> So what the pseudocode is saying is that after starting at 0, for each 428 00:21:47,380 --> 00:21:50,690 person in the room, we'll increase N by 1. 429 00:21:50,690 --> 00:21:53,050 Now is this algorithm correct? 430 00:21:53,050 --> 00:21:54,580 Well, let's bang on it a bit. 431 00:21:54,580 --> 00:21:57,270 Does it work if there are two people in the room? 432 00:21:57,270 --> 00:21:58,170 Let's see. 433 00:21:58,170 --> 00:22:00,260 >> In line one, we initialize N to 0. 434 00:22:00,260 --> 00:22:03,660 For each of these two people, we then increment N by 1. 435 00:22:03,660 --> 00:22:07,310 So on the first trip through the loop, we update N from 0 to 1. 436 00:22:07,310 --> 00:22:11,070 On the second trip through that same loop, we update N from 1 to 2. 437 00:22:11,070 --> 00:22:15,780 And so by this algorithm's end, n is 2, which indeed matches the number of 438 00:22:15,780 --> 00:22:16,700 people in the room. 439 00:22:16,700 --> 00:22:17,760 >> So far, so good. 440 00:22:17,760 --> 00:22:19,610 How about a corner case, though? 441 00:22:19,610 --> 00:22:22,590 Suppose there are 0 people in the room-- besides me, 442 00:22:22,590 --> 00:22:24,170 who's doing the counting. 443 00:22:24,170 --> 00:22:27,150 In line one, we initialize N to 0. 444 00:22:27,150 --> 00:22:30,280 This time, though, line three doesn't execute at all since there isn't a 445 00:22:30,280 --> 00:22:31,370 person in the room. 446 00:22:31,370 --> 00:22:35,260 And so N remains 0, which matches the number of people in the room. 447 00:22:35,260 --> 00:22:36,420 Pretty simple, right? 448 00:22:36,420 --> 00:22:39,630 >> But counting people one at a time is pretty inefficient, too, no? 449 00:22:39,630 --> 00:22:40,920 Surely we can do better. 450 00:22:40,920 --> 00:22:43,120 Why not count two people at a time? 451 00:22:43,120 --> 00:22:49,300 Instead of counting 1, 2, 3, 4, 5, 6, 7, 8, and so forth, why not count, 2, 452 00:22:49,300 --> 00:22:51,460 4, 6, 8, and so on? 453 00:22:51,460 --> 00:22:53,700 It even sounds faster, and it surely is. 454 00:22:53,700 --> 00:22:56,240 >> Let's express this optimization in pseudocode. 455 00:22:56,240 --> 00:22:57,800 Let N equal 0. 456 00:22:57,800 --> 00:23:02,450 For each pair of people in room, set N equal to N plus 2. 457 00:23:02,450 --> 00:23:04,120 Pretty simple change, right? 458 00:23:04,120 --> 00:23:06,750 Rather than count people one at a time, we instead count 459 00:23:06,750 --> 00:23:08,300 them two at a time. 460 00:23:08,300 --> 00:23:10,980 This algorithm's thus twice as fast as the last. 461 00:23:10,980 --> 00:23:12,180 >> But is it correct? 462 00:23:12,180 --> 00:23:12,920 Let's see. 463 00:23:12,920 --> 00:23:15,330 Does it work if there are two people in the room? 464 00:23:15,330 --> 00:23:17,550 In line one, we initialize N to 0. 465 00:23:17,550 --> 00:23:20,920 For that one pair of people, we then increment N by two. 466 00:23:20,920 --> 00:23:24,860 And so by this algorithm's end, N is 2, which indeed matches the number of 467 00:23:24,860 --> 00:23:25,650 people in the room. 468 00:23:25,650 --> 00:23:28,250 >> Suppose next that there are 0 people in the room. 469 00:23:28,250 --> 00:23:30,840 In line one, we initialize N to 0. 470 00:23:30,840 --> 00:23:34,330 As before, line three doesn't execute at all, since there aren't any pairs 471 00:23:34,330 --> 00:23:35,380 of people in the room. 472 00:23:35,380 --> 00:23:38,350 And so N remains 0, which indeed matches the number of 473 00:23:38,350 --> 00:23:39,570 people in the room. 474 00:23:39,570 --> 00:23:42,280 >> But what if there are three people in the room? 475 00:23:42,280 --> 00:23:44,130 How does this algorithm fare? 476 00:23:44,130 --> 00:23:44,990 Let's see. 477 00:23:44,990 --> 00:23:47,460 In line one, we initialize N to 0. 478 00:23:47,460 --> 00:23:50,870 For a pair of those people, we then increment N by 2. 479 00:23:50,870 --> 00:23:51,800 But then what? 480 00:23:51,800 --> 00:23:54,960 There isn't another full pair of people in the room, so line two no 481 00:23:54,960 --> 00:23:56,180 longer applies. 482 00:23:56,180 --> 00:24:00,530 And so by this algorithm's end, N is still 2, which isn't correct. 483 00:24:00,530 --> 00:24:03,810 >> Indeed, this algorithm's said to be buggy, because it has a mistake. 484 00:24:03,810 --> 00:24:05,820 Lets redress with some new pseudocode. 485 00:24:05,820 --> 00:24:09,670 Let n equal 0 for each pair of people in room. 486 00:24:09,670 --> 00:24:12,550 Set N equal to N plus 2. 487 00:24:12,550 --> 00:24:17,140 If one person remains unpaired, set N equal to N plus 1. 488 00:24:17,140 --> 00:24:20,140 To solve this particular problem, we've introduced, in line four, a 489 00:24:20,140 --> 00:24:24,520 condition, otherwise known as a branch that only executes if there's one 490 00:24:24,520 --> 00:24:26,640 person that we could not pair with another. 491 00:24:26,640 --> 00:24:30,440 And so now, whether there's one or three or any odd number of people in 492 00:24:30,440 --> 00:24:33,290 the room, this algorithm will now count them. 493 00:24:33,290 --> 00:24:34,560 >> Can we do even better? 494 00:24:34,560 --> 00:24:38,820 Well, we could count in 3s or 4s or even 5s and 10s, but beyond that, it's 495 00:24:38,820 --> 00:24:41,360 going to get a little bit difficult to point. 496 00:24:41,360 --> 00:24:44,660 At the end of the day, whether executed by computers or humans, 497 00:24:44,660 --> 00:24:46,750 algorithms are just a set of instructions with 498 00:24:46,750 --> 00:24:48,290 which to solve problems. 499 00:24:48,290 --> 00:24:49,792 These were just three. 500 00:24:49,792 --> 00:24:52,404 What problem would you solve with an algorithm? 501 00:24:52,404 --> 00:24:52,901 >> [END VIDEO PLAYBACK] 502 00:24:52,901 --> 00:24:55,883 >> DAVID MALAN: That is the only time I will appear in cartoon form. 503 00:24:55,883 --> 00:25:01,050 But where that story leaves off, now, is how can we do better? 504 00:25:01,050 --> 00:25:04,680 Threes and fours, we claim, we can count people much faster, but can we 505 00:25:04,680 --> 00:25:06,290 do fundamentally better than that? 506 00:25:06,290 --> 00:25:07,540 And I wager we can. 507 00:25:07,540 --> 00:25:11,980 >> If we introduce a bit of our own pseudocode here, I'm going to propose 508 00:25:11,980 --> 00:25:14,550 that we can achieve a line like this. 509 00:25:14,550 --> 00:25:17,280 We're not going to count people one, two, three, four. 510 00:25:17,280 --> 00:25:19,470 We're not going to go two, four, six, eight. 511 00:25:19,470 --> 00:25:23,390 We're going to do fundamentally better by rethinking the problem, and in this 512 00:25:23,390 --> 00:25:27,080 case, leveraging an otherwise underutilized resource. 513 00:25:27,080 --> 00:25:31,460 >> In just a moment, I hope you'll forgive and humor us by standing up in 514 00:25:31,460 --> 00:25:34,470 place, at which point we're going to ask each of you to take on in your 515 00:25:34,470 --> 00:25:36,400 minds the number 1. 516 00:25:36,400 --> 00:25:39,560 You're then going to increasingly awkwardly, as time passes, find 517 00:25:39,560 --> 00:25:42,740 someone else who is standing, combine your numbers together 518 00:25:42,740 --> 00:25:43,720 by adding them up. 519 00:25:43,720 --> 00:25:47,490 One of you is then going to race to sit down first, and the other person 520 00:25:47,490 --> 00:25:48,880 is going to repeat. 521 00:25:48,880 --> 00:25:53,090 >> So in other words, by seeding all of you with the number 1, and then 522 00:25:53,090 --> 00:25:57,800 combining those 1s into 2s and those 2s into 4s, with everyone increasingly 523 00:25:57,800 --> 00:26:02,740 sitting down, we should, at the end of this algorithm, have just one loan 524 00:26:02,740 --> 00:26:07,570 soul who didn't sit down fast enough but who has the entire audiences count 525 00:26:07,570 --> 00:26:09,180 in his or her mind. 526 00:26:09,180 --> 00:26:13,730 >> So if you would, let's go ahead and-- step one-- stand up in place. 527 00:26:13,730 --> 00:26:15,600 And execute. 528 00:26:15,600 --> 00:26:36,580 >> [CROWD MURMURING] 529 00:26:36,580 --> 00:26:38,820 >> DAVID MALAN: Do you know where Lauren is? 530 00:26:38,820 --> 00:26:40,179 729? 531 00:26:40,179 --> 00:27:23,350 >> [CROWD MURMURING] 532 00:27:23,350 --> 00:27:24,340 >> DAVID MALAN: All right? 533 00:27:24,340 --> 00:27:39,110 >> [CROWD MURMURING] 534 00:27:39,110 --> 00:27:41,365 >> DAVID MALAN: All right, we should be nearing the end. 535 00:27:41,365 --> 00:27:44,340 536 00:27:44,340 --> 00:27:47,670 We see one fellow standing here still. 537 00:27:47,670 --> 00:27:48,770 Who else needs to be paired? 538 00:27:48,770 --> 00:27:50,020 If you guys want to pair off. 539 00:27:50,020 --> 00:27:53,260 540 00:27:53,260 --> 00:27:56,520 Someone up top. 541 00:27:56,520 --> 00:27:58,150 Why don't I lend a hand here. 542 00:27:58,150 --> 00:28:01,370 For the very few people who are still standing, what numbers do you 543 00:28:01,370 --> 00:28:02,790 have in your mind? 544 00:28:02,790 --> 00:28:04,020 >> STUDENT: 78. 545 00:28:04,020 --> 00:28:06,010 >> DAVID MALAN: 78 plus-- 546 00:28:06,010 --> 00:28:07,840 who's standing down here? 547 00:28:07,840 --> 00:28:08,370 >> STUDENT: 39. 548 00:28:08,370 --> 00:28:09,590 >> DAVID MALAN: Plus 39. 549 00:28:09,590 --> 00:28:12,310 Plus who else is still standing? 550 00:28:12,310 --> 00:28:13,650 81? 551 00:28:13,650 --> 00:28:15,960 OK, who else? 552 00:28:15,960 --> 00:28:17,200 Another 81? 553 00:28:17,200 --> 00:28:17,860 Wow. 554 00:28:17,860 --> 00:28:19,210 And then what's in back? 555 00:28:19,210 --> 00:28:20,360 >> STUDENT: 49. 556 00:28:20,360 --> 00:28:21,812 >> DAVID MALAN: 49, plus? 557 00:28:21,812 --> 00:28:22,950 >> STUDENT: 98. 558 00:28:22,950 --> 00:28:24,980 >> DAVID MALAN: 98 plus? 559 00:28:24,980 --> 00:28:28,190 Is that someone else? 560 00:28:28,190 --> 00:28:29,155 12? 561 00:28:29,155 --> 00:28:30,460 Good job. 562 00:28:30,460 --> 00:28:33,610 >> [LAUGHTER] 563 00:28:33,610 --> 00:28:34,690 >> DAVID MALAN: Oh, 112-- 564 00:28:34,690 --> 00:28:35,410 oh. 565 00:28:35,410 --> 00:28:36,220 Good job! 566 00:28:36,220 --> 00:28:38,660 >> [LAUGHTER] 567 00:28:38,660 --> 00:28:42,570 >> [APPLAUSE] 568 00:28:42,570 --> 00:28:43,820 >> DAVID MALAN: Anyone else still standing? 569 00:28:43,820 --> 00:28:46,710 570 00:28:46,710 --> 00:28:47,260 Sorry? 571 00:28:47,260 --> 00:28:48,110 >> STUDENT: 99. 572 00:28:48,110 --> 00:28:49,810 >> DAVID MALAN: 99. 573 00:28:49,810 --> 00:28:52,620 Anyone else still standing? 574 00:28:52,620 --> 00:28:57,290 And the total number of students here is actually, according to-- 575 00:28:57,290 --> 00:28:59,400 do you have a number? 576 00:28:59,400 --> 00:29:03,170 Oh, the actual number of people in the room, according to the account that 577 00:29:03,170 --> 00:29:07,660 the teaching fellows were doing on everyone's way in, was 729. 578 00:29:07,660 --> 00:29:11,070 So out of a roomful of Harvard students who counted themselves, the 579 00:29:11,070 --> 00:29:14,126 answer is 637. 580 00:29:14,126 --> 00:29:15,480 >> [LAUGHTER] 581 00:29:15,480 --> 00:29:16,350 >> DAVID MALAN: So close. 582 00:29:16,350 --> 00:29:17,360 But still. 583 00:29:17,360 --> 00:29:22,110 OK, so that's a teaching moment, right? 584 00:29:22,110 --> 00:29:24,120 This now is what we describe as a bug. 585 00:29:24,120 --> 00:29:28,120 Somewhere along the way, we did some arithmetic wrong, or someone sat down, 586 00:29:28,120 --> 00:29:29,930 or left, or something went wrong. 587 00:29:29,930 --> 00:29:30,930 But that's fine. 588 00:29:30,930 --> 00:29:33,390 Because even still, we got pretty close. 589 00:29:33,390 --> 00:29:37,480 And I'd argue that we got to the wrong answer a lot faster than I would have 590 00:29:37,480 --> 00:29:39,770 using my more linear approach. 591 00:29:39,770 --> 00:29:42,630 >> So let's assume we did in fact get that correct, but think now about what 592 00:29:42,630 --> 00:29:46,870 was happening each time, versus my own naive pointing algorithm. 593 00:29:46,870 --> 00:29:48,420 One, two, three. 594 00:29:48,420 --> 00:29:53,010 If there are indeed 729 or 637 people here, that would have taken me 595 00:29:53,010 --> 00:29:57,720 literally 637 or 729 pointings of the finger and 596 00:29:57,720 --> 00:29:59,490 incrementing my total count. 597 00:29:59,490 --> 00:30:01,910 And I could do a little better by going two, four, six, eight, and 598 00:30:01,910 --> 00:30:05,660 double that speed, maybe even triple or quadruple, depending how well I can 599 00:30:05,660 --> 00:30:07,110 do that counting in my head. 600 00:30:07,110 --> 00:30:10,720 >> But this approach that you guys took was fundamentally different. 601 00:30:10,720 --> 00:30:12,770 Because at the beginning, all of you stood up. 602 00:30:12,770 --> 00:30:14,620 So all 729. 603 00:30:14,620 --> 00:30:17,370 And then literally half of you sat down. 604 00:30:17,370 --> 00:30:19,720 And after that, another half of you sat down. 605 00:30:19,720 --> 00:30:22,650 And after that, another half of you sat down. 606 00:30:22,650 --> 00:30:27,470 >> And the total number of times that you guys could have sat down is roughly 607 00:30:27,470 --> 00:30:31,740 eight or nine or ten total times, depending on what our total count is. 608 00:30:31,740 --> 00:30:33,300 And we can sort of do this the other way. 609 00:30:33,300 --> 00:30:37,740 If we had 1,024 people in the room, the total number of times you could 610 00:30:37,740 --> 00:30:41,870 halve 1,024 people is 10. 611 00:30:41,870 --> 00:30:43,370 >> Now think about it in the other direction. 612 00:30:43,370 --> 00:30:49,170 Suppose, ridiculously, that we had, say four billion people in this room, 613 00:30:49,170 --> 00:30:50,860 or a slightly larger room. 614 00:30:50,860 --> 00:30:54,550 How many times would we have gone through this algorithm, such that half 615 00:30:54,550 --> 00:30:58,110 of that class sits down? 616 00:30:58,110 --> 00:31:03,050 It's only going to take 32 such operations, even in a class of size 617 00:31:03,050 --> 00:31:03,770 four billion. 618 00:31:03,770 --> 00:31:04,055 Why? 619 00:31:04,055 --> 00:31:06,980 Because four billion goes to two billion, goes to one million, goes to 620 00:31:06,980 --> 00:31:09,925 500 million, goes to 250 million, dot, dot, dot. 621 00:31:09,925 --> 00:31:14,940 I can only do that division some 32 times, at which point, everyone except 622 00:31:14,940 --> 00:31:17,820 one person would be left standing. 623 00:31:17,820 --> 00:31:21,590 >> And that, too, is sort of a powerful idea that increasingly we'll try to 624 00:31:21,590 --> 00:31:24,690 leverage in this course, and in programming and computer science more 625 00:31:24,690 --> 00:31:29,400 generally, these germs of an idea with which we can then solve problems much, 626 00:31:29,400 --> 00:31:31,130 much more powerfully. 627 00:31:31,130 --> 00:31:34,610 So we started quite simple with that pseudocode and a guy in a room, but 628 00:31:34,610 --> 00:31:38,205 now with a whole room full of people have we done fundamentally better. 629 00:31:38,205 --> 00:31:41,460 >> Well, let's now transition from pseudocode to some actual code. 630 00:31:41,460 --> 00:31:44,200 This language you're about to see happen to be called JavaScript, and 631 00:31:44,200 --> 00:31:46,190 we'll return to this toward semester's end. 632 00:31:46,190 --> 00:31:49,960 It's a programming language that you use to make websites and other such 633 00:31:49,960 --> 00:31:51,360 software these days. 634 00:31:51,360 --> 00:31:54,890 And we have used it, thanks to a friend of ours at Stanford, to encode 635 00:31:54,890 --> 00:31:56,630 some hidden information here. 636 00:31:56,630 --> 00:31:59,500 This is the art of steganography, so to speak, where you can hide 637 00:31:59,500 --> 00:32:03,990 information in what otherwise appears to be noise or a completely different 638 00:32:03,990 --> 00:32:05,220 image altogether. 639 00:32:05,220 --> 00:32:10,120 But embedded in this particular image is indeed a secret message of sorts. 640 00:32:10,120 --> 00:32:12,950 >> So let me go ahead and pull up the same image here, this 641 00:32:12,950 --> 00:32:14,270 time in a web browser. 642 00:32:14,270 --> 00:32:17,710 And I'm going to wave my hand at some of the details for today, particularly 643 00:32:17,710 --> 00:32:21,780 for those of you who this looks like not only JavaScript but Greek, as a 644 00:32:21,780 --> 00:32:23,930 completely unfamiliar language. 645 00:32:23,930 --> 00:32:26,190 But this is an example of a programming language. 646 00:32:26,190 --> 00:32:30,660 >> And for now, take on faith that this first line of code-- 647 00:32:30,660 --> 00:32:32,470 and by code, I just mean text. 648 00:32:32,470 --> 00:32:35,660 Text that I could have literally typed into Microsoft Word, if I had the 649 00:32:35,660 --> 00:32:37,630 right software to then do something with it. 650 00:32:37,630 --> 00:32:42,120 Programming source code, programming code, is really just text, and it 651 00:32:42,120 --> 00:32:45,420 looks different based on what language you're using, not unlike English and 652 00:32:45,420 --> 00:32:49,200 Spanish and Russian all look different when you type them at your keyboard. 653 00:32:49,200 --> 00:32:53,520 >> So this first line, for now take on faith, simply opens a graphic from the 654 00:32:53,520 --> 00:32:56,160 internet, that noisy graphic we just saw. 655 00:32:56,160 --> 00:32:59,900 This next line here is an example of a loop, and we actually saw that same 656 00:32:59,900 --> 00:33:01,130 jargon in the TED video. 657 00:33:01,130 --> 00:33:03,750 A loop is something that happens again and again, and even though this 658 00:33:03,750 --> 00:33:08,440 absolutely looks cryptic, with the keyword for, and some parentheses, and 659 00:33:08,440 --> 00:33:09,510 some semicolons. 660 00:33:09,510 --> 00:33:13,070 We'll come back to that before long, but that loop there essentially is 661 00:33:13,070 --> 00:33:17,310 telling the program, iterate over all of those noisy dots, from left to 662 00:33:17,310 --> 00:33:18,980 right, top to bottom. 663 00:33:18,980 --> 00:33:21,260 >> Because at the end of the day, an image like this-- and you can actually 664 00:33:21,260 --> 00:33:22,860 kind of see it on this projector-- 665 00:33:22,860 --> 00:33:25,280 is really just a grid of dots. 666 00:33:25,280 --> 00:33:29,730 So we can identify each of those dots by a coordinate, x, y, and with this 667 00:33:29,730 --> 00:33:33,890 program, now can we begin to do something to those dots. 668 00:33:33,890 --> 00:33:37,540 >> So what I'm going to go ahead here and do is I'm going to make some changes. 669 00:33:37,540 --> 00:33:41,000 First I'm going to go ahead and get rid of all of that greenish and bluish 670 00:33:41,000 --> 00:33:43,520 noise, and I'm going to go ahead and type the following 671 00:33:43,520 --> 00:33:45,710 admittedly cryptic syntax. 672 00:33:45,710 --> 00:33:48,020 im for image. 673 00:33:48,020 --> 00:33:53,380 set blue at location x, comma, location y, to 0. 674 00:33:53,380 --> 00:33:55,610 In other words, I want to just turn off all of the blue 675 00:33:55,610 --> 00:33:56,920 dots in that picture. 676 00:33:56,920 --> 00:33:59,800 >> I'm going to go ahead now and click this Run/Save button, and you'll 677 00:33:59,800 --> 00:34:02,850 notice on the right-hand side, the resulting image appears. 678 00:34:02,850 --> 00:34:06,120 Now its super green, but that's not surprising, because I literally turned 679 00:34:06,120 --> 00:34:11,070 off, by making a 1 a 0, all of the blue in that picture. 680 00:34:11,070 --> 00:34:12,540 >> Well, now let's do it a bit more. 681 00:34:12,540 --> 00:34:16,989 im for image, dot setGreen, x, y. 682 00:34:16,989 --> 00:34:20,659 And that just means iterate from left to right and then top to bottom. 683 00:34:20,659 --> 00:34:23,520 Turn that off with a value of 0, as well. 684 00:34:23,520 --> 00:34:24,750 Save. 685 00:34:24,750 --> 00:34:28,100 And on the projector, you can't actually really see anything at all. 686 00:34:28,100 --> 00:34:31,380 >> On my laptop screen, if I peer in just the right way, I can see a bit of an 687 00:34:31,380 --> 00:34:33,300 image, because they're still some red in there. 688 00:34:33,300 --> 00:34:35,540 If you've ever heard the acronym RGB-- 689 00:34:35,540 --> 00:34:36,830 red, green, blue-- 690 00:34:36,830 --> 00:34:39,110 it's referring to this composition of an image using 691 00:34:39,110 --> 00:34:40,230 just those three colors. 692 00:34:40,230 --> 00:34:43,159 And right now, we've thrown away all green, all blue, but 693 00:34:43,159 --> 00:34:44,500 there's not much red. 694 00:34:44,500 --> 00:34:45,920 >> So let me crank up the red. 695 00:34:45,920 --> 00:34:47,070 How can I do that? 696 00:34:47,070 --> 00:34:49,300 Well, first, I'm going to ask this program a question. 697 00:34:49,300 --> 00:34:52,030 I'm going to go ahead and let's call it a variable, just like in algebra. 698 00:34:52,030 --> 00:34:54,060 You can have x or y or z. 699 00:34:54,060 --> 00:34:57,230 I'm going to declare a variable and say, put in this variable, 700 00:34:57,230 --> 00:35:02,790 temporarily, the value of the images getRed value at x, y. 701 00:35:02,790 --> 00:35:05,870 >> And again, we'll come back to all of this detail in the future. 702 00:35:05,870 --> 00:35:10,630 But for now, just take on faith that this line is asking the program, what 703 00:35:10,630 --> 00:35:12,740 is the red value at x, y? 704 00:35:12,740 --> 00:35:14,450 At that particular dot? 705 00:35:14,450 --> 00:35:15,710 >> Then I'm going to do something to it. 706 00:35:15,710 --> 00:35:21,100 Then I'm going to do image dot set red at x, y, y but this time I'm going to 707 00:35:21,100 --> 00:35:24,760 boost it by doing red times, let's say, 10. 708 00:35:24,760 --> 00:35:26,870 So increase it by a factor of 10. 709 00:35:26,870 --> 00:35:29,880 Let me zoom out now and click could Run/Save. 710 00:35:29,880 --> 00:35:36,430 And voila, that was there the entire time, even though our human eyes 711 00:35:36,430 --> 00:35:37,900 couldn't quite see it. 712 00:35:37,900 --> 00:35:41,470 >> So again, this now is real code, an example of a language that we'll come 713 00:35:41,470 --> 00:35:42,770 back to before long. 714 00:35:42,770 --> 00:35:46,670 But realize, particularly those of you with no such experience, it's quite 715 00:35:46,670 --> 00:35:50,280 soon that we ourselves will be writing code like that there. 716 00:35:50,280 --> 00:35:54,520 In fact, a tool with which you're all somewhat familiar, perhaps, is CS50's 717 00:35:54,520 --> 00:35:57,330 own course-shopping tool, which was actually rebooted this summer by some 718 00:35:57,330 --> 00:36:01,070 of CS50's own former students, now turn TFs. 719 00:36:01,070 --> 00:36:04,740 >> So this happens to be a website built in a language called PHP. 720 00:36:04,740 --> 00:36:08,510 It uses a database called MySQL, things with which we'll get our hands 721 00:36:08,510 --> 00:36:10,190 dirty later in the semester. 722 00:36:10,190 --> 00:36:14,140 But believe it or not, even something like this ultimately reduces to the 723 00:36:14,140 --> 00:36:19,480 simplest of loops and conditions and branches, like those we saw just a 724 00:36:19,480 --> 00:36:21,530 moment ago in the TED video. 725 00:36:21,530 --> 00:36:25,180 >> What I thought I'd do now is share not just something we the staff have made 726 00:36:25,180 --> 00:36:28,010 for the campus, but rather something a former student-- three 727 00:36:28,010 --> 00:36:29,080 students, in fact-- 728 00:36:29,080 --> 00:36:33,950 made this past year, Sierra, Daniel, and Sam, the last of whom had no prior 729 00:36:33,950 --> 00:36:36,370 programing experience when he took CS50. 730 00:36:36,370 --> 00:36:39,950 And for their final project, they exhibited, at the CS50 Fair, an 731 00:36:39,950 --> 00:36:43,720 application called wrdly, which is a web-based program for which they made 732 00:36:43,720 --> 00:36:47,670 this video that I thought I'd share to give you a sense of just what is 733 00:36:47,670 --> 00:36:49,280 possible by term's end. 734 00:36:49,280 --> 00:37:57,170 >> [MUSIC PLAYING] 735 00:37:57,170 --> 00:38:00,570 >> DAVID MALAN: That's from Week Zero to Week 12 this past year. 736 00:38:00,570 --> 00:38:05,470 >> [APPLAUSE] 737 00:38:05,470 --> 00:38:09,520 >> DAVID MALAN: As a teaser, too, really to whet your appetite is to what's 738 00:38:09,520 --> 00:38:14,580 possible, you may have seen already, or may soon see, market.cs50.net, a 739 00:38:14,580 --> 00:38:17,710 new tool that the course's team has been working on, this time in 740 00:38:17,710 --> 00:38:21,530 collaboration with Harvard Student Agencies, such that starting this year 741 00:38:21,530 --> 00:38:24,980 and continuing hopefully into this coming summer you'll have a standard 742 00:38:24,980 --> 00:38:27,890 opportunity on campus to buy and sell things of interest to you. 743 00:38:27,890 --> 00:38:32,220 And with partnership through HSA, you'll also be able to drop items off 744 00:38:32,220 --> 00:38:35,950 in one of HSA's physical stores at some point in the future, so as to 745 00:38:35,950 --> 00:38:39,150 proxy things, particularly as you graduate and don't necessarily want to 746 00:38:39,150 --> 00:38:44,110 discard things, but actually pay it forward to folks who might follow you 747 00:38:44,110 --> 00:38:45,270 here on campus. 748 00:38:45,270 --> 00:38:46,740 So more on that to come. 749 00:38:46,740 --> 00:38:49,830 >> But a little more concretely, a tool that's come out of CS50 in recent 750 00:38:49,830 --> 00:38:52,760 years, with which some of you might be familiar and others of you might be 751 00:38:52,760 --> 00:38:57,940 googling now, at CS50.net/2x, you'll find a link to a Chrome extension 752 00:38:57,940 --> 00:39:01,250 which is demonstrative of how you can use JavaScript, that same language we 753 00:39:01,250 --> 00:39:06,660 used with the Eiffel tower a moment ago, to implement 2x playback speed 754 00:39:06,660 --> 00:39:09,000 for all Harvard iSites videos. 755 00:39:09,000 --> 00:39:11,880 This is something that's built into CS50's own video player. 756 00:39:11,880 --> 00:39:14,870 But this, too, if you begin to dig into the source code, which we'll 757 00:39:14,870 --> 00:39:18,840 happily make available, you'll see how you can even solve problems like that, 758 00:39:18,840 --> 00:39:23,180 accelerating widgets in websites with which you're already well familiar. 759 00:39:23,180 --> 00:39:26,630 >> So a word now on the course and expectations and what lies ahead. 760 00:39:26,630 --> 00:39:29,445 In general, we'll indeed gather here on Mondays and Wednesdays-- though 761 00:39:29,445 --> 00:39:31,490 this Friday, we'll gather because of Shopping Week-- 762 00:39:31,490 --> 00:39:34,640 1:00 to 2:00 PM, though sometimes until 2:30. 763 00:39:34,640 --> 00:39:38,700 Given that you might therefore want or have to take some class at 2:00 PM 764 00:39:38,700 --> 00:39:42,480 onward, or even before, do realize the course is supportive of what's called 765 00:39:42,480 --> 00:39:45,900 simultaneous enrollment, whereby we'll support a petition to the Ad Board and 766 00:39:45,900 --> 00:39:49,400 your resident deans on your behalf if you have a conflict somewhere in this 767 00:39:49,400 --> 00:39:50,790 1:00 to 2:30 range. 768 00:39:50,790 --> 00:39:54,110 Head to that URL online for additional details. 769 00:39:54,110 --> 00:39:57,750 >> But in terms of the support structure that characterizes CS50, for students 770 00:39:57,750 --> 00:40:01,750 more and less comfortable alike, we offer distinct tracks of sections. 771 00:40:01,750 --> 00:40:04,730 And this is a couple of weeks off, but before long, you'll be asked as to 772 00:40:04,730 --> 00:40:05,770 your comfort level. 773 00:40:05,770 --> 00:40:08,590 Are you among those less comfortable, more comfortable, or 774 00:40:08,590 --> 00:40:10,520 somewhere in between? 775 00:40:10,520 --> 00:40:13,150 >> And we'll have three distinct tracks that cater to 776 00:40:13,150 --> 00:40:14,470 precisely those audiences. 777 00:40:14,470 --> 00:40:17,900 So at no point in the term should you even feel like you're competing 778 00:40:17,900 --> 00:40:21,390 against any student with more or less background than you. 779 00:40:21,390 --> 00:40:24,160 Indeed, the course is meant to be much more collaborative and much 780 00:40:24,160 --> 00:40:25,650 more open than that. 781 00:40:25,650 --> 00:40:29,030 >> In terms of the problem sets, you'll find, too, that in addition to the 782 00:40:29,030 --> 00:40:32,130 standard edition of each week's problem set, there's often a "hacker 783 00:40:32,130 --> 00:40:37,010 edition" that's meant to be targeted at the 5% to 10% or so of the 784 00:40:37,010 --> 00:40:40,270 demographic who's indeed among those more comfortable and would like more 785 00:40:40,270 --> 00:40:43,960 of a challenge than the standard edition of that pset expects. 786 00:40:43,960 --> 00:40:46,390 More details on those to be found in the syllabus. 787 00:40:46,390 --> 00:40:49,430 >> But also in there can be found details on the courses late days. 788 00:40:49,430 --> 00:40:51,570 Typically problem sets are due on Thursdays. 789 00:40:51,570 --> 00:40:55,550 However, you can extend many of your deadlines this fall from Thursdays to 790 00:40:55,550 --> 00:41:00,010 Fridays simply by meeting us halfway, so to speak, answering a few warm-up 791 00:41:00,010 --> 00:41:03,370 questions in some of the week's problem sets, that will automatically 792 00:41:03,370 --> 00:41:05,710 then give you an extra 24 hours. 793 00:41:05,710 --> 00:41:09,120 We will also drop your lowest score, as per the syllabus. 794 00:41:09,120 --> 00:41:12,170 >> To give you a sense of what the problem sets are-- because it's indeed 795 00:41:12,170 --> 00:41:15,120 the course's problem sets that ultimately define almost every 796 00:41:15,120 --> 00:41:18,760 student's experience, more so than lectures, more so than sections, more 797 00:41:18,760 --> 00:41:21,230 so than most any other aspect of the course. 798 00:41:21,230 --> 00:41:25,140 Last year, for instance, we began, as we'll begin this year, with Scratch. 799 00:41:25,140 --> 00:41:29,150 Particularly this Friday, we'll use, for just one day's time, a graphical 800 00:41:29,150 --> 00:41:32,260 programming language, with which we'll start programming by dragging and 801 00:41:32,260 --> 00:41:37,580 dropping puzzle pieces that only assemble physically if it makes sense 802 00:41:37,580 --> 00:41:38,990 to do so logically. 803 00:41:38,990 --> 00:41:43,460 >> Next week, we'll quickly transition to C, a fairly old but very small and 804 00:41:43,460 --> 00:41:48,510 simple language that will allow us to really go from 0 to 60 over the course 805 00:41:48,510 --> 00:41:52,290 of just a few weeks, and then parlay those same skills and knowledge of 806 00:41:52,290 --> 00:41:56,160 basic programming constructs into higher-level languages like PHP, 807 00:41:56,160 --> 00:41:58,240 JavaScript, and yet others still. 808 00:41:58,240 --> 00:42:02,560 >> Last year, the third pset in the course was that of cryptography, a 809 00:42:02,560 --> 00:42:06,380 domain-specific application whereby we challenged students to implement any 810 00:42:06,380 --> 00:42:11,140 number of ciphers, programs with which to scramble or unscramble information, 811 00:42:11,140 --> 00:42:11,880 to encrypt it. 812 00:42:11,880 --> 00:42:16,300 For the hacker edition, by contrast, we gave the hacker students a file 813 00:42:16,300 --> 00:42:19,900 from a standard Unix computer containing user names and passwords, 814 00:42:19,900 --> 00:42:22,740 the latter of which were encrypted, and we challenged those hacker 815 00:42:22,740 --> 00:42:26,850 students to decrypt, as best they could, those passwords, still on that 816 00:42:26,850 --> 00:42:27,770 same domain. 817 00:42:27,770 --> 00:42:30,580 >> Scramble, a game with which some of you are perhaps familiar. 818 00:42:30,580 --> 00:42:34,410 A forensics piece, where we ask students to recover data that had been 819 00:42:34,410 --> 00:42:38,530 otherwise deleted from my own digital camera's compact flash card, by 820 00:42:38,530 --> 00:42:42,740 actually writing software to figure out, where were the zeroes and ones in 821 00:42:42,740 --> 00:42:46,850 that digital camera that previously composed a JPEG graphic? 822 00:42:46,850 --> 00:42:49,710 >> A challenge of sorts last year involving writing the fastest 823 00:42:49,710 --> 00:42:53,160 spell-checker possible, competing against friends and classmates if 824 00:42:53,160 --> 00:42:53,860 they'd like. 825 00:42:53,860 --> 00:42:56,330 Implementing Huff 'n Puff, a compression program. 826 00:42:56,330 --> 00:43:01,930 And then ending the semester with CS50 Finance, a web-based application with 827 00:43:01,930 --> 00:43:06,570 which you create an eTrade-like website to buy and sell stocks, so to 828 00:43:06,570 --> 00:43:09,860 speak, by actually pulling nearly real-time quotes Yahoo! 829 00:43:09,860 --> 00:43:10,450 Finance. 830 00:43:10,450 --> 00:43:13,590 >> What we didn't do last year was one problem set that remains 831 00:43:13,590 --> 00:43:14,810 nonetheless a favorite. 832 00:43:14,810 --> 00:43:18,400 If you've never gone to shuttle.cs50.net, you'll see a user 833 00:43:18,400 --> 00:43:19,670 interface a little like this. 834 00:43:19,670 --> 00:43:23,530 But two years ago, the class implemented, using Google Maps and the 835 00:43:23,530 --> 00:43:28,570 Google Earth plug-in and a little bit of savvy with driving around campus, 836 00:43:28,570 --> 00:43:33,290 so that the objective of this game was, as you can see some of the faces, 837 00:43:33,290 --> 00:43:37,530 is to drive around campus looking for staff, teaching fellows and CAs, and 838 00:43:37,530 --> 00:43:40,080 when you do, putting them onto your shuttle bus. 839 00:43:40,080 --> 00:43:44,035 None of them actually seem to be here, so we're going to enter a cheat code. 840 00:43:44,035 --> 00:43:47,150 >> [LAUGHTER] 841 00:43:47,150 --> 00:43:48,430 >> DAVID MALAN: There we go. 842 00:43:48,430 --> 00:43:49,240 All right. 843 00:43:49,240 --> 00:43:51,750 And here now is the staff laced throughout campus. 844 00:43:51,750 --> 00:43:54,530 And as you can see, on the right-hand side of the screen, the shuttle bus 845 00:43:54,530 --> 00:43:55,510 has empty seats. 846 00:43:55,510 --> 00:43:59,000 And the objective was to write the code with which to simulate this 847 00:43:59,000 --> 00:44:01,790 driving and picking up and dropping off of passengers. 848 00:44:01,790 --> 00:44:04,960 That one, too, using a language called JavaScript. 849 00:44:04,960 --> 00:44:10,030 So realize that programs like that will be on our same trajectory this 850 00:44:10,030 --> 00:44:10,910 year, as well. 851 00:44:10,910 --> 00:44:13,640 >> In terms, now, of additional support, we have office hours. 852 00:44:13,640 --> 00:44:16,520 As you might have seen in your own house dining hall or in Annenberg, 853 00:44:16,520 --> 00:44:19,280 we'll be in the house dining halls four nights a week-- 854 00:44:19,280 --> 00:44:24,450 Leverett, Pfoho, Eliot and Annenberg this year, 8:00 PM to 11:00 PM. 855 00:44:24,450 --> 00:44:26,830 And what we thought we'd do this year is something a little different. 856 00:44:26,830 --> 00:44:29,650 >> If you heard rumblings last year that it was a bit too stressful, this 857 00:44:29,650 --> 00:44:32,800 year's office hours, as we'll describe next week, will be more organic, 858 00:44:32,800 --> 00:44:36,900 whereby upon arrival, you'll be dispatched to one particular table 859 00:44:36,900 --> 00:44:39,860 where multiple staff members await, and we'll do things much more 860 00:44:39,860 --> 00:44:40,440 organically. 861 00:44:40,440 --> 00:44:43,740 No more queue, no more iPad, but rather have more intimate 862 00:44:43,740 --> 00:44:47,300 conversations around a table of just eight or so students, so that we 863 00:44:47,300 --> 00:44:50,880 approximate the feel of what otherwise would be a much smaller class. 864 00:44:50,880 --> 00:44:54,120 >> We offer, as well, these things we called walkthroughs, videos filmed in 865 00:44:54,120 --> 00:44:57,330 advance by one of the course's teaching fellows, Zamyla, in which she 866 00:44:57,330 --> 00:45:00,690 walks you through the week's problem sets, offering tips and tricks for the 867 00:45:00,690 --> 00:45:02,640 challenges that lay ahead. 868 00:45:02,640 --> 00:45:06,230 And conversely, after problem sets are due, this year, we'll also release 869 00:45:06,230 --> 00:45:09,100 little clips call post-mortems that actually walk you through 870 00:45:09,100 --> 00:45:13,630 representative solutions, both good and bad, via which you can infer how 871 00:45:13,630 --> 00:45:17,550 you could have or should have implemented your own solution. 872 00:45:17,550 --> 00:45:20,500 >> And what we'll offer for the first time this year as well, particularly 873 00:45:20,500 --> 00:45:23,420 for those students who avail themselves of the course's other 874 00:45:23,420 --> 00:45:28,580 resources but nonetheless are struggling all too much, the course 875 00:45:28,580 --> 00:45:33,030 itself will pair those students, as resources permit, with tutors so that 876 00:45:33,030 --> 00:45:35,840 you have a much more intimate opportunity than house dining halls 877 00:45:35,840 --> 00:45:38,700 allow for one-on-one assistance. 878 00:45:38,700 --> 00:45:42,780 >> Now a final glimpse at some of the end games in sight. 879 00:45:42,780 --> 00:45:44,580 You might be familiar with the CS50 Hackathon. 880 00:45:44,580 --> 00:45:48,120 Well, coming this December, from 8:00 PM to 7:00 AM, at the beginning of 881 00:45:48,120 --> 00:45:51,410 Reading Period, will be an opportunity to gather with classmates-- 882 00:45:51,410 --> 00:45:53,130 this would be around 9:00 PM-- 883 00:45:53,130 --> 00:45:56,550 during which you dive into your final project's implementation alongside 884 00:45:56,550 --> 00:45:59,910 classmates, friends, and food. 885 00:45:59,910 --> 00:46:03,680 This would be around 1:00 AM, when the first batch of food arrived. 886 00:46:03,680 --> 00:46:08,470 And this is about 4:00 AM that particular year at the CS50 Hackathon. 887 00:46:08,470 --> 00:46:12,000 >> But the true climax of the course is meant to the CS50 Fair, a campus-wide 888 00:46:12,000 --> 00:46:15,790 exhibition of your own final projects, to which family and friends are all 889 00:46:15,790 --> 00:46:18,730 invited, as our recruiters and our friends from industry. 890 00:46:18,730 --> 00:46:22,170 This, for instance, is a glimpse of the 2,000-plus people who've attended 891 00:46:22,170 --> 00:46:23,160 past years. 892 00:46:23,160 --> 00:46:27,180 Expressions like this are not uncommon, and similarly do your 893 00:46:27,180 --> 00:46:29,660 classmates delight in things you've accomplished. 894 00:46:29,660 --> 00:46:33,170 >> And actually, toward that end, we have a start-of-term event, as well. 895 00:46:33,170 --> 00:46:37,400 If things like this appeal to you, or you're at least curious as to what 896 00:46:37,400 --> 00:46:41,590 this, know that a new tradition of the course is called CS50 Puzzle Day. 897 00:46:41,590 --> 00:46:45,710 And this was instituted a couple of years back to really signal to campus 898 00:46:45,710 --> 00:46:48,930 that computer science is not about programming, and it's certainly not 899 00:46:48,930 --> 00:46:51,960 about embracing only those students who have prior experience. 900 00:46:51,960 --> 00:46:54,200 It's really about problem-solving more generally. 901 00:46:54,200 --> 00:46:57,360 >> And so Puzzle Day, over the past few years now, has evolved into a nice 902 00:46:57,360 --> 00:47:00,500 partnership with our friends at Facebook, whereby there'll be fabulous 903 00:47:00,500 --> 00:47:04,830 prizes and pizza across the river at the i-lab this coming Saturday. 904 00:47:04,830 --> 00:47:09,180 Head to that URL with two or three friends if you would like to partake 905 00:47:09,180 --> 00:47:10,830 in this new tradition. 906 00:47:10,830 --> 00:47:14,180 >> So I'd like to ask that you keep one thing in mind, and we've got just a 907 00:47:14,180 --> 00:47:17,070 two minute clip on which to close today. 908 00:47:17,070 --> 00:47:19,640 73% is the number to remember. 909 00:47:19,640 --> 00:47:23,900 Cake, too, will await you outside this transept as we adjourn in just a 910 00:47:23,900 --> 00:47:26,710 couple of moments, which is a tradition of the course, as well. 911 00:47:26,710 --> 00:47:29,860 But this is the key quote from the course's syllabus to keep in mind. 912 00:47:29,860 --> 00:47:32,820 What ultimately matters in this course is not so much where you end up 913 00:47:32,820 --> 00:47:36,580 relative to your classmates but where you, in Week 12, end up relative to 914 00:47:36,580 --> 00:47:37,960 yourself in Week 0. 915 00:47:37,960 --> 00:47:43,670 >> But the glimpse that we will leave you with here today is this last one here 916 00:47:43,670 --> 00:47:47,580 by our same Daniel, who did the wrdly video just a moment ago. 917 00:47:47,580 --> 00:47:50,000 I leave you with this glimpse of what lies ahead. 918 00:47:50,000 --> 00:47:53,360 And as we do this, if we could have CS50 staff from the front of the room 919 00:47:53,360 --> 00:47:57,280 to come on up to the stage to paint all the more of a visual picture as to 920 00:47:57,280 --> 00:47:59,100 what awaits you this year-- 921 00:47:59,100 --> 00:48:00,350 getting awkward. 922 00:48:00,350 --> 00:48:02,200 923 00:48:02,200 --> 00:48:05,188 We'll conclude with this here on the screen. 924 00:48:05,188 --> 00:48:18,634 >> [MUSIC PLAYING] 925 00:48:18,634 --> 00:48:21,124 >> DAVID MALAN: This is CS50. 926 00:48:21,124 --> 00:50:00,226 >> [MUSIC - MATT & KIM, "IT'S ALRIGHT"] 927 00:50:00,226 --> 00:50:03,245 >> SPEAKER 1: I love CS50 more than cats. 928 00:50:03,245 --> 00:50:06,030 >> SPEAKER 2: Whoaaaa! 929 00:50:06,030 --> 00:50:06,990 >> [LAUGHTER] 930 00:50:06,990 --> 00:50:08,140 >> DAVID MALAN: This, then, is CS50. 931 00:50:08,140 --> 00:50:10,050 We will see you on Friday. 932 00:50:10,050 --> 00:50:13,370 >> [APPLAUSE AND CHEERING] 933 00:50:13,370 --> 00:50:17,540 >> NARRATOR: At the next CS50, an onstage demo doesn't go as planned. 934 00:50:17,540 --> 00:50:19,080 >> DAVID MALAN: We want to find Mike Smith in this phone book. 935 00:50:19,080 --> 00:50:20,380 Well, what are your instincts? 936 00:50:20,380 --> 00:50:23,750 I might jump roughly to the middle of the phone book, glance down, see that 937 00:50:23,750 --> 00:50:26,830 I'm at M, and I know now that Mike Smith isn't to the left. 938 00:50:26,830 --> 00:50:27,840 He must be to the right. 939 00:50:27,840 --> 00:50:30,515 And so at this point, we can literally tear-- 940 00:50:30,515 --> 00:50:33,300 at this point, we can literally tear-- 941 00:50:33,300 --> 00:50:36,490 at this point, we can figuratively tear the phone book in half. 942 00:50:36,490 --> 00:50:38,954 >> [UKELELE STRUMMING]