Skip to main content
Loading Explore guides…
Introduction to Algorithms · Acedra
Home
Explore
Computer Science
Introduction to Algorithms
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
155 segments
Copy
Hide video
0:00
The following 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. Hi, I'm Srini Devadas. I'm a professor of electrical engineering and computer science. I'm going to be co-lecturing 6.006, Introduction to Algorithms this term, with Professor Eric
0:34
DeMaine. Eric, say hi. Hi, Eric. And we hope you're going to have a fun time in 6.006 learning a variety of algorithms.
0:45
What I want to do today is spend literally a minute or so on administrative details, maybe even less, what I'd like to do is to tell you to go to the website that's listed up there and read it. And you'll get all the information you need about what this class is about from a standpoint of syllabus, what's expected of you, the problem set schedule, the quiz schedule, and so on and so forth. I want to dive right in and tell you about interesting things like algorithms and complexity of
1:23
algorithms. I want to spend some time giving you an overview of the course content.
1:29
And then we're going to dive right in and look at a particular problem of peak finding, both a one-dimensional version and a two-dimensional version, and talk about algorithms to solve this peak finding problem, both varieties of it. And you'll find that there's really a a difference between these various algorithms that we'll look at in terms of their complexity. And what I mean by that is you're going to have different runtimes of these algorithms, depending on
2:03
input size, based on how efficient these algorithms are. And
2:10
a prerequisite for this class is 6042. And in 6042, you learned about asymptotic complexity. And you'll see that. In this lecture, we'll analyze relatively simple algorithms today in terms of their asymptotic complexity. And you'll be able to compare and say that this algorithm is faster than this other one, assuming that you have large inputs because it's asymptotically less complex. So let's dive right in and talk about the class.
2:52
So the one sentence summary of this class is that this is about efficient procedures for solving problems on large inputs. And when I say large inputs, I mean things like the US highway system, a map of all of the highways in the United States, the human genome, which has a billion letters in its alphabet. a social network corresponding to Facebook that, I guess, has 500 million nodes or so. So these are large inputs.
3:28
Now, our definition of large has really changed with the times. And so really, the 21st century definition of large is, I guess, a trillion. Back when I was your age, large was like 1,000. I guess I'm dating myself here.
3:45
Back when Eric was your age, it was a million. What's happening,
3:51
really, the world is moving faster. Things are getting bigger. We have the capability of computing on large inputs. But that doesn't mean that efficiency isn't of paramount concern. The fact of the matter is that you can maybe scan
4:10
a billion elements in a matter of seconds. But if you had an algorithm that required cubic complexity, Suddenly, you're not talking about 10 raised to 9. You're talking about 10 raised to 27. And even current computers can't really handle
4:26
those kinds of numbers. So efficiency is a concern. And as inputs get larger, it becomes more of a concern. So we're concerned about
4:43
efficient procedures. We're solving large scale problems in this class.
4:58
And we're concerned about scalability. Because just as 1,000 was a big number a couple of decades ago, and now it's kind of a small number, it's quite possible that But by the time you guys are professors teaching this class in some university, that a trillion is going to be a small number. And we're going to be talking about 10 raised to 18 as being something that we're concerned with from a standpoint of a common case input for an algorithm. So scalability is
5:37
important. And we want to be able to track how our algorithms are going to do as inputs get larger and larger. You're going to learn a bunch of different data structures. We'll call them
5:54
classic data structures, like binary search trees, hash tables that are called dictionaries in Python, and data structures such as balanced binary search trees that are more efficient than just the regular binary search trees. And these are all data structures that were invented many decades ago, but they've stood the test of time, and they continue to be useful.
6:23
We're going to augment these data structures in various ways to make them more efficient for certain kinds of problems. And while you're not going to be doing a whole lot of algorithm design in this class, you will be doing some design and a whole lot of analysis. The class following this one, 6046, Design and Analysis of Algorithms, is a class that you should take if you like this one. And you can do a whole lot more design of algorithms in 6046. But you will look at classic data structures and
7:00
classical algorithms for these data structures, including things like sorting and matching and so on.
7:12
And one of the nice things about this class is that you'll be doing real implementations of these data structures and algorithms
7:24
in Python. And in particular, each of the problem sets in this class are going to have both a
7:38
theory part to them and a programming part to them. So hopefully it'll all tie together the kinds of things we're going to be talking about in lectures And recitations are going to be directly connected to the theory parts of the problem sets. And you'll be programming the algorithms that we talk about in lecture, or augmenting them, running them, figuring out whether they work well on large inputs or not.
8:06
So let me talk a little bit about the modules in this class and the problem sets. And we hope that these problem sets are going to be fun for you and By fun, I don't mean easy. I mean challenging and worthwhile. So at the end of it, you feel like you've learned something, and you've had some fun along the way. So content-wise,
8:37
we have eight modules in the class, each of which, roughly speaking, has a problem set associated with it. The first of these
8:50
is what we call algorithmic thinking. And we'll kickstart that one today. We'll look at a particular problem, as I mentioned, of peak finding. And as part of this, you're going to have a problem set that's going to go out today as well. And you'll find that in this problem set,
9:12
some of these algorithms I've talked about today will be coded in Python and given to you. A couple of them are going to have bugs in them. You'll have to analyze the complexity of these algorithms, figure out which ones are correct and efficient, and write a proof for one of them. So that's sort of an example problem set. And you can expect that most of the problem sets are going to follow that sort of template. So you'll get a better sense of this
9:44
by the end of the day today, for sure, or a concrete sense of this, because we'll be done with lecture and you'll see your first problem set. We're going to be doing a module on sorting in trees. Sorting you know about, sorting a bunch of numbers. Imagine if you had a trillion numbers and you wanted to sort them. What kind of algorithm could you use for that? Trees are a wonderful data structure. There's different varieties, the most common being binary
10:13
trees. And there's ways of doing all sorts of things like scheduling and sorting using various kinds of trees, including binary trees. And we have a problem set on simulating a logic network using a particular kind of sorting algorithm and a data structure. That is going to be our second problem set. And more quickly, we're going to have
10:45
Modules on hashing, where we'll do things like genome comparison in past terms. We compared a human genome to a rat genome and discovered they were pretty similar. 99% similar, which is kind of amazing. But again, these things are so large that you have to have efficiency in the comparison methods that you use. And you'll find that if you don't get the complexity low enough, you just won't be able to complete the your program won't be able to finish running within
11:19
the time that your problem set is due, which is a bit of a problem.
11:24
So that's something to keep in mind as you test your code. The fact is that you will get large inputs to run your code. And you want to keep complexity in mind as you're coding and thinking about the pseudocode, if you will, of your algorithm itself. We will talk about numerics.
11:47
A lot of the time, we talk about such large numbers that 32 bits isn't enough, or 64 bits isn't enough to represent these numbers. These numbers have thousands of bits. A good example is RSA encryption that is used in SSL, for example. And when you go use HTTPS on websites, RSA is used at the back end. And typically, you work with prime numbers that are thousands of bits long in RSA. So how do you handle that? How does Python
12:20
handle that? How do you write algorithms that can deal with what are called infinite precision numbers? So we have a module on numerics in the middle of the term that talks about that. Graphs, really a fundamental data structure in all of computer science. You might have heard of the famous Rubik's cube. Assignment from 006, a 2 by 2 by 2 Rubik's cube. What's the minimum number of moves necessary to go from a given starting configuration
12:53
to the final end configuration where each of the faces has uniform color? And that can be posed as a graph problem. We'll probably do that one this term. In previous terms, we've done other things like the 15 puzzle. And so some of these are tentative. We definitely know what the first problem set is like, but the rest of them are, at this moment, tentative. And to finish up, shortest paths. Again, in terms passed, we've asked if you write
13:25
code using a particular algorithm that finds the shortest path from Caltech to MIT.
13:31
This time, we may do things a little bit differently. We're thinking maybe we'll give you a street map of Boston. and go figure out if Paul Revere used a shortest path to get to where he was going, or things like that. We'll try and make it fun. Dynamic programming is
13:51
an important algorithm design technique that's used in many, many problems. And it can be used to do a variety of things, including image compression, How do you compress an image so the number of pixels reduces, but it still looks like the image that you started out with that had many more pixels. So you could use dynamic programming for that. And finally, advanced topics, complexity theory, research and algorithms.
14:25
Hopefully by this time in the course, you would have been sold on algorithms and most, if not all, of you would want to pursue a career in algorithms. And we'll give you a sense of what else is there. We're just scratching the surface in this class. And there's many, many classes that you can possibly take if you want to continue to learn about algorithms or to pursue a career in algorithms. All right? So that's the story of the class, of the synopsis of the class.
14:55
And I'd encourage you to go spend a few minutes on the website. In particular, please read the collaboration policy and get a sense of what is expected of you, what the rules are in terms of doing the problem sets, and the course grading breakdown and the grading policies are all listed on the website as well. All right. OK. So let's get started. I want to talk about a specific problem. and talk about algorithms for a
15:30
specific problem. We picked this problem because it's so easy to understand. And they're fairly straightforward algorithms that are not particularly efficient to solve this problem. And so this is kind of a toy problem. But like a lot of toy problems, it's very evocative in that it points out the issues involved in designing efficient algorithms. So we'll start with a one-dimensional version of what we call peak finding.
16:05
And a peak finder is something, in the one-dimensional case,
16:14
runs on an array of numbers. And I'm just putting
16:22
symbols for each of these numbers here.
16:28
The numbers are positive, negative. We'll just assume they're all positive. It doesn't really matter. The algorithms we describe will work. And so we have this one dimensional array that has nine different positions. And a through i
16:47
are numbers. And we want to find a peak.
16:53
And so we have to define what we mean by a peak. And so in particular, As an example, position two is a peak if and only if
17:11
b greater than or equal to a and b greater than or equal to c.
17:18
So it's really a very local property corresponding to a peak. In the one-dimensional case, it's trivial. Look to your left. Look to your right. If you're equal or greater than both of the elements that you see on the left and the right, you're a peak. OK? And in the case of the edges, you only have to look to one side. So position 9 is a peak if i greater than or equal to h. So you just have to look to your left there,
17:55
because you're all the way on the right-hand side. All right? So that's it. And the statement of the problem, the one dimensional version, is
18:08
find the peak if it exists.
18:19
All right? That's all there is to it. I'm going to give you a straightforward algorithm. And then we'll see if we can improve it. You can imagine that the straightforward algorithm is something that just walks across the array. But we need that as a starting point
18:43
for building something more sophisticated.
18:49
So let's say we start from left.
18:57
All we have is one traversal, really.
19:05
So let's say we have 1, 2, and then we have n over 2 over here corresponding to the middle of this n element array. And then we have n minus 1 and n. What I'm interested in doing is not only coming up with a straightforward algorithm, but also precisely categorizing what its complexity is in relation to n,
19:33
which is the number of inputs. Yeah, question? Why do you say if it exists with the criteria that you have for a peak bar, do you guarantee the peak? That's exactly right. I was going to get to that. So if you look at the definition of the peak, then what I have here is greater than or equal to. OK? That's a great question that was asked. Why is there if it exists in this problem?
20:04
Now, in the case where I have greater than or equal to, then this is a homework question for you and for the rest of you. Argue that any array will always have a peak. Now, if you didn't have the greater than or equal to, and you had a greater than, then Can you make that argument? No, you can. Right? So great question. In this case, it's just a question. You would want to modify this problem statement to find a peak. But if I had a different definition of a peak, and
20:43
this is part of algorithmic thinking, you want to be able to create algorithms that are general. So if the problem definition changes on you, you still have a starting point to go attack the second version of the problem. OK? So
20:59
you could eliminate this in the case of the greater than or equal to definition, the if it exists, because the peak will always exist. But you probably want to argue that when you want to show the correctness of your algorithm. And if, in fact, you had a different definition, well, you would have to create
21:17
an algorithm that tells you for sure that a peak doesn't exist or find a peak if it exists. Right? So that's really the general case. Many a time, it's possible that you're asked to do something, and you can't actually give an answer
21:34
to the question or find something that satisfies all the constraints required. And in that case, you want to be able to put up your hand and say, you know what? I searched long and hard. I searched exhaustively. Here's my argument that I searched exhaustively, and I couldn't find it. If you do that, you get to keep your job. Otherwise, there's always the case that you didn't search hard enough. So it's nice to have that argument. All right, great. Thanks for the question. Feel
22:04
free to interrupt. Raise your hand. And I'm watching you guys, and I'm happy to answer questions at any time. So let's talk about the straightforward algorithm. The straightforward algorithm is something that starts from the left and just walks across.
22:21
And you might have something that looks like that. All right, by this I mean the numbers are increasing as you start from the left. The peak is somewhere in the middle. And then things start decreasing. So in this case, this might be the peak.
22:47
You also may have a situation where the peak is all the way on the right. You started from the left. And it's 1, 2, 3, 4, 5, 6, literally in terms of the numbers. And you're going to look at n elements going all the way to the right in order to find the peak. So in the case of the middle, you'd look at n over 2 elements
23:13
if it was right in the middle. And the complexity, worst case complexity,
23:26
is what we call theta n. And it's theta n because in the worst case, you may have to look at all n elements. And that would be the case where you started from the left, and you had to go all the way to the right. Now remember, theta n is essentially something that says of the order of n. So it gives you both the lower bound and an upper bound. Big O of n is just the upper bound. And what we're saying here is we're saying This algorithm that starts from the left is going to
23:59
essentially require, in the worst case, something that's a constant times m. And that constant could be 1. You could certainly set things up that way. Or if you had a different kind of algorithm, maybe you could work on the constant. But bottom line, we are only concerned at this moment about asymptotic complexity. And the asymptotic complexity of this algorithm is linear. All right? That makes sense? OK. So someone help me do better. How
24:39
can we do better? How can we lower the asymptotic complexity of a one dimensional peak finder? Anybody want to take a stab at that? Yeah, back there.
25:00
For example, if you're in the middle on the right side, there's a higher number on the right side, then you would just look at that because you know there's a peak somewhere in there. And you continue cutting it back. Excellent. Excellent. That's exactly right. So you can do something different, which is essentially try and break up this problem, use a divide and conquer strategy, and recursively break up this one dimensional array into smaller arrays,
25:28
and try and get this complexity down. There's only one peak. No, we're not. OK. It's find a peak if it exists. And in this case, it's find a peak because of the definition. We don't really need this as it was discussed. All right? OK. So that was a great answer. And
25:52
this class, after a while, is going to get boring, right? Every class gets boring. So we try and break the monotony here a bit. And so, and then the other thing that we realized was that these seats you're sitting on, this is a nice classroom, but the seats you're sitting on are kind of hard. Right? So what Eric and I did was we decided we'll help you guys out, especially the ones
26:14
who are interacting with us. And we have these cushions
26:20
that are 6.006 cushions. And, you know, that's a two by two by two Rubik's cube here. And since you answered the first question, you get a cushion. This is kind of like a Frisbee, but not really. So I'm not sure I'm going to get it to you. But the other thing I want to say is this is not a baseball game, where you just grab the balls that come by. This is meant for him, my friend in the red shirt. So here you go. Ah, too bad. All right. It is soft. So it won't hurt you if it hits you.
26:51
All right? So if you've got a bunch of these, And raise your hands when I ask. There's going to be, I think, there's some trivial questions that we're going to ask just to make sure you're awake. So an answer to that doesn't get you a cushion. But an answer like, what's your name? Jace. Jace. An answer like Jace just gave is, that's a good answer to a non-trivial question. That gets you a cushion. OK? All right, great. So let's put up Jace's algorithm up
27:23
here. I'm going to write it out for the 1D version.
27:41
So what we have here is a recursive algorithm.
28:03
So the picture you want to keep in your head is this picture that I've put up there. And this is a divide and conquer algorithm. You're going to see this over and over, this paradigm, over and over in 6.006. We're going to look at the n over 2 position.
28:26
And we're going to look to the left, and we're going to look to the right. And we're going to do that in sequence. So
28:36
if a n over 2 is less than
28:42
a n over 2 minus 1, then
28:50
only look at left half, 1 through n over 2 minus 1, to look for p. for a peak. So that's
29:10
step one. And I could have done the right hand side or the left hand side. It doesn't really matter. I chose to do the left hand side first, the left half. And so what I've done is, through that one step, if, in fact, you have that condition a n over 2 is less than a n over 2 minus 1, then you move to your left and you work on one half of the problem. But if that's not the case, then if
29:42
n over 2 is less than n by 2 plus 1, then
29:49
only look at n over 2 plus 1 through n for a peak. So I haven't bothered writing out all the words. They're exactly the same as the. Left-hand side, you just look to the right-hand side. Otherwise, if both of these conditions don't fire, you're actually done. OK? That's actually the best case in terms of finishing early, at least in this recursive step. Because now the n over 2 position is a peak.
30:27
Because what you've found is that the n over 2 position greater than or equal to both of its adjacent positions. And that's exactly the definition of a peak. So you're done. OK? So all of this is good.
30:44
You want to write an argument that this algorithm is correct. And I'm not going to bother with that. I just waved my hands a bit. And you all nodded. So we're done with that. But the point being, you will see in your problem set a precise argument for a more complicated algorithm, the 2D version of this. And that should be a template for you to go write a proof or an argument, a formal argument, that a particular algorithm is correct, that it does what it claims
31:22
to do. And in this case, it's two, three lines of careful reasoning that I essentially say, given the definition of the peak, that this is going to find a peak in the array that you're given. So we all believe that this algorithm is correct. Let's talk now about the complexity of this algorithm. Because the whole point of this algorithm was because we didn't like this theta n complexity corresponding to the straightforward algorithm. So we'd like to do better.
32:08
So what I'd like to do is ask one of you to give me a recurrence relation of the kind t of n equals blah, blah, blah,
32:18
that would correspond to this recursive algorithm, this divide and conquer algorithm. And then using that, I'd like to get to the actual complexity in terms of what the theta of complexity corresponds to. Yeah, back there.
32:52
Great, exactly right. That's exactly right. So if you look at this algorithm and you say, from a computation standpoint, can I write an equation corresponding to the execution of this algorithm? And you say t of n is the work that this algorithm does on input of size n.
33:25
then I can write this equation.
33:31
And this theta 1 corresponds to the two comparisons that you do looking at, potentially, the two comparisons that you do looking at the left hand side and the right hand side. So 2 is a constant. So that's why we put theta 1. All right? So you get a cushion too. Watch out, guys.
33:49
Whoa. Actually, that wasn't so bad. Wears left. Eric, where's left? So if you take this and you start
34:02
expanding it, eventually you're going to get to the base case, which is
34:09
t of 1 is theta 1. Because you have a one element array.
34:16
For that array, you're just going to return that as a peak. And so if you do that and you expand it all the way out, then You can write T of n equals theta 1 plus theta 1. And you're going to do this log to the base 2 of n times. And adding these all up
34:43
gives you a complexity theta log 2 of n. So now you compare this with that. And there's really a huge difference. There's an exponential difference. If you coded up this algorithm in Python,
35:01
and I did both these algorithms for the 1D version, and if you run it
35:08
on n being 10 million or so, then this algorithm takes 13 seconds. The theta n algorithm takes 13 seconds. And this one takes 0.001 seconds. Huge difference. So there is a big difference between theta n and theta log n. It's literally the difference between 2 raised to n and n. It makes sense to try
35:38
and reduce complexity, as you can see, especially if you're talking about large inputs.
35:45
And you'll see that more clearly as we go to a 2D version of this problem. So you can't really do better for the 1D. The 1D is a straightforward problem. It gets a little more interesting. The problems get a little, excuse me, the algorithms get a little more sophisticated when we look at a 2D version of peak finding. So let's talk about the 2D version.
36:15
So as you can imagine, in the 2D version, you have a matrix or a two-dimensional array. And we'll say this thing has n rows and m columns.
36:34
And now we have to define what a peak is. And it's a hill. It's the obvious definition of a peak. So if you had A in here,
36:45
C, B, D, E, then as you can guess, A is a 2D peak
36:59
if and only if A greater than or equal to B, A greater than or equal to D, C, and E. So it's a little hill up there. And again, I've used the greater than or equal to here. So that's similar to the 1D in the case that you'll always find a peak in any 2D matrix. Now, again, I'll give you the straightforward algorithm. And we'll call it the greedy ascent algorithm.
37:41
And the greedy ascent algorithm essentially picks a direction and tries to follow that direction in order to find a peak. So for example, If I had this particular
38:01
matrix 14 13 12 15 9, 11, then what might happen is if I started at some arbitrary midpoint, So the greedy ascent algorithm has to make choices as to where to start. Just like we had different cases here, you have to make a choice as to where to start. You might want to start in the middle. And you might want to work your way left first. Or you just keep going left, or keep going right. And if you hit an edge, you go down. So you make some choices as to what the default traversal directions are.
38:47
And so if you say you want to start with 12, you're going to go look something to your left. And if it's greater, then you're going to follow that direction. If it's less, then you're going to go in the other direction in this case, for example. So in this case, you'll go 12, 13, 14, 15, 16 17 19 and 20. And you'll find this peak. Now, I haven't given you the specific details. of a greedy ascent algorithm. But I think
39:26
if you look at the worst case possibilities here with respect to a given matrix, and for any given starting point, and for any given strategy, in terms of choosing left first versus right first, or down first versus up first, you will have a situation where Just like we had in the 1D case, you may end up touching
39:57
a large fraction of the elements in this 2D array. So in this case, we ended up touching a bunch of different elements. And it's quite possible that you could end up touching, starting from the midpoint, you could end up touching half the elements, and in some cases, touching all of the elements. So if you do a worst case, analysis of this algorithm, a particular algorithm with particular choices in terms of the starting point and the direction of search, a
40:30
greedy ascent algorithm would have theta nm complexity. And in the case where
40:37
n equals m, or m equals n, you'd have theta n squared complexity. I want to spend very much time on this because I want talk to you about the divide and conquer versions of this algorithm for the 2D peak. But hopefully you're all with me with respect to what the worst case complexity is. All right? People buy that? Yeah, question back there. Is that an approximation or can you actually get to n times m traversal traversal? So there are specific. greedy ascent algorithms and specific
41:19
matrices where if I give you the code for the algorithm and I give you a specific matrix, that I could make you touch all of these elements. That's correct. So if you're talking about worst case, you're being very paranoid when you talk about worst case complexity. And so I'm hand-waving a bit here simply because I haven't given you the specifics of the algorithm yet. This is really a on a set of algorithms because I haven't given you the code. I haven't
41:46
told you where it starts and which direction it goes. But you go do that, fix it, and I would be the person who tries to find the worst case complexity. Certainly, it's very easy to get to theta and m in terms of having some constant multiplying n times m. But you can definitely get to that constant being very close to 1, if not 1. So let's talk about divide and conquer. Let's say
42:17
that I did something like this, where I just tried to jam the binary search algorithm into the 2D version.
42:37
So what I'm going to do is
42:43
I'm going to pick the middle
42:49
column, j equals m over 2. And I'm going to find a 1D peak
43:00
using whatever algorithm I want. And I'll probably end up using the more efficient algorithm, the binary search version that's gone all the way to the left of the board there. And let's say I find a binary peak at ij. Because I've picked a column, and I'm just finding a 1D peak. So this is j equals m over 2. That's i. Now,
43:27
I use ij, in particular, row i
43:32
as a start to find a 1D peak on row i.
43:48
up here and I'm really happy, OK, because I say, wow. I picked a middle column. I found a 1D peak. That is theta n complexity to find a 1D peak, as we argued. And once I, theta m.
44:08
Oh, I'm sorry. You're right. The log n complexity, that's what this was. Where do I have that here? Yeah, log n complexity. Thanks, Eric. And then once I do that, I can find a 1D peak on rho i.
44:26
In this case, the rho i would be m wide. So it would be log m complexity. If n equals m, then I have a couple of steps of log n. And I'm done. Am I done? No.
44:39
Can someone tell me why I'm not done precisely? Yep.
44:54
That's exactly correct. So this algorithm is incorrect. It doesn't work. It's efficient but incorrect.
45:06
You want to be correct. Being correct and inefficient is definitely better than being
45:14
incorrect and efficient. So this is an efficient algorithm in the sense that it would only take log n time. But it doesn't work. I'll give you a simple example here where it doesn't work.
45:32
The problem is a 2-D peak
45:40
may not exist on rho i.
45:46
And here's an example of that.
45:53
Actually, this is exactly the example of that. Let's say that I started
46:01
with this row. I'm starting with the middle row, and I could start with this one or that one. Let's say I started with that one. I
46:12
end up finding a peak. And if this were 10 up here, I choose 12 as a peak. It's quite possible that I've returned 12 as a peak, even though 19 is bigger, because 12 is a peak, given 10 and 11 up here. And then when I choose this particular row, and I find a peak on this row, it would be 14. That is a 1D peak on this row, but 14 is not a 2D peak. So this particular example, 14 would return 14. And 14 is not a 2D peak.
46:53
You can collect your cushion after the class. So not so good. Looked like an efficient algorithm, but doesn't work.
47:06
So how can we get to something that actually works? So the last algorithm that I'm going to show you, and you'll see four different algorithms in your problem set. that you'll have to analyze the complexity for and decide if they're efficient and if they're correct. But here's a recursive version that
47:34
is better than, in terms of complexity, than the greedy ascent algorithm. And this one works. So what I'm going to do is pick a middle column.
47:49
equals m over 2 as before. I'm going to find
47:56
the global maximum on column j.
48:05
And that's going to be at ij. I'm going to compare
48:13
i comma j minus 1, i comma j. and ij plus 1, which means that once I've found the maximum in this row, I'm going to look to the left and the right and compare. I'm going to pick the left columns if i comma j minus 1 is greater than i comma j. And similarly for the right,
48:49
If, in fact, either of these two conditions don't fire, and what I have is i comma j is greater than or equal to i comma j minus 1 and i comma j plus 1, then I'm done. Just like I had for the 1D version, if
49:14
i comma j is greater than or equal to i comma j minus 1 and i, j plus 1, that implies i, j
49:26
is a 2d peak. And the reason that's the case is because i, j was the maximum element in that column. So you know that you've compared it to all of the adjacent elements looking up and looking down. That's the maximum element. Now you've looked at the left and the right. And in fact, it's greater than or equal to the elements on the left and the right. And so therefore, it's a 2dp. OK? So in this case, when you pick the left
49:56
or the right columns, you'll pick one of them. You're going to solve the new problem with half the number of columns.
50:16
All right? And again, you have to go through. an analysis or an argument to make sure that this algorithm is correct. But it's intuitively correct simply because it matches the 1D version much more closely. And you also have your condition where you break away right here, where you have a 2D peak, just like the 1D version. And what you've done is break this matrix up into half the size. And that's essentially why this algorithm works.
50:51
When you have a single column, find the global maximum,
51:07
and you're done. So that's the base case. So let me end with just writing out what recurrence relation for the complexity of this is and argue
51:20
what the overall complexity of this algorithm is. And then I'll give you the bad news. All right. So
51:32
overall, what you have is you have something like t of nm equals t of n m over 2 plus theta n. Why is that? Well, n is the number of rows. m is the number of columns. In one case, you will be breaking things down into half the number of columns, which is m over 2. And in order to find the global maximum, you'll be doing theta n work, because you're finding the global maximum. You just have to scan it.
52:05
That's what it's going to take. And so if you do that and you go run it through, And you know that T of n1 is theta n, which is this last part over here. That's your base case. You get T of nm is theta of n added to theta of n
52:28
log of m times, log 2 of m times, which is theta of n
52:40
log 2 of m. So you're not done with peak finding.
52:48
What you'll see is four algorithms coded in Python. I'm not going to give away what those algorithms are, but you'll have to recognize them. You will have seen versions of those algorithms already in lecture. And your job is going to be to analyze the algorithms, as I said before, prove that one of them is correct, and find counterexamples for the ones that aren't correct. The course staff will stick around here
53:15
to answer questions, logistical questions, or questions about lecture. And I owe that gentleman a cushion.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat