MIT OpenCourseWare http://ocw.mit.edu 6.00 Introduction to Computer Science and Programming, Fall 2008 Please use the following citation format: Eric Grimson and John Guttag, 6.00 Introduction to Computer Science and Programming, Fall 2008. (Massachusetts Institute of Technology: MIT OpenCourseWare). http://ocw.mit.edu (accessed MM DD, YYYY). License: Creative Commons Attribution-Noncommercial-Share Alike. Note: Please use the actual date you accessed this material in your citation. For more information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/termsMIT OpenCourseWare http://ocw.mit.edu 6.00 Introduction to Computer Science and Programming, Fall 2008 Transcript – Lecture 9 ANNOUNCER: Open content is provided under a creative commons license. Your support will help MIT OpenCourseWare continue to offer High-quality educational resources for free. To make a donation, or view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu . PROFESSOR ERIC GRIMSON: Let's recap where we were. Last lecture, we talked about, or started to talk about, efficiency. Orders of growth. Complexity. And I'll remind you, we saw a set of algorithms, and part of my goal was to get you to begin to recognize characteristics of algorithms that map into a particular class. So what did we see? We saw linear algorithms. Typical characterization, not all the time, but typical characterization, is an algorithm that reduces the size of a problem by one, or by some constant amount each time, is typically an example of a linear algorithm. And we saw a couple of examples of linear algorithms. We also saw a logarithmic algorithm. and we like log algorithms, because they're really fast. A typical characteristic of a log algorithm is a pro-- or sorry, an algorithm where it reduces the size of the problem by a constant factor. Obviously-- and that's a bad way of saying it, I said constant the previous time-- in the linear case, it's subtract by certain amount. In the log case, it's divide by an amount. Cut the problem in half. Cut the problem in half again. And that's a typical characterization of a log algorithm. We saw some quadratic algorithms, typically those are things with multiple nested loops, or iterative or recursive calls, where you're doing, say, a linear amount of time but you're doing it a linear number of times, and so it becomes quadratic, and you'll see other polynomial kinds of algorithms. And finally, we saw an example of an exponential algorithm, those Towers of Hanoi. We don't like exponential algorithms, or at least you shouldn't like them, because they blow up quickly. And we saw some examples of that. And unfortunately, some problems are inherently exponential, you're sort of stuck with that, and then you just have to try be as clever as you can. OK. At the end of the lecture last time, I also showed you an example of binary search. And I want to redo that in a little more detail today, because I felt like I did that a little more quickly than I wanted to, so, if you really got binary search, fall asleep for about ten minutes, just don't snore, your neighbors may not appreciate it, but we're going to go over it again, because it's a problem and an idea that we're going to come back to, and I really want to make sure that I do this in a way that makes real good sense you. Again. Basic premise of binary search, or at least we set it up was, imagine I have a sorted list of elements. We get, in a second, to how we're going to get them sorted, and I want to know, is a particular element in that list.. And the basic idea of binarysearch is to start with the full range of the list, pick the midpoint, and test that point. If it's the thing I'm looking for, I'm golden. If not, because the list is sorted, I can use the difference between what I'm looking for and that midpoint to decide, should I look in the top half of the list, or the bottom half of the list? And I keep chopping it down. And I want to show you a little bit more detail of that, so let's create a simple little list here. All right? I don't care what's in there, but just assume that's my list. And just to remind you, on your handout, and there it is on the screen, I'm going to bring it back up, there's the little binary search algorithm. We're going to call search, which just calls binary search. And you can look at it, and let's in fact take a look at it to see what it does. We're going to call binary search, it's going to take the list to search and the element, but it's also going to say, here's the first part of the list, and there's the last part of the list, and what does it do inside that code? Well, it checks to see, is it bigger than two? Are there more than two elements there? If there are less than two elements there, I just check one or both of those to see if I'm looking for the right thing. Otherwise, what does that code say to do? It says find the midpoint, which says, take the start, which is pointing to that place right there, take last minus first, divide it by 2, and add it to start. And that basically, somewhere about here, gives me the midpoint. Now I look at that element. Is it the thing I'm looking for? If I'm really lucky, it is. If not, I look at the value of that point here and the thing I'm looking for. And for sake of argument, let's assume that the thing I'm looking for is smaller than the value here. Here's what I do. I change-- oops! Let me do that this way-- I change last to here, and keep first there, and I throw away all of that. All right? That's just the those-- let me use my pointer-- that's just these two lines here. I checked the value, and in one case, I'm changing the last to be mid minus 1, which is the case I'm in here, and I just call again. All right? I'm going to call exactly the same thing. Now, first is pointing here, last is pointing there, again, I check to see, are there more than two things left? There are, in this case. So what do I do? I find the midpoint by taking last minus first, divide by 2, and add to start. Just for sake of argument, we'll assume it's about there, and I do the same thing. Is this value what I'm looking for? Again, for sake of argument, let's assume it's not. Let's assume, for sake of argument, the thing I'm looking for is bigger than this. In that case, I'm going to throw away all of this, I'm going to hit that bottom line of that code. Ah. What does that do? It changes the call. So in this case,