[ Silence ] >> Alright, welcome back to CS50. This is the end of Week 3. Couple of announcements, if you still need to make any changes to your section please do so today. You can email help@cs50.net otherwise follow the directions that were in the email that the bot sent you this weekend with--regarding your section assignments. A few invitations, as well, so Zynga makers of Farmville which may appear a little too often in your Facebook walls is here today 6:30 p.m. in a recruiting capacity in Maxwell Dworkin 119. Maxwell Dworkin for those unfamiliar is the CS building down the streets on the left, on Oxford Street. It looks like there will be free food and free giveaways and bring resumes and win an HP Mini Notebook. So, that's 6:30 today. For those of you looking for interns or full-time roles, Brian Kernighan, is the man who thought me CS50 years ago. He is a faculty at Princeton and he's here on sabbatical this fall and he's actually gonna be giving a talk tomorrow and giving out ice cream. Tomorrow at 3:30 p.m. will be ice cream in Maxwell Dworkin which is actually a weekly tradition over at the School of Engineering followed by his talk at 4 p.m. I remember this man, frankly because his first lecture far out--has far outshined mine. He stood up on stage, had apparently spent the summer growing a nice beard, and then his algorithm was not putting on socks but was how to shave using hedge clippers. It's something that stays with you for some time. But the talk he's giving on Thursday for those of interest and realize, too, as if my being in 50 now is any indication, he's very much adroit when it comes to speaking to nontechnical or less technical audiences. Do not fear we'll be over your head. "The Changing Phase of Programming" is his talk tomorrow. The rapid evolution of languages, tools, environments, and expectations presents major challenges and opportunities for programmers and for software engineering education. This is true across all kinds of programming but is especially true for web systems which are now routinely written in untyped scripting languages and include Ajax, Mashups, toolkits, frameworks like Rails and Django and a profusion of interfaces all operating asynchronously on distributed systems. Few new pieces of jargon there that we will touch upon towards semesters and the growing popularity of phone applications has not made life easier for programmers or instructors. For the past 10 years, I've been teaching a course on advanced programming techniques that is more and more stretched between important old material and new unproven material that might be important. In this talk I will illustrate some of the challenges and discuss ways in which we might use complexity and rapid change to advantage. He's a wonderful man and a wonderful speaker to be honest. So if you have some time tomorrow for a little ice cream and talk, please do feel welcome to join. And finally, Facebook. Facebook is a social networking website. [Laughter] They will be here on Monday in the form of Thomas Carriero, who's one of CS50's former head TFs, also in a recruiting capacity. Lunch will be served. For those unfamiliar or for those a little intrigued by the opportunities that await in Mountain View, Facebook is hiring brilliant engineers who want to make an impact as we grow and shape the way the world connects and shares with each other. No one has ever done what we're trying to do at such speed and scale on top of that we do it with only about 500 engineers. Our active user to engineer ratio is over one million users to one engineer, and growing. You won't be able to get that personal impact in any other tech company in the world. So if you'd like some lunch, if you'd like to reunite with an alumnus and like to hear a bit more about Facebook before class, Monday 12 p.m. Maxwell Dworkin 1 not G119, 119 which is one floor up upstairs. Alright, so we left off last time with a whole bunch of pieces of paper on the wall and the challenges of the day, were here's in a array and unfortunately was unsorted. These were just semi random numbers in some random order and the challenge at hand was find the number 50. Now, a reasonable person as we--as a reasonable person we might start at the left and then move our array right word and you might start to realize like this is a bit of a game and jump ahead at some point. But for the most part, you can't do much better than good luck when it comes to searching an array of unsorted integers. You might have some heuristics but again but at the end of the day, if you don't know anything about those numbers it really is just guess at work. Now in fairness, it was deliberate on my part that I put 50 all the way over here just for demonstration's sake, but in the real world that very much could happen and one of the themes today in moving forward is gonna be this notion of worst cases, worst possible inputs. And in the worse possible case in that small problem the thing I'm looking for is all the way at the end which means I have to do a huge amount of work just to find a single value. Now thankfully there're approaches that are more intelligent than that. When we did this in the first day with the phonebook and we did it last time with this second array of numbers and the key difference there was that the second array of numbers was sorted and this simple little detail was a huge advantage. Right, in the real world, you can imagine the nightmare it would be if Horizon just published a big book with numbers in the order in which people signed up for telephone numbers, right, from left to right. Whether you have to search the whole damn phonebook or at least half of it on average to find some random friend whose number you're looking up. Well same here. If you don't know anything about the numbers, you ultimately might have to check them all but not the case if those numbers are actually sorted. And so one of the questions we'll look at today is if you are given a seemingly random sequence of numbers not even certainly that large, what are your options for actually sorting this? Now, we'll use numbers because they're easy to talk about but in the context of Facebook for instance, you might wanna sort your friends. You might wanna find friends of friends. In the context of Google you might wanna search or sort web pages so certainly could you apply what we'll look at in this small context of numbers to really any type of objects that you can impose some sorting on. But first, some new tools for your toolkits, thus far printf has probably been your primary tool for debugging. To debug a program means to find the bugs and remove them or to chase down logical errors that you might have made or even syntax errors that you might have made. Now, if you've made a syntax error that is, the characters you've typed at the keyboard just don't belong where you put them, you put a semicolon in the wrong place, you forgot a parenthesis. Well, GCC nicely enough will just yell at you before it even finishes compiling telling you I can't compile this 'cause I don't know what you mean. You've expressed yourself in an incorrect way. But very often will you actually get your code to compile and you'll be able to run it and then you'll get segmentation fault, which we've seen already it refers somehow to memory and more on that next week as well. You might just get the wrong output, you might get the answer, you might get no answer or whatsoever, and at this point your code yes compiles but it's surely not correct and so you might go back in as you have been and sorting printf statements here or there, printing the value of this variable, printing out what the user just wrote just to do some sanity checks for yourself and presumably you delete those printf statements before you actually submit and call this program complete. But this is a little bit hackish, right? And its programs get longer than a few dozen lines, a couple of hundred lines inserting printf statements all over the place and then recompiling your code, rerunning it, going back and changing the printf statements. This really isn't the happiest workflow. It doesn't scale very well and it's just not very interactive. You have to kind of do--make the change, compile, run. Make the change, compile. This is three steps just to accomplish a relatively simple goal, which is find my problem. So thankfully, there exist tools. And one we'll look at today is called GDB, the new debugger. This is a program that you run at the command line just like GCC itself. But what happen is once you compile your program with GCC you of course get your executable, your binary the program like a.out or czar or whatever the program is called. What you do with GDB is you run GDB but pass it. Your program is an argument and what GDB does for you is essentially runs your program for you line by line by line but slowly so that you can watch things happen step by step and you can set what we'll call breakpoints which is to say, if you only wanna see what's going on at line 20 'cause you're pretty sure that's where you're having some issues, you don't have to step to the first 19 steps. You can just say break at line 20, enter, then run the program. It will run terribly fast and then pause at line 20 for you to then poke around at what's going on inside the computer. So it's gonna feel a little arcane at first. In terms of interface, you'll find a nice cheat sheet on CS50's website on the resources page. But what I thought I'd do today and you'll see in sections in the weeks to come are some new tricks of the trade and to be honest with just a few commands that I'll use myself here, you can get a lot done. So I'm gonna go back in time to a program we used last week which was called Buggy3. As the name implied it was in fact buggy not because it didn't compile or because there were syntax errors but what was the problem with this swapping program if you recall? >> It didn't actually swap. >> It didn't actually swap, right. I claimed this swapped 2 numbers and yet we dug in a little deeper, right? I used a printf ad nauseam here and it did actually swap those numbers when I added a printf at the very bottom of my program here but then as soon as the program--as soon as swap the function returned--just looking for my laser pointer, as soon as swap returned it seemed all the hard work we have done was for nothing and the values remained unchanged in main. Alright, so this is an approach that you might reasonably take with printf, printing out every thing you wanna see line by line and then as I did too, once I was done I deleted that line from swap 'cause I don't want it printed out all over the place. I just wanted it to print it out for debugging techniques. Well, let's do this instead. Let me go ahead and quit nano. I'm gonna go ahead and make Buggy3. And notice this. There's a whole bunch of stuff that's been flashing on the screen in the past few couple of weeks and some of them we've talked a little bit about for instance -LCS50, it's wrapping from over there. That of course means link in CS50 library, -lm, little sanity check is the math library. >> So you can use functions like round and a few others if you need them. For those doing the hacker edition, -lcrypt means--so use the crypt function. So for those tackling the hacker edition, it involves cracking or decrypting passwords and there exist a function called crypt for that and it is among other functions in a library called crypt. Now, what's this other stuff? Well, some of these things are flags, as we call them, that have been configured by us. We've pre-configured Make on the cloud for you. And though you might resent us for this -Wall or rather -Werror means even if there's the slightest syntactical mistake in this program or thing you really shouldn't do, yell at the student and refuse to compile the code. So, this is deliberate in that it really forces you to get things perfectly right but there are some side effects. Some of you might have gotten annoyed at the computer or at us because you declare a variable X and you're not quite ready to use it yet. You're just, you know, you wanna use X but you wanna write some more code first and it won't let you even compile 'cause you're not using X. Well again, this is a pedagogical tool and it's also frankly a matter of good practice because there's too much code out there, too much code that's vulnerable out there that just hasn't been as rigorously checked as this little configuration options allow for. Now, for today, we're taking--making use of this guy over here, -ggdb is a flag that we've been secretly including and make all this time. But what it does is I think I said a couple of weeks ago is it adds to your program. You're a.out, your czar, some additional bits that re-help a program like GDB follow along where you are. It includes things like line numbers essentially. So that when you're walking through what is otherwise just a file with 0s and 1s, there're still some reminders inside your file as to where those 0s and 1s came from. What original line, so if you are still in a habit of running GCC manually at the prompt, that's fine but henceforth if you wanted to use GDB, you're gonna have to include this flag as well manually. So, we're all ready at the point frankly where you might as well just be using Make 'cause it automates all of this for you and saves you a whole lot of typing. So now, I'm gonna go ahead and run the program itself which is called Buggy3. And of course, it seems to in fact be buggy. And here are my printf statements that seemed to be confirming that it is not in fact working. And just to be clear, let me go back in nano Buggy3 and recall that what we did last time was I did a little sanity check. I said, printf A equals percent D, new line let's say, comma A. So I wanna print out the value of A and then I wanna print out the value of B. So this was my sanity check. So I'm gonna save, Enter, I'm gonna recompile with Make, and I'm gonna re-run Buggy3, and sure enough it seems to be working. It starts off at 1-2, becomes 2-1, but then reverses back to 1-2. And this is how we concluded definitively. This thing is not working as intended. So let me remove these superfluous printf statements 'cause again, this isn't the best habit long term to get into. Let me recompile, so I have the freshest copy. But now instead of running Buggy3, I'm gonna run GDB space Buggy3 and then Enter. You get a whole lot of stuff that's pretty useless, just warrant the information and all this but then you get a GDB prompt. Alright, at the GDB prompt I get to do a few things, among them run my program. So one of the new tricks today, and again all this is documented in a cheat sheet on CS50.net/resources. I'm gonna hit Enter. It apparently runs your program, so not all that useful yet. I could've done this, you know, a second ago at the original command line, but notice this as a teaser. When a GDB tells you program exited normally, it turns out that means that main returned what? >> Zero. >> Zero, right. So as promised, returning 1 or 2 or 3 or 0 for success cases in main thus have utility when you're using tools like this so that you can actually see what's being returned or be informed that it in fact all was well. So this was not all that useful though, just running my program, I wanna know what's wrong. So I'm gonna go ahead and do this. I'm gonna type break and then I'm gonna type main. What' nice and let me move this up to the top, I'm gonna type break main and this step is what's called a breakpoint. A pause point in the program at the function called main, notice I get a slightly cryptic output which is breakpoint number 1 is now at OX, and what does this mean perhaps? [ Inaudible Remark ] >> Yes, so this is the address in memory. So we'll talk more about this overtime. Frankly, it's used for silly things, like photoshop, colors, and web colors. But hexadecimal notation is just another base system like binary which we've discussed, decimal which we've grown up with, 0x typically denotes hexadecimal which is base 16, and as we'll see this is just a more compact way of representing numbers so that they don't get ridiculously long. So this just means in RAM, in my program's memory space, in RAM lives a function called main, the so-called text segment from last time but more on that to come. And that is where it happens to live, is this relevant, not so much for us just yet, but as things get more advanced then we get more savvy, certainly details like that can help. But for us, it looks like we've set a breakpoint in this file at line 21 'cause that's apparently where main began. So now if I run and hit Enter, notice that execution does break at line 21. So again, the output is a little cryptic at first but this is just telling me what happened. This is saying, here's line 21, here's what's on line 21 but it hasn't executed line 21 yet. In fact, it won't until I actually hit the command Next. So I'm gonna go ahead and hit Next and now I'm on line 22, X has already been assigned the value of 1 and which I confirm by typing the command Print, so it is not printf or anything like that, there's no parenthesis. These are just commands in a program, not functions, print X, Enter. And in fact, X equals 1. Now as this thing here, the dollar-sign notation is just handy if you wanna get fancy and refer back to the same answer later on, kinda of like in a fancy graphing calculator allows you to do. But for now, what we care about is that the answer is 1. Meanwhile, if I type print Y--well, that's weird. How did Y become 3,223,540? What--'Cause we haven't initialized it yet, right? So this is 1 already. A visual lesson that if you don't' initialize variables in a program to something, who knows what they're gonna be. This computer, the clouds have been on for several days time. Even this program did some other stuff when we first started it up, on--but known to us or that we didn't see visually. And surely the program might have used some of the memory that's allocated to my program for other purposes if temporarily. But now Y happens to live at a certain location and it just has this garbage value, a meaningless value that I should absolutely not trust is anything legitimate if I haven't assigned it a value explicitly as I'm about to in line 22. So even though I typed a few commands, I have not preceded to continue executing this program. We're still at line 22. So now if type Next or if I'm getting a little lazy with keystrokes, you can just type N, the first letter or two of each command, N. Now I'm at line 24. So now if I do print Y, I should hopefully see in fact the answer is 2. And again, ignore the dollar-sign stuff for now. It's what's on the right hand side that's interesting. Alright, so if I now type, oops, Next again, this printf line is going to execute. So I'm gonna see the programs output commingled with GDBs. Alright, so there it is. X is 1 on the left then I'm at line 25, let me go ahead and I'm gonna scroll things up to the top so you can see in front. Let's type Next again, Y is 2, I claim in the moment that we're swapping dot, dot, dot, so let's do Next. Alright, so here's an interesting decision point. This is a function call. I am about to on line 27, call the function Swap, which I wrote. Remember it's lower in the file, called buggy3.c. I'm about to call this function and so I can. I'm gonna go ahead and do Next. That function will execute. Something will hopefully happen to X and Y, let's check. Print X--uh-oh, print Y, still nothing. So that function seems in fact to have had no effect. Now, this was not all that useful in exercise 'cause now my program is pretty much done, right? I claimed swap, I then claimed that X is something, Y is something. I now hit this curly brace. I hit Next again. Now I'm this weird part of my world because remember I've used other functions, I've used printf and the like. So don't get distracted if you see stuff that's clearly not yours. I know I'm at the end of my program 'cause I already saw this curly brace pass me by. So I'm just gonna go ahead and type continue which undoes the effect of brake, it just says, "Keep going. Forget about this breakpoint. I'm done caring. And now, I'm in fact done with the program." It finished up whatever leg work it needed to do at the end. Alright, so this was not all that helpful. All I did was very slowly discover what I'd already discovered before with printf but here's the power of something like GDB, let's redo this. Let me rerun Run. It's gonna automatically start at the beginning. It still have that breakpoint, so I'm gonna hit again. And now let me step through a little more quickly. Next, with N, next, next, next, next. Okay, here's an interesting point. Now I wanna step into this function 'cause what's powerful about a debugger is you can poke around anywhere you want in your program. So I'm gonna type a Step instead of Next. Step means step into this function whereas Next means step over this function while still executing it, Enter. And now notice what I get as output. I am being informed, okay, I am in the scope as we've discussed of swap. It was past these two arguments, A is 1, B is 2, and the line I'm currently paused at is line 41 of my program. So here, too, it's helpful if you have two terminal or two putty windows open, have your source code in one, have GDB in the left hand one and you can watch things progress in the big window. So, let's see. This is swap. Actually I can also type List if you wanna see in the context of GDB, what code you're currently dealing with, with the line numbers on the left hand side, but I'm on line 41 as this thing here says. So this is uninteresting at the moment. So let's do a quick check. Print the value of temp and let me move it to the top. I'm gonna print the value of temp, alright 0. >> So it may be the case that just by happened stance a variable seems to be initialized to some value very often 0 but that's clearly not a guarantee. So do not trust that. So now let's go ahead and type Next, execute that line of code. So now if I print temp, it should be--if you recall I passed in 1 and 2 and I assigned it the value of A. So in fact, yup, it's 1 here. So a--temp is currently 1. Now I'm gonna clobber the value of B. So let's do quick sanity check. Print A, print B, and that's consistent with what I passed in to swap, but here we go, we're about to execute line 42 and I'm gonna do this just by typing Next. Next. Alright, so now I'm gonna do it again. Print A, print B, and there it is. So we are half way through the swapping process 'cause now A and B happen to be the value of 2. Now what can we do here? Well, I can go ahead and just say, okay next, next, I'm kinda losing interest in this and so as soon as that function returns, notice it reminds me, I'm back in main, I'm at line 28 and you're about to do this. So in short, you have this power with just a few commands, Run, Break, Next, Step, and Continue. You can do a lot of useful things. And there is yet more that we'll look at in this section and is documented online. But let me show you one last trick that's not terribly useful for this program 'cause it's so short but when we start writing programs that have multiple, multiple, multiple functions that you wrote, that get called in succession, watch what you can do. I'm gonna hit Run and because it's not finished, it's gonna yell at me start it from the beginning, that's fine. I'm done with this iteration. So, Y for Yes. I'm at the top of my program, I broke in as usual. I'm gonna go ahead and type Next, Next, and you can do up--use the up arrows as before. Next, I don't wanna take Next here. I wanna hit Step to dive in. And now suppose this is a reasonably sized program, I'm actually getting disoriented with where I am, what I've stepped in to and what not, that's fine. You can do a little sanity check, you can type the command back trace. And as the name implies, it kind of looks back in time at where you came from and what it says is this, the place I am now is the first line. I'm in frame 0. So I'm in swap, I past in this variables, and that happens to happen at this line. Where did I come from? In other words, how did I get to that line of code? Well previously, in the other frame that is currently in may RAM, I started in main. So the reason this prints kind of in reverse order is actually consistent with that picture we drew on the board the other day. When we talked about RAM having stacks and frames that grow like this, it's the same idea. Notice that main is on the bottom and swap is on top. So if swap itself calls a third function, it is gonna be located in RAM up here. And so pictorially it's pretty consistent. Okay, so a bit of world wind tour. The next couple of problems that will encourage you and walk you through the process of using this to the extent you need it--but any questions on the usage, the concept, anything? Yeah. [ Inaudible Remark ] >> Absolutely, you don't have to set breakpoints only at main if you have a function called swap, I could have typed the break swap. Or if I again know that there's a certain line I care about, I could even do this, break line, let's say 23, 'cause I care about line 23. Then when I type Run, it will start running from the top of the program as usual but stop at that specific line. So it's actually quite versatile. Yeah. >> Can you break continue then break again? >> Can you break and then continue again, yes. So the--yes. The continue command is useful also in the context of loops. Because if you set a breakpoint somewhere in the middle of a loop, you might get bored with typing next, next, next, next, next throughout all this lines, you really just wanna get to the next iteration or the next iteration. So if you type Continue, it's not gonna run to the bottom of the program, it's gonna run as the logic of your code suggest. So it will iterate in this loop and if you hit that same breakpoint again, you will in fact pause. Now if you're iterating a hundred times and you only care about the 99th iteration, this could very quickly get tedious. But you'll see in the online PDF, you can say like continue 98 times and then break. So again, you pick up little tricks along the way. Any other questions? Yeah. [ Inaudible Remark ] >> So you can't start execution at a certain line. Your program has start at the beginning but you can break at any line. And break just means pause here so I can poke around and then it's up to you to decide if you wanna continue execution by hitting Next or Continue itself. [ Inaudible Remark ] >> No, so your--if you wrote the code here, you're gonna have to execute it from here to here. You can't just say start running my program at a different point. Alright, so that's a little tool for your toolkit, so to speak. It might very well be useful for this P set if you're not yet done or not yet started. But for the next ones and ones moving forward, it's one of this things honestly where statistically many of you probably won't take this advice for at least a couple of P sets but this is one of those things that certainly in programing where if you spend that frustrating first 30 minutes, maybe an hour of learning something like this, it will absolutely save you 10 times that much time by semesters end. But when you get comfortable with this stuff, printf is not going to be your best friend for very long 'cause it's so terribly limited and so terribly tedious. So invest this time, this week or next just learning some of the basics of GDB. And honestly, it's one of those things that will absolutely help you help yourselves and in the end save you time for sure. So here are some numbers and the goal at hand is to get to the point of actually having these numbers sorted so that we can actually find pieces of data more efficiently. Now again, I've chose some fairly simple numbers here up on the board, you could imagine gaps in them like we had on the chalk board on Monday so that they're not just evenly spaced by 1 number apart and you can certainly imagine each of this things representing a web page or name in the phonebook or anything that will lends itself to actually being sorted. But how do we go about sorting something like this? Well, a human probably will just kind of scan the list and say, alright, there is the number 1, let's move that, there's 2. And we all have some kind of intuition behind how you sort this numbers just as a normal person probably already knows before taking CS50, how to find someone in the phonebook pretty intelligently, right. Before this class, odds are you were not starting at the begging and moving from left to right. But how do we begin to now express what we as humans consider to be intuition if not obvious in a way that the computer can now understand so that it can do our bidding using our own life lessons but far more quickly than we could ourselves. So if you don't mind, perhaps some fresh faces this time, I have 8 pieces of paper and need another bite of volunteers. If you'd hear me, come on up, 2, 3, no one ever wants to come up from up here. There you go, 4, 5, 6 and 7. Let me see if I counted properly, 1, 2, 3, 4, 5, 6, 7 okay, good and 8 in the red. Alright, so if you could, first part is easy. And you have to be comfortable on camera before you step on stage. First part is easy, line yourselves up and let's say over here, just so we have you all together in the same order as the projectors indicating now. Alright, thank you. Alright, so line up if you could in this way. [ Noise ] >> And so that you are not anonymous, we wanna say, who you are and one interesting thing which might mean concentration house, sports, extracurricular, whatever and just pass it down. >> My name is Chi [phonetic], I wanna do CS. >> Very nice. >> May name is Mar [phonetic] and I'm in the best house on campus, Eliot [phonetic] House. [ Cheering ] >> My name is Luis [phonetic], and I like yoghurt. [ Laughter ] >> My name is Daniel [phonetic] I also have the grand fortune of being in Eliot House. [ Cheering ] >> Hi, my name is Aziza [phonetic] and I'm in Eliot, too. >> Hi, I'm Carl and I'm from Leverett. [ Cheering ] >> I'm Ron, freshman from Canada. [ Cheering ] >> I'm Ian, I'm on the Alpine ski team. It's pretty fun. >> Alright. [Laughter] Alright, so, now you know these eight folks and we have a couple of approaches that we might take here. So I'm gonna propose one and then see if these eight can help me execute this method. So as a human, I might take the step back and say, alright, number 1, I'm gonna put you over here, number 2. But don't do that just yet, right 'cause it's kinda--there's this intuition that presumably all of us have and we can sort this list in a couple of seconds. Now ironically what we're about to do is probably gonna take more than a few seconds. But once this input gets larger than N equals A and as N equals a million or a billion or the like, surely some of this tricks will be again a leverage to our advantage. So, I'm actually gonna point out first. If these folks are implemented in a computer, they're probably implemented not as 8 variables, X1, X2, X3 'cause we've already introduced arrays, odds are they're just called number and that--the size of this array numbers is probably 8 and each of them is an int inside of this array. But the catch is with the computer, I don't have this sort of god-like ability to just look out on them all and see--taking all of this numbers at once. I have to be much more deliberate. In an array, you can iterate from left to right, from right to left, you can jump randomly by a random access to any value inside the array by of the square bracket notation. But you certainly can't see them all at once. So just for visual's sake, if you guys can just turn your papers around so they're blank white on this side. I mean this really is what the computer is handed. There is 8 numbers, yes, but I certainly can't take some aggregate view all at once. I have to look more carefully. So go ahead and flip back the normal way and I'm gonna propose a very simple heuristic. I'm gonna start at the beginning 'cause it's just easy to iterate from left to right, I'm gonna look at the first 2 elements, 0 and 1. Index values, 0 and 1 and I see that the number 4 is at location 0, and the number 2 is at location 1, this is wrong, right. >> The goal at hand is to sort this numbers so you know what I'm gonna do, the simplistic heuristic I can come up with, I'm gonna say swap. Now, go ahead and swap. Now this took how many steps? Well if we implemented this in code, it's like at least 3 lines of code. We need a temporary variable then we need to clobber A then replace B and so forth. Now in fairness, our swap function is a little dysfunctional right now. We have yet to see a working version of swap but that's coming. In fact we'll introduce that in something called pointers next week that allows us to pass by reference and not by value or by copy. So let's take for granted today that surely there's some solution to this problem with swap, we just haven't done it ourselves yet. So I swap these two guys and now what do I do? Well, I don't have to look at them just yet in pair anymore, I can advance one step, so I plus-plus. Now 4 compared to 6 checks out. I don't have to do a swap so I can take another step, I plus-plus. 6 against 8, okay, plus-plus. 8 against 1, I need to do another swap. So that'll take a few CPU cycles. Now, you know, I could start backtracking because clearly 1 should be going this way but I'm gonna keep implementing the same approach, right. You wouldn't change your code in the middle of a for loop, it's gonna execute again and again in exactly the same way so let's do the plus-plus. 8 and 3, alright, plus-plus. 8 and 7, plus-plus. And 8 and 5, and now probably I do plus-plus. My for loops condition are my wild condition, what it is, realizes that I've gotten too big and so I reset to the start of this list. So it seems like I have a loop that's going this way, right, so that's I plus-plus, I plus-plus, I plus-plus. So I've looped through the whole array. So that would seem to suggest I'm done. I've looked at every value but obviously, no. So just intuitively, how many more times am I gonna have to come back to the end of this list much like a typewriter going back to the carriage return and go again. If I do it once more, will it fix the problem? >> No. >> No, so maybe--I feel like maybe 8 or so, 7 or 8 total times am I gonna have to do this because why is that? Well, intuitively, number 1 a moment ago was here. But how far did she move down the list with just 1 step. Now 8 made some pretty good progress so it seems like there is some asymmetry in the benefits of this algorithm. But again, anyone who is too small to be on that N is only stepping one at a time. It's but--these small numbers like 1, number 3, or bubbling up, if you will, pretty slowly to this side whereas 8 is already in place. So if that suggests in the worse case that 1 started over there, let's say, well each iteration of this loop, plus, plus, plus, plus, plus would number 1 just move 1 step which means I've got to go back here, do it again, do it again, do it again as many as 7 times or really N times. N being 8, give or take to this again and again. So let's do this once more and this time I won't deliberately go through all the verbiage, let's see if you guys can execute now down the line. So ready, this is iteration number 2. [ Noise ] >> Okay, now what do we do? So I reset. So it feels like if you're thinking this through, I'm doing plus, plus, plus, plus, plus, plus, then I'm going all the way back round, it feels like we just have a nested loop. You did this in scratch. You might have done this in C already, maybe with visionaire if you've already started that part. And even visionaire can be done without a nested loop. But it feels like a nested loop 'cause I'm looping again and again and again and then I've got this bigger outer loop that's bringing me back home after 8 or so steps. Alright, let's go the third round. Okay. Okay. Okay and now, what do I do? [ Inaudible Remark ] >> Okay, so I go back to the beginning. Alright, so hopefully we're almost there. Now, can I stop? Alright, so maybe intuitively, you might think, yeah, it's right. But again, you don't have that aggregate view. The only way we're gonna know if we're done is to keep checking pair wise, pair wise, pair wise, pair wise, pair wise, now am I done? So, visually yes, but on this iteration, I made a swap and unless I've added some very sophisticated conditions or checks all I know is I just made one swap. So surely, if I made one swap, I might not be done because maybe that number that I swapped has to bubble down even further. So really the only way to this for sure is to now do 1 additional pass and say, uh-hmm, uh-hmm, uh-hmm, uh-hmm. And now, maybe I have a counter, called counter. And every time I do a swap, I increment this by 1, right. And now, my counter is still just 0. So now I'd be stupid frankly to go back to the beginning and do this again, do this again, do this again. So that then begs the question in total, how many steps does this algorithm involve? How much work does this algorithm involve? Well in the best case, let's start with the easier one. In the best case, this group of folks did not line up like that. They lined up right like this. In which case, how many steps does it take for me, the computer, to sort N individuals. >> One. >> Eight. [ Inaudible Remark ] >> Okay, we have disagreement. Everyone here says 1, and this guy says 8. So which is it? Well, it kinda boils down frankly to semantics. What do we mean by step? Do we mean one outer loop, maybe, do we mean one individual, yeah, step maybe. I'm gonna say--minimally let's say 8. Because let's literally count any line of code that I execute or physically any step that I take. So to know that all of this folks are sorted minimally, I'm gonna have to check each pair keeping track of how many swaps I do. Still 0, now I can quit. Even though I was in a loop, some of you might have used a special instruction in C called break that will break you out of a loop. You might not have occasion to use this before but just because you say a loop needs to iterate 8 times or N times, you can break out if you want if just this situation warrants at any point. You could do this with scratch, too, with the stop all or stop script block as well. So now, what about the worse case? Well, what was the worse case? If you guys don't mind for the visual, can you arrange yourselves in the worse possible case? The worse case in not random, right? Actually, worse case for our purpose is, is the most amount of work that I might have to do to fix this problem. Now in fact, this is the worse possible case because now, everyone is in the wrong position. And in fact, number 8 is way the heck over here, number 1 is way over there. This is the worse possible case. That was actually somewhere in between, best and worse, how many steps now is it gonna take me to sort this folks. [ Inaudible Remark ] >> So 64, if you count it up. And can we generalize if these are actually N individuals, as oppose to 8 specifically? [ Inaudible Remark ] >> And so, N squared. And where does this number come from? Y N squared, N times N. Oh, what's that? >> Inner and outer loop. >> Yeah. So it's this inner and outer loop. The inner loop is obvious to see 'cause I keep taking all these steps across the stage. Every time I check for swapping opportunities, I'm taking 8 or maybe 7 steps but for simplicity, let's just round up to 8 so we don't have to do N minus 1 all the time. Let's say this took 8 steps to get here. But now in the worse possible case, I'm gonna have to reset myself like a typewriter all the way back to the beginning with one more time then another time, then another time. And if number 1 needs to move, let's say 1, 2, 3, 4, 5, 6, 7. If number 1 needs to participate in 7 swaps which is really almost 8, so let's call it N or we could really be fanatic and do N minus 1, that's N swaps. So in each iteration, she only moves maximally 1 step. She only bubbles up a little to this N. So to get here all the way here, I need to take N steps this way and I need to do that as many as N times round. So in the worse case to sort N individuals with this algorithm it would seem to take, give or take N squared. N times 2 number of steps. Now 8 times 8, 64, that's not that bad, right. It felt like the intuitive human way was a little faster but N squared isn't that bad but what about when N is not 8 but 10. So that's 10 squared, that's a 100 or 100, 10,000, now we start getting a very and very quickly to much larger scarier values and this feels like it could very quickly start consuming a lot of resources. So can we do better? Let's try one other approach. If you guys could reset to this random approach, so we don't always consider best case worse case. Let's see if we can't do something a little different. So that was the simplest most naive algorithm I could come up with a sort of a newbie computer swapping the things that I see next to each other. Let's try to leverage the common sense that most of us have, that all of us have in this room when it comes to finding the smallest number. And let's just grab the smallest number then look for the next smallest, then look for the next smallest, right, 'cause odds are when you glance at this numbers and you're told to sort them, you probably latch on to the number 1 first. Maybe the number 8 if you prefer to work backwards, but at least the number 1 then 2, so let's see if we can't leverage that. So again visually, if you could flip your papers around, this is what the computer sees in advance. I just know there is eight elements, I can't see them all at once. So now if you could go back to normal, now, I'm gonna be the computer and I'm gonna look for the smallest possible value. Alright, so 4, he is the smallest possible value at this point in time. So I'm gonna make a mental note. Or in computer terms, I'm gonna use a variable to remember 4 is the smallest and he is at location 0. Alright, oh, disqualified. He is no longer the smallest value, I've now found number 2 at location bracket 1, now I'm gonna remember that and I'm gonna forget about him. Alright, 'cause it's a lot easier to keep track of one number than two at once. So now, I keep looking 'cause maybe your not number 1. So umm, you don't change my variables, definitely not. One, we've already ousted number 2. So here is the smallest possible value at location 0, 1, 2, 3, at location 4, so I should remember that. Do I now know I found the smallest? >> No. >> Alright. So not--technically no, visually obviously. But technically no unless I was given an assumption, here our 8 numbers, the smallest number is 1 but I was just given 8 numbers in random order, the only way I know, number 1 is in fact the smallest is by continuing a total of 8 or N steps. But now what do I do, I remembered with some variable that she's at location 4. >> So what can I do? Well unfortunately, this is an array. An array thus far re-fixed the size. When you create an array as we've seen like an array for quizzes, we said two quizzes go here. And we used the constant at that time. And in fact in C, unlike some languages like PHP and JavaScript we'll see, when you declare an array it's a fixed size. Now this is a problem because I might wanna move number 1 to the start of this list but there's no room. Alright, I only have 8 slots I have 8 numbers. I can I have temporary variables so I could hold you out if you will from the array leaving kind of a duplicator or a gap in it so what, what are my options? How do I move number 1 to her appropriate place? So I could swap, right? What could I do? You know, he doesn't' need to be there, right? I definitely don't need number 4 there or really in general any one other than 1 there. So why don't I do that? And actually before I do that, what's an alternative before we correct--do this right? Alright, I could just--guys could just--that way, yeah. But wait, that looks obvious, looks intuitive but that's 1, 2, that was three steps 'cause each of these variables or each of ints has to be moved deliberately by the computer with a line of code. So that's three steps to move these guys over, maybe 4 to move him over as well. Let's take the simpler approach. 4 again doesn't need to be there. This numbers we given to me in random order. Who cares if I mix them up even more if I don't care where they are just yet. So let's move number 1 over here, number 4 over there. And now this is 1 swap not a 3 or 4 total swaps. Now what do I do? Well at the back at the end of the list, now nicely enough, I can have a little optimization. I never again need to look at number 1 because I already have decided--[laughter] because I've already determined she's the smallest so it would just be a waste of CPU cycles to start here again. So I can maybe have another variable that says start this time at number 1. Not in number--location 0, start at location 1. So here we go. Number 2, I found him. He's already right here. But I don't know that necessarily. So now you might be thinking but why didn't you just remember this the last time and I could but that's a different algorithm. That's more memory. Right now I'm just using a couple of variables to keep track of who and who's where and what they are. So 2, is currently the smallest. So I'm gonna remember that. 6 doesn't beat him, 8, 4, 3, 7, 5, so that's another N minus 1 steps 'cause I didn't bother looking at number 1 again. So that's almost N steps. He is in fact in the right place. I don't have to do any work at all. Now, let's continue I can move my left boundary here. 6 is currently my smallest number not beaten by 8--oh, beaten by 4. 4 is now the smallest. Oh, 3 is now the smallest number. No, nope I made metal note of where 3 is, what do I do? >> Swap. >> Swap 3 with 6. And now I'll stop telling the story verbally if you guys, I'll just point, can execute now, so. Actually this really isn't very, very clear if I just point and say nothing. Okay, so [laughter] 4 is currently the smallest value that I found. So where do we move you? So we swap this. And again, it might seem that 8 is moving into his position and that is true 'cause presumably it is bigger and is moving up. But for the most part, these swaps are just moving random numbers to other random location. So we're not actually making the problem any worse fundamentally. So now 8 is my smallest. Oh, now 6 is, now 5 is. So 5, alright, it's good. And now 6 is my smallest, 7 is my--6 is my smallest, 6 is still smallest, 6 is still smallest and so no swaps. Now I do the same thing, the same thing so this begs the question. This was a little more a little real world, a little more human-oriented 'cause I just implemented my commonsense. I found the smallest number put her in place, found the next smallest number, put him in place and then repeat, repeat, repeat. So how much time, how many steps did this algorithm take? [ Inaudible] >> So it's not N factorial. It kind of feels like one of those expressions but that would actually be really bad, right? That's 8 times 7 times 6 times 5 times 4. That gets really big quickly. So it's actually not that bad. [ Inaudible Remark ] >> And log in, it's not that good. [ Inaudible Remark ] >> N squared, so you know what, it turns out it almost is. It's not as bad as this. It's almost N squared. It feels like we had some optimizations. We stopped looking at 1 then we stopped looking at 2 and we only took as many steps as we had to do and on each time I didn't just blindly swap. I actually looked for the optimal position for someone by plucking out the smallest and yet I claim now that this is still roughly N squared. Why? Let's take a 5-minute break, give these guys are round of applause and we'll be back in 5. [ Applause ] >> You guys can keep those. If you can just meet the TF over there, that'd be great. Okay, so the cliff hanger that we left off with was how much time the selection sort take, vis-a-vis bubble sort. So bubble sort we said pretty much takes N squared comparisons. So N squared steps rather is something like bubble sorts in the worst case--oh, actually I'm the only one who knows this bubble sort. So the first algorithm we looked at and I was kind of trying to hint it this just by using the--by saying bubbling this way, bubbling that way. But in this much as when we compare values, one of them might bubble up that way and the other one might bubble down this way. The world generally calls that first algorithm where we just did ParaWise swaps something bubble sort. And what's nice about it is you could actually code it up in any language very, very straightforwardly. But the down side is it doesn't feel like the most efficient thing. How slow is it? Well, we'll see and feel that in just a moment. But in the worst case it was in fact, N squared. But in the best case it was just N, right? In the best case, when I was handed all of the humans in the correct order, I just had to do a sanity check once down the list of N people to see, I didn't make any swaps, therefore I'd be foolish to do that again and again and again so I can terminate that algorithm early after just N steps. Now the second algorithm we did might be called selection sort. That's what the world generally calls it. In as much as you are selecting on each iteration the smallest value. And you could completely flip it around and just select on each iteration the largest value. But the algorithm would be the same in the N. So selection sort, it wasn't as clear at first what the running time is. What the performance of this actual algorithm is. But let's see, so with selection sort, to find the smallest element it might take me what? N steps. So I have to look at N values because number 1 might be all the way over here, then I swap but then I leave number 1 in her correct place and so now I move on to look for the next smallest element which might be in the worst case, where? Might be over here. But this is only seven steps this time. So it feels like an optimization is brewing here, right? Because one, I don't have to looking at it as I said. I'm just now looking for the smallest--the next smallest value which happens to be 2. I find him maybe worse case over here. I swap him. that takes just a single step or maybe three. And here's where I'll start to wave my hands at some implementation details. But visually swapping those two people we can think of that as just one step. It's one swap, one operation. So now I did eight steps to find number 1. Took me seven steps, worse case to find number 2. Might take me six steps then five then four, so it seems that we have this kind of process, 8 plus 7 plus and then down to 1 to find the very last person. Those of you who would like looking at formulas like this might see a little something like I equals 1 up to 8. Alright, so a little summation like that and what has this actually work out to be if you use that cheat sheet in the back of a--like high school math book? Alright, so if we actually do this out, 8 plus 7 plus 6 plus 5, I believe this works out to be N times N minus 1 over 2, is that right? Right, so how did I get to that? Well, frankly you can--What's that? >> N plus 1. >> And plus 1? Okay, N times N plus 1 over 2, I get the end result of a formula that's what? If I actually multiply this out well this is N squared plus N over 2. So you know there's an N squared in there. Is it N plus 1 or N minus 1? >> Plus. >> Okay, plus 1. So, N plus 1--N squared plus N over 2, now that feels better than N squared alone was, right? Because even though this is N squared plus N then I'm having it. So this actually feels pretty good, but here is the thing. When it comes to actually implementing algorithms and analyzing algorithms, it's in the context of computers, these kinds of constant factors like the number 2, this really isn't all that interesting. I might claim selection sort is twice as fast give or take than bubble sort. Because look, it takes half as many steps. Now again, N squared plus N, I'm kind of waving my hand at some of the terms here. But this, too, kind of means that you have the running time, the amount of time it takes for this algorithm to run. But you know what, who cares, right? Every year CPUs and consumer PCs seems to get faster and faster so that this year I might have a gigahertz computer, next year I'm gonna have a 2 gigahertz computer which means next year selection sort will be twice as good as it is today. Alright, so it's hard to make claims with algorithms that are just these constant factors better than one another. Because again, with the hardware you can kind of hide those details. What we really wanna do is find an algorithm that even if computer--if the computer speeds double next year, well, my algorithm itself gets even more than twice as fast. We really wanna ride the curve as best as possible. But for now, we're gonna wave our hands for a bit until we get more precise. And this is to say if selection sort takes N squared plus N over 2 steps, eh, this isn't that interesting. And you know what, even this term here maybe this is relevant when it's N squared, so that's 64 plus 8. That's an 8 additional units of measure more than 64. That's non trivial here. But what if now N is a billion? A billion squared plus another billion that's actually not all that much more, so relative proportion. So you know what, forget this. This, in the long term as N gets bigger, this is kind of a meaningless addition to the formula. So we're gonna claim for now that selection sort, too, in the worst case is actually pretty much comparable to bubble sort. >> Not if you line up the numbers precisely but at least big picture if you think in terms of large N and you compared the graphs, as we'll do in a moment, that this formulas make. You know, it's pretty much N squared. And in fact, there's a problem with selection sort. What if in the best case, I'm handed 1, then 2, then 3, then 4 and I try to sort those elements with bubble sort. How many steps is it gonna take to sort N people in the best case with selection sort? >> The same. >> It's the same, right? Because even though it felt like this nicely intuitive algorithm just keeps selecting the smallest possible value. Well, what's gonna happen in the best case. They're all lined up from 1 to 8. I find number 1 here and I say, okay, he's the current smallest then I find 2, uh-hmm, 3, uh-hmm, uh-hmm and not until I get to the end do I realize, we'll that was stupid I found him in the very first step, now let me go back to the beginning. I don't have to look at him anymore because now I have to look for the next smallest and so I'm looking now for 2, right. So now where's the next smallest? Well 2 is right here, but maybe there's 1.5 or something like that over there. I have to keep looking and looking and looking so here's the downside of selection sort. In the best case, it too is N squared so while it might feel more intuitive, it might feel like the more obvious algorithm, we've just made the situation worst 'cause I don't know in advance what these elements are. So let's add some nomenclature here that computer scientists are fond of using. There's a symbol that the world generally uses to describe what's called the worst case and this is the capital O, often written in italics so this is what the world generally calls big O notation. And if you say an algorithm is in big O of N squared that just means in the worst possible case if you handed everything completely out of order, it might take as many as this many steps. Now in the best case, we use a different symbol a Greek one this time, omega. Omega just is the fancy way of saying in the best possible case this algorithm might take N steps. So these two correspond to bubble sorts' worst and best cases. Now we can do the same symbology for selection sort and so we now have big O of N squared for the worst case, omega of N squared for the best case and just to toss out one additional piece of jargon if you say theta of N squared that just means it's essentially in both big O of N squared and in omega. So in other words, if these are the same, you can then whip out this notation as well, this theta notation. Now why do we use this? 'Cause it's just a nice shorthand way of saying best case, worst case and we can now start to talk about the efficiency of our algorithms. We can talk about the quality of their design in terms of their performance in a way that's not CPU specific. It doesn't matter if it's Intel Inside or anything else because now we're looking at a higher level than we have in the weeks past at the underlying operation. Swapping two things conceptually or stepping down an array conceptually. It's step after step after step. So let's see if we can't visualize a couple of these algorithms in a more rapid way than humans here allowed for. So this is a little program that's available online. We've linked to it on CS50's website. I switched over to one of the TF's PCs here because it doesn't work properly on a Mac unfortunately. The buttons don't appear on the bottom but that's fine just realize if you play with it on your Macs, you'll be missing some of the demo and notice that in the bottom left hand corner of this little applet, happens to be written in Java, I can choose a whole bunch of sorts and I've preselected bubble sort, that's the first thing we started with. You can specify what the array is gonna look like at first, you can specify a time delay here. I'm gonna go ahead and just click start and we'll see what happens. So what you see on the board now is just a visualization of what we did a moment ago with humans. Each of these bars represents a number. The taller the bar, the bigger the number, the smaller the bar, the smaller the number, so small bar might be 1, big bar might be like 100. And what's happening here in red is that this algorithm much like my feet on stage is looping from left to right, left to right on an each iteration it's comparing two elements making them red and then swapping them, if in fact they are out of order. And even though this is moving at a pretty good clip, you can see a couple of features here. One, it's kinda boring and it's kind of slow even though those bars are moving in a decent clip left to right but clearly visually are the larger elements bubbling up to the right hand side and gradually are the smaller elements bubbling down if you will to the left hand side. So it's almost done, almost done, almost done, almost done, almost done and it only makes them red when it actually swaps them, okay done. And down here if you're curious afterwards to the play with the demo in more detail, it actually counts how many comparisons you're making, how many swaps you're making and so forth. So now let's do this, let me go ahead and click stop here. I'm gonna change the algorithm to selection sort. I'm gonna use the same speed to be fair and click start and now less seems to be happening from unit of time, there is less flashiness but notice now highlighted in red is the smallest element just encountered and as soon as it's found, by conforming, by going all the way to the right, it drops it into place. So visually, this algorithm is working kind of the opposite direction. The end result is of course gonna be the same and it actually felt a little faster and it absolutely did fewer swaps because this time when we're swapping, we're really swapping it as far away as we want. We're not just doing these adjacent swaps but these too, if you actually count out the number of steps in the worst possible case, you'll see these numbers N squared. You've got 100 elements, it's gonna be 100 squared possible steps for comparisons or swaps and same deal for bubble sort as well. So that then begs the question, can we do different and why would we wanna do different? Well let me toggle back here to these visuals and see what the implications are for algorithms that are in fact N squared or just in general not so well implemented. So this is a little chart that I just I happen to make up with Excel. There's not all that much going--oh kind of not the best fidelity on the screen here but I'll point out the details that are actually important. Here--thanks, got it. Okay, so on the X axis here we just had N so this happens to be 0, this happens to be 33, 66 and so forth. It doesn't matter what they are just on the right--on that X axis, there's a value of N and it's increasing so this implies more and more humans or more and more numbers to sort. Meanwhile on the Y axis here, this is meant to be--depict time so and if you have 33 elements as this suggests according to this chart here, it's saying this takes 5 units of time and this means more units of time and if it's up here, that's even more units of time. So the numbers frankly are irrelevant, it's really the curves of these things that are worth considering for just a moment. So there's 3 different graphs here that I made with Excel. One represents N, so the little diamonds or the ones here on the left hand side and even though it's not going up at a 45-degree angle based on how I did the axes, it's obviously a straight line. An algorithm that takes N steps, means if you increase the number of humans or the number of numbers by 1, it's gonna take you 1 more step to count it. So consider for instance bubble sort in the best case. If I didn't have 8 volunteers but I had 9 volunteers well in the best case, it's gonna take me one additional step to count that--check that one additional human 'cause I just have to take one 9th step over here so that we can see as pictorially as this relationship here. Now suppose I come up with a smarter algorithm as I did in the first day of class. Recall that the simplest algorithm for counting all you guys is 1, 2, 3, 4, 5, 6, 7, 8, this takes a while but it's slightly faster actually it's twice as fast if I use that little grade school trick of 2, 4, 6, 8, 10, 12 and so now that algorithm is in fact twice as fast. It's still a straight line and that's what this one what the squares represent. So according to the axes, I've chosen here it's still a straight line but notice that it moves at a lesser gradient so that's good because it means as N increases the amount of time taken to count--the amount of time involved in counting people in 2s instead of 1 obviously is less than if you're just counting them one at a time. But here is really the end game, this thing here. So recall that the other algorithm we deployed in the very first day of class was that self-counting algorithm where you guys all stood up and half of you sat down, half of you sat down, half of you sat down so that we went from like 500 to 250 to 125 and so forth and so there were just one in theory person standing. Now, it will took a while 'cause there's a lot of social issues and coordination of all that going on but in theory, on each iteration that problem was getting halved, halved, halved. Just like the phonebook getting halved, halved, halved. Well, what does it look like when you halve a problem again and again and again. Well it looks like this chart here. When we describe that algorithm as logarithmic or log base 2 of N, this is what it looks like and again it's curves here that are interesting because it looks like if I'm counting people in Sanders, the naive way one at a time, I mean this is gonna take a ridiculous amount of time, the chart literally goes up to the roof. Now it's slightly better if I count you in 2s but even that eventually for large N, it's gonna take a ridiculous amount of time but if we use something like the divide and conquer strategy of the phonebook or as applied to humans having half of you sit down, half of you sit down, this is when this curve gets amazingly powerful, right. Literally, on that first day of class, we could have had like justice come back into Sanders, right, doubling--more than doubling the number of students in the room and yet the algorithm you guys were applying one more step, right, 'cause we could've made all of justice sit down the moment they enter the room and we just--right? [Laughter] We know that we've taken a bite out of the problem that's half as large as N itself. So this is really the sort of golden ring that you're after when you're trying to come up with the most efficient or the most alluring algorithm possible and the payoffs as this chart suggests are huge. This is one 130 here, this means if we have 260 students that's over here and then 500 or so over here, that chart or that graph rather is flat lining in this way far more so than these things. Now of course, we cannot sort N elements in log N time, right. Log N seems to be again what we're after. >> The holy grail of algorithms 'cause look how much better it is than anything we've looked at thus far. But I claim we can't sort N individuals in logarithmic time so neither of these algorithms were that good and I don't think I can come up with one that's good and intuitively why might that be the case? Why can you not sort N people or N numbers in the log base N of time? So clearly, yeah? >> So this at least gets you run through from the beginning to the end. >> Yeah. There's this one got to. You can't possibly sort any individuals in less than say N time because you don't know if they're actually sorted unless you actually check that list, right. Otherwise, it's guesswork. Now we--the humans might glance at the list, oh, sort it. But how did you do that? Well maybe unbeknownst to you or your brain, you actually did scheme that list at least one eye movement for each person up here so that's at least 8 steps. So this might work for searching and that's what we've--this might work for counting. I'm searching the phonebook, counting the students but for sorting we need to spend a bit more. Well, what would these algorithms feel like. We'll here's a different chart, a different axis but again it's the shape that we care about. So here is the same chart but we've given us more of a Y access. Here is what I will call N so this is--if you increase the number of students, your algorithm increases by 1. It's a 1 to N ratio here or rather it's a one to one ratio. Here is log base 2 of N so when you--right, this is how you can kind of mislead people with statistics and charts and consulting and all of this where I change your axis and look how N looks you know not all of that much worse than log base N--log base 2 of N, right. Your clients might as well buy the N algorithm, it's not all that much slower. But notice here if we actually are now looking at algorithms as we're gonna start to in class that take may be N log N squared or actually this is pretty rather--sorry. If we look at algorithms that take N squared time like bubble sort and like selection sort, I mean my God, if only we could sort N individuals in just N time. You really start to feel the difference again even irrespective of the axis. The shapes of these graphs suggest that if you can avoid N squared, you really should. In fact if we zoom out even further, there are some algorithms in this world that are believed to be exponential. This isn't even as bad as factorial, exponential here at top. If you have algorithm that takes 2 to the N steps which we may discuss briefly in time, for more on this CS121, CS124, I mean my God, this is absolutely an algorithm to be avoided because here you are like 200,000 or so steps and well, here is N down here at which point all of these algorithms look better and better, but this is the take away. When you start looking at problems like Facebook faces and Goggle faces and N is actually big, these are the kinds of curves that are particularly alluring for someone. So can we do better and how can we describe these things. Well, again we got big O, we've omega got and theta. Let's see if we can't describe yet another running time here but we need a tool for this. So, we have talked certainly about the phonebook. It's sort of ad nauseam at this point and that was an example of divide and conquer. Divide the phonebook in half and then do it again, do it again, do it again and there in lies kind of the insight of divide and conquer. We did this too on Monday with the second array. We dived into the middle of the array, then we dived into the middle here, then the middle here and voila, there was our element, the number 50. So when you do something again and again and again and the only thing that's changing is really the size of the problem, the steps you are executing are still the same. I'm still tearing a phonebook in half. It's just half as big now. I'm going it again. It's now a quarter as big but it's still the same algorithm. Well, this is in general known as recursion and we can write functions and I did this just kind of for fun the other day, we can deliberately write functions that recurs by calling themselves. Now what do we mean by this. Well, in the context of C, we can write a function and surely that function can call itself. If I define a function called, fu, if I want fu to call itself, I just have to write the word fu open parenthesis, close parenthesis, semicolon, inside fu itself, but bad things happened when I did this last time. What happened when I wrote literally a function fu that called itself? >> Seg fault. >> So I got a seg fault. Now why was that? Well again just think back to the building blocks we've been looking at, right? Where you have memory in our computer, we keep drawing it as a rectangle. Every time you call a function, you add a frame to that stack. In other words, you ask for some memory and conceptually it's like putting it on top of the stack of memory you've already asked for so you call fu, you call fu, you call fu, fu, fu, fu, fu, what eventually happens? >> Run out. >> Right, you run out or you hit some other memory that doesn't belong to you and that's something we'll see before long called the heap but in short doing this again and again and again is bad so recursion does have this risk in it. If you do the same thing again and again but in each time allocate memory, you might run into some trouble but perhaps it's nonetheless a technique we can leverage. So let's take a look at one piece of code here that was among in the printouts from Monday and this is something called sigma 1. Just out of habit, I'm gonna start using VI sometimes instead of nano. It's just another text editor with more arcane commands but it does the same thing. I'm gonna scroll down and introduce this relatively tiny program. So this program here has a main function and the first thing this function does is ask the user for int so this is actually a good use of the do-while construct because recall that do-while tells the user to do something and maybe get something from the user but if the user is being difficult, I can force it to loop again and again after I check that value. So this chunk of code here is the comments explained. I'm forcing the user to give me a positive integer, not a negative nonzero but a positive integer. Now at this line in the story, I'm apparently declaring a variable called answer it's of type int and I'm lining it with value of sigma so I chose sigma based on this symbol here just to be clever but sigma is apparently a function that I wrote. It takes one argument. I'm passing it apparently an integer so let's see what it does. Well actually, this is pretty simple, it looks a little cryptic at first but this is like day 1 stuff now, right. Sigma is gonna return an int. It's gonna take an int as it's argument and I'm calling it M just because on a little sanity check, I don't wanna get into an infinite loop here by accident so I'm making sure M is not less than 1. If it is, I'm returning 0 just so bad things don't happen and now what am I doing? I'm declaring a variable called sum, initializing it to zero and then this loop here. Well, actually it's pretty straightforward. I starts at 1 goes up to and through M and on each iteration plus equals just does what? It adds the thing on the right to the left. This is equivalent and it's just shorthand notation for saying sum equals sum plus I. It's just a little more succinct than that. So in the end, the sigma function just returns the sum of all of the numbers from N down to 1 or down to 0 which are equivalent. Alright, so this is one way to do it. Let me go ahead and go back to the original here so this is plus equal 1, let me ago ahead and compile sigma 1. I'm gonna run sigma 1 and I'll give it a positive integer of 8 people. Alright so 36, so that's 8 plus 7 plus 6 plus 5 let's do it for 10. Alright 55, okay let's do it for 100. Alright, so this program seems to work and frankly it's doing this a lot faster than I could off the top of my head so we have a nice useful program here. But can we implement it in a different way. Well, this is isn't necessarily the best way to implement it but it's a nice way of demonstrating this idea of recursion in a very simple context. So this is version 2, sigma 2 and here we have same code. Get the int, put it in N and make sure it's not less than 1 and then call sigma again and I'm gonna print out the answer. So apparently, main is identical. So let me scroll down to sigma and here is something that's beautiful to my eyes at least. So what does this mean, sad though that is. So it returns an int. It takes an int but now I just have 2, no 4 real lines of code and even those are not all that interesting 'cause one is an if and an else, what am I doing? Well, first this is pretty much the same sanity check as before. If M is less than or equal to 0, just return 0 right away so that the user doesn't hand me a negative number and completely break this program. But notice this, all that work I did last time using a four loop, an incrementing I and the sum and all this messy syntax. it looks like I could just do this. This is an example of recursion, right, just as I could look for someone in the phonebook by looking in the middle then going checking left or right then doing it again. Well technically you could sum numbers in the same way. If you hand me the number 8, I can say the answer to sigma of 8 is 8 plus sigma of 7 and I can completely punt on the rest of the problem and let you deal with that, right. You ask me for sigma 8, I say it's literally 8 plus sigma 7. Well now, you come back to me and you say fine. What's sigma of 7and I sort of smart ass say, 7 plus sigma of 6, right and again and again. Now, I'm sort of picking a contrived example here but what's nice is just like with the phonebook, just like with the counting students, we can take a bite out of this problem, maybe it's only size 1, it's one number but I can take a bite out of this problem and then apply the exact same algorithm to this slightly smaller problem. And if I code this correctly, notice what happens. If I code this correctly, I can take the small bite out and then I can defer to who, to myself, right. If I am now the sigma function who knows how to compute this even though it's in this--the smart aleck way, well I can just say it's M plus sigma of M minus 1. Now conceptually, what does that mean? It means this is gonna get added to the return value of sigma of N minus 1. Well how do you compute that? We'll here's sigma, you pass it now in the number 7 instead of 8, 7 is not less than zero so you don't return 0 what do you return? You return 7 plus sigma of 6. Now at this point, it gets to be a bit of a mind game, right. 'Cause now you have to keep saying call sigma, call sigma, call sigma and you're never actually finishing any of these answers until what? When you call sigma of 0, finally the seeming endless loop stops because at that final 8th call you say, well what's sigma of 0? >> And I don't give you again the smart aleck answer, I instead say 0. And that means you can then kind of reverse the process. So you can say, okay if the answer to that last question was 0 then a 0 plus 1 and that means 1 then the answer to the previous question was 2 plus that and you can kind of unwind in your mind and it's a little hard to think of it first, but what's the end result. You can implement in--there's this beautiful way, this very elegant sort of logical way, the notion of summation that we just did but using just one line of code and leveraging the code sigma that you already wrote. Now what's the power of this? Well once you have the ability to do things recursively, you don't necessarily or you're not necessarily able to solve problems in different in--you're not necessarily to solve problems that you couldn't otherwise using iteration and loops but you can solve them a lot more intuitively and you can use a programming technique recursion in a way that really lends itself to the problem, and for that, let me introduce this. I'm gonna pull up a different demo here. This one also happens to be implemented in Java but it's just the visualization as in aside, the world has come up with all sorts of sorts. We won't look in this course at bozo sorts or cocktail sorts, shaker sort but there's a whole bunch of them out there. Let's pick the ones we did look at. Bubble sort there, I'm gonna pick a selection sort here. And it turns out one of our favorites because of its power is something called merge sort. So I've zoomed in on this graph. What you see here is same kind of visualization as last time but instead of the numbers being vertical, this guy just implemented it sideways so in a moment, I'm gonna click each of this graphs. They're randomly oriented. Small bars means small number, big bars means big number and what you're gonna see assuming I click them all fast enough is each of this 3 algorithms running simultaneously and my claim is as we've seen bubble sort in the worst case is N squared, selection sort in the worst case is N squared but this thing merge sort is an example of an algorithm that's in N times log of N. So, it's not as good as log N which was the case for divide and conquer and for searching, but N log N is definitely smaller than N times N 'cause log N is smaller than N. So here we go, I give you in conclusion bubble sort, the selection sort, the merge sort. [ Pause ] >> So that is what it means the solve problems effectively. See you on Monday. [ Noise ] ==== Transcribed by Automatic Sync Technologies ====