0:00

So now we have,

Â we have reasoned about how to solve the [INAUDIBLE] structure problem.

Â And we got to our recursive formula, which we said,

Â we can easily just now turn it into a recursive, recursive algorithm.

Â How do recursive algorithms work?

Â Again, recursive, the recursive algorithm is going to start from opt of 1N,

Â and then it's going to start breaking the problem into smaller problem, and

Â solving, and solving, and solving.

Â If you think about it, if you try that algorithm and you look at it carefully,

Â you will see that there will be many times where you for

Â example opt of IJ will be solved over and over and over again for a same I and J.

Â Okay?

Â So the, one of the issue with recursive algorithms in these kind of problems.

Â Is that there are some problems that are going to appear multiple times when we

Â break the problem into sub-problems.

Â And these sub-problems are going to be solved again, over and over and over.

Â Now instead of doing that,

Â how about when we solve a sub-problem, we store the value.

Â So when we solve opt of I J, we store the value of opt I J.

Â And then next time we see, next time we encounter opt of I J,

Â instead of solving that again, which will take time, we can just look up the,

Â the value of that I J in a matrix, I by J.

Â Right?

Â And this is actually the, the, the technique that we,

Â I'm going to show now, or the implementation of that, of that algorithm.

Â That instead of doing recursive implementation is going to

Â store values in a table and every time we need,

Â we need a value instead of re-computing it we'll just look it up in a table.

Â And this the, this is the implementation here of the algorithm I just described.

Â Again, I'm going to, I'm going to start.

Â Instead of, of starting opt of 1 N,

Â I will starting from opt of, of I J from smaller values of I J.

Â From 1, 1, 1, 2, and so on, and go all the way and build towards opt of 1 N.

Â So, wha, first thing is I, I can op, initialize opt of IJ to zero for

Â every case where I is greater than or equal to J minus 4.

Â because remember, the no sharp turns say that i has to be smaller than J minus 4.

Â So, for every case where I is greater than or equal to minus 4.

Â This can't, this has to be zero.

Â I cannot have any pairs, in the, in the set.

Â So, now that, that this is the case, I can initialize k from 5 and onwards,

Â and I start with the sequence with the onward sequence from position 1 to,

Â all the way to N minus K.

Â When I look at position 1, in my a, in my RNA sequence.

Â 2:31

If this is the position, I look at I equals 1,

Â then J has to be incremented by value K, again here by 5,

Â so that it doesn't violate the, the, the no shorts conditions.

Â I can start now solving between I and

Â J, then I increment J, solve this case, then J is here.

Â I solve this case.

Â When I'm done with every possible value of J,

Â I increment I and I repeat the same exercise.

Â At the end I will have the value of I all the way between one and N.

Â Okay?

Â So this is the algorithm that is not a recursive implementation.

Â So here OPT of I J is not,

Â OPT is not the name of a function, it's a name of a matrix.

Â Suppose OPT, assume that OPT is basically a, a matrix where I am storing values.

Â Okay?

Â So, OPT is a matrix that is, that is indexed by I and j and every time

Â I come to this, what I am saying is OPT of I, J is the max of OPT I, J minus 1.

Â So I lookup the value.

Â In the table, at, put, at, in the row I, column J minus 1.

Â Max again, vary the value of T and look up these values.

Â Since I'm building the matrix from smaller I and J towards bigger ones,

Â every time I come to I and J, these values have already been computed.

Â And I can just look them up in the table okay?

Â So the difference again, between our recursive implementation and

Â this sort of implementation,

Â is in that recursive implementation I would have called the function OPT, and

Â I will pass parameters i, n, j in addition to the, to the RNA string.

Â And it would start from OPT of 1N, and starts going down and

Â building, and trying to solve sub-problems, sub-problems.

Â And when it solves all the sub problems, it goes back.

Â And, and compute the solution to the main problem.

Â This implementation, instead is going to start from the simpler cases.

Â I'm going to say, yes you want opt of one n.

Â I'm going to start from opt one and six for example.

Â One of 7, 1 of 8 and 1 of 9, and start building my solution toward opt of 1N.

Â and this is basically the algorithm.

Â Again these are all, keep in mind that OPT here is the name of a matrix, and

Â when I say return OPT of 1, n, I'm saying look up the entry in row 1,

Â column n, in this matrix and just return.

Â Okay?

Â So this is an algorithm that is not recursive.

Â 4:55

And it stores values in a table, and every time it wants to,

Â to, to compute a new value, it's just based on looking up values in a table.

Â So lets, lets illustrate this algorithm with this string here.

Â So if I have a, an, an RNA string of 9, of 9 symbols.

Â And I have this algorithm, again the initialization is that it's for

Â every I and J where I is greater than or equal to J minus 4.

Â We are going to fill this matrix here with zeros, okay.

Â So for example, if I look at 4 and 6, when I is, is 4 and J is 6.

Â This is going to be zero because 4 is greater than or equal to 6 minus 4.

Â So in particular, we will see that this is going to be ze,

Â zero, this is going to be, these are all going to be zeros here.

Â 5:47

Okay? So here 1 and 6, 1.

Â Is great 1 6 minus for is 2, so

Â this one, actually is not going to be 0's here, just these one's, right?

Â So when i is 1 and this is 1 is not greater than or

Â equal to 6 minus 4 which is 2, so this is fine here, okay?

Â So these.

Â These three rows here are going to be,

Â these three diagonals are going to be all zeroes, all right.

Â Based on that initialization.

Â Now we go to the more interesting cases.

Â I say let K equal 5.

Â So now let's think about k equal five.

Â 6:41

Okay? So I is going to traverse these values.

Â For each I, J is going to be I plus K.

Â So 1 plus 5 is 6.

Â 2 plus 5 is 7, 8, 9 okay?

Â So this algorithm is going to compute the values in the matrix for

Â these pairs of indices.

Â So it's going to compute pt of 1, 6, opt of 2, 7, opt of 3, 8, opt of 4, 9.

Â Okay? So if we star with 1, 6.

Â Opt of 1,6.

Â [SOUND] Opt of 1,6 it can be the max.

Â Let's look at how this computation would be.

Â It's either opt of 1, 5, this 1,

Â or the max over sum T.

Â 7:54

Okay?

Â Now, of course, here when I add one,

Â I'm basically assuming that 1,6 can go together.

Â 1 and 6, A and U, can go together in this case.

Â For example, when I go to 1, 7, when I'm if I'm looking at 1, 7,

Â 1 and 7 cannot go together so the t wouldn't count there.

Â OKay?

Â So here opt of 1, 5.

Â Opt of 1, 5 is going to be, where is that here?

Â Opt of 1,5 is zero.

Â And because it, because of the initialization.

Â And this one here is going to be, the value is going to be one.

Â So we'll end up at, actually the,

Â the value will be end up computing here is going to be one.

Â And if I repeat this exercise for K equal 5 and now looking at, at 2, 7 and then 3,

Â 8 and then 4, 9, I'll end up with 1, 0 here and 1 and 0.

Â Okay?

Â 8:48

And repeat now the exercise.

Â When we are done with this now, we increase K to 6.

Â But notice the interesting thing that's happening here is that every time I

Â want to compute these values, all these entries are already in the matrix, okay?

Â There are already in the matrix, okay?

Â So, now I, I increase K to 6.

Â If, when K is set, is, is a 6, this is going to go, I is going to from 1,

Â 2 to 3 and J is going to be I plus K.

Â Okay?

Â So, now we're going to be, the way this algorithm is, is working is that, it will,

Â it completed this diagonal.

Â Then next time, it's going to do this diagonal here.

Â Then the, then this, and then, finally, this one.

Â Okay?

Â So if we look at this here, and we do the computation right,

Â you will notice that it will do, it will get values ones here.

Â 9:45

Then we come to this one, it will compute these values again,

Â just using this this relation.

Â And notice that every time when I come to compute this one,

Â it's going to be based on values that have already been computed.

Â It was never a need, when I compute this, it will not need this value,

Â which hasn't been computed.

Â Then at the end it will compute this value which is two.

Â Okay?

Â So, the important thing to keep in mind here is that this algorithm.

Â It's building a matrix that's called opt, here.

Â It is indexed by this I N J and then at the end of

Â the day what I'm really interested really in, is this here.

Â This is of opt of 1,9, which is optimal number of positions that

Â are matched together in, when I'm doing the RNA structure and the entire sequence.

Â And the other thing that is very important to note is that every time I'm filling and

Â entering the matrix I am using entries that have already been filled.

Â 11:10

Of this algorithm, and this implementation belongs to a class of

Â algorithms that we call dynamic programming.

Â Okay? This is called dynamic programming,

Â which is different from recursive algorithms because a recursive algorithm

Â would have implemented this algorithm recursively without storing values in

Â the matrix, whereas here we are storing values in the matrix.

Â And every time we will see an instance of the problem, that we had solved already,

Â we will just look up the value of that instance from the matrix.

Â