>> Welcome back to CS 50. This is Week 3. And on the evaluations at the end of last fall we got a comment from a student about how they apparently were in incentivized to come to class early simply because we started most every lecture with a little something stupid. So I thought we'd begin two minutes early so that we can squeeze in two such minutes of motivation. This one related, of course, to Problem Set 2, which for those of you doing the hacker edition challenges you not to implement ciphers but to do the reverse, cryptanalysis, and actually decrypt some known people's passwords. So with that, I give you this perhaps famous clip. 

>> What's going on, what are you doing to my daughter? 

>> Permit me to introduce the brilliant young plastic surgeon, Dr. Philip Slotkin, the greatest nose job man in the entire universe and Beverly Hills. 

>> Your Highness. 

>> Nose job, I don't understand, she's already had a nose job. It was her sweet 16 present. 

>> No, it's not what you think. It's much, much worse. If you do not give me the combination to the [Inaudible] Dr. Slotkin will give your daughter back her old nose! 

>> No! Where did you get that? 

>> All right, I'll tell, I'll tell. 

>> No, daddy, no, you mustn't. 

>> You're right, my dear. I'll miss your new nose, but I will not tell him the combination no matter what. 

>> Very well. Dr. Slotkin, do your worst. 

>> My pleasure. 

>> No! Wait, wait! I'll tell. I'll tell. 

>> I knew it would work. All right, give it to me. 

>> The combination is 1. 

>> One. 

>> One. 

>> Two. 

>> Two. 

>> Two. 

>> Three. 

>> Three. 

>> Three. 

>> Four. 

>> Four. 

>> Four. 

>> Five. 

>> Five. 

>> Five. 

>> So the combination is one, two, three, four, five. 

>> That's the stupidest combination I ever heard in my life, that's the kind of thing an idiot would have on his luggage. 

>> Thank you, your Highness. 

>> What did you do? 

>> I turned off the [Inaudible] -- 

>> No you didn't, you turned off the whole movie. 

>> I must have pressed the wrong button. 

>> Put it back on, put the movie back on. Got to get that thing fixed. We're back, and we have the combination. 

>> What? 

>> We're done with you. Go back to the golf course and work on your putts. 

>> Let's go, Arnold, come Gretchen. Of course you know I'll still have to bill you for this. 

>> Bet she gives great helmet. 

>> Did it work? Where's the key? 

>> It works sir, we have the combination. 

>> Great. Now we can take every last breath of fresh air from plant [Inaudible] What's the combination? 

>> One, two, three, four, five. 

>> One, two, three, four, five? 

>> Yes. 

>> That's amazing. I've got the same combination on my Luggage! Prepare, Space Ball One for immediate departure. 

>> Yes sir. 

>> And change the combination on my luggage. 

>> Okay, it really doesn't get stupider than that. So this is CS 50. We left off last week looking at cryptography, the motivation for which ultimately was to introduce a problem domain for Problem Set 2. But more than that, it was to make clear this reality that if you've already sat down to tackle P Set 2, or will soon this week, what's ultimately a fairly interesting idea, taking plain text, converting it to cipher text, and generally doing something useful, encrypting information, it really reduces to some things that are very, very simple. You're going to find that taking in plain text is a matter of calling something like get string, which of course returns to you a string, which of course is just an array of characters. Well, encrypting text, then, is really going to reduce itself to just iterating over that array from I equals 0 on up on the length of the string, and then doing some kind of manipulation of each of the characters. Maybe in the case of Caesar, some addition. But there's a problem with the Caesar cipher. So the Caesar cipher is this -- this algorithm via which you take some text and quote unquote rotate each of the characters by some number of places. And rot 13 [Assumed spelling] was a very specific instance of that, where the secret rotational value, the so-called key was in that case 13. But we can generalize. It can be anything, from 0 on up to infinity. But of course only a few of those, say 26, actually have some utility. How would you go about cracking, that is figuring out someone's password, if it were encrypted with the Caesar cipher? If I hand you a string of text, it looks like nonsense because it's been encrypted with rot 13, not twice, but once. What would you do? 

[ Inaudible audience comment ] 

>> What's that? Okay, so frequency analysis. So a fancy way of saying, well, there's some letters in the alphabet that are more popular than others. If you've ever watched Wheel of Fortune, you'll realize that most contestants know this. So maybe you look for the most frequently reoccurring letter in the cipher text and realize, hmm, Q, Q appears an awful lot. But wait a minute, this has been encrypted. It's probably the case that Q is the result of encrypting a more common letter, maybe E, for instance, and getting Q as a result. So you might be able to reverse engineer what the secret key is by making some inferences. Or even if you're not that clever and you've never heard this term frequency analysis, but you know it's been encrypted at least with Caesar, I mean, what is another approach, a correct approach, if naive approach, even. Yeah? 

[ Inaudible audience comment ] 

>> Yeah, that's only 26 keys that might have been used if we're talking about Caesar. So yeah, might be a little tedious, but it's not going take forever just to try all possible keys. And in fact, you don't have to try all possible keys on the entire message, especially if this is an entire letter or paragraph or whatever that's been encrypted. It will try the first few letters, and if you start seeing English pop out, or maybe French or Spanish or anything that can be expressed with A through Z, odds are if it looks like a word, if it looks like a sentence, bam, you found a key. So Caesar is not all that strong, and maybe it was in fact used back in the day, but there have been certainly improvements on it since. Because even we with a pace of paper and a pencil could crack the Caesar cipher. Well, the Visionaire [Assumed spelling], cipher, which came along some years later is a little for sophisticated. It takes the approach of Caesar, of rotating letters in the alphabet by some number of places, but of rotating different letters by a different number of places. So instead of using K, the key, the numeric key, to encrypt every single letter in your plain text, it uses a different key for each successive letter. Now that doesn't go on forever, you usually pick a fixed number of keys, and in fact, if you just need a fixed number of keys, you just choose what we call a keyword. So something like foobar. Now, as an aside, if you've wondered why I constantly resort to fu and bar and all Baz and all of these strange names for variables, you'll find that this is just a silly computer science thing, a silly programming thing, a convention. Whenever you need to whip out a random variable for the sake of discussion, fu is typically one's first instinct. Bar, is followed by that, and then ucks [Phonetic], and then there's a whole bunch of silly ones after that. So foobar is sort of a conical example of a random word that we might use. But we just have to realize that each letter in foobar in this case just represents a different key. So F represents one key, O represents another. O happens to represent the same. B is another key, so in other words you take your keyword, you line it up under your plain text, and you rotate each of the plain text characters by the number of places implied by the key. So now what is F? Well, let's see, if we start counting as zero as we typically do, A is zero, so then it's B, C, D, E, F. So F represents the number, the key 5. So what does that mean? Well, if my plain text P is hello world, and I need to rotate H by F, that is by 5 places, I go H I J K L M. Okay, so the resulting cipher text letter is M, and then I repeat that same process using different keys. Now presumably, I might -- plain text, the message I want to encrypt, is hopefully going to be longer than the key. If you're remembering a key that's longer than your actual message you're losing some efficiency there, perhaps. So foobar is only six letters. So what if our plain text is longer than six letters? Well, you just start repeating again and again and again. So let's ask the question for just a moment, then. If there are 26 possible keys for Caesar, how many possible keys are there for Visionaire, by contrast? Little louder, little more confident. Okay, infinitely many, certainly, because we can pick any possible keyword of any length. But let's generalize. Suppose we have N letters in our keyword for Visionaire. How many end letter key words are possible for Visionaire? Right, so 26 to the end. So if every -- you have an N letter keyword, six in this case, and each of those letters can be A through Z through any of 26 possible letters, you've got 26 options times 26 option, times 26, so that's 26 on the N. And then if I relax the constraint that the key is six letters, and I say ehh, the key is any number of letters, then you have even more. You have 26 to the 2, plus 26 to the 3, plus 26 to the 4, so in short, the key space is a lot larger. Now ultimately you could still crack the Visionaire cipher by a few ways. You could do some intelligent manipulation, you could look for patterns, for instance, you could do frequency analysis. Some fairly sophisticated heuristics, or you could try all possible keys. Start with all the one letter keys, then once you've tried all those and gotten back non sense, try all the two letter keys, the three letter keys. And that algorithm, though naive, would eventually work, at least in theory. If you have enough time to wait around. Unfortunately, these days, when you've got two gigahertz of power underneath your own desk or your laptop, you can churn through a lot of keys very quickly, and in fact there's this algorithm called DES, D-E-S, and this is actually an algorithm that's used in the function that's typically used on a Linux or UNIX or Mac os system, still today, to encrypt your own passwords. So you've got a user name and password, maybe on your own computer, certainly on Nice dot F A S dot Harvard.edu now, and your password, fortunately, is stored in encrypted fashion, and this is why, for instance, the user assistants, beg them as you might, cannot tell you your password if you forget it, because the system stores it in encrypted fashion. So this algorithm, this function called DES was used for some time, many years after Visionaire, but in more recent modern times, and there were with DES 72 quadrillion possible keys because of the number of bits used to encrypt something with this particular algorithm. Now we won't go into the specifics, I put this little snippet from a text book to just kind of hit at the relative complexity of this. Visionaire is very simple, you can do it paper-pencil. DES starts to take a computer or calculator, as all of these arrows and this flowchart generally implies. But a computer can compute DES-encrypted text fairly quickly. Unfortunately, too quickly. So the reality is these days if you encrypt something with DES, you know, if someone has enough time and enough CPU cycles at their disposal they can crack your password. And that's in fact, exactly what Problem Set 2's hacker edition is all about. Now this is you know, interesting maybe fun in the context of passwords on some random university's system. It's a lot more worrisome, if random people, students in CS 50 with a laptop on their lap, can crack information that has been encrypted with something like DES. DES is not very secure any more. 56 bit keys, as it once used, no longer very secure. So there are variants. In fact, someone came up with the bright idea of not just using DES, but let's run DES three times, call it tripped DES or 3 DES. And that actually is a little more secure, but not terribly so. So the world has come up with more sophisticated algorithms. And if you take or have time to take over your years here computer science 120, and there's a cryptography class, and there's some graduate level ones, it's really interest space. But the funny thing is a lot of the security of today's cryptographic mechanisms ultimately boil down to assumptions. The safety of them boils down to assumptions. In other words, there is this algorithm called R S A, and you might have seen this listed to various web sites, you might have heard of this algorithm before. It basically boils down to a really fancy way of allowing web sites to communicate with browsers securely, but that's just a specific case. You can use it for far many more interesting purposes; ATM machines, bank transactions, a whole bunch of interesting stuff. But it ultimately, the security of R S A, whether you're using keys that are 56 bits long, which is pretty short these days, or 128 bits long, or 1,024 bits long, ultimately, whether or not this algorithm actually works reduces to whether mankind can come up with a fast way of factoring large numbers. So again, long story short, this algorithm called R S A boils down to assuming that mankind, and their computers, cannot take a really big number and factor it really quickly into two large prime numbers. So put another way, if you want to encrypt some information and you want to use an algorithm like R S A, you take two really big prime numbers, and it's not hard to generate prime numbers, even big ones, it's not hard to multiply them together. But it is much harder to undo that process, when all you do is hand an adversary or hand a computer a really big number and then say hey, this just so happens to be the product of two really big primes, tell me what they are. We, thus far, have not come up with a relatively fast way of figuring that out. It will take more units than we have in our lifetimes, for instance, to make sweeping generalizations. But the key is, no pun intended, that there is a lot of interesting opportunities to improve upon or even break some algorithms that the world itself is now entrusting our money, our security, and a whole bunch of things too. To give you a sense of what a bigger key looks like. So this is intentionally rather small and deliberate, this is a key, a really big number, that happens to be represented with alphabetical characters and numbers, just for efficiency's sake, that represents a key one might use with an algorithm like R S A. This is a lot bigger than a number from 1 to 26, this is a lot bigger than a word like foobar. So this hints at the types of security that's actually in use today. And so that's where we pick off -- pick up today. So we spent a lot of time in the past couple of weeks talking about syntax and C and programming, now finally that we've gotten some of the minutia out of the way, what a for loop is, what a while loop is, and granted, you might still need another week or two of practice to get comfortable with even those syntactical details, we finally now have the ability to start talking at a slightly higher level about how you actually start to think more effectively, as the syllabus and course catalog claims, how you can solve problems more efficiently, as is the other promise made. And we started this course with this sort of visually interesting example of taking a really big phone book, and I claim I could find Mike Smith much faster than say a completely naive person would, by starting at the front and flipping through the As, and then the Bs, and then the Cs. Because I took this approach of dividing the problem in half and conquering only half of it. And then I realized, oh, if Mike I know is in the right-hand side of the phone book, let me do this again, and split the problem again and again. And our take away was that if that phone book, and it pretty much was, a 1,000 pages or 1,024 pages, how many times would I actually have to split that problem in half to find someone like Mike Smith. So just ten, right? If you have 1024 pages, and you just do the math in your head or on a piece of paper, you can divide that number in half ten times. Now there might be some interesting rounding issues at the end when you get to the last page, but ten times, instead of 1024 pages. Suppose that phone book, as we said in week 0, were not 1,000 pages, but 4 billion pages, that's a hell of a phone book, with a lot of names in it. But how many pages would I actually have to look at. How many times would I have to chop a 4 billion page phone book in half. 32 times. Why? Well, you can take 4 billion and divide it in half roughly 32 times. And that speaks to the power of actually designing algorithms intelligently, that speaks to the power of what you can do with this basic device and just a modicum of intelligence inserted into your algorithm. Right, if I told you to search a phone book right know, you could certainly recently through how you might implement, divide, and conquer, but by far the simplest way to implement search for a phone book using the syntax and the capabilities of C you have now is what, like, write a for loop, I gets zero, I less than or equal to 4 billion, and then just check from I on up to 4 billion whether or not someone is in the current variable or in the current array or however you actually code it up. You could implement that with just a few minute's time. But that thing's going to take a while to run. By contrast, put a little more thought up front and the algorithm itself will execute far more quickly. So we're not going to stand up and indulge in this again, but this is an instance of the same idea. The first day you all stood up, you paired off with someone, and then half of you sat down, then half of you sat down, then half of you sat down. Now, granted, that turned into a bit of a disaster, as is often the case. Took way longer than for me to just go 2, 4, 6, 8, 10, 12. But in theory, had there not been the social awkwardness, had there not been the problems with arithmetic, we would have been able to -- you would have been able to count the people in this room so much more quickly than I, because whereas I'm sort of going like this, 1, 2, 3, so with every CPU cycle I'm doing one thing, you, by contrast, with every toll of the clock, with every CPU cycle, half of you were sitting down. You were taking a half -- 50% of the problem out of the room at once. Where I was just taking one nth of it out of the way. So this too has implications. So this is just a fancy way -- I whipped this up with Excel -- to depict the following idea. So on the X axis here is this number N, which generally is going to refer to the size of the problem, how many pages are in the phone book. Let's call it N. How many students are in Sanders. Let's call it N. So I have from zero on up to 130. And then on the Y axis I have what I call T of N, the running time of an algorithm whose input is of size N. So it's just a general way of describing the running time, how much time does it take for an algorithm to run, and what do we mean by time? Like steps or seconds, minutes, whatever, so long as we all agree what the metric is. And these different lines represent different running times. So at the top left, we have a little legend there. It's kind of small to see, but we have three graphs here. One is this one up top. So on the left-hand side we have a very steep curve, but this is a line, this is a linear graph. And this represents an algorithm that given A inputs takes N steps to run. And that is representative of the running time of 1, 2, 3, this linear algorithm of counting students. But we realized in Week Zero we can do better, right? We can actually sped those up. So the second graph there, the second line that's a little bit to the right of the first one, that would be the result of my doing 2, 4, 6, 8. It's actually twice as fast, now contrast this with your line, so log of N, as we described your algorithm that day, as we described this general principle of divide and conquer. What this means is your algorithm should take way less time. In other words, the more students are in the room, look at the contrast between how many steps or how many seconds, how many units much time your algorithm should take versus mine, which is literally off the charts. Now what does this mean? If we add -- if one more student comes into this room that takes me one more step. If one more student comes into this room, that's kind of rounding error for you. Because you can kind of assume that one additional student. So let's actually take a bigger -- let's increase the problem more significantly. Suppose we have roughly 2, 300 students in this room. Suppose another 200 or 300 students come into this room within the next few seconds. Well that's going to take me literally twice as long. If it took me N steps before, it's going to take me 2 N steps by doubling the size of the room. Now my contrast, if 200 or 300 more students enter this room in the next few seconds, how many more steps or unit of time does it take you to count those additional students? Just one, right? Because within the first iteration of your algorithm, those same kids will sit down right away. And that's a huge bite out of the problem, whereas mine has grown significantly. And that's the fundamental contrast between something that's linear, like in my case, and something that's logarithmic, or at least mathematically more interesting. And not to overwhelm with numbers, but just to give -- put concrete values on what the implications here are, this is just a big chart that computes some very basic functions. So in the left-hand, the third column here, right above where I'm standing, this is N, so we arbitrarily have 1, 2, 4, 8, 16, a whole bunch of values of N. So my algorithm, 1, 2, 3, 4 -- if we have let's say 1 million students in this room or 1,048,576, that's obviously going to take me 1,048,576 steps. But my contrast, if you scroll back to the left, and you can do this, you know, with a calculator or even in your head perhaps, that same student body of a million students in Sanders could be counted by you all in just 20 steps. And so the take away visually of a graph like this, and we'll revisit this or you can revisit this as we introduce yet more algorithms, is exactly how significant the implications are of well-designed algorithms. And we can zoom out even further, if you look at various graphs like these three here, the specifics are not so interesting today, but notice this last one here. So it's small to see, but that big curve that's going to the north there is called 2 to the N. 2 to the N being an exponential function. So we'll talk about it at times and in future classes if you take other theory classes in CS, even just for fun or if you're minoring in CS, you'll find that exponential algorithms, very bad. Because as N increases they take a ridiculous amount of time. But back to our motivation today of cryptography, when we say it's really hard to factor large numbers quickly, what we mean, essentially, is that factoring large numbers generally boils down to something that takes exponential time, not linear, not quadratic, not polynomial, if you recall the terms, but exponential. So graphs like that, very bad. Takes a good amount of time to run. So how can we start to describe the running times of algorithms. Right? It's sort of -- it's easy enough to pick a few examples, talk about which one's better, why it's better, and steps it takes. But can we generalize. Can you start to look at your own code or your own programs and say this algorithm is good because it takes this amount of time, or this implementation I wrote last week sucks because it takes this much time in general. Can we slap some labels or some formalities on just so we can start comparing algorithms against one another, even in different languages or written by different people. Well, there's three basic constructs, three little pieces of jargon we'll start using. One is called big O, one -- and that's the guy at the top. The middle guy is called theta. And the bottom is omega. And these symbols are just generally used by mathematicians in computer science to express the running time of algorithms. Now what does this mean? So formally, it means this. And these slides are on line, if you like the mathematical formalities, because there's actually some juicy ideas in there, but for today, they reduce to some relatively simple ideas. If you have an algorithm that in the worst case takes N steps, you say that that algorithm is in -- you say that that algorithm is in big O of N. So this is the worst case running time of time linear algorithm of counting students, and as an aside, happy birthday to Jansen and Mike. If, though, your algorithm in the best case might actually take fewer steps, well then you start talking about omega notation. Now in the case of counting students, this really doesn't help us, because in the best case how many steps is it going to take to count N students? Well, N. Right, I kind of have to count everyone. In the best case? Well, if I want to count all of the students, it's still going to take N steps. But let's pick another algorithm arbitrarily. Suppose students file into the room, I want to search for a student named Mike, just because. So in the worst case, how many steps will be take me to find a student named Mike as they file in the door. All right, so N steps. Because in the worst case, the Mike or the several Mikes we have in the course this semester are just -- just so happen going to be the last people coming into the room. Just by chance. But in the best case, where might Mike be in the line? First, right? Common sense. So in the best case there we say that algorithm of finding Mike, searching for Mike, is in omega of 1 in the best case, just takes one step, bam, I ask the question, I get the answer I'm looking for right away. So when you have an algorithm that's both in big O of N or omega of N, so not the searching but rather the counting, then can you say that that algorithm is described by theta of N. So in short, we have worst case running time up top, we have best case running time at bottom, and if those two just so happen to be the same, then you can say that the algorithm is in theta of whatever formula you've come up with, and in that case. All right, so what does this mean exactly? So in the case of a phone book, when I tore the phone book again and again and again, and what was the running time of finding Mike Smith or really finding anyone, for that matter, in a phone book that happens to have N pages? In the worst case, searching a phone book takes how many steps? Okay, so log N, if my algorithm is to just start at the first page and go from left to right all the way to the end of the phone book. So that might be one implementation, and this will be say, linear search of a phone book. But we can do better. In other words, if I want to compare one algorithm, the linear algorithm that we started class within Week Zero versus the more intelligent one of divide and conquer, divide and conquer worst case running time is instead what? Log N, right? Because we said multiply times now that in the worst case we're going have to keep chopping the phone book in half and half and half, until we get to one page where Mike Smith is finally listed. How many times can we do that chopping? Log in time, so this is something that we'll call logarithmic. All right, what about the best case running time of the phone book searching algorithm? Yeah, right? Because in the best case -- and again, when you talk about an algorithm, you talk about a general input. We don't talk about an algorithm for finding Mike Smith, we talk about an algorithm for finding someone. Well, the best case running time of finding someone in a phone book whether you use the linear algorithm or the logarithmic one ultimately boils down to just constant time, right? Because you might be looking for Abigail Adams, who just so happens to be on the first page of the phone book. Bam, you're done, you don't even have to divide the phone book in half multiple times. And we'll call the running time of that algorithm constant, whether it takes one step, maybe it takes two steps, because there she is on the page, now I have to find what row she's in on the page. But those are just a constant number of steps, so we're going to generalize as just constant time. So what's the point of all this? Well, we now, just as we did, have this means of comparing not apples and oranges, per se, but apples and apples. If we have two different algorithms, linear search and then divide and conquer for the phone book, we can now say something qualitatively about which one is better in terms of its running time. And the notation folks tend to use for exactly that, is this notation here. So just to toss out some jargon in case you see it anywhere, constant time we discussed, logarithmic time we discussed, linear time we discussed. We'll see this running time often, N log N. Frankly, in 12, 15 years of computer science I've never heard one human say supra linear, but that is in fact the formal term. N squared, we'll see today and-or Wednesday. That's called quadratic. More generally, if you have N raised to some power, that's a polynomial. And then there's N factorial, which is even worse than any of those, but you tend not to see that unless your algorithm is frankly downright stupid. So couple of announcements. There's one hand out today, very little code, but nonetheless, it's out there. Lunch seems to have gone well, so we were kind of overwhelmed by responses. We ended up having a barbecue for 60 of your classmates. So we'll try to do another such thing some future Friday, more on that in a future class. If you've not yet returned sensor boards from the hacker edition of P set 0, that's fine, just hand them to one of the TFs in our little nook over here. P set 2 went out the door on Friday. The walk through was filmed yesterday, on Sunday, that video will go on line by tomorrow. Office hours have been in progress, do take advantage of those, and sections have already begun. So your assigned section, you should have been informed of by e-mail. Either you went last night or your section is probably today or tomorrow, so do take advantage of those as well. And we also deployed per Problem Set 2 this link on Friday. So there is now the bulletin board, which if clicked will log you into a little interface that looks like this. And the bulletin board is meant to serve a couple of purposes. One, it's meant to allow us to answer the same question once for many different people to benefit from the answer. It's meant to be an opportunity for you to potentially field each other's questions, so long as it doesn't cross that line of outright telling someone some answer, and what you'll find is that week to week we'll add another category to the bulletin board for P set 2, P set 3, P set 4 and so forth, and the goal of the bulletin board is to ask questions that you're pretty sure anyone can hear the answer to, anyone can see the specifics, but if you find that asking your question really requires that you show us your code, then continue to use help at CS.50 for that, but what you'll find more importantly, especially for those less comfortable, when you log in for the first time although it does authenticate you with user name and password, we have made your name the default value of students. So you can have that pseudonym, you can change it to something other than that, your own name or something fun. But realize the point of the bulletin boards, anonymity is so that you can post what you fear is the proverbial dumb question, and no one else, other than the staff as necessary, is going ask that you even asked that question. So if that gives you more comfort, by all means, ask for questions in that way. That was a lot to absorb, let's take our five minute break. 

[ Background noise ] 

>> All right, we are back. So we do the following with key note. We have eight doors here, behind which are little surprises. To reveal what's behind these doors, though, I need to solicit the ever-awkward volunteer to come up on stage, if you will. Yeah? Come on down. Again, you'll need to sign your rights away in perpetuity in a moment. Come on up. What is your name? 

>> Edward. 

>> Edward, okay. David. Nice to meet you. Got a fan over there. All right, so Edward, much like a game show, we have the same doors -- oops -- [Inaudible] will spoil the surprise. So we have eight doors behind these pieces of paper here. So we have two arrays. So I'm going start using the geek terminology. So we have two arrays, arrays of integers. Each is of size eight. And you are now just a human who's been presented with a very awkward situation. The goal of which in this top array is to find me the number 3. And what we the audience hope to learn from this is exactly how you the human go about solving this problem. So if you would, on the top row only, find us the number 3, please. See the number 2. Oh, that was very good. See the number 3. Okay, so if you would, can you explain how you found the number 3? 

>> Just went up, [Inaudible] pieces of paper at random. 

>> Okay, so that was just chance, then, it was not spoiled by the wind. 

>> Right. Systematically go through and check all the paper. 

>> Okay, good. So thank you, first, for spoiling my demo by finding it so quickly. So -- but let's ask the question nonetheless. What is the running time of the algorithm that Edward just tried, can we slap a label on this. Best case running time. It's apparently two, but one in the truly best case, so this is in omega of 1, we'll say. In the best case, he just happens to go straight for the right number, just by chance or by some more sophisticated heuristic. And in the worst case, how long would it have taken you to find the number 3? Okay, 8 or more, generally big O of N. So again, we have an algorithm that's big O of N, or omega of 1. So the question now at hand is can we do better than that. So let's see. How could we fundamentally improve upon that algorithm, any suggestions for Edward. Could we do better than big O event. Because big O event is great when it's only eight, but if N is now 4 billion, as we've discussed, N, not so good any more. Sorry? 

[ Inaudible audience comment ] 

>> Okay, so we could sort these things, right? There is an advantage that we had all this time since Week Zero of a phone book. Someone else, Verizon or whomever, has done the hard work of sorting that phone book alphabetically so that we can make certain assumptions. An assumption like when I go down the middle and end up at the Ms or the Ns I know the Smiths, the Ss, are going to be to the right. Now I didn't give Edward any such assumptions, and in fact, it's a little weird that 2 is over here, and yet 3 is over here, kind of suggests that maybe these things are not so sorted. And in fact, there's 8, there's 1. So the top row is not in fact sorted. So if we now give you the added assumption that the bottom array of 8 numbers is in fact sorted, how might you go about, without answering, just doing, finding the number 50 in the bottom array. Different numbers, but they are now sorted. I see 171. Dammit! Okay. Okay, very good. Okay. So what did you do this time? 

>> Well, since you told me it was sorted, I assumed it meant it was either -- there was going to be some sort of pattern. So either the larger numbers were on the right or on the left. So I checked both sides. 

>> Okay, good. So as an aside, this demo was far more effective last year when we spent like 10 minutes on this. It was somewhat awkward, actually, because your predecessor spends a lot of time thinking about which number to reveal, thinking there was perhaps some trick to this, when really, five minutes before class I had written random numbers on the board. So you're doing much better. He was a good sport about it. Okay, so bottom array is now sorted. Let's slap some numbers on this. Best case is apparently two again, in reality, but formally or asymptotically, any time we start talking about big O and omega, we're talking asymptotically, which means as inputs get large, as N gets large, what generally happens to running time. So in the worst case, how long would you algorithm have taken. Okay, N, because why, what was your algorithm here? You said I went high, I went low, but we didn't really get to see what you would have done next. In fact, let's continue this. Find me the number 52. I see 51. I see 61. Good. Back on top. Okay, so pause there, because we know you're going to struggle now. So what was your algorithm? Now we have to push a little harder. 

>> So I was assuming they were sorted numerically. So that -- 

>> Okay. 

>> So when you said 52, since I new 50 was already down there, I just went to the same row. 

>> Okay, good. So in short, I can summarize. So at first you went high because 50 is a pretty big number, certainly relative to the number 3 we looked for before. So you went high, didn't find it, then sort of thought maybe I was messing with you, so went left to look for the number 50 there. Didn't find it, but you did know it was sorted. So the rest of your algorithm after this guess work at the beginning, try high, if not high, try low, was presumably to iterate then from left to right. Okay, so we can still slap some formality on this approach too. In the worst case, how many steps would that take, as you said. N steps, right? Because maybe you went high here. Okay, that wasn't 50. Then you went low, not here still, then you end up iterating over the N minus 1 remaining elements, okay, big O event. But again, best case running time is omega of -- in your case there, is just 1. So in constant time. So this sort of begs the question then, how long did it take me, the person setting this up, to actually sort these values. So let's put you out of your awkward [Inaudible] round of applause if we could. 

[ Applause ] 

>> Legal form awaits. Okay, so that begs the question, then, how do we actually go about sorting these values. Because I kind of did it for free. Right? I did it before class, kind of cheated by having the numbers pre-baked. But if you're just handed a bunch of numbers as Edward effectively was, and I left it to him to sort those values so that he could then impress us with the running time of his better algorithm, how much time does it takes to sort these numbers. Well that, we'll see, is a much harder question to answer and a much more time consuming problem to solve. But let's see if we can express now what Edward kind of did or in an ideal world would have done exactly. We can express this algorithm, or really any algorithm moving forward in the course, not just in C code which gets fairly pedantic, writing out all the minutia, we just want to convey the idea of an algorithm, just like we did in Week Zero and One, we can go with pseudo code. There is no formal standard for what pseudo code is, different people take different approaches. The only important thing is to communicate your idea clearly without getting bogged down in stupid details like semicolons and parentheses, which add nothing to the logic and only distract from your idea. So I took the somewhat conventional but somewhat arbitrary approach of defining my pseudo code as follows. For linear search, as I called it, and this is what the world generally calls an algorithm where you start from here to here to here to here, and move from left to right, so on input N, for N elements, for each element I, if I equals, equals N, return true. So on input N, for each element -- yup. So this is -- there are many different ways you can implement this pseudo code or write it, but it implies that there's an array of some sort, but syntactically, doesn't matter how we express this. So I'm going to take the approach of saying for each element I in my array, if I happens to equal N, the thing I'm looking for, go ahead and return true. But then per the indentation, if I never return true, the last line in my program says return false. And the answer is no, as was the case when Edward failed to find 52 because it just wasn't in that second array. But we can do what I was hoping he could do, but it is okay, I can do it myself, we can implement what we might call binary search, which is actually direct application of the whole divide and conquer idea. Now this algorithm looks at first glance certainly more complicated than linear search, but we've already seen how much time it saves on things like searching phone books and what not. So in theory, if I were searching for the number 50 here and I didn't have this heuristic of going high or going low, because maybe that would work, but even Edward had to make a guess, is 50 big or is it a small value. Well in this case, it was actually relatively small value, because we had 50 here, but then 171 here. And in the end, although it was a clever trick, and he actually solved that problem very quickly to his credit, the algorithm itself, ultimately boiled down to no better than just linear search. Because in the end these clever heuristics, which in the real world clearly saved us some time, and garnered him some applause, the rest of the algorithm, had he not been so lucky, is still the same linear algorithm. So what if I instead apply the Mike Smith approach. I go into the middle of my phone book, the middle of my array. And now I'm looking for the number 50. Well, we have some weird mathematical rounding errors that I'm sure we can work out with the rounding function or ceiling or floor or whatever, so I'm going to arbitrarily go here. Is this the number 50? No, it's the number 105. But just like in Week Zero when I was able to tear away the problem of the phone book, I now know that my answer is definitely not going to be to the right. So I can focus only on the remaining numbers here. Where do I go next? Well, I think essentially the same problem. I'm still looking for the number 50, I've still got an array, upside is half as big as it once was. I can use that to my advantage performance-wise, so let me just go smack-dab into the middle. I've got to pick left or right arbitrarily, because the math isn't working out beautifully, so let's pick this one. 51, not the case. But now I know it's this way. So now I know it's not here, 51 or 61. And I'm left with a problem that's a quarter of my original size. So already, fundamentally, I'm definitely moving faster than Edward would have, given many more elements in his array, which clearly is going to the case when we have more room and more interesting problems. So I've got two elements left. I arbitrarily go right, as I've been doing. Aha, the number 50. Now, granted, and this is actually a use full take away, granted, my algorithm was slower than Edward's. Edward took two steps. I took three steps, and yet I'm going to make the claim, arrogantly, nonetheless, my algorithm is better because as N increases, asymptotically, the bigger and bigger N gets, the more and more you'll be impressed by the running time of my algorithm, and more and more Edward's algorithm, in all fairness, just devolves back into a very slow but correct implementation of the same idea of search. Now as an aside, for the astute, this just so happens to be all of the computer science courses you're qualified to take after or before C S 50. So keep that in mind at shopping terms -- shopping periods time. But for now, the take away is that very subliminal, I know, maybe it's not subliminal if I tell you what they are, so for now we just need a way of expressing this. So there's many different ways we can express this. This is what I would call an iterative implementation of binary search. Thus far in the class we've only talked about phone books and splitting them in half, throwing half away, repeating. But now you have this ability to program a machine, you kind of start -- you need to start expressing yourself more precisely. You can't just tell the computer find me the number 50, or 52, you need to tell it how to do that. You need to teach the machine, so to speak. So one way we might imply that in pseudo code is as follows. On the input of an array, where we call it array bracket zero on up to N minus 1, so the length of most any array we ever discuss now is N, but the largest element index is obviously N minus 1, we start counting from zero, and input K, where K is the value I'm looking for. I kind of need to implement this idea of binary search. So I'm going to define in italics here a variable called first. And initialize it to zero. I'm going to define another variable called last, and initialize it to N minus 1. And what the subsequent steps do, if you think it through, as a future Problem Set may ask you to do, it's going to ask you to implement very precisely this approach. Here's N elements, I'm going to use my left hand as my left variable, my right hand as my right variable, and what is it telling me to do on the first step? Well, while first is less than or equal to last. So good, my left hand is indeed less than my right hand, because it's to the left of it. What do I do? Let middle equals first, plus last, divided by 2. So what that math does for me is if I add this index and this index, divide by 2 and take care of the rounding, that gives me a number in the middle. Let's say 105 for now. So middle equals that element there. So if K is less than the middle element in the array, then let last equal middle minus 1. All right, so I'm looking for the number 50. So 50 is indeed less than the middle element of the array. So what do I do? Well the then condition says then let last equal middle minus 1. Here's last, here's middle, here's middle minus 1. And already in one iteration we've seen how to translate a very simple idea, right? Split the problem in half, in half, to something much closer to what GCC could understand, much closer to what you could actually code up in nano. And if you follow the logic there, what you'll find is that iteratively [Inaudible] my right hand, keep moving closer to my left, sometimes my left goes closer to my right, if my hands ever cross what's the implication, presumably? That it's not there. I'm looking for 52, and you know, I went too far to the right, too far to the left, my hands cross because it's just not there, or I end up smack dab on top of the number I'm looking for. Whether it's 50 or 52. But what we've sacrificed here is this beauty of the original algorithm. What's really cool about divide and conquer is it's so damn simple to explain. Take the phone book, split it in half, look at the elements. If it's less than, go left, if it's greater than, go right. Repeat. There's this elegance about this, where you just say divide the problem in half, check for something, and then repeat, repeat. This really clouds some of the simplicity of that algorithm. But we have this ability, it turns out, in C, and in Java, in C++, and all of these languages, particularly ones like Lisp and Scheme, which you could cover in C S 51, of this feature of recursion. So it turns out that whenever we've said something like repeat, you can repeat by essentially applying the same algorithm again. Now thus far in C, how do you implement an algorithm? Well, you write a function like cipher or Caesar that implements some algorithm. So if we ever have to express this idea of repeat, maybe we can have a function just invoke itself again on a smaller piece of the puzzle. Well, what do we mean by that. Well, let's take a look at this very simple program. So this is sigma 1.C, this is one of today's two print outs, two pieces of code that's printed out. So this is going to be a function that returns that an int it's called sigma in homage to the little symbol from your math book that looks like this, and just implies summation. So I want to do this. I want to sum up all of the numbers from I equals 0 to M. So if I want to express this like the back of a high school math book which, this is I equals 0 on up to M of I. So I just want to compute the sum of all the numbers from 0 up to M. Okay, so not an interesting problem, but it's interesting how we can solve it. So here's one little sanity check. When we said last week you better get into the habit for your own sake and your program's sake for error checking, you've got to do sanity checks like this. Just because the function is going to be passed in int per the definition, per its signature, so to speak, per its declaration up here, that doesn't mean it's going to be an int you want. It might be negative. It might be zero. Neither of which we want if we're trying to sum up positive values only. So I'm going to avoid the risk of an infinite loop by just doing a sanity check. If M is less than 1, return zero. So here's an interesting feature of C and a lot of languages. If you have to somehow signify an error condition, some languages, as you may know from high school, like Java, have this thing called exceptions where you can kind of raise a red flag and not bother returning a value at all. But languages like C require that a function return a value, generally. In this is case an int. And sometimes you need to return what we called last week a special sentinel value, a special value that the person calling your function had better check for if they want to see if your function worked correctly. So it's not sufficient for a function like this to just print out warning, M is less than 1. Because how is the code that called this function going to know that an error occurred, right? This is the point we were trying to make last week with side effects versus return values. A human can see side effects. A computer can only see return values. So if we're trying to write code that calls this function and I want my code to be able to check if an error happens, I can't rely on print def, I have to rely on return values. So what value could I return in the event that the input just doesn't make sense? Well, here I arbitrarily chose zero. What might have been another reasonable value to return to signify essentially error? Negative 1, why? Well just because. If you return a negative value clearly the caller, the function that called this function can infer by getting back a negative number when the whole point of the exercise was summation of positive numbers, that something went wrong. So think too, back to last week when we mentioned very briefly, because we'll come back to it, that get string sometimes can return a bogus value or not return a string per se. It can sometimes return a special sentinel called what? This was null, so we'll see this many more times, it hasn't really come up, but N-U-L-L in all caps is a constant that signifies, there is no string, but I'm a function with a return value, I have to return something. So when you start consulting man pages later in the course for new functions that you might want to employ, you'll need to check the section of the manual that says what return values does this function have, because sometimes you want to check with your own little if condition, did I get back a value I care about. Well, this code is easy. Now once I've done this sanity check and I want to sum up the numbers from 1 through M or equivalently 0 through M, I'm going to do this, I'm going to declare a variable called sum, it's going to be a type int, and I'm going to initialize it to zero. I'm then going to iterate from I equals 1 all the way up to M -- equals, less than or equals to M -- and then I++, and then what does this code ultimately do? It just sums up all the numbers from 1 to M or 0 to M. All right, so if I see this in action, let me go ahead to a terminal window here. I've got -- let's go ahead and open a new one, let me go ahead and SSH to nice.fas.harvard.edu, and if I go into my CS 50 directory, okay, Lecture 3, Week 3, okay, sigma one. So this is the same exact code. Notice -- oh, why do I have this at the top of this file? What's the point of significant -- declaring sigma as a prototype up there? Yeah, so remember from last week, if you are calling a function that just so happens to be implemented later in the file but you're trying to call it from main, which apparently I am, so this was not on the slide a moment ago, but apparently I am calling sigma from main -- it's a stupid detail, but you've got to proactively tell the compiler hey, there is a function in this file called sigma, it returns an int, it takes an int, just know to expect it eventually. And realize this too. It turns out that when you declare a prototype for a function, you don't have to provide the names of the variables, all the compiler needs to know at that point in time is what types of variables it has as arguments. So you can literally just write inter, or if it takes two arguments, int, comma, whatever. So either approach is fine. I could have specified the name of the variable up here with int-M, but it just isn't necessary. So I tend to be fairly minimalist when I write the code. All right, so here's the function down there. And notice one other detail, just to make this more compelling. Why did I not do this, because this was a question asked, I think on the bulletin board this weekend. Why did I not do -- say, this. Probably a couple problems here. What's one, yeah? 

[ Inaudible audience comment ] 

>> Yeah. So there's a logical error, declaring int, reinitializing sum to zero every time. So that's not good. What if I did this, as I've seen before. I can sometimes initialize two variables to a value in my for loop. So that seems to be okay. But what kind of error am I going to run into next. Some of you may have -- yeah? Oh, this is -- don't stretch like this during class. Okay. Yeah. In the back. 

[ Inaudible audience comment ] 

>> Exactly. Remember last week's discussion of scope. So generally, when you declare a variable, say inside curly braces, or in this case, inside the for loop, that variable only lives inside of that for loop, which means this math is perfect. We initialize sum to zero, we keep adding to sum I, but the moment down here I try to return sum, my compiler is going to complain to me sum not declared, even though it is, because it's outside of the scope. So it was very deliberate a moment ago when I declared this variable outside of the loop so that it would remain in scope the entire time. All right, so let's go ahead and save this. Let's make sigma 1. I'm not going to bother typing GGC and all that, because this handles a lot of the magic for me now. I'm going to go ahead and dot slash sigma 1. Be ever so clear for security reasons that it's in this current directory. Enter, positive integer please, let's say 10. Hopefully, that's correct. 9. All right. Let's do one I can check quickly. 3. Yes, I'm pretty sure that 3 plus 2 plus 1 equals in fact 6. So feels like this code is correct. But turns out we can implement this in a very different way. How it this function get called first? Well, here is an example of where do while is useful. We said last week -- we said last week that do while is often useful when you want to ask the user for something, give them a chance to give it to you, and then reprimand them or ask them again if they fail to provide what you're looking for. So here's exactly that scenario. Declare an int called N. I'm going to do the following. Tell the user positive integer, please. I'm going to then use get int from the CS 50 library to get the int. And then right here rather elegantly am I going to check within my while construct, if N is at this point in time less than 1, do it again, and do it again. So this is a general approach, do while, to getting user input and the result to be clear is if I try messing with the computer and say negative 123 or negative 6, it's just going to keep pestering me. But remember, my random word of last week, monkey, why does it say retry instead of positive integer here? So this is [Inaudible] to get int. So as the name get int implies, get int will do its best to get an int from the user, but it doesn't guarantee it's going to be positive or negative or anything like that. It just gets you an int. So turns out we can implement this same function in a really interesting way that hints at the beauty of this thing called recursion. A function is recursive if it calls itself. Now on first glance or first hear that might be a little worrisome. If I'm a function and I got called with an input, and I try to solve that problem by calling myself, that should immediately should infinite loop, bad stuff happens. But hopefully there's some way of making sure that you don't keep calling yourself in perpetuity, and there is. It's called the base case. So notice this implementation of Signa is only four lines of code, and frankly, if I got rid of some of the indentation, all that, it's maybe like a two line program, maybe a one line program that implements exactly the same function, exactly the same formula of adding numbers together. So what do I do? On input M I ask myself is M less than or equal to 0. If so, just return 0, because bad things will happen if I start trying to deal with negative numbers. Now apparently all I need to do to answer this question is call myself. And this is where you get this weird sort of circular magic. Notice that all I do otherwise, after my base case, after my sanity check, is return the result of M, the value I was passed, plus sigma of M minus 1. Now that alone actually works. If I go back to my terminal and I compile sigma 2, and I run sigma 2, and I give it the number 3, I get back 6. If I give it 10, I get 55. In fact, it works, and yet how is it doing that? Well, let's see. So it turns out that this problem of adding all the numbers from 0 on up on M, or equivalently M all the way down to 0 is pretty easy, even conceptually. If you hand me the number M and ask me what's the sum from M down to 0, well, I could say, all right, well, it's M plus the sum of all the numbers from M minus 1 on down there. All right, so let me ask you again. What is the sum of M minus 1 on down to 0. Well, it's M minus 1 plus the sum of M minus 2 all the way down to 0. Right? You can be this really argumentative human pushing back on the person in wise-ass form, oh, well, it's just the answer of M plus the rest itself. Well, what's the rest of it. Well, it's a little bit less than the rest of it, plus the rest of that. Right, you just keep taking this bite, this bite, minus 1 out of each piece of the puzzle. And that would seem to go on forever, but not quite. Because eventually when I get over here, my last piece of the puzzle is going to be M equals what? Zero. And that's when I hit the so-called base case, when all of my answers now start to bubble up. In a sense, I was kind of passing the buck by playing this game with the person asking the question, well, what's M plus all the numbers below it? Well, it's M plus the sum of all the numbers below it. What's the sum of that, right. Eventually, we bottom out at zero, and then I finally start getting useful answers back until the M result is precisely the same. But what's been the point of all of this? Well, and again, this is something that you perhaps begin to see eventually, and maybe you never see, but there's kind of a beauty about expressing something as silly as addition of numbers with just this recursive scenario. And this will be a very representative approach to solving much bigger, much more interesting problems. But there is a catch. Let me go ahead and run sigma of one, my first version, on 100. That works pretty well. How about 1,000. Works pretty well. How about 10,000. Still working. 100,000. All right, then eventually I'm going to start to exhaust an int. Okay, so now I exhausted the int, but we would expect that. Let me try now to run sigma 2. So it's a more elegant solution, feels like it should be even faster because there's just frankly fewer lines of code, well, let's see what happens. Sigma 2 -- oops, 10. That works, how about 100. That works. How about 1,000. Still working. 10,000. All right. 100,000. Okay, come on, break. Oh, now some of you have seen this problem too. And we actually smiled. So in all fairness to the anonymized student asking the question on the bulletin board, is it okay if my program quits by saying segmentation fault, [Inaudible] dump. No, so this is a bad thing. Bless your heart for asking, but this is not a solution to the problem. This is, as I said in the bulletin board post, frankly -- or maybe -- actually, maybe this was a private e-mail, as I said in my response -- as I said in this response this is sort of the LINUX equivalent of Microsoft Word just hanging, or your Mac program just freezing or unexpectedly quitting, which is ever so annoying. This is sort of the equivalent in the LINUX world. But fortunately, now that we're the programmer and we're not just the user, the fact that it's dumping core, so to speak, is actually useful. So for today's purposes, segmentation fault means something bad happened with respect to memory. Because memory in your computer is generally modeled as a bunch of segments, so a segmentation fault means something went awry with regard to memory. Core dumped means that something useful was left in my current directory. If I type LS for list, notice that I have this file called core. Core is actually a file containing pretty much the contents of the computer's RAM at the moment in time when my computer screwed up. Now it's not all of the memory from all users on the system, because that would be a security concern or privacy concern, but it's diagnostically useful, we'll see in a week or so once we start dissecting the insides of that file. But for now the question is quite simply why it this happen, why did it not appear capable of handling the same number of zeros as the first version. Now granted, the first version, still broken, but it doesn't ultimately choke in the same horrific way. So what is happening in sigma 2 that's not apparently happening in sigma 1. And again, some of you have tripped over this, and frankly, by the end of the semester you will all have core dumped. Why? What might be going wrong here? So it has to do with memory. Where is memory getting used in this program. I don't even see any local variables other than the parameter called M for this function. So where's the memory getting used. Like, why do I have memory problems? Yeah, so when I call M -- when I call sigma does what? 

[ Inaudible audience comment ] 

>> So it makes -- so it allocates a bit more memory. In fact, let me remind of this little picture from last week, and we said we'd come back to this. This recalls the rectangle that represents your computer's RAM. But recall the more important point from last week that any time you call a function a little chunk of memory does get allocated on the so-called stack for that function. And that chunk of memory we call a frame, so if sigma is called by name and then sigma calls who in version 2? Sigma. And then sigma calls sigma, and sigma calls sigma, you know, even though on this picture I've not implied that there is an upper bound on the amount of memory you can allocate, but in reality there is. On a typical system, a given program often cannot use any more than say 2 gigabytes of memory. Now that's a lot of memory, but not necessarily for programs like Photoshop, and so there actually are some interesting real world implications here. But the point is that rectangle eventually has a top to it. And if you keep trying to put more and more stack frames on your memory stack, eventually you're going to overlap with something else that needs it more. In fact, what did we say is at the very top of this rectangle, if briefly, last week? Sorry? 

[ Inaudible audience comment ] 

>> So there's a bunch of -- there's global variables, but there's also the text segment, as we called it, the program itself. Your zeros and ones of your program itself. Now this doesn't mean that you're overwriting your program on disc, it doesn't mean you're erasing your code. But it does mean that the operating system is just going to bail all together if you try using memory that already belongs to something else. So let's go ahead and end there, and on Wednesday we'll figure out how to work around this. 

[ Background noise ] 

==== Transcribed by Automatic Sync Technologies ====