So the time has arrived to begin our 
study of dynamic programming. 
So this is a general algorithm design 
paradigm. 
As I mentioned at the beginning of the 
course, it has a number of justly famous 
applications. 
However, I'm not going to tell you just 
yet what it is that makes an algorithm 
dynamic programming. Rather, our plan is, 
over the next few videos, to develop from 
scratch an algorithm for a non trivial, 
concrete computational problem. 
The problem is finding the maximum weight 
independent set and a path graph. 
This concrete problem is going to force 
us to develop a number of new ideas. 
And, once we've finished solving the 
problem, at that point, we'll zoom out, 
and I'll point out what are the 
characteris-, characteristics of our 
solution which make it a dynamic 
programming algorithm. 
Then, armed with both a sort of formula 
for developing the dynamic programming 
algorithms, as well as a concrete 
instantiation, we'll move onto a number 
of further, and in general harder 
applications of the paradigm. 
Indeed, even more than usual, the dynamic 
programming paradigm takes practice to 
perfect. 
In my experience, students find it 
counterintuitive at first, and they often 
struggle to apply the paradigm to 
problems that they haven's seen before. 
But here's the good news, dynamic 
programming is relatively formulaic, 
certainly more so than our recent study 
of greedy algorithms, and it's something 
that you can get a hang of. 
So with sufficient practice, and that's 
exactly what I'll be giving you in the 
next couple of weeks, you should find 
yourself with a powerful and quite widely 
applicable new tool in your programmer 
tool box. 
So let me introduce you to the concave, 
concrete problem we're going to study 
over the next few videos. 
It's a graph problem but a very simple 
graph problem. 
In fact, we're going to restrict our 
attention merely to path graphs. 
That's graphs that consist solely of a 
path on some number n of vertices. 
The only other part of the input is a 
single non-negative number per vertex. 
We're going to call these weights. 
For example here's a path graph on four 
vertices, and let's give the vertices the 
weights one, four, five, and four. 
The responsibility of the algorithm is 
going to be to output an independent set. 
What that means is a subset of the 
graph's vertices, so that no two vertices 
are adjacent. 
So in the context of a simple path graph, 
it just means you gotta return some of 
the vertices and always avoiding 
consecutive pairs of vertices. 
So when you have a path of four vertices, 
examples of independent sets include the 
empty set, 
any single vertex, 
vertices one and three, 
vertices two and four, 
and vertices one and four. 
You could not, for example, return 
vertices two and three. 
Because those were adjacent. 
That is forbidden. 
Now, to make this interesting, we're 
going to want just, not any old 
independent set, 
but the one whose sum of vertex weights 
is as large as possible. 
That's the max weight independence set 
problem. 
So what I'm going to do next is use this 
concrete problem as an opportunity to 
review the various algorithm design 
paradigms that we've seen so far. 
Along the way we'll see that none of them 
actually work very well for this problem. 
And that's going to motivate us to devise 
a new approach, 
and that approach is going to turn out to 
be dynamic programming. 
. 
So there's always our standard punching 
bag, brute force search. 
This would entail iterating through all 
of the independent sets and remembering 
the one with maximum total weights. 
Of course it's correct, no question about 
that, but as usual this would require 
exponential time. 
Even in just a path graph, the number of 
independent sets is exponential in the 
number of vertices, n. 
. 
So what other algorithm design paradigms 
do we know? 
Well we just finished a big segment on 
greedy algorithms, we could certainly 
think about that. 
You know, pretty much most problems it's 
easy to propose greedy algorithms, and 
this one's no exception . 
I think the most natural greedy algorithm 
you might try to use to compute a 
maximally independent set would be well. 
What's the myopic decision? 
Well, you want to get as much weight 
overall. 
So, in each step, you want to just pick 
the vertex with the highest weight that 
you haven't already chosen. 
Now, of course you have to worry about 
feasibility. 
Remember, we're not allowed to output 
adjacent or consecutive vertices. 
So, if any vertex is ruled out by 
adjacency, we ignore it. 
And amongst those that preserve 
feasibility, we include the highest 
weight one in our set so far. 
Well, let me redraw the four node path 
graph we had in the last slide and let me 
ask you. 
What would this greedy algorithm compute 
on the four node path, and how does that 
compare to the optimal solution, the 
independent set with the maximum total 
weight? 
So the correct answer is the second one. 
Let's see why. 
So let's start with the optimal solution, 
the maximum independence set. 
Remember independence sets are forbidden 
from choosing adjacent or consecutive 
vertices. 
so in this case the only sensible 
solutions to consider are the first and 
third vertex, the second and fourth or 
the first and fourth. 
Of these, the best is the second and 
fourth for a total of eight. 
So what about the greedy algorithm? 
Well, you know, we just had this period 
of time where we got really spoiled with 
the success of greedy algorithms. 
especially the minimum span entry 
problem. 
But let me remind you, you know, greedy 
algorithms, you know, they're often good 
heuristics. 
They're often not guaranteed to be 
correct. 
And so I'm happy to have this opportunity 
to quickly remind you again, of that 
drawback of greedy algorithms. 
They're quite frequently not correct. 
So this is another such case, so what 
will the greedy algorithm do? 
Well, it begins by picking the max weight 
vertex over all. 
So that would be this vertex with weight 
five. 
That unfortunately blocks the algorithm 
from picking either of the two vertices 
that has weight four. 
The only remaining option that preserves 
feasibility is to pick. 
The vertex of weight one. 
So that gives us an indepenedent set of 
weight six. 
So this greedy algorithm is not correct. 
You could of course try to devise other 
types of algorithms, but I don't know of 
any greedy approach that will actually 
solve this problem optimally. 
So that's a bummer, but we still haven't 
exhausted our algorithm design paradigms. 
remember, you know, we learned this quite 
powerful divide and conquer approach 
early on in part one of this class. 
And you know, it seems like it could work 
here. 
We had all these successful applications 
where the input was an array. 
We broke it into two halves. 
We were cursed on both sides and combined 
the results. 
And here, you know, path graphs don't 
look so different than an array of 
numbers. 
So the obvious approach for divide and 
conquer is to break the path into two 
paths, each of half the length of the 
original, 
recursively compute a maximum weighted 
independent set of each, and then somehow 
combine the results. 
With the issues with the divide and 
conquer approach are already apparent, 
just in our simple four vertex example. 
So if we recurse on the left half, that 
is the first two vertices, and we compute 
a max weight independence set, that's 
just going to be the second vertex by 
itself. 
And if we independently recurse on the 
right hand side, on the vertices three 
and four, the maximum weight independence 
set on right half is going to be the 
vertex of weight five. 
And now when we, the recursion's complete 
and we get our sub-solutions back, we 
have the second vertex and we have third 
vertex, 
but the problem is the union of those two 
solutions conflicts. 
Right? 
We cannot simultaneously output the 
second and third vertices. 
Those are consecutive, 
those are adjacent, and that's not 
allowed. 
Moreover, you know, in a four note graph. 
It's sort of easy to see how to repair 
this conflict. 
But in a big graph with say thousands of 
nodes, if you have a conflict right where 
the two sub-problems meet, it is not at 
all obvious how you would quickly fix 
that and get a feasible and optimal 
solution to the original problem. 
Now in some sense the divide and conquer 
paradigm is more powerful or better 
suited for this problem than the greedy 
approach, in that I do know of divide and 
conquer algorithms that could solve this 
problem optimally that run in quadratic 
time. 
But doing better than that in a divide 
and conquer matter seems quite 
challenging. 
And the dynamic programming based 
algorithm we'll develop will solve the 
problem in linear time. 
That's coming up next.