[ Silence ]
>> Alright, welcome back! This is the start of week 4 and this is CS50, and this is an actual receipt that floated around online after someone photographed it. It perhaps speaks to what goes wrong when you have the problem of floating point imprecision, particularly bad if it's a cash register. This is--just to zoom in--this is the receipt from a restaurant. And again, things should probably not cost 1.48999 cents, probably unintentional. But computers make mistake and apparently people buy computers with mistakes. So, looking ahead to this week, so Problem Set 3 introduces you to this sort of age old game of The Game of 15, whereby you've got a board like this and the goal is to move the puzzle pieces up, down, left to right so that you've ordered them ultimately from top to bottom, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 with a blank in the bottom right hand corner so the problem set this week introduces you too for the first time to something we'll call Distribution Code, Distro Code. Something that someone else wrote, in this case it's code written by us but we stop short of implementing this whole game and rather we left blanks, little holes for you to fill in throughout the frameworks so that the goal of this game is really twofold so far as the P set goes. One is understanding someone else's code, so not diving in with a blank slate and figuring out how to implement the whole thing from scratch, but rather understanding how a framework works that we provide and you'll see its all nicely commented and indented, and we then direct you toward the holes you need to fill in with code of your own. Now, those of you enticed with this Hacker Edition will know that the goal is not to implement the game per se, but a solver for the game. So that if you actually play this thing rather than be the human typing in the number 3 and 4 and 15 to move the puzzle pieces around, instead you will type G-O-D in all caps, and voila! The computer will solve this problem for you and its quite fun to see it happening live animatedly. So you can play with the Hacker Edition even if you're doing standard in the appliance because we've included the solutions to both--in CS50's own directory. So also as part of this problem set is an opportunity to dabble with the couple of sorts and searches so you'll be asked to implement essentially binary search and we talked about binary search. We looked at Sean's implementation of binary search on video last week. And there's a couple of ways you can implement it if you look back at the walkthrough from yesterday on video if you've not already, if you need some guidance there. And then you're asked to implement sort, because again this notion of sorting elements is what ultimately empowered someone like us on stage to find numbers more efficiently, more quickly. We were able to find Mike Smith in the phonebook some four weeks ago because the thing was sorted but that begs the question, how expensive? How time consuming? Is it to sort? And so we looked at Bubble Sort, and Selection Sort, and unfortunately those weren't the fastest players out there, they were in what we call big O of N squared since they might take N times N steps but they did get the job done. Now, those of you interested in the Hacker Edition also needs to implement sort but you need to do it in Big O of N, linear time, but you're allowed a couple of assumptions as the spec directs you toward. So by popular demand on two accounts, CS50 WiFi now exists so if you're here for your--with your laptop, its time to pull up Facebook if you like and use the CS50 SSID, it is password protected at the moment but the password is--
>> The combination is--
[ Laughter ]
>> One.
>> One.
>> One.
>> Two.
>> Two.
>> Two.
>> Three.
>> Three.
>> Three.
>> Four.
>> Four.
>> Four.
>> Five.
>> Five.
>> Five.
>> Six, seven, eight, so the software required that they assigned an 8 digit password but 12345678 should work for you, if not just catch one of--myself or one of the TFs on the way out and we'll figure out how you get you started for next week. Also, lunch, so this Friday we'll be joined by an alumnus who's also now with the Venture Capital Firm NEA, so if you'd like to not only dine with and chat with me and the TFs and CAs but also have some vision of a business you would like to pitch to a--a friendly VC, do feel free to RSVP at the usual URL, cs50.net/rsvp. So, these were the numbers that we played with quite a bit last week and these were just random numbers but there were 8 of them and 8 is almost always convenient 'cause we can divide by 2, divide by 2, but in reality and in P set 3, you're not gonna have the luxury of assuming that you're only gonna have 8 numbers, but this allows us to at least discuss them and we looked at again, a number of algorithms: Binary search, Linear search. Binary being the faster of the two, it was that divide and conquer strategy, linear search was just left to right, or right to left, but they were both correct but one performs, of course, better. We looked at a couple of searches and in English terms, how did Bubble Sort work anyone? If you implement Bubble Sort, how does it work?
[ Inaudible Remark ]
>> Okay, good! So it compares two values that are adjacent to one another and in short, if they're out of order, swap them, and then repeat, and then repeat, and then repeat, and then repeat, and at what point could KC or anyone sorting N elements stop doing those comparisons? Does she--did she just need to walk across the stage once comparing these two, these two, these two, and by the end done with Bubble Sort? Well, no, 'cause remember in bubble sort in the worst case, the person who's all the way at the end if we had the number one completely in the wrong spot, he or she might only bubble up one place despite KC's pass through the entire list of people so KC potentially had to go back and again, and again, and again potentially N times and that's where we got the N squared from. So what about Selection Sort? This was the first version and it was actually pretty intuitive, pretty consistent with what a normal human being would do. How do you define Selection Sort? Just in English, how do--someone else? Yeah?
>> It's where you find the lowest number and put it all the way to the left.
>> Okay, so you find the lowest number and put it all the way to the left, perfect! And then repeat, but you do it with the next smallest number, and then the next smallest number, the problem with this though as clean and as intuitive as it is, it too involve just as much work because recall if the list was completely backwards, number one is over there, number 8 is over there, KC would have to go all the way over here, find "Oh! Here's number one, let me move him or her over here." And just evict this person, and just swap them over there 'cause they're in random at order in the first place, it doesn't matter we just shove them to the end anyway, but now she has to repeat and who knows where number two is so you have to look again, and again, and again, and finally we get N squared again 'cause she has to make N traversals back and forth across the stage, each time looking at potentially some N or N minus one or fewer humans so to see this in action, we can actually look at this visualization which is a little--this shows us not just the ones we looked at but a few others as well so this again, each of the bars represent a number, smaller bar smaller number, big bar big number. And in a moment I'm gonna click that green arrow at the--the top, and you'll see there's a few more sorts in this world than just Selection Sort, Bubble Sort, and Merge Sort, which we looked very briefly at the end of--last time. There's Insertion Sort, there's Quick Sort, there's Shell Sort, Heap Sort, couple of which we'll come back to eventually but there's dozens of these things and really it's the principles in just a few of them that--that we'll focus on for now. But the takeaway here is this. I've clicked random order so that we just kind of got some random numbers, small and big in there. If I click Go, what's neat about this visualization is it's gonna show us more than three, it's gonna show us all 8 of these algorithms at once, and recall Merge Sort one last time, he's doing pretty well this time. Apparently, Insertion Sort's pretty good, Heap Sort, Quick Sort, Quick Three, Shell--I mean, maybe we should've started with these, right, 'cause these are clearly much higher performance, apparently. Here comes Insertion Sort, and there's N squared for you. So as simple as Selection Sort was and as intuitive as it was, and as correct as it was, it's clearly suboptimal, at least on random inputs and we can do this again and again, but unless you get lucky with--whereby maybe they're all sorted initially, those two algorithms in particular are gonna perform and feel slower, and thus is N squared. So hopefully, we can do better. In fact, if--you might not have seen this a few years back, a certain someone was running for president and he was actually asked this question of, what--which of these various sorts would you use? It's perhaps worth hammering home this point that N squared is indeed a little slow with this interview with former Google CEO Eric Schmidt.
[ Pause ]
>> Oops, start at the beginning.
[ Applause ]
>> Now--now, Senator, you're here at Google and I like to think of the presidency as a--as a job interview.
[ Laughter ]
>> Now, it's hard to get a job as president.
>> Right.
>> And--and you're going to [inaudible]. It's also hard to get a job at Google.
>> Right.
[ Laughter ]
>> We--we have questions and we ask our candidates questions and this one is from--Larry Schwimmer.
>> Okay.
[ Laughter ]
>> What--you guys think I'm kidding? It's right here. What is the most efficient way to sort a million 32-bit integers?
[ Laughter ]
>> Well--I--I--
>> I--I'm, maybe--I'm sorry maybe we should
>> No, no, no, no--
>> That's not--
[ Simultaneous Talking ]
>> I--I think--I think the--the Bubble Sort would be the wrong way to go.
[ Laughter ]
>> Come on, who told him this?
[ Applause ]
>> So there you have it. So today, we'll look at one of these faster algorithms and sort of the principles that you can leverage in order to do better than Bubble Sort but first a few empowering techniques. So thus far with problem sets and even lecture code if you've been playing along at home, you will run into bugs, right? Your code might not compile. You might get segmentation faults or core dumps. You--your program might never stop and so it just produces output and output and output or the cursor never comes back to you. There's so many ways in which you can screw up a program and it gets easier, trust us, to actually find the problems there in, so thus far if you've been debugging programs, hopefully you've realized that printf is absolutely your friend, plugging a few printfs to see what the value of X is, what the value of Y is--this point, and this point, and this point can certainly help you along, but unfortunately printf can only take you so far plus it's tedious then you have to rip out that code once you found your problem, and especially now that we're in problem set 3 which is a game, The Game of Fifteen, there's a little bit of primitive animation there and you're gonna completely screw up the game board if you're trying to print out some error messages or the values of variables on the screen at the same time. And so we kind of need more sophisticated techniques now to debug programs. So enter into the picture a program called a debugger, so one of the most popular debuggers out there for Linux, and Mac OS and it's available on Windows as well is a program called GDB, the new debugger. And what this program allows you to do is set what are called breakpoints in your program whereby you say, don't run my program all the way from top to bottom rather pause execution on line 13 of main. Why 13? Well, you are suspicious that you have a bug somewhere around line 13 but your program's flying by so fast that you can't really wrap your mind around what the problem is so you'd really like to slow things down and look at step 13, then 14, then 15. Well a breakpoint, as the name suggests, allows you to brake at a certain point in your program and then at your pace, your human pace, only advance line by line when you're ready. Similarly, while you're inside this debugger you're gonna be able to printout the values of variable, so you don't have to use printf, you can just ask the debugger what bits are inside of this variable X, what number is there, or what string is here? And so you can actually see the inside of your program while still interacting with it. So let me go ahead and open up the appliance here, and I'm gonna go ahead and open up, let's say a program called--let's go with--about buggy3, so buggy3 was this program and we'll actually finally start solving this program--this problem this week and next. This was that broken swap function whereby in main we had an int X and Y, they each had some values. We have some printfs, then we called this--function Swap which then looked like this and we claimed verbally a week or so ago that Swap was correct at least in so far as it goes when it comes to swapping A and B, but it did not swap X and Y. The moment swap returned, yes, A and B we claimed were swapped but X and Y were unchanged, they were still 1 and 2, respectively. So just conceptually, what was the explanation behind the bugginess of this program? Yeah?
>> The variables would pass that value not--
>> Yeah, so the values of X and Y--the X and Y were passed by "value" which meant a copy of X and Y was passed into Swap, Swap just so happened to call them A and B, but it could call them whatever it wants, but they're indeed distinct 32 bits worth of integer so at this point when Swap was called, we claimed that there exist in this world X and Y, and then also A and B, and if you think back to how we drew the RAM inside of our computer, mains--variables were down here, this slice of the stack frames so to speak, and then on top of it somewhere else in RAM was A and B, so just pictorially too, they were distinct chunks of memory. So, now we can finally see things like this and this program isn't just--fixing this program actually takes a bit of ingenuity. And we'll actually get there later this week. But for now, we can at least understand what's going on and not just have to take my own word for, and along the way we can actually learn some of these commands. So I'm gonna go ahead and do this. I'm gonna open a larger terminal here, just so we can see more at one time. I'm gonna go ahead and run make buggy3, okay, it's up to date, which means I already compiled it last week so that's good. And I can go ahead and run it just to prove that it's still broken. So X is one, Y is two, there's still one and two at the end of this. So let's now, instead of running this as Buggy 3, lets instead run GDB and then pass to GDB as they're so-called Command Line Argument, the name of the program I wanna debug. So I'm gonna go ahead and hit Enter now. And now I see a bunch of warranty information and all this and then a new kind of prompt. At the bottom left there is a prompt that says, in parenthesis GDB, and that means I'm inside of the debugger and nothing's gonna happen just yet. I can hit Control L to clear the screen, now I'm inside the debugger but my program is not running yet but I can run it. I can literally type Run Enter and voila! I've run the program inside of the debugger. Now, unfortunately this is not at all useful thus far. All I've done is now run my program inside of another program but I haven't specified that I wanna poke around. I haven't specified breakpoints. I haven't specified I wanna see anything. So let's do that. This time, I'm gonna hit Control L just to keep the screen clean, I'm gonna type break, and I don't actually remember the line number 13 I made up before, but I know the function name so I'm gonna start simple, break at the function called main, and what you see now on the screen is "Breakpoint 1 at 0x804842d file buggy3.c line 21." So--on the one hand, GDB figured out where main starts, it's apparently line 21, but what in the world is this 0x804842d do you think?
[ Inaudible Remark ]
>> Yeah, so it's a memory address and we'll start seeing more things that look like this but almost any time you see a number in the context of programming that starts with OX, first of all, that's indication of hexadecimal notation or basics team, but we'll come back to that but for now it's just another way like decimal and binary of expressing numbers. And yes, that represents the address inside of my computer's memory at which what lives? Main itself, right? We said last week that main itself and really your program itself lives inside of RAM, in fact, it's one of the things that's up on toward the top of your memory and one of the things you run the risk of clobbering if you call functions way too many times, such that you overlap that memory but for now GDB has figured out where it is, it at a breakpoint number 1 and now if I go ahead and type Run and hit Enter, now it runs but it seems to break quite quickly. So it says "Breakpoint 1, main at buggy3.c line 21" well, I forget what that is but GDB is reminding me. If you'd like to see it in context, you can go back to G Edit and you can scroll down and find line 21. If you've never noticed in the bottom right corner of G Edit, it always tells you what line you're on and even what column you're on so you can do a quick sanity check there, so I'm gonna go back to my terminal now. And GDB at this point is saying, "You're on line 21, I'm about to execute line 21, what do you want to do?" Well, let's go ahead and do this. Let's move on to the next line. So next means execute what you see and move on to the next line. Alright, now, I'm gonna go ahead and say, "Yep, lets go ahead and execute this next." Okay, now I'm gonna get to line 25 and it's gonna print out it seems the value of Y. Well what is this? Why did I just do that? Interesting. Let me go ahead and do this. Print Y Enter, so is that consistent with what we expected if I go back to the code here? So yeah, Y was initialized to two here, I'm now down at this line here. The reason I'm kind of mumbling to myself is I'm actually not sure why GDB just skipped X there, so we'll come back to that later, but for now, we're at this line here where Y is percent D. If I print out Y within GDB, it is in fact 2, so let's hit Next again. And now, indeed, it prints out as much, and now let's go ahead and say, Next, and oh, this is interesting. This is the line of code that if executed is supposed to swap X and Y, so quick sanity check, let me go ahead and first print X, it's still one. Print Y, it's still 2. As an aside, the dollar sign notation here, this is just the GDB thing, it's giving you temporary nicknames for those values in case you wanna refer back to those values, but for now you can essentially ignore the dollar sign 2 and dollar sign 3, all we're seeing now is the value of X and the value of Y. Alright, so let's go ahead and hit Next and let Swap do its thing so I hit Enter, now it's about to print out Swapped exclamation point but lets do a check. Print X, still 1; Print Y still 2, so clearly it's broken here, so let's start over and actually see where the problem is, so let me go ahead and type Run again, it's gonna say, "Wait a minute, you're still debugging, do you wanna start it from the beginning?" I'm gonna say yes, and now we're back at the beginning, so now let me go and do a sanity check, print X--seems like I've got multiple bugs, what's going on here?
[ Inaudible Remark ]
>> Sorry?
>> You haven't hit Next yet.
>> Yeah, so I haven't hit Next yet which means what? Line 21 has not yet executed which means what should be the value of X?
[ Inaudible Remark ]
>> Right, it's some garbage value, right? We talked last week about how because these stack frames are always piling up and going down, and up and down, you're reusing the same bits that some other function maybe not even written by you has actually previously used. So what we're seeing at X's location is this number 3,219,444, those are just random bits left over from something else's execution and so we're just seeing the remnants of that, but if I do click Next, and then print out X--okay, whew! It's back to one. If I print out Y, same thing, another complete garbage value but if I hit Next now and then go ahead and print Y, now it's back to two.
>> So let's hit Next, let's hit Next, and notice it's just doing the printf's and this is printing correctly, I must have hit something wrong earlier so let's hit Next now, and now Swap. So if you wanna step into a function and not step over it, what you do instead is literally type Step, so if I type Step, now notice what GDB is telling me, I'm now inside of a function called Swap, the arguments that were just passed to this function are one and two for the variables A and B respectively, I'm at line 41 in the same file, buggy3.c and I'm about to execute line 41 so let's go ahead and do this. So let's do Next, let's do Next, let's do Next, and now line 44 is the curly brace. So this is where our story verbally used to stop. Let's do a quick sanity check, Print A, Print B, and what should Temp be if I print Temp? And fifty-fifty percent chance here, and it's indeed one, 'cause we initialized the two to the value of A and then used that to put that same value in B. So this looks right. When I printed A, I got 2. When I printed B, I got one, so let's go ahead and click Next and now I'm back. GDB is telling me back in main where I left off, line 28, so if I now print out X, print out Y, they're still broken as we expected and if I try printing A, no symbol A in current context Print B, same thing because they're no longer in scope. So to be honest, using GDB even for these simple operations of using Print, Next, Step, and Break are hugely more powerful than just using printf alone, so we'll spend time on these in section and certainly more over time as well here. But if you go in the meantime to cs50.net/resources, you'll see that under the GDB tag, there's one a--some documentation here, but there's also a little quick reference cheat sheet that has way more commands than you'll probably care about initially, but it's a one-page PDF you can print out and it's a cheat sheet of sorts and you'll see that it gives you a quick sense of the various commands you can type, and also GDB is nice in that you can be fairly succinct. You can just say--P for Y, PX. You can almost always type just the first one or two characters of the command. So you don't have to redundantly type out print all the time. And you can also scroll up, down, left, right. And finally when you're done just type Q or quit. And that will warn you that you're about to quit. And now you're back at the appliances prompt, so a hugely useful tool. And this is one of those things honestly where I did the same thing. We sort of introduced this. We claim that's incredibly useful. But there's invariably a learning curve, whether it's ten minutes, an hour or so to acclimate to it. And so this is absolutely one of these tools that like almost every student puts off, myself included back in the day, until later and later and later in the term. But honestly, spending the ten minutes, the hour for P Set 3 and 4 to play with GDB, I promise will save you hours of time in the future. It is so much more useful than just using printf in your own brain sometimes when looking through code. It allows you to step through much more reasonably. Alright, any questions on debugging or GDB? Yeah?
[ Inaudible Remark ]
>> Good question, if you're dealing with arrays by default, GDB will usually know how to print something that's like an array or a string which is an array of characters. It does sometimes depend on the context. But for now if you declare an array inside of a function and then type "print space foo" where "foo" is the name of that array, you should see all of the members of that array, yes. The only problem arises sometimes if you start passing that array around which we haven't really done, except in problem set three's distribution code that sometimes GDB essentially loses track of the length and so it has trouble printing it for you. Other questions on GDB? Alright so comparing values, and now sorting values, how can we do this better? So this little picture here suggests that one of the fundamental operations, anytime we're actually doing sorting is that we need to compare stuff, alright? We need to compare one value against the other. In Bubble Sort that's literally what we were doing. And really in Selection Sort, that's what we were doing as well. Even though we describe it as go find the smallest value. Well, how do you find the smallest value? Well you look at the first person, there number 8, you just assume they're the smallest by default because they are thus far. Then you look for someone smaller and smaller every time comparing the person you found against the number you're considering replacing them with. So comparisons are really fundamental to this process of sorting and then to some extent, so is swapping, of course swapping is very easy if you just use X and Y in a temporary variable in your function but of--we've seen that it gets problematic if you have a Swap function but we'll fix that problem on Wednesday but realize that for Problem Set 3, you don't need to implement your own Swap function, right, with just three lines of code, case in point, you can implement Swap inside of a for loop or inside of main, you don't necessarily need this auxiliary function just yet. So, can we do better and how can we go about doing better? Well we need a new technique. So if we want to solve these problems more effectively, it'd be nice if we could express ourselves a little more elegantly, and it's not gonna necessarily empower us to solve problems we couldn't with something called Iteration, otherwise known as Looping, but besides for loops and while loops and do-while loops, there's other ways to do something again and again and again, and thus far we did it once intentionally, though foolishly, recall that when I implemented a function foo, and then I had foo call foo, I think that was the function's name, what happened when I had a function call itself?
[ Inaudible Remark ]
>> It kept going, it kept going, it kept going, until what happened?
>> Segmentation--
>> Segmentation fault, right, core dumped. So why was that? Well, we claimed last time that when you think of your memory as that big rectangle and you keep calling a function, each invocation, not the function, each call of that function gets its own slice of RAM another, another, another, another, and even though you might have gigabytes worth of RAM, eventually you do something infinitely long and you're going to take up more than you're allowed and so the operating system's gonna kill you, you're gonna dump core, and inside of that file or the contents of memory. As an aside, before I forget, if you are very good at creating core dumps in your programs, realize that GDB here can also save the day. If you do find that you do have one of these files called Core, what you can do with GDB is run GDB on whatever your program name was but then specify as a third word at the command line the name of the file, Core, C-O-R-E. And then hit Enter, and if I actually had had a core dumped from this invocation of this program, the GDB is being handed not only the program called Program, but also the core dump and inside of the core dump, is what did we say?
[ Inaudible Remark ]
>> It's the contents essentially of RAM at the point your program crashed which means this is your opportunity for an autopsy of sorts, this is the dead program sitting there in the file called Core and with GDB, you can now step through and type Print, and other commands to actually look inside of what happened there. So there, too, is an opportunity. Alright, but we'll be having plenty of segmentation faults Wednesday onward when we finally introduce something called Pointers but for now, really an elegant technique, and this is something we won't use all that often this semester but in future courses if you decide to proceed particularly courses like 51, or in a Data structures, or algorithms class or really in the real world when you start trying to solve really complex problems, this notion of recursion is really powerful. And recursion boils down to calling yourself, like you are a function, you are said to be recursive if you call yourself. Now, we saw last week that this is apparently a bad thing. If you call yourself, you get into this infinite loop and use segmentation fault. But that's true if you'll just call yourself--if you just call yourself again and again without even considering stopping. But suppose we introduce a branch or a condition that says, sometimes you should stop so that we can short-circuit this otherwise infinite looping. So here's some generic pseudo-code for that algorithm Merge Sort, so just as a teaser here, here's how Merge Sort works. Merge Sort was that super fast algorithm we saw at the end of last week and we saw among the 8 candidates today it works as follows. If you were handed N elements and N is less than two, you just return, right? If you get fewer than two elements, how big is the list? It's zero or one, in either case the list is sorted so you're done. Else, if you actually get an interesting size list of size two or three or a thousand or anything bigger, you're gonna instead do this. Sort the left half of elements, sort the right half of elements, then merge the sorted halves. That's it! Right, you might have thought that Merge Sort, wow, must be really interesting and complex, it's gonna take, you know, really complex demonstration but no--maybe, probably, actually you didn't think any of that. So instead Merge Sort is defined literally this simply, it literally calls itself. Right, if you're an algorithm and you wanna kind of be a smart-ass algorithm and you're told here, sort these N elements, you could just push back and say, "Okay fine, I'm gonna sort these N elements by first sorting the left half, then sorting the right half, and then I'll merge the two sorted halves." But that then beget--that then begs what question cyclically, okay fine, how are you gonna sort the left half? How are you gonna sort the right half? Well, I can give you the same wisecrack answer and say, well I'm gonna sort the left half of the left half and the right half of the left half and then the other side and I'm gonna merge the two, right?
>> Now these two feels like you're being difficult and aren't really answering the question but you kind of are because what if you get down to the point in this sort of back and forth argument where all I do is hand you two numbers like this. Well, you're gonna say the same thing, I'm gonna sort the left then I'm gonna sort the right then I'm gonna emerge the two. Alright, find I'm gonna push back one last time and say "Fine, how are you gonna sort the left half? Well, the left half looks like this. How you're gonna sort this?" It's already sorted. Right, so there is the brilliant insight. Once this argument kind of bottoms out and the list is of sufficiently small size the problem is trivial to solve. All you have to do is hand me back the list. So in Merge Sort as its name kind of suggests the real magic is not so much in the sorting per se but in the last step the merging. That must be where the sorting in real terms actually happens. Now in as much as this algorithm Merge Sort effectively calls itself by cyclically saying, how do you sort N elements? Well, you sort these elements then you sort these elements. The fact that you're answering question with the same question means that it's recursive. So let's see this notion of recursion, but first in a simpler context. Let me go over to this file here and the appliance and open up let's say sigma1. So for those following along at home over the PDF this is sigma1.c. And I'm gonna scroll down here and let's see what this sigma function does. So this function gets its name incidentally from just the Greek symbol for adding a bunch of numbers together that looks a little something like that. So this is just an addition function at the end of the day. So how is this addition actually working? Well, let's take a look. So we have at the very top of the file a prototype for a function called sigma whose argument is an int and whose return type is an int. Recall that I mentioned that for prototypes you don't strictly need to mention the name of the variable just its type. So that's an example of that shorthand notation up at the top. Now here is main, so what's main doing? It's gonna ask the user for a positive int. So here's an example of using do-while. Again, we keep using do-while in programs and P sets anytime you wanna get something from the user then yell at them if they don't oblige the first time. So it's a good construct for that. So all of these first five or six lines are doing are getting an integer that should be positive from the user. Then, apparently I'm declaring an int called answer. I'm storing an answer, the result of calling a function whose name is sigma and the input to sigma is N, whatever the user typed N. So, I claim that sigma's purpose in life is to compute the sum from 1 up to N. So if the user types in two sigma should give me 1 plus 2 it should give me 3. And if the user types in 3 the program should give me 1 plus 2 plus 3, 6. I should get back. You should get the summation of those numbers. And then, all this program is gonna do is report the answer. So let's go ahead and run this to see. Let me go on to the source directory, I'm gonna go ahead and make sigma 1. Okay, compile is okay. Let me run sigma 1 on 2. Oops, no, doesn't take a command line argument. Let me run sigma 1, then give its number 2 and it does give me 3. If I give it 3, it gives me 6, if I give it 10,000, it gives me a really big number. So it seems to be working but, you know, I could be the difficult one or the TF, do something like this. That was probably a bad idea.
[ Laughter ]
>> So what might be happening here? That's a pretty big number. It's bigger than 4 billion. You know it's pro--feels like it's looping infinitely even though that's a big number. So what--remember what can happen if you overflow an integer it could be mistaken as negative, so it's possible I'm actually looping ad nauseam now because I've never gonna hit my condition. So in any case that's something where we'd have to assume a way, we would tell you in a P set, assume the user is not gonna type something more than two or four billion. But at least it seems to be working for small value. So let's go back and see how. So how is sigma working? Well, it's actually pretty simple. And this is kind of week 1, week 2 stuff now. So sigma takes an argument we called it M. But it could be anything so long it's an int. First we do have a bit of--oh, so interesting I actually made that up for just a moment ago 'cause I'm actually checking for negative value so there must be something else. And we could use GDB to figure out what was really going on there. So it's saying if M is less than one return zero immediately so that we don't run the rest of an infinite loop. Now in here, return the some of 1 through M how does this work? I've got a variable initialize to zero. I've got a for loop that's gonna go from literally 1 up to an equal to M. So that's a literal translation of the goal and then sum plus equals I and then return the sum. So it feels like a very reasonable simple implementation of summation from I equals 1 up to M and then returning the value. And we did get back that value. But there's kind of an opportunity here, right? If I wanted to solve this problem in sort of fundamentally another way, what does it mean to compute the sum of 1 through N? Well, it's--if I wanna be the wise ass like here. It's really, alright it's N plus the sum of 1 to N minus 1. Alright, so that bags the question, what is the sum of 1 to N minus 1? Well, it's N minus 1 plus the sum of 1 to N minus 2. And okay fine, what's the sum of 1 to N minus 2? Well, its N minus 2 plus the sum of 1 to N minus 3, right? So you keep going and going and going and this could become problematic if you do go negative. But it's if at some point you do have a mental check that says what? What's the sum of 1, 2--1 to 1? Well it's just 1. So you better stop asking me this stupid question. Right, at some point there should be a very simple case, let's call it a base case where it just wouldn't make sense to recursively or to cyclically ask the same question again. So let's translate that idea now to code. Let me go ahead and close sigma1 and open up sigma2 instead and scroll down here and notice this part of the program is now identical. I still have a printf and a do-while loop. I still have a sigma call storing the result and answer and I still print out what the answer is. The only that's different now is the implementation of sigma. So let's scroll down here. And look how relatively simple this now is. No extra variables, no for loop, no plus plus, no syntactic distraction. There's like real elegance here. In fact, if I get rid of these comments, just look how simple it is to express this idea. If M is less than or equal to zero, you better stop, right, 'cause bad things will happen if we go negative, so let's just return zero. Now, this is not necessarily the right answer because this is not the sum if you actually try to sum up negative numbers. But we have to make a design decision so we're not gonna support negative numbers. So if M is less than or equal to zero, return zero otherwise, what's the answer to the question? What's the sum from one to M? Well, it is M plus the sum of everything below it. So, now, think about what's happening here. Main gets called then--and let's suppose the user types in the number three. We'll keep it small for simplicity. So the user types in three and Main gets called. Main calls sigma with an argument of three. What does sigma do? Well, sigma says, all right, is three less than or equal to zero? No. So we do the second case, the else. So what's the answer to the question? What is the sum of one through three? Well, it's three plus the sum of? The sum of one to two which is otherwise expressed as three plus sigma of two, all right, so what's sigma of two? Well, sigma of two is two plus sigma of one. What's sigma of one? Well, it's one plus sigma of zero? What's sigma of zero? That's where we hit the base case, right? So this is the thing I did not have a week or two ago when I completely broke the program by just having foo call itself again and again. I never once said, if something is true, stop doing this. But, indeed, with a recursive function like this, if you do have a decision point that says stop the recursion if something is true, you avoid that process of overflowing the stack so to speak. So let's see if this thing now works. Let me go to sigma2. Make sigma2. Seems to compile okay, let me do sigma2, Enter. And now, let me go ahead and do positive integer, let's give it two. So that works. Let's give it three. That works. Let's give ten, seems to be working. Let's give it a bigger number, seems to be working. Let's give it an even bigger number. Okay, interesting. So just because we have a base case doesn't mean the solution is perfect, right? Even apparently calling this is, what, one million times calling the same function a million times is apparently bad. But that's okay 'cause this technique of recursion is still something we can leverage to solve, say, the problem of sorting, because especially with sorting, even if there are a million elements, the goal of doing divide and concur recall is to whittle these problems down to something much smaller, much fewer steps than anything linear with N. So let's go ahead and take a quick break but when we come back we'll now play this idea to the solving of sorting.
[ Noise ]
>> All right, so before class I borrowed a few milk cartons from Annenberg across the way to see if we can take a human approach to sorting these elements while still executing these relatively straightforward instructions and let's see if we can understand why and how Merge Sort is actually speeding ahead so much more effectively than Bubble or Selection Sort.
>> For this, we need just one volunteer, someone perhaps who hasn't been up here before to kind of run the show with these eight milk cartons. Come on down. All right, so, let's see how well this works. The algorithm itself is correct. So let's see if we can now do it some justice. What's your name?
>> Joseph.
>> Joseph? Okay, good to meet you. Come on up. David. All right, so here are the same exact numbers in the same exact order as last week. And for logistical purposes, you wanna hop back down on the ground floor there? And the goal is gonna be to sort these things, but thankfully this time we have some written instructions. So the input here now is of size eight, so first thing, I ask the question, is eight less than two?
>> No, it's not.
>> Okay, so no it's not, obviously so we proceed with the else, so else I say sort left half of element. So left half looks like these four here. So now if you interpret the same algorithm, how are you going to sort the left half of these elements?
>> I'm gonna cut them in half and do it again?
>> Okay, so he's gonna cut them in help and do it again. And just hold it a little closer there. So, okay, so cut it in half. Why cut it half? Well, Joseph needs an algorithm with which to sort the left half. The only algorithms we have are Bubble Sort and Selection Sort. Today, those are disqualified. It's way too slow. So we only have Merge Sort, so let's do the same thing. So here is now list of size four, so is four less than two?
>> No.
>> No. No. So now we sort the left half of elements. So you hand me this. What do you do?
>> N is not less than two?
>> Not less than two 'cause it is two.
>> We cut in half again.
>> So we cut in half again. So now here is a list of size one. Is one less than two?
>> Yeah.
>> Okay, obviously, it is. And so, what do you do?
>> Return.
>> Okay, so this is sorted, right. This is progress now. The left half of the left half of the left half is now sorted, even though Joseph literally didn't need to lift a finger. So what step comes next? Where are we in the story?
>> We merge.
>> Careful.
>> We're at the else. We return and then we call again.
>> Good. So we sorted the left half, but what comes after sort left half?
>> We sort the right half.
>> So now we sort the right half. Here is the right half on input. N equals one. Is one less than two?
>> Yeah.
>> It is. So he returns. This is great. Now, we have two bites of the problem solved, so now what's the next step?
>> We merge them.
>> Okay, so we merge them. So now you can finally do something. Okay, so good. This is actually pretty good progress. We've sorted this part of the list. Now, they're not necessarily in perfect order, 'cause two probably this shouldn't be out all the way at the end 'cause there is a one. Four shouldn't be there. But at least this is progress. So, now, mentally, we kind of have to start rewinding. How did we get to the point of merging these two halves? Well, we started here because this is the right half of the input of size four, right, so you kind of have to mentally recourse in backwards to where we started. So here is input of four. You just sorted the left half. What comes next?
>> Right.
>> All right, so let's sort the right half. How do we sort the right half?
>> Cut it in half again.
>> Okay. Here's the left half.
>> Return six.
>> Here's the right half.
>> Return eight.
>> Here's both of them together?
[ Inaudible Remark ]
>> Okay. Merge. They're already merged. All right, so that's good. It's really minimal work so far. So where are we in the story?
>> Now, we have to merge the two halves together again.
>> Perfect 'cause now, if you again rewind mentally, we've sorted the left half, we just sorted the right half. So what comes next? Merge the sorted halves.
>> Now, it's a little more interesting, so go ahead and implement this idea of merging.
>> Well.
>> Good, very well done. So 2, 4, 6, 8, so we're done. Hopefully, the right side is gonna be more interesting. So where are we now in the story? We've hit the bottom of that else condition. This was the left half of the input of size?
>> Eight.
>> All right, so why don't we put you on autopilot now, and do--tell us, though, verbally what you're doing.
>> Okay, so now we're on the right half of the input of size eight, so we cut that in half and look at the left half and then we cut that in half and look at left half of that. Return one, return three for the right half, and those are already merged. So then we come over here and we cut this half and half and return seven, return five, and then merge these. Beautiful!
[ Laughter ]
[ Noise ]
>> Very well done.
>> And now we have to merge the whole half with the whole half.
>> Good. Both halves are size four. So now how do we do this? And this part--so, clearly, the real work is involved in the merging, right? Again, hence the name Merge Sort. So be a little precise now verbally. How are you gonna merge these two?
>> Okay, well--
>> And just to be clear, there is one half, there is the other.
>> Okay, so I say we look at the left hand of this half, this half, and the left hand of that half and compare it over.
>> Okay, so comparison, another theme thus far.
>> Right. And so, if that entity is smaller than half entity, we then merge those two first.
>> Okay, so good. So it turns out here is one point worth making. So we kind of need some extra space now, right, because if we kind of take last week's approach of just swapping these guys, then we're screwing up all the work we just did. It is a good thing that two is on the left over here. It's a good thing that one is on the left of the right half. So we can't just kinda arbitrarily swap two people and say we'll fix that later, 'cause if we fix that later, the supposedly fast Merge Sort algorithm is gonna start taking even more time. So it turns out the one that the hidden costs of Merge Sort and one of the key ingredients to making it so fast in those visualizations is that Joseph actually needs extra space. So it was actually deliberate that I left a foot or so of space here in front of these buckets because Merge Sort gains its efficiency. It increases--it decreases its time by increasing its space requirement, its memory requirement. So put more--technically, for Merge Sort, you need two arrays. One empty, one is the original array, and use the empty one to put the elements into by the end. So now you have as much memory as you want; eight new spots. So where are you gonna put one? Okay, so one goes there. And, actually, there, let's put them in different places so separate arrays, but we can still let it peak through. Okay, so now what happens next? One was less than two, so one goes into the left most location of the new array. What do you wanna do next?
>> So then you--but you still compare the left, this array with the next element in the--
>> Perfect! So you repeat. So, you look at the left end of the left half, the left end of the right half. Compare those two values, turns out two is in fact smaller, so where does 2 go?
>> Right there.
>> Right there? And so let's put it into the new memory space. All right, so now what are you gonna compare?
>> The left end of this and the left end of that.
>> So four versus three?
>> And three is smaller.
>> Okay. So even though this kind of feels like there is a lot of work going on here, notice one key takeaway. Every time Joseph puts a number into the new array, he never has to go back, right? There is no looping back and forth like KC had to do last week. Moreover, he's only looking at each of these--he's only moving to the left of these elements once. As soon as he considers an element and decides it's smaller, that's it. It's out of rotation. So how many elements in total do we have to merge?
>> Eight.
>> Eight, right? Or really seven because the last one we get for free, so N or N minus 1, so that two is key here. The number of elements we need to merge is maximally N 'cause we have N empty spots. We have N buckets. We need to put them into the empty spots, all right. So, where are we in the story comparing what?
>> So now we're comparing four and five.
>> Four and five.
>> Four goes--
>> Okay. Now, we're comparing?
>> Six and five.
>> Okay.
>> It goes here.
>> Now, we're comparing?
>> Six and seven and 6 goes here and then eight and seven. Put seven here and then the eight goes right there.
>> Done! Okay, a big round of applause for Joseph. Well done!
[ Applause ]
>> So, as is always the case with these human demos, it feels like that took a while, right? It really did take some time but think about how much time if we try to express it in those N terms that we did last week. So, every time--the way we started this algorithm is we divided the list in half. And then we divided the list in half. And then we divided the list in half. Well, this is kind of an easy answer now to this part of the question, how many times can you divide N things in half formulaically?
>> Log N.
>> So that's log N, right? It's technically log base 2N and even if you're a little hazy on what the logarithms are, for now just know that anytime we ask the question, how many times can you divide something in half? Well, it's gonna be log base 2 of the something or really we again, just like last week, we said "Divided by two plus two, who cares? Let's ignore constant factors." Same deal with the logarithms. So, we'll almost always just say log N. So log N is what gives us that nice shaped curve that was not straight but rather curved and that's what gave us that added performance boost. So, there is definitely something log N involved here. So, a quick sanity check. Can you sort N element in log N time? All right, is that the answer? It's actually not but why can--does it take more than the log N steps to sort N elements?
[ Inaudible Remark ]
>> Okay, so that's actually the full answer but just logically. If I've got N elements and I claim I can sort these in log N steps, you can immediately say, "Hmm, not possible." Even if you have no idea how I'm claiming to do it because what? In order to sort N elements, you kind of just logically minimally need to do what with each of them? At least like look at it, right? You at least have to check, is it in the right place? So just logically, if you need to solve the problem that involves sorting N elements, minimally, the lower bound is going to be N steps because if it's any less than that, you're just guessing. You're just claiming sorted when you haven't even looked at all of those elements. So again, here too is kind of a mental rule of thumb. You can decide, "Hmm, that's not realistic because you can't possibly sort all N elements in less than N steps because again, you need to look at each of them. Now, a quick sanity check. When we had Sean on video up at the board here, he was able to find an element in log N steps but that was okay.
>> When Sean was looking for the number seven, he didn't have to look at all of the other elements, right? When they were sorted, rather Sean was doing it randomly but when we then did it ourselves up on stage, we sorted the elements in advance and so you don't need to look at all of the elements if you already know. "Those are less--those are smaller than what I'm looking for. Those are bigger than what I'm looking for." You can throw elements away but not so with sorting. So, with Merge Sort, we're gonna have the list log N times and that's as many times as we can divide something in half. But every time we have the list, there is this key step of merging. Well, suppose I have the list down to size 2, how many steps are involved in merging a list of size 2? It's like two or you know, it's like two or three, right? You have to compare them. Then you need to move one, then move the other. So it feels like it's two or three, give or take. But it's some linear factor of the number of bucket, same here. How about when we had 2 halves like this? These were sorted and these were sorted, then we had to merge them. How many steps did it take to merge these things? Well, you can actually simplify this logically. If these plastic bins were at this location a moment ago, and this half was sorted, this half was sorted, now we needed to sort--now we needed to merge the two halves. Well, how many steps does this take? Well, you can just kind of infer well, this guy ultimately has to move into his location. This guy has to move into his location. This guy has to be merged into his location and this guy into his, so it's again four, maybe give or take if we have to--if it's actually--maybe it's eight, right? Maybe you need to compare them and then move it around, but it's still linear because there are only four things you need to merge in total. So it feels like every time we have the list, we have to do something as many as N times for the merging process. And so in the end, merge sorts and we'll see this in just a moment. Merge sort is what we'll say as in big O of N times log N. So, this refers to the merging. At the end of the day, you've got to merge N elements but this refers to the number of times you're gonna have the list again and again and again so you get N log N. Now again, just quick sanity check without dwelling on what a logarithm even is necessarily, which of these are smaller, N or log N?
>> Log N.
>> So log N is smaller. So then, why is Merge Sort so much fast--why is merge sort so much faster than Bubble Sort or Selection Sort? Well, those things are N squared or N times N. This is the same. This is bigger. It's because this second factor is bigger than this that you actually get that N squared feel, that slowness to the algorithm. Well, let's just see this another way rather than just based on buckets. We can express this actually completely formulaically, very simple formula. So recall our implementation of this was just this algorithm. We have a base case at the top, then we've got some recursion going on, sort the left, sort the right and then merge. So let's now slap some running times on this. And here is another takeaway. You don't even need to write or see code in order to analyze the running time of an algorithm. We can just kind of infer it from the pseudo code. So, I claim that the running time of this algorithm--call it T for time given an input of size N is gonna be zero if N is less than two. In other words, it takes me no time at all to sort a list of size N if N is actually less than two, if it's zero or one, right? It's just done. So, we'll claim the cost of that is zero. Well, that's obviously not the running time or merge sort. It's not zero. There's got to be some approximation of N log N, so let's get there. So, what's the recursive case? That was the base case. So, in the recursive case, what's the time involved to sort N elements? Well, here is where we can kind of cheat with ourselves and to say, "Hmm, it's this plus this." The running time to sort N elements equals the running time to sort N over 2 elements plus the running time to sort N over 2 elements, left half plus right half plus the N is the merging. So again, a quick sanity check here. If the very first step of the algorithm is sort the left half, sort the right half, here is the left half, here is the right half merging. How do you merge? Well, think about what Joseph was doing. If I kind of do it with my fingers here, he was pointing to the left end of the left half and the right end of the right half, sorry, and the left end of right half. And what was he doing? He was comparing them, figuring out which is smaller. Then he decided one is smaller, so he'll pick that one out of the lineup. Then what did he do with this finger? He advanced it to the next left most elements of the left half. What did he do next? Well, in this here, here, then he would go here, here, here. So think about how many times did my fingers move from left to right. Well, once per bucket, right? I only moved to the left. I never did this. KC did a lot of this last week, going back and forth, back and forth. Joseph never did that. So, where do we get this N factor? You sort the left half, you sort the right half, then you just essentially conceptually have to point at each bucket once in order to move it into place as Joseph did. So, unfortunately this isn't the answer. I don't even see a log N in here because now we have to recursively answer our same question. What's the running time involved in sorting N over 2 elements? Well, what's it gonna be mentally? T of N over 4 plus T of N over 4 plus N over 2, but this is just gonna get very messy very quickly. So, let's try to simplify this with just an example. So that is in fact an algorithm. It's a recursive formula rather. Let's try to do this with actual numbers. Suppose for the sake of discussion, we've now got 16 buckets, 16 numbers just so the math is a little more compelling than 8. What's the running time to sort using this algorithm 16 elements? Well, it's T of 8, plus T of 8, otherwise known as 2 times T of 8 plus 16. So to be clear, one of those T of 8s is the amount of time involved to sorting 8 elements on the left, the other T of 8 is 8 elements on the right assuming a total of 16. And what's the 16 for? Merging those, right? Taking 8 from both halves, merging them together so that you get a collectively merged 16 elements. So now we have to dive in and let's do this one because it's relatively easy numerically. What's T of 8? Well, T of 8 is just 2 times T of 4 plus 8. What's T of 4? T of 4 is 2 times T of 2 plus 4. What's T of 2? T of 2 is 2 times T of 1 plus 2. All right, I'm just halving, halving, halving. So hopefully this is gonna bottom out ad sure enough, what's T of 1? If I hand you a list of size 1 and I say sort this just as Joseph did, you hand it right back, you're done. So now, what can we do? Just algebraically, we can say all right, well I've got this T of 1 here. Well, I can plug this in here. So this zero is gonna go here. That's gonna give me two times zero which is plus two is two. So now I know what T of 2 is. So now I can plug that two in there. So two times two is four, four plus four is eight. So that means this thing is eight. So let's change this. So, two times eight, that's 16 plus eight, right, is--come on, I'm the only doing it, 24. And if we keep going with this, what should we get in the end? Sixty four, all right, so 64, quick sanity check then, so, I claim that this algorithm runs in N times log N. So I claim that that's gonna be 16 times log base 2 of 16. Well, for those who remember, what's this? It's four, right? So if log base 2 of 16 is four, 16 times four is 64. So sure enough, this is frankly proof by example which is an illegitimate way of proving any point that you ever might need to make academically. However, it at least confirms, albeit with one simple example that we are getting numbers along the lines of N log N. And even though again, this is just one simple example, recall just what the implications are when you actually run this. If I go again to this tier, let's choose reversed. So now this is the worst possible scenario for all of these algorithms Merge Sort, recall is on the bottom left here. Let's see just how well it performs in this potentially worst case scenario. Last time, recall we started with random. So those other performers, Heap, Quick, Shell, those are still looking pretty good. Merge Sort is pretty good. So we chose a decent one, Insertion Sort which we didn't talk about a little slower but my God, Bubble Sort and Selection Sort are gonna be here all day with these example. So that is in fact N log N. So, it's one thing to see these things graphically and to kind of reason through them. Something one person did on the internet which is actually quite fascinating is actually assigned audible frequencies to the lengths of these bars so that you can actually hear these various sorting algorithms. This is about a minute of audible animation. Let me go ahead and pull this to the forefront.
[ Pause ]
[ Background Noise ]
>> This is Insertion Sort.
[ Sound ]
[ Background Noise ]
>> This is Bubble Sort.
[ Sound ]
[ Background Noise ]
>> Again, sound aside, notice that Bubble Sort true to its name, the big values are kind of bubbling up to the top slowly but bubbling up to the top.
[ Sound ]
[ Background Noise ]
>> Selection Sort.
[ Sound ]
[ Background Noise ]
>> And again, remember Selection Sort keeps plucking the smallest element so it makes sense that it's looking correct on the left but yet the right.
[ Sound ]
[ Background Noise ]
>> Merge Sort where you can really see the halves that Joseph was merging.
[ Sound ]
[ Laughter ]
[ Background Noise ]
>> This is something called Gnome Sort.
[ Sound ]
[ Applause ]
>> So, that's it. This is N log N, this is CS50. We will see you on Wednesday.
[ Noise ]
[ Silence ]