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. .