So the starting point of this observation is the correctness of our algorithm, our

one line algorithm. Which of course we established in the

previous video. And by correctness I mean what's

guaranteed that this algorithm will populate each entry of your array

correctly. The number in the ith entry is indeed the

maximum weight of independent set in the graph G I.

So remember our thought experiment about what the optimal solution could possibly

look like. We concluded it could only be one of two

things, and we really wound up wishing we had a little birdie that could tell us

whether or not the rightmost vertex v.sub.n was in the optimal solution or

not. If we knew which case we were in we could

just recursively compute the remainder of the solution from a graph that has either

one or two fewer vertices. So here's the point,

this filled in table, that's our little birdy.

Here's what I mean. But what, what's, what's the reasoning

that our algorithm goes through to fill in this last entry of this array, and

don't forget, we've already proven that our algorithm's correct, we did that in

the last video? Well, it does a comparison between the

two possible candidates vying for the optimal one.

On the one hand it commutes the case one solution that looks up the optimal value

of a solution for the graph with one fewer vertex and it compares that to the

case two solution including V N the last vertex and adding that to an optimal

solution with two fewer vertices. And in this max operator in the line of

code it's explicitly comparing which is better, case one.

The solution which excludes B sub N, or case two, the solution which includes B

sub N. So, whichever one of those was the

winner, whichever one of those cases was used to fill in that last entry.

That exactly tells us whether or not B sub N is in the optimal solution.

If we use the first case, that means B sub N is not in the optimal solution, it

gets excluded. If the second case was the winner, then

we know B sub N is in the optimal solution, because that was the winner.

If we have a tie, then there's an optimal solution either way.

There's one that includes BN and there's one that excludes BN,

So those are the tracks in the mud left for us by the forward direction of the

for-loop. We can just go back and look at which

case was used to fill in each entry of the array.

Again, for the ones that used case one, that corresponds to excluding the current

vertex; for those that used case two to fill in the entry, that corresponds to

including that vertex, in the solution. So the reconnect structure algorithm will

take as input the filled in array that was generated by our one line algorithm

on the previous slide. And what it's going to do, it's going to

trace through this array from right to left.

And at each step of the main loop, it's going to say, it's going to look at the

current entry. And it's just going to compute explicitly

which of the two candidates were used to fill in this array entry.

If you want, you can also cache the results of these comparisions on the

forward pass. That's an optimization that will be

useful later for harder problems. But for now if you want, you can just

think about redoing the comparision thing.

Hey, you know, their were two possible. More ways that we could have filled in

this entry, let's just check which of the two were used.

So if in fact the preceding array entry is at least as large as the one from two

back plus the weight of the current vertex, that corresponds to case one

winning, to the sub-solution that excludes the current vertex being better

than the one that includes it. So in that case we just skip the current

vertex V sub I and we decrease the array index by one in our scan.

If the other case wins, that is, if we fill in the current entry, if an optimal

solution to the current graph G sub I comprises the current vertex of E sub I

plus the optimal solution to the graph with two fewer vertices.

In this case we know we'd better include V sub I.

That's part of an optimal solution to the current sub-problem.

Moreover, that's the case where we need to look up the optimal solution with two

fewer vertices. So, we include the current vertex and we

decrease the array and index by two. So formally we have a correctness claim

which is that the final output S return by the reconstructing algorithm is, as

desired, a maximum weight independent set of the original graph g.

We've already talked about all the ingredients necessary for a formal proof,

for those of you who are interested. Of course, it precedes by induction and,

in the inductive step, you use the same case analysis we've been using over and

over again. The optimal solution at any given point,

it has only two possible candidates. The algorithm explicitly figures out

which of the two it is and that is what. Triggers whether or not to include or

exclude the current vertex. The running time, it's even easier.

We have a wild loop that runs in most an iterations.

We do constant work in each of the iterations.

So just like the forward pass, this backwards pass is really just a single

scan through the away. It's going to be lightning fast linear

time.