Transcript
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. So, welcome to 6.046. My name is Srini Devadas. I'm a professor of computer science. Uh This is my 27th year at MIT. I'm teaching this class with great course staff with co-lecturers Eric Demaine over here. And Nancy Lynch who's over there. And a whole bunch of TAs who you will meet through the term. Uh we just signed up our last TA yesterday.
So, at this point even I don't know their names. Uh but uh we hope to have a great semester. I'm very excited to be teaching this class with Eric and Nancy. I recognize some of you folks from 006 from a year ago. Uh so, hello again. Uh and from other classes. Uh and so, uh let's get started. Um I mentioned 006. Uh 006 is a prerequisite for this class. Uh so, if by chance you've skipped the class, uh I MIT or EECS has allowed you to skip that. Uh make sure um you check in with us uh to see that uh you are ready for 6.046 because we will assume that you know the 6.006 material. Uh and by that I mean basic material on data structures, classical algorithms like sorting, uh algorithms for um uh for dynamic programming or algorithms that use dynamic programming I should say.
Uh algorithms for shortest paths etc. Uh 6.046 itself, uh we're going to run this course uh pretty much off the Stellar website in the sense that that'll be your one-stop shop for getting everything including lecture handouts, uh problem sets, turning in your problem sets etc. And I should mention that this course is being taped for OpenCourseware. And while it'll take a little bit of time for the videos to be put online, uh we hope to do that perhaps in in clumps uh before the exams, the the quizzes that you will have as we have to have in in our class. Uh so So, let me uh just say a couple more things about logistics and then we'll get started with the technical content.
Uh as I mentioned we're going to be running this course off Stellar. Uh please sign up for registration section by going to the Stellar website and choosing a section that works for your schedule. Uh sections go from 10:00 a.m. all the way to 3:00 p.m. I think. Uh and uh we've placed a limit on the number of students per section. We want the sections to be manageable in size, but there's plenty of room for everybody and the schedule flexibility should allow you to choose a section uh pretty easily. I we have a course information document and an objectives document on the website uh that has a lot of details on the grading policy, the collaboration policy etc.
Please read it very carefully uh from the first page all the way to the end. And I will mention one thing that you should be careful about uh which is that while problem sets are only 30% of the grade, uh we do require you to attempt the problems and there's actually a penalty associated with not attempting problems and not turning problem sets in that is way more than 30%. All right. So, keep that in mind and please read the collaboration policy as well as the grading policy carefully and feel free to ask us questions. You can ask us questions anonymously through Piazza or you could certainly send us email.
All the information is on Stellar. So, that's all I really had to say about course logistics. Um let me tell you a little bit about how the content of this course is structured. Um We have several modules and uh Eric, Nancy, and I'll be uh in charge of each of these different modules as the term goes on. Our very first module um is going to start really next time. Today is really an overview lecture. But uh it's a module on divide and conquer and you learned about this divide and conquer paradigm in 006 or equivalent classes. Uh it's breaking up a problem into smaller problems and getting efficiency that way.
Merge sort is a classic algorithm that follows the divide and conquer paradigm. We're going to take it to a new level and I guess that's sort of the theme of 046. You know, take the material in 006 and raise the stakes a little bit, raise the level of sophistication and you'll see things like fast Fourier transform, uh finding an algorithm for a convex hull. We'll do that next time that uses the divide and conquer paradigm. Uh we're going to do a ton of optimization. Divide and conquer can obviously be used for search and also for optimization. In particular, uh we'll look at strategies corresponding to greedy algorithms, Dijkstra which hopefully you remember shortest path algorithm uh from 006 is a example of a greedy algorithm.
We'll see a bunch of other examples. Um And we'll we'll look at one today. And dynamic programming, it's a wonderful uh hammer uh algorithmic hammer that you can apply to a wide variety of problems. Certainly to shortest paths as well. We'll look at it in many different contexts. And then really quickly, um network flow which is a problem that's associated with here's a network. There's capacities associated with a network. Uh the capacities could correspond to uh uh the width of the roads in a in in in a highway system or not or the number of lanes, the amount of traffic that can go through. How do I maximize the set of commodities or the amount of commodities that I can push through the network.
That uh it turns out is again a uh uh a problem that has many different applications. So, it's really a collection of problems. Um we're going to spend some time a little bit today, but a little more than in 6.006 talking about intractability. So, a lot of the algorithms that we're going to talk about are efficient in the sense that they're polynomial time solvable. And uh of course, you know, polynomial time solvable doesn't imply efficiency in the practical sense. So, if you have an n raised to eight algorithm, it's polynomial time, but really it's not something that you can use on real world problems where n is relatively large.
But I generally in a theoretical computer science class, we'll think about tractable problems as being those that have polynomial time algorithms uh that can solve them exactly or optimally. But uh intractability then corresponds to problems that uh at the moment uh we don't know of a polynomial time algorithm to solve them and the best algorithms we have take worst case exponential time. And so, the question is what happens for those problems? Uh and we'll look at things like approximation algorithms uh that can get us in the case of optimization problems, uh get us with to within a certain fraction of optimal guaranteed and run in polynomial time.
So, you can't get the absolute best, but you can get within 10% or you can get within a factor of two. That may be enough for um a particular instance of a problem or or a set of instances of a problem. And we'll do a bunch of advanced topics. I think we have distributed algorithms planned. Nancy works in that area. Uh and uh uh I we'll also talk about cryptography. There's a deep connection between um number theory algorithms and cryptography that uh towards the end of the lecture I should say towards the end of the course I will look at a little more closely. So, so much for overview. Uh let's get started with today's lecture for real.
And here's the theme of today's lecture. Um I talked a bit about tractability and intractability. And what is fascinating about algorithms is that you might see a problem uh that has a fairly obvious polynomial time solution or a linear time solution. Then you change it ever so slightly and uh the linear time algorithm doesn't work. Maybe you can find a cubic algorithm. Uh and then you change it a little more little more and you end up with something that you can't find you can't find a polynomial time algorithm for. You can't prove that the polynomial time algorithm or any polynomial time algorithm gives you the optimal solution in all cases.
And and then you go off into complexity theory. Uh, you maybe discover that uh our show that this this problem is NP-complete and now you're in the intractability domain. So, very small changes in problem statements can end up with very different situations from a standpoint of algorithm complexity. And so that's really what I want to point out to you in some detail with a concrete example. So, I want to get a little bit uh pedantic here with respect to intractability and tractability. Uh, you've seen I think these terms before in the one lecture in 006. Uh, but we'll go over this in some detail today and more later on in the semester.
But for now, uh let's recall some basic terminology associated with tractability and intractability or complexity theory broadly speaking. Capital P is the class of problems solvable in polynomial time. And think of that as big O n raised to k for some constant k. Now, you can have log factors in there, but once you put a big O in there, uh you're good. Uh, you can always say uh uh order n even if it's a logarithmic problem. Uh, big O lets you be sloppy like that. Uh, and uh there are many examples of polynomial time algorithms, of course, uh for interesting problems like shortest paths. So, the shortest path problem is order V square where V is the number of vertices in the graph.
There's algorithms for that. Uh, you can do a little bit better uh if you um uh use fancier data structures. Uh, but uh that's an example. NP is uh another class of problems that's very interesting. Uh, this is the class of problems uh that are whose solution is verifiable in polynomial time. Uh, so an example of a problem in NP uh that uh is not known to be in P is the Hamiltonian cycle problem. And the Hamiltonian cycle problem corresponds to given a directed graph find a simple cycle. So, you can't repeat vertices, but you need the simple cycle to contain each vertex in V. And uh determining whether a given cycle is a Hamiltonian cycle or not is simple.
You just uh traverse the cycle, make sure that you've touched all the vertices exactly once, and you're done. Clearly doable in uh polynomial time. So, therefore Hamiltonian cycle is in NP, but uh determining whether a graph has a Hamiltonian cycle or not is a is a hard problem. And uh I in particular uh the notion of NP-completeness um is something that um uh defines the level of intractability for NP. The NP-complete problems are the hardest problems in NP. And Hamiltonian cycle is one of them. If you can solve any NP-complete problem in polynomial time, you can solve all problems in NP in polynomial time.
So, that's what I meant by saying that NP-complete problems are in some sense the hardest problems in NP because solving one of them gives you everything. So, the definition of NP-completeness is that the problem is in NP and is as hard an informal definition as any problem in NP. And so Hamiltonian cycle is an NP-complete problem. Satisfiability is an NP-complete problem and there's a whole bunch of them. So, going back to our theme here, what I want to show you is how for an interval scheduling problem that I'll define in a couple of minutes, uh how we move from linear time, therefore P, to something that's still in P, but it's a little more complicated if I change the constraints of a problem a little bit.
And finally, if I add more constraints to the problem, generalize it, and you can think of it as adding constraints or general generalizing the problem, uh you you get uh with small changes to something that becomes NP-complete. Right? So, uh this is something that uh algorithm designers have to keep in mind because uh before you go off and try to design an algorithm for a problem, uh you'd like to know where in the spectrum your problem resides. And uh in order to do that, uh you need to understand algorithm paradigms, obviously, and be able to apply them. But you also have to understand reductions where you can try and translate one problem to another, and if you can do that and uh the first problem um is is is is known to be hard, then you can make arguments about the hardness of the of your problem.
So, these are the kinds of things that we'll touch upon today. Uh, the uh analysis of uh of of an algorithm, uh the design of an algorithm, and also uh the complexity analysis of an algorithm, which may not just be an asymptotic, well, this is order n cubed or order n square, but more uh in the realm of uh NP-completeness as well. Okay? So, so much for context, let's dive into our interval scheduling problem, which is something that you can imagine doing for classes, uh tasks, you know, particular schedule during a day, you know, life in general. Uh, and in general setting, we have resources and requests.
And we're going to have a single resource for our first version of the problem. And our requests are uh 1 through n, and we can think of these requests as requiring time corresponding to the resource. So, the request is for the resource, and you want time on the resource. Maybe it's computation time, maybe it's your time. I could be anything. Um each of these requests corresponds to an interval of time, and that's where the name comes from. SI is the start time. FI is the finish time. And we're going to say SI is strictly less than FI. Okay, so I didn't put less than or equal to there because I want these requests to be non-null, non-zero.
So, otherwise they're uninteresting. And uh we're going to have a start time and we're going to have an end time, and they're not equal. So, that's uh the first part of the specification of the problem. And then the second part, uh which is intuitive, is that two requests we have a single resource here, remember, um I and J are considered to be compatible, which means you can satisfy both these requests. They're compatible. Incompatible requests you can't satisfy with your single resource simultaneously, provided they uh don't overlap. And an overlapping condition might be that fi is less than or equal to sj and or fj less than or equal to si.
So again, I put a less than or equal to here, which is um important to spend a a minute on. I I what I'm saying here uh uh that uh in in this context is that I really have um open-ended in intervals on the on the right-hand side corresponding to the uh fis. So, pictorially you you could look at it this way. Um let's say I have intervals like this. So, this is interval number one. That's interval number two. All right, here uh I have s of one out here, f of one out here s of two out here, and f of two out here. So, this is s uh f of one for that and s of two for this. I'm allowing s of two and f of one to be exactly equal and I still agree that these two are compatible requests.
Okay? So, this is just uh uh uh I guess it's terminology. It's uh uh it's it it it it's ba- it's our definition of compatibility. So, you can imagine now an optimization problem that is associated with interval scheduling where in a different example I have this interval corresponding to s1 and f1 I might have a different interval here corresponding to uh two, then corresponding to three and then maybe I got four here five and six. Right? So, those are my six intervals corresponding to my input. I have a single resource. I've just drawn out in a two-dimensional form the six different requests that I have, the six different intervals.
Intervals and requests are synonyms. I and my goal here, and it's kind of obvious in this example is to select a compatible subset of requests or intervals that is of maximum size. And I'd like to do this efficiently. So, we'll always consider efficiency here, but in terms of the specification of the problem as opposed to a requirement on the uh the complexity of the algorithm I I want maximum size for this subset. So, as I showed you or I mentioned earlier uh in this case it is clear from uh the drawing that I put up there that the maximum size for that six request example that I have is three.
Okay? So, that's the setup. Now we're going to spend the next few minutes talking about uh a greedy strategy for solving this particular problem. Uh we don't know if the greedy strategy is going to always produce the maximum size or not. In fact, it depends on the particular uh greedy heuristic, the the selection heuristic that a greedy algorithm uses. So, that's going to be important and we'll take a look uh and hopefully you can suggest some at uh a a few different greedy heuristics. But, my claim, overall claim that I'm going to have to spend a bunch of time here justifying and eventually proving is that we can solve this problem using a greedy algorithm.
Now, what is a greedy algorithm? You've seen some examples. Um as the name implies, it's something that's uh myopic. It's doesn't look ahead. It looks to maximize the the very first thing that you can maximize. Uh it uh it says uh uh you know, traffic is a good example. Uh don't let anybody cut in front of you. Uh you you got some room up there, you know, get up there. As I uh uh generally people um are greedy when it comes to uh you know, getting to work, uh trying to uh minimize the time in this case on the time that they spend on the road. But, uh we've had other examples. Uh uh for example, when you uh look at interval scheduling, uh you might say uh I'm going to pick uh uh the smallest request and I'm going to pick the smallest request first uh and I'm going to try and collect together as many requests as possible.
And if the requests are small in the sense that si and fi for the two requests are uh close to each other, then maybe that's the best strategy. Right? So, that's an example of uh a greedy strategy for our particular example. But, just to give you a slightly better definition of of greedy than what I've said so far a greedy algorithm is uh myopic algorithm that does two things. It processes the input one piece at a time with no apparent look ahead. So, what happens is that greedy algorithms are typically quite efficient. Um what you end up doing is um looking at a small part of the problem instance and deciding what to do.
Uh when once you've done that, uh then you're in a situation where the problem has gotten a little bit simpler because you've already solved part of it and then you move on. So, what would a template for a greedy algorithm look like for our interval scheduling problem? Here's here's a template that hopefully puts it all together and gives you a a good sense of what I mean by greedy at least in this context. So, before we even get into particulars of uh selection strategies let me give you a template for greedy interval scheduling. So, step one. Use a simple rule to select a request. And once you do that if you selected a particular request let's say you've selected one.
What happens now? Once you've selected one. Well, you're done. You can't select two, you can't select three, you can't select four, you can't select five, you can't select six. Right? So, if you're selected one in this case uh you're done, but we have to codify that in a step here. And what that means is that we have to reject all requests that are incompatible with I. Okay? And at this point because we've rejected a bunch of requests, our problem got smaller. Okay? And so you now have a smaller problem and you just repeat. Go back to step one until all requests are processed. Right? So, that's a classical template for a greedy algorithm.
Uh you just go through these really simple steps. And the reason this is a template is because I haven't specified a particular rule. And so, it's not quite an algorithm that you can code yet because we need a rule. So with all of that context uh let me ask you uh what is a rule that you think would work well for an interval scheduling problem? Yeah, go ahead. Uh select one with the earliest finish Select one with the earliest finish time. All right. Well, I did not want that answer. But now that you've given me the answer, I have to do something about this. Right? So, I want a different answer, but uh So, we'll go to a different person, but before I do that, um let me uh uh uh reward you for that answer I did not want.
Um with uh a limited edition 6046 Frisbee. Okay? All right. Uh you need to stand up because I don't want to take people's heads off. Yeah, sorry. Right? So, here you go. All right. Good. So, people do People do cookies and candy. I think Eric, Nancy, and I are cooler. So, we do Frisbees. Okay. All right, good. So, the fact of the matter was that uh this class was scheduled for 9:30 to 11:00 on Tuesdays and Thursdays. That's when we decided to do Frisbees. Uh and then it got shifted over to 11:00 to 12:30, but then we bought all these Frisbees, so we said whatever. Right? It's not like we could use all of them.
Right? All right, good. So, I don't like that answer. Uh and I want a different one. Give me Give me another one. Yeah, go ahead. I'm sorry? Iterate through in numerical order. Is that going to work? And what's an example where it didn't work? The one right there. Right? Should I get her a Frisbee? We should. I'm going to be generous at the beginning. You can just Right. But that's an answer I liked. Yeah. Oh. Here you go. So, uh iterate through in numerical order isn't going to work. This is a great example, right? Right there. Right? Uh um Give me another one. I'm going to run out of Frisbees right here.
Over there. Yeah. Ah, try the one with the shortest time. Okay, so um so the shortest time in this case might be this one, right? Uh the shortest time might be this one, and hey, maybe that might work in this case because you pick this one, which is the shortest, or maybe it's five, which is the shortest. Uh either way, you could get two, five, and six in a looking at this picture seems to work. Uh maybe four, five, and six if you pick five first, etc., right? Uh I'll give you a Frisbee if you can take that same algorithm and give me a There's one right in the middle. Exactly right. Yeah. So, uh let's see where What do I do?
Oh, here. So, pictorially, you can look at this and you can actually figure out whether your heuristic works or not. But this is I think what you were thinking about. There you go, right? So, do you get one? So, that clearly doesn't work. So, this one was smallest doesn't work. Uh the suggestion here was uh numeric doesn't work. Um Here's one that uh might actually work. Uh for each request, find the number of incompatible requests. So, you got a request, you can always intersect the other requests with it and decide whether these the the second request is compatible or not, right? And you do this for every other request.
And you can collect together uh numbers associated with how many incompatible requests a particular request has, and you say, "Well, uh let me use that as a heuristic." Right? So, each request, find number of incompatible requests, and select the one with the minimum number of incompatibles. Right? So, just to be clear, in this case, you would not select one uh because clearly one is incompatible with every other request. Right? So, that clearly is not numeric order. In this case, you would not select this one because it's incompatible with this one and that one. Right? So, you select the one which has the minimum number of incompatibles.
Right? So, do you think this is going to produce the the correct answer, the maximum answer in every possible case? No? Who said no? Well, anybody who said no should give me a counterexample. Yeah, go go for it. Right. So, I that's that's a good thought. Uh um you'll have to concretize that, and I think this particular example does exactly what you said. Um which is instantiates your um notion of mutual incompatibility. So, here's here's an example where I have something that's a little more complicated. As you can see, this is a pretty good heuristic. It's not perfect, as you can see from this example, where I have s- something like this.
So, if you look at this, what I have here is I have a just a bunch of requests uh which have uh this is incompatible with this and that and these two. So, clearly a lot of incompatibilities for these. Lot of incompatibilities for these. Which is the minimum? The one in here. Right? But do What happens if you select that? Well, clearly you don't get the solution, which is optimal, right? The one on top. Right? So, this is a bad selection. So, this doesn't work either. Okay? Here you go. So, as it turns out, uh the reason I didn't like that first answer was it was it was correct. I it it's actually a a beautiful heuristic.
Earliest finish time is a heuristic uh that uh is Well, it's not really a heuristic in the sense that if you use that selection rule, uh then it works in every case. Uh in every case, it's going to get you the maximum number. Okay? Earliest finish time. Right? So, what does that mean? Well, it just means that I'm going to scan the f of i's associated with the list of requests that I have, and I'm going to pick the one that is minimum. Minimum f of i means earliest finish time. Right? Now, you can just step back, and I'm not going to do this for every diagram that I have up here, but look at every example that I've put up.
Apply the selection rule associated with earliest finish time, and you'll see that it works and gets you the maximum number. For example, uh over here, this has the earliest finish time. Okay? Not this, not this, it's over here. So, you pick that, and then you use the the greedy algorithm step two to eliminate all of the intervals that are incompatible. So, these go away. Right? Once this goes away, this one has the earliest finish time. Right? And so on and so forth. Right? So, this is something that you can prove through examples. Right? Um that's not really a good notion, but you can prove to yourself uh using examples.
And this is where I I guess the the uh essence of double essence of 6046, to some extent double 06, uh comes into play. We will have to prove beyond a shadow of a doubt, using mathematical rigor, that the earliest finish time selection rule always gives us the maximum number of requests. Okay? And we're going to do that. It's going to take us a little bit of time, but that's the kind of thing you will be expected to do and you'll see a lot of in 046. Okay? So, everyone by by earliest finish time? Yeah, go ahead. So, Yeah. Uh well, then you get one for if there's only two requests and uh the area maximum number is one.
So, you pick uh it doesn't matter. It's not like you want efficiency of your resource. In this particular case, we will look at uh cases where uh you might have an extra consideration associated with your problem which changes the problem that says I want my resource to be maximally utilized. If you do that, then this doesn't work. And that's exactly It's a great question you asked. Uh but I did say that uh that we were going to look at the theme here uh which I don't have anymore, but uh of how problems changes change algorithms, right? And so, that's the problem change. Okay? You have a question?
Right. Okay, so you're Are you claiming that uh there's going to be a counter example to earliest finish time? All right, I will write it down on a sheet of paper, right? Uh and get me a concrete example. You can just slide it by. And if you get that before I finish my proof, right? Uh you win. Okay? Uh uh Uh and so, I would write it down, right? Just write it down. Right? So, good. All right, so this is a contest now. Okay? All right. So, we're going to try and prove this. So, uh there's many ways you could prove things, and I mean prove things properly. Uh it I don't know if you've read the old 6042 uh proof techniques that are invalid, you know, which is things like proof by intimidation.
Um you know, proof uh because the lecturer said so, you know, things like that. Uh this is going to be a classical proof technique. It's going to be a proof by induction. Right? We're going to go into it in some detail. Um later on in the term, we're going to put out uh sketches of proofs. We're going to be skipping steps in lecture uh that are obvious uh are maybe not so obvious, but if you paid attention, uh then uh you can infer uh the middle step, for example. Uh and so, we'll be doing uh proof sketches, right? And proof sketches are not sketchy proofs. Okay? So, uh keep that in mind. But this particular proof that we're going to do, I'm going to put in all the steps because it's our first one.
Okay? Uh and so, what we're going to do here is prove a claim. And the claim is simply that Oops, this is not writing very well. What is going on here? Okay. Back to the white. Given a list of intervals L, our greedy algorithm with earliest finish time produces K star intervals where K star is minimal. So, that's what we'd like to prove. Sorry, what happened? Oh, right. Good point. maximum What we're going to do is prove this by induction. And it's going to be induction on K star. And so, the base case uh is almost always with induction proofs trivial, and it's similar here as well. And in the base case, if you have a single interval in your list, uh then obviously that's a trivial example.
But what I'm saying here for the base case is slightly different. It says that the optimal solution has a single interval. Right? And so, now if your problem has one interval or two intervals or three intervals, you can always pick one, and it's clearly going to be a valid schedule because you don't have to check compatibility. And so, the base case is trivial even in the case where we're not talking about neces- not uh we're not talking just of intervals that have uh cardinality one, but the optimal schedule has cardinality one. So, that's the trivial case. So, the hard work, of course, in uh induction proofs is assuming the hypothesis and proving the n plus one or in this case the K star plus one case, and that's what we'll have to work on.
So, let's say that the claim holds for K star, and we are given a list of intervals whose optimal schedule is K star plus one. It has K star plus one intervals in the optimal schedule. So, L may be some large number, capital L, maybe in the hundreds, and K star may be 10, uh what have you. They're They're different. I want to point that out. So, our optimal schedule we're going to write out as as this. Uh S star. So, usually we use star for optimal in 046. And it's got uh K star plus one entries, and those entries look like uh S uh F uh pairs. So, I'm going to be using the subscript J1 through J K star plus one to denote these uh these intervals.
So, the first one is SJ1, FJ1. That's an interval that's been selected and is part of our optimal solution. And then if we keep going, and we have um SJ K star plus one, comma F J K star plus one. Right? So, um no getting away from uh subscripts here in 046. So, that's our uh uh that's that's what we have in terms of This is what the optimal schedule is. It's got size K star. Of course, what we have to show is that uh the greedy algorithm with the earliest finish time is going to produce something that is K star plus one in size. And so, that's the that's the hard part. We can assume the inductive hypothesis, and we'll have to do that, but there's a couple of steps in between.
All right, so let's say that what we have is S1 through K is what the greedy algorithm produces with the earliest finish time. So, I'm going to write that down. S I K F I K. Right? So, notice I have K here, and K and K star at this point uh are not comparable. I'm just making a statement that I took um this particular problem that has K star plus one in terms of its uh optimal solution size, and for that problem, I have K intervals that are produced by the earliest finish time greedy heuristic. Okay? And so that's why the subscripts here uh uh are different. Well, I have I1 here uh and IK and then over here I have the Js.
And so that they these intervals are different. Um if I look at uh f of I plus f of I1 and if I look at f of J1 what can I say about f of I1 and f of J1? Is there a relationship between f of I1 and f of J1? They're equal? Do they have to be equal? Yeah. Less than equal to. Less than equal to. Exactly right. So they're they're less than equal to. Uh it's possible that uh you might end up with a different optimal solution uh that uh doesn't uh use the earliest finish time. We think earliest finish time is optimal at this point. We haven't proven it yet. But it's quite possible that you may have other solutions that are optimal that aren't necessarily the ones that earliest finish time gives you.
Right? So that's really why the less than equal to is important here. Uh now what I'm going to do is create a schedule S star star that essentially is going to be taking S star and pulling out the first interval from S star and substituting it with the first interval from my greedy algorithm's schedule. So I'm just going to replace that and so S star star is um SI1 f J1 and then I'm going to be going back to SJ2 f J2 because I'm going back to S star and all the other ones are are coming from S star. So they're going to be S JK star plus one uh comma f JK star plus one. Okay. So I just did a little substitution there um associated with uh the the optimal solution and I stuck in part of the greedy algorithm solution.
In fact, the very first schedule. Okay. Oh, this should be uh I1. Thank you. Yeah. Good. So we got a couple of things to do, a couple of observations to make and we're going to be able to prove some relationship between K and K star that is going to give us our the proof for our claim. So clearly S star is also optimal. All I've done is taken one interval out and replaced it with another one. Hasn't changed the size. It goes up to K star plus one. So S double star is also optimal. S star is optimal. S double star is optimal. Now I'm going to define L prime as the set of intervals with S of I greater than or equal to f of I1.
Right? So what is L prime? Well, L prime is what happens in the second step of the greedy algorithm where in the second step of the greedy algorithm, once I've selected this particular interval and I've pulled it in, I have to reject all of the other intervals that are incompatible with this one. Right? So I'm going to have to uh take only those intervals for which S of I is greater than or equal to f of I1 because uh uh those are uh those are the ones that are compatible. Okay? So that's what L prime is. And I'm going to be able to say that since S double star is optimal for L S double star two to K star plus one is optimal for L prime.
Right? So I'm making a statement about this optimal solution. I know that's optimal. And basically what I'm saying is subsets of the optimal solution are going to have to be optimal because if that's not the case, I could always substitute uh the something better and shrink the size of the the K star plus one optimal solution uh which obviously would be a contradiction. Okay? So S double star is going to is optimal for L and therefore S double star two through K star plus one is optimal for L prime. Right? Everybody buy that? Yep. Good. And so what this means of course is that the optimal schedule for L prime has K star size.
Right? I'm starting with two. I've taken away one. So now I have L prime which is a smaller problem. Now you see where the proof is headed. Um if you didn't already. Uh I have a smaller problem which is L prime. Clearly it's got fewer requests. And I I have constructed an optimal schedule for that problem by pulling it out of the original optimal schedule I was given and that size of that optimal schedule is K star. Right? Um and now I get to invoke my inductive hypothesis because my inductive hypothesis says that this claim that I have up there holds for any set of problems that have an optimal schedule of size K star.
Right? That's what the inductive hypothesis gives me. And so by the inductive hypothesis when I run the greedy algorithm on L prime I'm going to get S K schedule of size K star. Right? Now can you tell me based on what you see on the board by construction when I run the greedy algorithm what am I getting? On L star. By construction, when I run the greedy algorithm on L I'm sorry, L prime. There's too many subscripts here. When I when I run the greedy algorithm on L prime, what do I get? Someone? Yeah. We get S of I sub two S of I sub two interval. Exactly right. I get um everything from the the second thing here all the way to the end.
Right? Because that's exactly what the greedy algorithm does. Remember the greedy algorithm picked SI1 FI1 and then rejected all requests that were incompatible and and then moved on. When you rejected all requests that were incompatible here, you got exactly L prime. And uh by construction, uh the greedy algorithm should have given me uh all the way from SI2 to uh SIK. Right? Thank you. So by construction the greedy on L prime gives S two to K. Right? And what is the size of this? Two to K gives me a size of K minus one. Right? This is K minus one. So So if I put if I put these two things together what what do I have?
What is the next step? Uh I have the inductive hypothesis giving me a fact. I have the construction giving me something. Now I can relate K and K star. What's the relationship? K star is equal to K minus one. Right? Do you people see that? Right. So, size K star which is K minus one. Right? So, what that means is um given that S 2 K is of size K star, it means that S 1 K is of size K star plus one, which uh is exactly what I want. That's uh optimal because I said in the beginning that we had K star plus one in our uh in inductive hypothesis case as being the optimal solution. So, this last step here um is all you need to to argue now that um um uh S of 1 K going back up here, um this is optimal because K equals K star plus one.
Right? There you go. So, so that's the kind of argument that you like have to make um in order to uh prove something like this in 046. And what you'll see in your problem sets, uh uh including the one that's going to come out on Thursday, is that different uh problem uh that you'd have to have uh a proof for a greedy algorithm for. Uh I forget exactly what technique you'll have to use there, perhaps induction, perhaps contradiction. And these are the kinds of things that uh uh gets you to the point where you've analyzed the correctness of algorithms, uh not just the fact that you're getting a valid schedule, but you're getting a valid uh maximum schedule in terms of the maximum number of requests.
Okay? Um any questions about this? Do people buy the proof? Yep. Good. Um so, that was greedy for a particular problem. I told you that the theme of our lecture here was uh changing the problem and uh getting uh different different algorithms that had different complexities. So, let's go ahead and do that. So, the rest of this uh lecture we'll just take a look at different kinds of problems and talk a little more superficially about uh what the problem complexities are. And so, one thing that might come to mind is that you'd like to do weighted interval scheduling. And what happens here is each request has weight W I.
And what we want to do is schedule a subset of requests with maximum weight. So, previously it was just all weights were one, so maximum cardinality was what we wanted. But now we want to schedule a subset of requests with maximum weight. Um someone give me an argument as to whether the greedy algorithm earliest finish time first is optimal for this weighted case or give me a counterexample. Yep. Uh go ahead. Right. Exactly. Exactly right. All right, I owe you one, too. Here you go. Um so, it's a fairly trivial example. All you do is W equals one, W equals one, W equals three. Right? So, there you go.
Um so, clearly the earliest finish time would pick this one and then this one, which is fine. You get two of these, but this was important. You know, this is I don't know, sleep, party, 6046. Right? So, there you go. So, the weight is I should make that infinity. Right? Right. It's most important thing in the world. At least for the next uh 6 months. Um so, uh how does this work now? So, turns out uh the greedy strategy, the template that I had, uh fails. Okay? Uh there's nothing that exists on this planet that uh at least I know of, uh uh where you can have a simple rule uh and use that template to get the optimum solution, in this case maximum weight solution, for every problem instance.
Right? So, that template just fails. Okay? Um what other programming paradigm do you think would be useful here? Yeah, go ahead. DP, right. So, do you you want to take a stab at uh a potential DP solution here? Yeah, that's uh that's the perfect divide and conquer. Uh and then when you include it, what do you have to do? Right. How many subproblems do you think there are? I I want to make you earn your Frisbee. Right? Well, that's a that's a number of uh subsets that you have. Uh so, you have N intervals, then you have two raised to N subsets. Right? But remember you want to go uh you know, you want to be smarter than that, right?
You you want to be a little bit smarter than that. Uh and uh so, here you get a Frisbee anyway. No, not anyway. There you go. Right. Um so, uh anybody else? Uh what So, what I want to use uh is dynamic programming. We've established that. Right? I want to use dynamic programming. And with dynamic programming, you have some experience with that in 006. Uh the name of the game is to figure out what the subproblems are. Right? Um the subproblems are kind of going to look like a collection of requests. I mean, there's no two things about it. They're going to be a collection of requests. Right? Uh and so, uh the challenge here is not to go to the two raised to N, okay?
Because two raised to N is bad, right? Um for uh if we want efficiency, so we have to uh have a polynomial number of subproblems. So, someone who hasn't answered yet, go ahead. So, So, you're looking at every pairs of I's and J's. Uh and uh well, not all of them are going to be valid. They won't be intervals associated with that. Right? But you know, that's that's that's a reasonable start. Right? Someone else? Uh someone who hasn't answered yet, back there? Uh best from the start to any given point. All right. Well, you got you got close. Uh it's Michael. Here you go. Uh you need to stand up.
Oh, bad throw. Uh that's a bad throw. I got to practice. Okay. So, um as you can see with dynamic programming, uh the challenge is to figure out what the subproblems are. Uh the fact of the matter is that there's going to be many different uh uh possible algorithms that are all DP for this weighted problem. There's at least two interesting ones. We're going to do a simple one, which is based on the answer that uh the gentleman just here just gave. Uh but uh it turns out you can be a little smarter than that, and uh most likely you'll hear that the smarter way in the section. Okay? But let's do the simple one because that's all I have time here for.
And uh the key is to define the subproblems, and then once you do that, uh the actual recursion ends up being a a fairly straightforward and intuitive step. So, let's uh look at dynamic programming, one particular way of solving this problem using the DP paradigm. So, what I'm going to do is define subproblems R star. So, R is the total number of requests that we have, and the subproblems are going to correspond to I'm going to pick request J belonging to R such that Oh, I'm sorry. This was R of X. Um such that S J greater than or equal to X. Right? So, um, what I'm doing here is um, a given a particular X, I can always shrink the number of requests that I have based on this rule.
Okay? And then you might ask, you know, what is X? And now you can apply the same subsetting property by choosing the X's to be the finishing times of all of the other requests. Right? So, uh, X equals f of i. So, what this means is um, when I put uh, f of i over here, it means all of the requests that come after the i-th request finished are part of R of f i. Right? So, R of f i would simply be requests later than f of i. Okay? And there's something subtle here that I want to point out, which is R of f i is not the set of requests that are compatible with the i-th request. Okay? It's it's not exactly that.
It's the set of requests that are later than f of i. Okay? So, keep that in mind because what happens here is we're going to solve this problem uh, step by step. We're going to construct the dynamic programming solution um, essentially uh, uh, by picking a request and then, just like in the greedy case, and then picking the request that comes after that. So, we're going to pick uh, uh, uh, an early request and then we're going to subset the solution, pick the next one, just like it we did with the greedy. Um, and so, uh, the subproblems that we will actually solve potentially bottom-up if we're doing recursion, um, are going to correspond to a set of requests that come later than uh, the particular subset that we're looking at, which is defined by a particular interval.
All right? So, requests that are later than f of i, not necessarily all of the requests that are compatible with the i-th request. And so, if you do that, then the number of subproblems here are small n, where n is the number of requests. So, if n is the number of requests in the original problem, the number of subproblems equals n cuz all I do is plug in an appropriate i, find the f of i for it, and generate the R of f of i for each of those. So, there's going to be n of those subproblems. And um, we're going to solve each subproblem once and then memoize. And so, the work that we have to do is uh, the basic rule corresponding to the complexity of a DP, which is number of subproblems times the time to solve um, each subproblem or a single subproblem.
And this assumes order one for uh, lookups. So, you can you can think of it that recursive calls as being order one. Because you're assuming you're doing memorization. Okay? So, I haven't really told you anything here that uh, you haven't seen in 006 and likely applied a bunch of times. Um, over here, we've just defined what our subproblems are for our particular DP. And we argued that the number of subproblems that are associated with this particular choice of of subproblems corresponds to n if you have n requests in the original problem instance that you're given. So, the last thing that we have to do here to solve our DP is, of course, to write our recursion out and to convince ourselves that this actually all works out.
And let's do that. And so, what we have here is our DP guessing. And we're going to try each request i as a possible first request. All right. And so, that's where this works. You might be thinking, boy, I mean, this R of f i looks a little strange. Why doesn't it include all of the requests that are compatible with uh, with with the i-th request? I mean, I'm somehow shrinking my uh, my subsequent problem size if I'm ignoring some requests that are earlier that really should be part of the are are part of the compatible set, but they're not part of the R of f i set. Right? And so, some of you may be thinking that, well, uh, the reason this is going to work out is because we're going to construct our solution, as I said before, from the beginning to the end.
So, we're going to try each request as a possible first request. Okay? So, even though this request might be uh, in our chart, you know, all the way to the right, uh, it might have a huge weight. Okay? And so, I'm going to have to try that out as my first selection. And when I try that out as my first selection, then the definition of my subproblem says that this will work I can only have to look at requests that come later than that. Because the ones that came earlier, I've tried them out, too. Okay? So, that's something that you need to keep in mind uh, in order to argue correctness of this recursion that I'm going to write out now.
And so, the recursion, and I have opt R, what is the first thing that I'm going to have on the right-hand side of this recursive formulation? What uh, mathematical construct am I going to have to do here? When I And you see something like guessing and seeing something like try each request as a possible first, what mathematical construct am I going to have to put up here? Max. Who said max? No one wants to take credit for max? It's max, right? So, I'm going to have max um, one less than equal to i less than or equal to n. And I'm going to um, uh, someone want to tell me what the rest of this looks like?
Someone someone else? Couple of freebies left, guys. What does the rest of this look like? Yep. One plus the optimal R f Uh, not one. Just uh, we have what what kind of problem do we have here? It's not one anymore. Uh, The weight. Weight. The weight. Yeah. So, w i plus the optimal um, R f i. Right? Okay? So, we that w i plus optimal of R of f i. Okay? So, uh, and the reason you said one, but I that close enough. If it was one, you'd use greedy. And so, that's why we're in the w i mode and we end up getting this here. So, that's it. You try every request as a possible first. You obviously pick that request, so it's part of your weight in terms of your uh, the weight for your solution.
When you do that, because it was the first request, you get to prune the set of requests that come later corresponding to um, R of uh, f i that you see here. And then you uh, go ahead and simply uh, find the optimum for a smaller problem, clearly has a fewer requests, and uh, as long as you maximize over the set of guesses that you've taken, and there's n guesses up at the top level. Obviously, at the lower levels, you're going to have fewer requests uh, in your R of f i's and you'll have fewer uh, iterations of the max, and uh, but it's n at the top level. Okay? So, um, one last question, uh, what is the complexity of what we see here?
n squared n squared, right? And the reason it's n squared is you simply use You can be very mechanical about this. You you you say, if this was order one, I'm doing a max over n items and therefore that's order n time to solve one sub problem. And since I have n sub problems, I get n times order n, which is order n squared. Okay? So, the last thing I'll do and I just have one more minute is give you a sense of a small change to interval scheduling that puts us in the NP-complete domain. Okay? So, so far we've just done two problems. There's many others. With interval scheduling, that was greedy linear time.
Weighted interval scheduling is order n squared according to this particular DP formulation. Turns out there's a smarter DP formulation that runs in order n log n time. That you'll hear about in section on Friday. But still polynomial time. Let's make one reasonable change to this, which is to say that we may have multiple resources and they may be non-identical. Right? So, turns out everything that we've done kind of extrapolates very well to um to identical machines, even though there's many identical machines. But if you have non-identical machines, what that means is you have resources or machines that have different types.
So, maybe your your machines are T1 to three TM. Okay? And um it's essentially a situation where you say, this particular task can only be run on this machine or this other machine, some subset of machines. So, you can still have a weight of one for all requests, but you have something like Q of I belonging subset of T is a set of machines that I runs on. Okay? That's it. That's the change we make. Q of I is going to be specified for each of the eyes. So, you can even have two machines. And you can say, here's a set of requests that could run on both machines. Here's a set that only runs on the first machine.
And here's another set that runs on the second machine. That's a simple example of this generalization. If you do this, this problem has been shown to be NP-complete. And by that I mean, NP-complete problems are decision problems. And so, you say, can some specific number K less than n requests be scheduled? This decision problem is NP-complete. Okay? And so, what happens when you have NP-complete problems? Well, we're going to have a little module in the class that deals with intractability. We're going to look at cases where we could apply approximation algorithms and maybe in the case of the optimization problem, if the optimum for this is K star, we'll say that we can get within 10% of K star.
The other way is to just deal with intractability by hoping that your exponential time algorithm runs in reasonable amount of time for common cases. So, in the worst case, you might end up taking a long time, but you just sort of back off after an hour and take what you get from the output of the algorithm, but in many cases, the algorithm might actually complete and give you the optimum solution. Okay? So, done here. Make sure to sign up for registration section and see you guys next time.