So we now have an algorithm, a very 
elegant one, that solves the weighted 
independent set problem in path graphs. 
Moreover the algorithm runs in linear O 
of n time, clearly the best possible. 
But before we do a victory lap I want to 
point out that there's something this 
algorithm doesn't do that you might want 
it to do, mainly hand you the actual 
optimal solution, not merely the value of 
that optimal solution. 
So the point of this video is to show you 
how we can reconstruct an optimal 
solution given the table-filling 
algorithm from the previous video. 
So we just write that algorithm back 
down. 
It's so short, it won't take me too long. 
Now when this algorithm completes, what 
do we have in our hands? 
We have an array, and this array is 
filled with numbers. 
In particular, in the last entry in the 
array is a number like 184 so that's 
great. 
That tells us that the maximum weight 
that any independence set possesses is 
184. 
But, in many applications, we're going to 
want to know not just that information 
but actually which vertices constitute 
that independence set with total weight 
of 184. 
So, perhaps the first hack that comes to 
mind to address this issue is to augment 
the array, so that each entry stores not 
just the value of an optimal solution to 
the sub-problem produced by the graph G 
sub I, but also an actual set of vertices 
achieving that value. 
And I will leave it for you to if you 
want, rework the previous pseudo codes so 
that when you fill in a new entry, you 
fill in not just the value of an optimal 
solution given solution to the previous 
sub-problems but infact also the solution 
itself. 
This hack however is not generally how 
things are done in dynamic programming. 
It unnecessarily wastes both time and 
space and a much smarter approach is to 
reconstruct from the filled in table an 
optimal solution as needed. 
So if you think about it, it's kind of 
cool that this is even possible, that our 
one line algorithm doesn't cover its 
tracks, that it leaves enough clues for 
us as detectives to go back and examine 
and reconstruct what the optimal solution 
is. 
The following key point articulates 
exactly why this is indeed possible. 
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.