Transcript
the following content is provided under a Creative Commons license your support will help MIT open courseware continue to offer highquality educational resources for free to make a donation or view additional materials from hundreds of MIT courses visit MIT opencourseware at ocw.mit.edu so for the last two lectures we've been talking about analyzing algorithms complexity orders of growth how do we estimate the cost of an algorithm as the size of the input grows and as I've said several times I'll say at least once more how do we also turn it the other direction how do we use thoughts about choices of pieces of algorithm in terms of implications on the cost it's going to take us to compute we saw last time a set of examples constant algorithms linear algorithms sorry constant algorithms logarithmic algorithms linear algorithms quadratic algorithms exponential algorithms today what I'm going to do is fill in one more piece a log linear algorithm something that's really a nice kind of algorithm to have and use it to talk about one last class of algorithms that are really valuable and those are searching and sorting algorithms so a search algorithm kind of an obvious statement you use them all all the time when you go to to Google or Bing or whatever your favorite search mechanism on the web is it's just a way to find an item or a group of items from a collection if you think about it that collection could be either implicit or explicit so way back at the beginning of the term we saw an example of a search algorithm when you were looking for square roots and we saw simple things like en or exhaustive enumeration we'd go through all the possibilities we saw our first version of section search there where you would do approximations Newton RS and these are all examples of a search algorithm where the collection is implicit it's all the numbers between some point and some other point more common is a search algorithm where the collection is explicit I don't know for example I've got all the data records of students and I want to know how do I find a particular student so I can record that A+ that everybody in this room is going to get next Tuesday on that exam that's not a promise sorry but we'll work on it so could do it implicit could do it explicit today I want to focus on doing search explicitly and it could be on different kinds of collections but I'm going to focus just as an example on search over lists and to make it a little easier let's just do search over lists of numbers but it could obviously be other kinds of elements now you've already seen some of this right we did search where we said we could do linear search Brute Force just walk down the list looking at everything till we either find the thing we're looking for or we get to the end of the list sometimes also called British museum algorithm or exhaustive enumeration I go through everything in the list nice news is the list doesn't have to be sorted it could be just an arbitrary order what we saw is that the expected sorry not expected the worst case behavior is linear in the worst case the elements not on the list I got to look at everything so it's going to be linear in terms of complexity and then we looked at bsection search where we said the list needs to be sorted but if it is we can actually be much more efficient because we can take advantage of the Sorting to cut down the size of the problem and I'll remind you about both of those there was our simple little linear search right set a flag that says I haven't yet found it and then just Loop over the indices into the list I could have also just Loop directly over the list itself checking to see if the I member of the list is a thing I'm looking for if it is change the flag to tr so that when I come out of all of this I'll return the flag either false because it was set that way initially or true because I found it and of course what we knew is we have to look at everything to see if it's there or not I could speed this up by just returning true at this point well that would improve the average case doesn't improve the worst case and that's the thing we usually are concerned about because in the worst case I got to go through everything and just to remind you we said this is order length of the list to go around this part the loop right here and inside the loop it's constant work I'm doing the same number of things each time that's order n * order 1 and by our rules that's just order n so it's linear in the size of the problem okay we said we could do it on sorted lists but just again walk down the list again here I could Loop over everything in the list checking to see if it's a thing I want return true and if I ever get to a point where the element of the list is bigger than the thing I'm looking for I know it can't be in the rest of the list cuz all the things to the right are bigger yet I could just return fults and drop out in terms of average Behavior this is better because it's going to stop as soon as it gets to a point where it can rule everything else out but in terms of complexity it's still order n because I still on average have to not average in the worst case I'm still going to be looking end times through the loop before I get to a point where I can decide to bail out of it so order in and then finally last piece of recap bsection search repeat again the idea here is take the midpoint of the list look at that element if it's the thing I'm looking for great I just won the lottery if it isn't decide is the thing I'm looking for bigger or less than that middle point if it's bigger than that I only use the upper half of the list if it's less than that I only use the lower half of the list and the characteristic here was at each step I'm reducing the size of the problem in half I'm throwing away half of the remaining list at each step and I'll just remind you of that code I know it's a lot here but just to remind you it said down here if I've got an empty list can't be there I'm going to return faults otherwise call this little helper function with the list the thing for which I'm searching and the beginning and end point indices into the list initially the start and the very end and this code up here B basically says if those two numbers are the same I'm down to a list of one just check to see if it's the thing I'm looking for otherwise pick something halfway in between and ignore this case for the moment basically then check to see is the thing at that point bigger than e in which case I'm in general going to call this only with from the low point to the midpoint otherwise I'm going to call this with the midpoint to high and that was just this idea of keep cutting down in half the size of the list last piece of the recap the thing we wanted you to see here is there are the two recursive calls I'm going to only going to do one because I'm making a decision at each step I'm cutting down the problem by half and that says the number of steps the number of times I'm going to iterate through here will be log in the length of the list and if that still doesn't make sense to you it says I need to know when 1 over two to the K where K is the number of steps is equal to one because on each step I'm reducing by half and that's when K is log base 2 of n so that's why it's log linear and so this just reminds you again that recap number of calls redu or sorry the call gets reduced by factor of two each time I'm going to have log in work going around it and inside it's constant amount of work because I'm just passing the pointers not actually copying the list and that's a nice state to be okay so sounds good could just use linear search it's going to be linear when you use binary search or bsection search um we can do it in log time that's great we assumed the list was sorted but all right so that Les basically says okay so when does it make sense to sort the list and then do the search right because if I can sort the list cheaply then the search is going to be logarithmic that's really what I would like this little expression basically says let's let sort be the cost of sorting the list I want to know when that cost plus something that's order log in which is what it's going to cost me to do the search when is that less than something that's order n because then it's going to be better to do the sort first and do the search and so I can just rearrange it it needs to be when does the cost of sorting when is it less than this expression which basically says when is sorting going to be less expensive than the linear cost crud actually good news for you right this is a really short lecture because it says it's never true ouch don't worry we got more to go in the lecture the reason it can't be true if you think about it just informally is if I've got a collection of n elements and I want to sort it I've got to look at Le each one of those elements at least once right I have to look at them to decide where they go oh that's n elements so sorting must be at least order n because I got to look at everything and in fact as it says there I'm going to have to use at least linear time to do the sort sounds like we're stuck but we're not and the reason is often when I want to search something I'm going to do multiple searches but I may only want to sort the list once in fact I probably only want to sort the list once so in that case I'm spreading out the cost I'm amortising the expense of the sort and now what I want to know is if I'm going to do K searches the cost of those K searches I know is going to be K log in because it's loged to do the search and I simply need to know is the cost of sorting plus this can I have something where it's less than case searches just using linear search and the answer is yes there are going to be for large case ways in which we can do the sort where the sort time becomes irrelevant that the cost is really dominated by the search and so what I want want to do now is look at all right how could we do the sort reasonably efficiently it's going to have to be at least linear we're going to see it's going to be a little more than linear but if I could do it reasonably I'm going to be in good shape here so what I want to do is show you a number of ways in which we can do sorting take a list of elements and sort them from in this case smaller to higher or in in increasing order so here's my goal I want to efficiently sort a list I want to see if we can do this as efficiently as possible I'm going to start I'm going to say with a humorous version of sort you've all convinced that my humor is non-existent you're right but it sets the stage for this is a sort you can look it up it's called monkey sort BOGO sort stupid sort slow sort permutation sort shotgun sort and here's how it works Anna has nicely given me a set of numbers on cards here here's how you do BOGO sort I got to do that better I got to spread them out randomly like this oh good I'm going to have to sorry Tom I'm now walking and now I picked them up saying is that less than this Which is less than o crud they're not sorted all right I pick them all up and I do it again a little brain damage right now it's intended to get your attention I did I heard a couple of Chuckles those are a students by the way I heard a couple of Chuckles here we could actually do this exhaustively basically it's called permutation sort because you could search through all possible permutations to see if you find something that's sorted that by the way the complexity of that is something like n factorial which for large n is n to the nth power and if 's anything bigger than about two don't do it all right but it would be a way to think about doing this all right now having caught in the humorous version of this how could we do this a little bit better oh sorry I should say What's the complexity there is a nice crisp definition of BOGO sort its best case is order n because I just need to check it sorted its average case is n factorial and its worst case if I'm just doing it randomly as God knows because I could be doing it here forever so we're going to move on here's a second way to do it called Bubble sword I'm going to do this with a small version of this I'm going to put out a set I'll turn these up so you can see them in a second the idea of bubble sword is I'm I'm going to start at I'm going to call this the front end of the list and I'm going to walk down comparing elements one pairwise and I'm always going to move the larger one over so I start here and I say one's less than 11 I'm okay 11's bigger than five I'm going to bubble that up 11's bigger than six I'm going to bubble that up 11's bigger than two I've basically bubbled 11 to the end now I go back here I say one is less than five that's good five is less than six that's good ah six is bigger than two two bubble that six is less than 11 you get the idea comparison comparison and swap comparison comparison and now if I go back to this part and do it you'll notice that's in the right order that's in the right order that's in the right order that's in the right order I'm done small round of applause please I was able to sort five elements thank you the little video was sort of showing the same thing you can see the idea here it's called bubble sort because you're literally bubbling things up uh to the end of the list it's pretty simple to do you're just swapping Pairs and as you saw when I get to the end of the list I go back and do it until I have a pass where I go all the way through the list and I don't do any swaps and in that case I know I'm done because everything's in order and I can stop one of the properties of it is that the largest unsorted element is always at the end after the pass in other words after the first one I know that the largest elements at the end after the the second one the largest thing left is going to be in the next place and that tells me among other things that this is going to take no more than n times through the list to succeed might actually take fewer than that okay again let's look at some code for it let's look at its complexity and let's actually run this so here is a little simple version of bubble sort I'm going to set a flag up here I'm going to call it swap initially to false that's going to let me tell when I'm done when I'm gone through everything in the list without doing a swap and then I'm going to loop as long as swap is false so the first time through it's going to do that loop I set swap initially to true and notice what I then do I let J range from one up to the length of the list and I look at the jth element and the previous element If the previous element is bigger I'm going to flip them right there and that's just doing that swap what I just did down here and if that's the case I'm going to set the flag to false which says I've done at least one bubble as part of this which means when I come out of here and go back around to the loop it's going to do it again and it will do it until all of this succeeds without this ever being true in which case that's true which makes that false and it will drop out okay let's look at an example of this running it's just to give you a sense of that assuming I can find the right place here so there's again a version of sort um on the side and I'm going to bring this down to the bottom I've got a little test list there and I'm just I've put a a print statement in it so you can see each time through the loop what's the form of the list as it starts and assuming I've done this right there you go there's the list the first time through notice after one pass 25's at the end of the list the biggest element exactly what I like but you can also see a few other things have flipped right right in there there have been some other swaps as it bubbled through and in fact uh you can see uh it's well you can see that idea you can see 25 moving through notice on the next step a whole bunch of the list is actually in the right order it's just because I got lucky all I can guarantee is that the second largest element is at the second and or the second from the end at the list but you can see here even though the list is I think nine long it only took us four passes through so this is nice it says at most end times through the list and at the end we actually get out something that's in the right form okay so let's go back to this and basically say what's the complexity well that's length n right has to be I'm going through the entire list and inside of there is just constant work four operations I'm doing a test sorry five I'm doing a test and depending whether that test is true or not I'm setting a flag and doing some movement of things around but it's just const I don't care about the five and there how many times do I go around the loop in the worst case n all I can guarantee is after the first pass biggest thing is here after the second pass the second biggest thing is there after the third pass you get the idea so I've got order and things inside the loop and I'm doing that Loop end times and I hope that looks familiar we've talked about this right this is nested Loops what's this quadratic so it's order n squ where n is the length of the list now as you also saw on average it could be less than that but it's going to be order n squ okay that's one possibility here's the second nice simple sord algorithm it's called selection sort you can kind of think of this as going the other way not completely but going the other way when I say going the other way the idea here is that I'm going to find the smallest element in the list and I'm going to stick it at the front of the list when I'm done and simply swap that place with whatever was there flip them I might do a few other flips along the way depending how I implement this next pass I'm just going to look at everything but the first element because I know that one's done I'm going to do the same thing find the smallest element remaining in the list put it in the second spot and keep doing that what I know is if I imp this correctly after I steps the first I elements of the list will be sorted and everything in the rest of the list has to be bigger than the largest thing in the first part of the list okay so we could build that before we do it I'm going to show you a little video starring Professor gag this is his Cameo per performance here but I want to just show you an example of this using not numbers but people all right so now we're going to do selection sort the idea here is at each step we're going to select the shortest person and put them next in line of the sorted group so we'll bring the leftmost person forward and we will compare her to everybody else so one at a time step forward you're still the winner you go back please step forward and watch the number of comparisons that go on by the way we're going to go back to that still the winner next ah a new winner all right so you can take her place so here we're choosing to actually insert into the spot in the line we could have put her back at the front but this compare same old winner same winner no change it's getting kind of boring don't fall that we same winner please this is a tough one oh close but I think you're still shorter all right next no change which means you are the first in line congratulations so smallest element now guarant the first now you step forward and we'll compare are you and I would invite you to watch the left hand of the list notice how it is slowly building up at each stage to have that portion sorted and we deliberately admit students to be of different heights so John can do this demo you are the winner take your place in line next it's you and once again we have a lovely group of students sorted in height order and check out I want you to remember number of comparisons 55 not that the 50 but I want you to see a comparison as we go on in a second so again selection sort this is this idea of find the smallest element put it at the front and I might do a little number of flips as you can see here along the way but this is the same sort of animation of that so let's first of all convince ourselves it will do the right thing and then look at some code and then run the code so to convince ourselves that this is going to do the right thing we could talk about something that we often refer to as a loop invariant we're going to write a loop where we're going to walk through this and the invariant here we want to just demonstrate if it's true at the beginning and it's true at each step therefore by induction as we did earlier I can conclude it's true always is that if I'm given the prefix or the first part of a list from zero up to I and a suffix or a second part of the list from i+ one up to the end of the overall list given that then I'm going to assert that the invariant is that the prefix is sorted and no element of the prefix is larger than the smallest element of the suffix just what I said earlier says at any stage here if this is the amount of sort I've done so far I can guarantee I'm going to claim this will be sorted and everything here is bigger than that thing there how do I prove it the base case is really easy in the base case the prefix is empty I don't have anything so it's obviously sorted and everything in the suffix is bigger than anything in the prefix so I'm fine and then I just want to say as long as I write my code so that this step is true then I'm going to move the smallest element from the suffix the second part of the list to the end of the prefix since the prefix was sorted this is now sorted and everything in the suffix is still going to be bigger than everything in the prefix and as a consequence by induction this is going to give me something that says it's always going to be correct so here's code that would do that here I'm just going to set a little thing called the start of suffix or suffix start initially it's going to point to to the beginning of the list and then I'm going to run a loop and as long as I still have things to search in the list that that pointer doesn't point to the end of the list what am I going to do I'm going to Loop over everything from that point to the end of the list comparing it to the thing at that point if it's less than I'm going to do a swap because I want it to move it up and you can see by the time I get through this loop I will have found the smallest element in the remainder of the list and I would have put it at that spot whatever suffix start points to and when I'm done all of that I just change this by one having found the smallest element I've stuck it at spot zero I'll do the same thing having found the next smallest element I know it's at 0.1 and I'll just continue around one of the things you can see here is as opposed to bubble sort this one is going to take n times around the loop because I'm only moving this pointer by one so it starts at zero and then one and then two all the way up to n minus one you can also see in this particular implementation while I'm certainly ensuring that the smallest element goes into that spot I may do a a few other flips along the way I'm going to find something I think is the smallest element put it there and put that element here and then when I find another smaller element I may do that flip I could have implemented this where I literally search for the smallest element and only move that doesn't make any difference in terms of the complexity all right what's the complexity here already said this part I will Loop end times because I start at zero and then one you get the idea inside of the loop I'm going to walk down the remainder of the list which is initially n and then n minus one and then n minus 2 times but we've seen that before as well while it gets shorter that complexity is still quadratic order and times going through this process within the process order and things that I have to compare and yes n gets smaller but we know that that that that n term if you like dominate so again this is quadratic okay before you believe that all sorting algorithms are quadratic I want to show you the last one the one that actually is is one of the I think the the prettiest algorithms around in a great example of a more efficient algorithm is called merge sort merge sort takes an approach we've seen before talked about divide and conquer break the problem down into smaller versions of the same problem and once you've got those Solutions bring the answer back together for merge sort that's pretty easy it says if I've got a list of zero or one elements it's sorted duh okay if I got a list of more more than one element here's my trick going to split it into two lists I'm going to sort them and when I'm done I'm just going to merge those two lists into one list and the merge is easy because if I've got two lists that are sorted I just need to look at the first element of each take the one that's smaller add it to my result and keep doing that until one of the lists is empty and then just copy the remainder of the other list you can probably already get a sense of what the cost is going to to be here because this is cutting the problem in half now I've got two pieces so I need to think about both of them I want to give you a couple of visualizations of this here's the first one it says basically I've got a big unsorted list I'm going to split it and I'm going to split it and I'm going to split it until I get down to just lists that are either zero or one which by definition are sorted and once I'm at that level then I just have to merge them into a sorted list and then merge them pairwise into a sorted list and you get the idea so it's divide and conquer the Divide is dividing it up into smaller pieces the conquer is merging them back together and we have Professor good tag back for an encore together with his students so let's show you an example of merge sort so we're about to demonstrate merge sort and we're going to sort this rather mly collection of MIT students by height so the first thing we need to do is we're going to ask everyone to split into a group of two so you split a little bit you two are together you two are together you two are together you two are together and you are all by yourself I'm sorry all right forna so now let's take the first group take a step down and what we do is we sort this group by with the shortest on the left and look at this we don't have to do anything thank you feel free to go back up we then sort the next pair please and it looks to me like we need to switch all right take a step back ladies okay ladies gentlemen also okay and again okay notice each subgroup is now which is great now what we do is we take these groups and merge the groups so let's have these two going to sort these groups have them step forward and now what we're doing is we're doing a merge of the the two sorted groups so we start by merging them we'll take the leftmost person in this group and compare her to the first person in this group and decide she's still the shortest take a step back now we're going to look at you and say you're actually taller than this fellow so you now step up there and we're good here both of you take a step back now we'll take these two groups and follow the same procedure we'll merge them let's see we'll compare you the first person in this group to the first person in this group now it's a little tricky so let's see the two of you compare let's see back to back we have a winner set back and now we need to compare the shortest person in this group to the shortest person in this group we have a winner it's you I'm sorry and now we just we're okay please step back now we'll have these two groups come forward we'll compare the shortest person in this group to the shortest person in that group I actually need you guys to get back to back here you are the winner and it's pretty clear that the shortest person in this group is shorter than the shortest person in that group so you go there and you step back notice the groups sorted now we repeat the same process and notice how the whole subgroup now goes up once we know that one group is empty and you can see that we have a group of students sorted in order by height remember the first number right 55 28 now this just numbers but you can see the expectation is this is going to take less time and it certainly did there so getting just the demo another way visually I'm sorting sorry I'm splitting down until I get small things and then just merging them up I may have to do multiple passes through here but it's going to be hopefully faster than the other methods we looked at I'm going to show you code in a second and then we're going to run it just to see it but let me stress one more time just the idea of merging you can see the idea I keep splitting down till I got something small enough I want to merge them back the idea of merging you've seen it from Prof from Professor good tag but I just want to highlight why this is going to be efficient if I've got two lists comparisons I'm only comparing the ends of the list I only therefore look at each element or the number of comparisons rather I should say I do I may look at each element more than once the number of comparisons is going to be at most the number of elements in both lists and that's going to be a nice cue as we think about how to solve it so here's the code to merge and then we'll write merge sort and I know there's a lot of code here but we can walk through it and get a good sense of it I'm going to set up variable called result that's going to hold my answer and I'm going to set up two indices I and J that are initially zero they're pointing to the beginning and remember the input here is two lists that we know are sorted or should be sorted or we screwed up in some way so initially I and J are both pointing to the beginning of the left and right list and look at what we do we say as long as there's still something in the left list and still something in the right list I is less than the length of left J is less than the length of right do the comparison if the left one's smaller add it to the end of result to the end of result right I'm appending it because I want it to be in that sorted order and increase I if it's not add the right one to the end of result and increase J and I'll just keep doing that until I exhaust one of the lists and when I do I can basically say if the right list is empty I know if I get out of here they can't both be true in other words if there's still something in the left list just put it on the end otherwise if the only things left in the right list just put them on the end so I'm just walking down the list doing the comparison adding the smallest element to my result and when I'm done I just return result complexity we can already begin to see here right this says the left and right sublists are order so I'm just moving the indices depending on which one holds the smaller element and when I get done I'm just returning the rest of the list so what's the complex here I'm going to do this a little more informally you could actually do that kind of relationship I did last time but what am I doing I'm going through the two lists but only one time through each of those two lists I'm only comparing the smallest elements so as I already said this says that the number of elements I copy will be everything in the left list and everything in the right list so that order is just the length of left plus the length of right and how many comparisons do I do the most I have to do is however many are in the longer list right that's the maximum number I need to have oh that's nice that says if the lists are of order n I'm doing order n copies because order n plus order n is just 2 N which is order n and I'm doing order n comparisons so it's linear in the length of the list okay sounds good that just does the merge how do I do merge sort well we set it break the problem in half keep doing it until until I get sorted lists and then grow them back up so there's merge sort it says if the list is either empty or of length one just return a copy of the list it's sorted otherwise find the Middle Point there's that integer Division and split split the list everything up to the middle point and do merge sord on that split everything in the list from the Middle Point on do merge merge sord on that and when I get back those two sorted lists just merge them again I hope you can see what the order of growth should be here cutting the problem down in half at each step so the number of times I should have to go through this should be log in the size of the original list and you can see why we call it divide and conquer I'm dividing it down into small pieces until I have a simple solution and then I'm growing that solution back up so there's the base case there's the divide and there's the nice conquer piece of this okay I'm going to show you an example of that but let's actually look at some code sorry about that let's look at some code to do this and in fact I meant to do this earlier and didn't I also have a version of bubble sort here sorry selection sort I've already done bubble sort there's selection sort let's uncomment this and let's run both of those and just see the comparison between them and sorry just to make that a little easier to read indeed there we go so we saw bubble sort it only went through four times so less than n times there's selection sort and as I said to you it has to do n passes because it can only ever guarantee that it gets one element at the beginning so you can in fact see in this case from the first or after the initial input until the end of the first step it looks like it didn't do anything because it determined eventually that one was in the right spot and similarly I think there's another one right there where it doesn't do any or appears not to do anything all it's guaranteeing is that the next smallest element is in the right spot as we get to to the end of it and in fact ends up in the right place and then let's look at merge sort and do one more visualization of this so again let me remove that and if we run it again I've just put some print statements in there here you can see a nice behavior I start off calling merge sort with that which splits down into doing merge sort of this portion eventually it's going to come back down there and do the second one it keeps doing it until it gets down to simple list that it knows or sorted and then it merges it does the smaller pieces and then merges it and having now two merged things it can do the next level of merge so you can see that it gets this nice reduction of problems until it gets down to the smallest size so let's just look at one more visualization of that and then get the complexity so if I start out with this list sorry about that what I need to do is split it take the first one split it keep doing that until I get down to a base case where I know what those are and I simply merge them pass it back up take the second piece split it until I get down to base cases do the merge which is nice and linear pass that back up having done those two pieces I do one more merge and I do the same thing I want you to see this because again you can notice how many levels in this tree log log in the size because at each stage here I went from a problem of eight to two problems of four each of those went to two problems of two and each of those went to two problems of size one all right so the last piece is what's the complexity here's a simple way to think about it at the top level I've got I start off with n elements I've got two sorted lists of size n over two and to merge them together I need to do order and work because as I said I've got to do at least n comparisons where n is the length of the list and then I got to do n plus n copies which is just order and so I'm doing order n work at the second level gets a little more complicated now I've got problems of size n over4 but how many of them do I have four oh that's nice because what do I know about this I know that I have to copy each element at least once so not at least once I will copy each element exactly once and I'll do comparisons that are equal to the length of the longer list so I've got four subl lists of length n over 4 that says n elements oh that's nice order n at each step sub problems get smaller but I have more of them but the total size of the problem is n so the cost at each step is order n how many times do I do it log n so this is log n iterations with order and work at each step and this is a wonderful example of a log linear algorithm it's n log n where n is the length of the list so what you end up with then is all right a joke version some reasonable ways of doing sort that are quick and easy to implement but are quadratic and then an elegant way of doing the search that's end log in and I'll remind you I started by saying as long as I can make the cost of sorting small enough I can amortise that cost and if you go back and look at last lecture's notes you'll see n log n grows pretty slowly and it's actually a nice thing to do it makes it reasonable to do the sort and then I can do the search in order and time and here's the last punchline it's the fastest we can do I'm going to look at John again I don't think anybody has found a faster um sword algorithm right this is the best one can do unless you do sorry the best worst case absolutely John is absolutely right there are better average cases again our concern is worst case so this is as good as we're going to do in terms of a worst case algorithm so there you now have sorting algorithms and searching algorithms and you've now seen excuse me sorry constant log linear log linear quadratic and exponential algorithms I remind you we want things as high up in that hierarchy as possible all right I have six minutes left some of you are going to leave us we're going to miss you but that's okay I'm sure we'll see you later on for those of you hanging around this isn't a bad time just to step back and say so what have we seen and I want to do this just very quickly sorry I'm remind you we started by in some sense giving you a little bit of a contract of things we were going to show you and I would simply suggest to you what have we done we given you a sense of how to represent knowledge with data structures tupal lists dictionaries more complicated structures we've shown you some good computational metaphors iteration and Loops recursion as a great way of breaking problems down into simpler versions of the same problem and there really are metaphors there ways of thinking about problems we've given you abstraction the idea of capture a computation bury it in a procedure you now have a contract you don't need to know what happens inside the procedure as long as it delivers the answer it says it would or another way of saying it you can delegate it to somebody and trust it you're going to get what you like out of it we've seen classes and methods as a wonderful way to modularize systems to capture combinations of data and things that operate on them in a nice elegant way and we just spent a week and a half talking about classes of algorithms and their complexity if you step up a level what we hope you've gotten out of this are a couple of things you've begun to learn computational modes of thinking how do I tackle a problem in divide and conquer how do I think about recursion as a tool in dealing with something you've begun to begun I will use that word deliberately to master the art of computational problem solving how can you take a problem and turn it into an algorithm and especially You' begun to have the ability to make the computer do what you want it to to say if I've got a problem from biology or chemistry or math or physics or chemical engineering or mechanical engineering how do I take that problem and say Here's how I would design an algorithm to give me a simulation a way of evaluating what it does and so what we hope we've done is we started you down the path to being able to think and act like a computer scientist all right don't panic that doesn't mean you stare at people's shoes when you talk to them not all computer scientists do that just faculty sorry John so what do computer scientists do and this is actually meant to be serious and I've put up two of my famous historical figures that computer scientists they do think computationally they think about abstractions about algorithms about automated execution so the three a of computational sying and in the same way that traditionally you had the three Rs of Reading Writing and arithmetic computational thinking we hope is becoming a fundamental that every well-educated person is going to need and that says you think about the right abstraction when you have a problem in your europ what's the right abstraction how do I pull apart the pieces how do I think about that in in terms of of decomposing things into a relationship that I can use to solve problems how do I automate how do I mechanize that abstraction how do I use what I know happens inside of the machine to write a sequence of steps in a language I'm using to capture that process and then finally how do I turn that into an algorithm and that not only means I need a language for describing those automated processes and and if you like allowing the abstraction of details but frankly also a way to communicate if you have to think crisply about how do I describe an algorithm it's actually giving you a way to crystallize or clarify your thinking about a problem this is not to say you should talk to your friends in Python I don't recommend it but it does say you should use that thinking as a way of capturing your ideas of what you're going to do and that leads then to this idea of how difficult is a problem how best can I solve it we've shown you these complexity classes and we've hinted at the idea that in fact some problems are inherently more difficult than others that's something I hope you come back to as you go along and especially we want you to start thinking recursively we want you to think about how do I take a hard problem break it up into simpler versions of the same problem and then construct the solution and that shows up lots of places right recursion is in all sorts of wonderful places so just to give you an example I could say to you recursively this lecture will end when I'm done talking about this lecture which will end when I'm done talking about this lecture which will end when I'm done all right you don't like infinite recursion good luck on the exam