So we saw in the last video why if you represent scheduling constraints among courses by a digraph that it's critical that that digraph in fact be a DAG. And let's now look at this scheduling issue represented by DAGs in more detail.
So here's a chart of a selection of Course 6 prerequisites-- some of them obsolete, but they serve the purposes of being an illustrative example-- and the little arrows here are indicating arrows in the digraph. So what this tells me is that 18.01 is listed as an immediate prerequisite in the catalog for 6.042. 18.01 is also an immediate prerequisite of 18.02. 6.001 and 6.004 are both prerequisites of 6.033, and 6.042 of 6.046, and 6.046 of 6.840.
So we're seeing here this indirect prerequisite issue that I mentioned before, which is that even though the only thing listed as a prerequisite for 6.840 in the catalog is 6.046, as a matter of fact in order to take 6.046 you have to have taken 6.042. So 6.042 is an indirect prerequisite of 6.840. So in terms of graph language and path language, a subject u is an indirect prerequisite of v when there's is a positive length path from u to v in the digraph that describes the prerequisite structure among the classes. It simply means that-- using our notation for R plus is the positive length path relation of a digraph or a binary relation R-- it simply means u R plus v, which is read as there is a positive length path from u to v.
Now, a key idea that we're going to be examining in learning how to do scheduling is the idea of a minimal subject. So the definition of a minimal subject is a subject that has no prerequisites, no arrows in, a freshman subject. So nothing comes in. There are three examples of subjects with no prerequisites in the preceding chart, namely 18.01, 8.02, and 6.001.
Let me say a word about where this funny terminology minimal comes from. It's because another way to talk about DAGs is in terms of things that are like order relations called partial orders, which we'll be looking at shortly. And so you think of the later subjects as being bigger than the earlier subjects. So a minimal subject is one where there is nothing less than it. Now, there might be several minimal subjects, because it might be that neither one of them is less than the other, but there's nothing less than 18.01. There's no other subject that you have to take before 18.01. So that's the definition of minimal. Nothing smaller.
Now, you could ask what's a minimum, which you may be more familiar with. A minimum means that not only is there nothing before it, but it comes before everything else. It would be the earliest of all possible subjects in the indirect prerequisite chain. There isn't any in this example, but there actually used to be one at MIT. For a while, we experimented with giving an orientation week summer assignment, that is, an assignment over the summer for newly admitted students in order for them to take a subject during orientation week in which they discussed some book that they had all been assigned to read beforehand.
Seemed like a great idea to kind of pull the freshman community together, but it turned out to be unsustainable because they couldn't find enough faculty and others willing to conduct these seminars. So MIT stopped having a minimum subject.
So let's look at the prerequisites again, and discuss how to do a scheduling. And the first thing we're going to do in the schedule is, as I say, identify the minimal elements. There are the three of them that we mentioned. And we're going to start by deciding that we'll take those three in the first term. So we're going to be operating with basically what's called a greedy strategy. We're going to take as many things as we possibly can take at any term given the constraints. So we can take all the freshman subjects in our first term because they have no prerequisites.
Well, the next step, then, is just get rid of them because they're scheduled already. So we can get rid of all those occurrences of 18.01, 8.02, and 6.001, not only-- there are other occurrences as well here where 18.01 is a prerequisite for things. So they're all gone, and we get a simplified diagram where we've removed the minimal elements.
Now in the new diagram, there are now things that didn't used to be minimal before but are minimal now. These are the new minimal elements, and we can identify those. Here are five subjects-- four here and one there-- that now have no more prerequisites. These are kind of the second level minimal elements, and we're going to schedule them next.
So those are all the subjects that we can possibly take after we've taken the first set of minimal subjects. They're the second level minimals. And we'll schedule them in the next term. This is our five subject second term schedule.
Likewise, you delete these guys, and then you discover that 6.046 and 6.004 are the resulting minimal ones, which it's now possible to take because all their prerequisites have been satisfied. So we schedule them in the third term, 6.840 and 6.033, by the same reasoning, in the fourth term, and 6.857 in the fifth term.
There is our complete term schedule obtained in this particular way. There's, of course, many other ways to schedule it, but this is a particular orderly way where the strategy, again, is greedy. You take as many things as you possibly can take in a given term.
Now, there are some concepts that come up when you're talking about schedules that are worth introducing. So one of them is an antichain. An antichain is-- in this particular example means a set of subjects where there are no indirect prerequisites among them. They can be taken in any order, because it doesn't matter whether you've taken one or not when you're thinking about taking the others.
In technical language, again motivated by the idea of thinking of there being a path as though it was less than or equal to something, these are elements that are incomparable. Neither one is less than or equal to another. So in terms of the path relation, u is incomparable to v if and only if there is no path from u to v of positive length and there's no positive length path from v to u.
So let's look at some antichains-- and the part of the point of defining it is we have chosen antichains as our schedule for each term. So the freshman subjects with no prerequisites, clearly there's no path among them, because there is no path to them at all. So they are an antichain. The next level we chose were the second level minimal elements, which only had as prerequisites the original minimal elements, and so certainly none of them was a prerequisite of the others. So that's another example of an antichain. And of course the third level and the fourth level and the fifth level are antichains.
But not all antichains are there in our schedule. So for example here, is a diagonal lying antichain. 6.840, 6.004, and 6.034 have no paths between them. So in fact it's possible to take them simultaneously, because you could have taken all their prerequisites in the upper left here and then take the three of them.
So that's what an antichain means here. So the technical definition is no path between any two of them, but in terms of the scheduling of courses, it means it's possible to take them in the same term if you've satisfied all their prerequisites, which it is possible to do.
So let's ask about the various patterns of scheduling that are possible. We've discovered this particular greedy one, where we take as many things as we can each term. But suppose that I was constrained to only take one subject per term. I was going to-- I have an outside job, I'm too busy to take more than one class a term, and if MIT will let me dawdle so long, that's what I'd like to do. So can I do this?
Yeah, well sure. Just schedule all the minimal elements first in any order, one, two, three. And then schedule the five second level minimal elements next, and the third level, and so on. And it's perfectly possible, then, to modify the schedule that we found into a schedule in which you only take one subject per term, and of course you only take a subject after you've taken all of its indirect and direct prerequisites.
This is called a topological sort. Again, the sorting word comes from the motivation of thinking of there being a path as like a less than or equal to relation. So we're sorting things in order of increasing size. 18.01 would be, in this case, a smallest element and 6.857 a biggest in this list of elements.
A chain is kind of technically, literally, a thing called the dual of an antichain. A chain is a sequence of subjects that must be taken in order. That is, these are subjects where for any two of them, you know which one has to come first. That is, between any two of them there is a path in one way or the other. Now of course, it's a DAG, so there can't be paths in both directions. So a chain is simply a set of comparable elements, which implies that there's an order in which they have to be taken.
So here are some chains. This one was shown pictorially as a vertical chain with five courses in it. Here's a vertical chain of four. And not all of them are vertical. Here's a chain where you have to take 18.01 before you take 18.03 before you take 6.004. So they form a chain.
It's important to realize that this is a chain with five subjects in it, but a chain doesn't have to have every possible element that could be in it. It's still a chain even if it's only got these three subjects, because there's a path from 8.02 to 6.004 and a path from 6.004 to 6.857.
But maximum length chains, chains that are as full as possible, are important theoretically. And so this in particular is a maximal length chain. The longest chain here is of length 5. Now, it's not the only one. There's another chain of length 5 here if you look for it. But no chain is of length longer than 5 and there is one of length 5, and that leads us to the question of how many terms is it necessarily going to take to graduate.
Well, we saw that you can graduate in five. But given that there's a maximum chain of length 5, it means that you can't do it in fewer, because those five courses have to be taken consecutively. The third has to be taken in a term after the first two have been taken. The second has to be taken after the first. If you have a chain of any size, actually, the number of terms to graduate has to be at least as big as that chain, which means it has to be at least as many terms as a maximum size chain.
So five terms are necessary, and we saw using our minimal strategy of being greedy that you can always do it in maximum chain length. So five are also sufficient. This is providing that you can take an unlimited number of subjects per term. Remember our strategy to graduate in five terms was to take as many subjects as we possibly could each term. So there's the sufficient way to take subjects to graduate in five terms.
And of course, one consequence is that in my second term freshman year, I was taking five subjects because it was possible. But that leaves me with a kind of heavily loaded term compared to-- here's a term with two subjects, and there's a term with only one subject at the very end.
So it's possible, in fact, to somewhat adjust the term load. Let's just shift taking 18.02 to the third term. It's perfectly feasible to do that, because I will have satisfied all the prerequisites of 18.02 after the first term, but I don't have to take it in the second term. Let's shift it off. So now I've lightened the load in the second term to four subjects, somewhat increasing the load-- I had to do it somewhere-- in the third term to three subjects. So now I have to take no more than four subjects a term. And as a matter of fact, if you fiddle, you can actually find a graduating schedule in which you can only take three subjects per term.
And we will examine what's the minimum number of subjects per term in the next segment.