Alright. So the answer to this question is the

second one, is B. And I hope if you could keep the notation

straight then the answer was fairly clear.

So let's remember what, what does PIJ mean?

That's the total penalty of an optimal alignment between the first i letters of

X, and the first j letters of Y. So consider Pi zero.

So now we're asking about aligning the first zero letters of X with the first

zero letters of Y. That is with the empty string.

Well the optimal way to match any string to the empty string is you're just going

to insert gaps into the empty string to equalize their lengths.

And so if your string has length i, you need to insert i gaps.

What's the? Penalty of that alignment is just i times

the penalty for a single gap, and that's the answer here in B.

So we're ready now to give the algorithm, and as with all these dynamic programming

algorithms once you know the sub-problems and once you know the recurrence that

relates their solutions there's really nothing to do.

All you do is systematically answer solve all of the sub-problems moving from

smallest to largest. So we're going to use an array A to keep

track of the solutions of all of these sub-problems.

A is going to have two dimensions. The reason for two dimensions is we have

two independent parameters which are keeping track of the sub-problem size.

One for how many letters of X we're dealing with, and the second dimension

for how many letters of Y that we're dealing with.

That's analogous to the knapsack problem, where we also had two dimensions to keep

track of. The number of items in play, and the

residual knapsack capacity. We just figured out what the base case

is, so we just solved those in a pre-processing step.

So if one of the two indices is zero, then the optimal solution value is just

the gap penalty times the non-zero index. And, now we just go to our double four

loops. It's double four loops because we have

two indices into out array. And whenever we get into a sub problem,

we just evaluate the recurrence invoking of these solution to the already computed

smaller sub problems. So one sanity check you should always

apply when you're writing out the code for a dynamic programming algorithm: when

you look at the right hand side of your recurrence, when you look at these

purportedly already solved subproblems whose solutions you're using to solve the

current subproblem, make sure you have actually already solved those

subproblems. So in this case we're good to go because

the indices of the subproblems are only less than the entry that we're filling in

right now. So indeed all three of the relevant

subproblems, A-I - 1 j - 1 A-I - 1 j, and A-I j - 1 they've already been computed

in earlier iterations of our double four loop.

So they're just hanging out, waiting to get looked up in constant time.

And as usual once you've actually figured out the key ingredients for the dynamic

programming solution, namely the sub-problems and the recurrence, it's

pretty much self evident why the things going to work and it's also self evident

exactly what its running time is going to be.

So why is the algorithm correct? That is, why does it terminate with every

entry Aij equal to the true optimal penalty Pij of the corresponding

sub-problem. Well, this just follows because our

recurrent is correct, that's where all the hard work was, and then we're just

systematically solving all of the sub-problems.

So, formally, if you like, it would be proof by induction.