CS6515 Lecture01 DP1 FIB LIS LCS

Our first topic is dynamic programming.

This is one of my favorite topics to teach because it's extremely useful.

Students often have some trouble with it initially, but with enough practice it'll sink in and actually it'll seem quite easy once you get the hang of it.

I'll do my best to show you how I solve dynamic programming problems and from there the key to really mastering dynamic programming is to do lots and lots of practice problems. The homeworks are just a start. Do additional problems

from the textbook and from other algorithms textbooks and from other courses you can find on the web. We'll

start with a toy example, computing Fibonacci numbers, to illustrate the basic idea of dynamic programming. Then

we'll dive into a variety of example problems to get a feel for the different styles of DP algorithms. Longest increasing subsequence, LIS, longest common subsequence, LCS, the classic

knapsack problem, chain matrix multiplication, and finally we'll look at a few shortest path algorithms using DP. Given an integer n, we're going to

DP. Given an integer n, we're going to look at an algorithm for generating the nth Fibonacci number.

This will be a very simple algorithm, but it'll illustrate the idea of dynamic programming and then we'll look at dynamic programming in general, the two the techniques for designing a dynamic programming algorithm and we'll look at

some more sophisticated examples. Recall

the Fibonacci numbers are the following sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 and so on. There's a simple recursive

formula that defines the Fibonacci numbers.

The first two numbers in the sequence are 0 and 1.

And then the nth Fibonacci number is the sum of the previous two Fibonacci numbers. We're going to take as input a

numbers. We're going to take as input a non-negative integer n and our goal is to output the nth Fibonacci number. We

want an efficient algorithm and therefore we're aiming for a running time which is polynomial in n. Now the

Fibonacci numbers are defined by this simple recursive formula. Therefore, we

might think a recursive algorithm is the natural algorithm to for this problem.

Let's look at that natural algorithm, that natural recursive algorithm, and then we'll analyze it. Now let's look at the natural recursive algorithm for computing the nth Fibonacci number.

Recall from the previous slide the recursive formula for the nth Fibonacci number is the sum of the previous two Fibonacci numbers. Let's detail the

Fibonacci numbers. Let's detail the recursive algorithm for computing the nth Fibonacci number. We'll call the algorithm Fib1.

A little bit of foreshadowing that what this will be our first attempt and we'll have a second successful attempt for efficiently computing the Fibonacci numbers.

Recall the input to our algorithm is a non-negative integer n and the output is the nth Fibonacci number or more precisely actually the n plus first Fibonacci number if you're keeping track

of the indices. First we'll deal with the base cases. The first two Fibonacci numbers are 0 and 1.

In general, we'll utilize the recursive definition of the Fibonacci numbers where where we will recursively compute the n minus first and n minus second Fibonacci number and we'll return the

sum of those two. This completes the definition of our algorithm. Now let's

take a look at the running time of our algorithm. To analyze the running time

algorithm. To analyze the running time of our algorithm, let's create a function T of n which denotes the number of steps of our algorithm on an input of size n. We have our two base

cases first. Those each take order one

cases first. Those each take order one time.

And then we have our two recursive calls, one of size n minus one and one of size n minus two. Those take time T of n minus one plus T of n minus two.

Putting it all together, we have the following formula. Our running time on

following formula. Our running time on an input of size n is order one for the two base cases and then T of n minus one in order to compute the n minus first

Fibonacci number and T of n minus two to compute the n minus second Fibonacci number. Now this formula may look a

number. Now this formula may look a little bit familiar. Notice it reminds us of the Fibonacci numbers. Fibonacci

numbers, the n minus nth Fibonacci number is the sum of the previous two.

This is the sum of the previous two plus an extra term. So it's at least as large as the nth Fibonacci number. Therefore,

our running time on input of size n is at least the nth Fibonacci number. Now

unfortunately, the Fibonacci numbers grow exponentially in n. More precisely,

they grow exponentially in this constant phi.

What is phi? Well, phi is this constant defined as 1 plus square root 5 over 2, which is roughly 1.618.

But phi is a magical constant. It's

known as the golden ratio. The golden

ratio has many applications. For

example, if you're designing a building such as the Parthenon or if you want just a cool fact to show your kids, then look up the golden rectangle. But for

us, the punchline is that the Fibonacci numbers grow exponentially in n and the running time to compute the nth Fibonacci number using our recursive algorithm is at least the nth Fibonacci

number. So our running time is

number. So our running time is exponential in n. So this is a terrible algorithm for computing the nth Fibonacci number. Let's take a look at

Fibonacci number. Let's take a look at exactly why our running time is so terrible and then we'll get an idea for a more efficient algorithm. Let's take a look at the recursive nature of our

algorithm. At the top level of the

algorithm. At the top level of the recursion, we're computing the nth Fibonacci number. Then we have recursive

Fibonacci number. Then we have recursive sub calls computing the n minus first and n minus second. Then we recursively compute the n minus first Fibonacci number in which our algorithm is going

to recursively compute the n minus second and n minus third Fibonacci number. And for the n minus second, it

number. And for the n minus second, it recursively computes the n minus third and n minus fourth Fibonacci numbers and so on.

Notice that the n minus fourth Fibonacci numbers can be computed many times.

Similarly, when we get down to small Fibonacci numbers, we're going to be recompute them many times, exponential number of times. That causes the inefficiency of our algorithm because we're recomputing the solution to the

small subproblems many times.

To get around that, we're going to flip the algorithm on its head. We're going

to compute the small subproblems first and then work our way to the larger subproblems. In particular, we're going to make an array F, we're going to call it, to

denote the Fibonacci numbers and F of I is going to be the ith Fibonacci number.

We're going to start at index zero and we're going to record the first Fibonacci number and the second Fibonacci number and then we're going to use our recursive formula to compute the third Fibonacci number

and so on. We're going to increase our index using the recursive formula.

Finally, we'll get the nth Fibonacci number. This is the idea of our

number. This is the idea of our algorithm. We'll start with the small

algorithm. We'll start with the small indices, compute the small Fibonacci numbers, and then we'll work our way up to compute the larger Fibonacci numbers

using our recursive formula. This is our dynamic programming algorithm. So let's

define it more precisely so we're all clear.

Now let's detail our dynamic programming algorithm for computing the nth Fibonacci number. Here's our second

Fibonacci number. Here's our second attempt at an algorithm for computing the nth Fibonacci number. Recall we're

going to create an array F which is going to store the Fibonacci numbers and we're going to start at the small indices, namely at the first two indices we store the two base cases, 0

and 1, which are the first two Fibonacci numbers in the sequence.

Then we have a for loop which goes from two up to n, which is our goal, and using the recursive formula, the ith Fibonacci number is the sum of the previous two, which are already stored

in our array. Finally, we return the nth Fibonacci number which is stored in the last index in our array.

This completes our algorithm. Notice the

key thing is that our algorithm has no recursion in it.

We have a recursive formula which defines the Fibonacci numbers, but our algorithm has no recursion in it.

Finally, let's analyze the running time of our algorithm.

Once again, the base cases take order one time each.

Then we have a for loop of size order n.

The one step of the for loop takes order one time. Therefore, the total time of

one time. Therefore, the total time of the for loop is order n time and the total run time of our algorithm is order n time.

This completes our algorithm and gives us a glimpse of a dynamic programming algorithm.

Before moving on to a more sophisticated example, let's recap a few key issues. I

want to stress one important point about dynamic programming algorithms. Our algorithm had no recursion inside of it.

We used the recursive nature of the problem to design our dynamic programming algorithm, but the algorithm itself has no recursion inside of it.

Now there is an alternative approach to dynamic programming. In this approach,

dynamic programming. In this approach, you use a hash table or some other similar structure to keep track of which subproblems have already been solved so that you don't recompute those problems.

Now we're not going to use this at all in our course.

This approach is called memoization.

Try to say that five times. I can't and therefore we're not going to use it in this class.

But actually, the real reason why we're not using it is because the goal of this unit is to learn dynamic programming.

Therefore, to avoid any confusion, we're going to say no recursion in our algorithms. Dynamic programming has several advantages over memoization or similar techniques. Some might say the

similar techniques. Some might say the algorithms themselves are more beautiful. Certainly, they're faster

beautiful. Certainly, they're faster because they have less overhead from avoiding recursion.

And finally, it's much simpler to analyze the running time of dynamic programming algorithms. Dynamic programming is widely used. At first,

students often find it challenging, but what we'll find is that with enough practice, the algorithms, the dynamic programming algorithms, start to seem similar to each other. At that point it'll click and hopefully it'll seem

easy to design a dynamic programming after that. To get to that point, what

after that. To get to that point, what do you need to do? Practice, practice,

practice. Do a lot of practice problems and then it'll click and you'll find dynamic programming easy. We're going to do some in class, you're going to do some in during the homework, and then do a lot on your own. There's a lot of

practice dynamic programming problems out there in the textbook and other online resources that you can find. Do enough practice, you'll ace the

find. Do enough practice, you'll ace the topic. Let's look now at a more

topic. Let's look now at a more sophisticated example of dynamic programming. The problem we're going to

programming. The problem we're going to consider is the longest increasing subsequence problem and for simplicity we'll call it LIS. The input to the problem are n numbers

which will denote as A1, A2 up to AN.

Our goal is to compute the length of the longest increasing subsequence in the n numbers of the input. One important

note, we're only trying to find the length of the longest increasing subsequence. We're not trying to find

subsequence. We're not trying to find the subsequence itself. But if we can find the length, then we're going to get to the heart of the problem and then it'll be easy to turn transform that into an algorithm to output an actual

subsequence of longest length. Let's

take a look at a specific example to help illustrate the terminology in this problem. Here's an example where n

problem. Here's an example where n equals 12. Before defining subsequence,

equals 12. Before defining subsequence, let's recall the definition of the more common term substring. A substring is a string that occurs inside the larger string. So it's a set of consecutive

string. So it's a set of consecutive elements.

For instance, here's one substring, -3 9 1 10.

Another substring is four itself and another substring is 9 10 4 5 8 9 3.

These are all substrings.

How many substrings are there possible?

We can specify a substring by the start index and the end index. Therefore,

there's at most order n squared substrings. Now our problem is not

substrings. Now our problem is not defined for substrings, it's defined for subsequences.

A subsequence is a string you can obtain by deleting elements of the larger string. So it's a subset of elements in

string. So it's a subset of elements in order, but we can skip elements. It

doesn't have to be consecutive elements.

Let's look at some example subsequences.

For instance, 4 -3 1 9 is a subsequence.

Another subsequence is one itself.

Another subsequence is 5 7 3. Now we're trying to find a

3. Now we're trying to find a subsequence which is increasing. That

means that each number is strictly larger than the previous. In this case, it's not increasing because of three is smaller than seven. But an increasing

subsequence, for instance, is 4 9 10.

Another subsequence is 4 4 8 9, but that is not an increasing subsequence. That's a non-decreasing

subsequence. That's a non-decreasing subsequence. And we don't allow that in

subsequence. And we don't allow that in our example. Our goal is to find the

our example. Our goal is to find the longest increasing subsequence in the input array.

For this example, what is the longest increasing subsequence? The longest

increasing subsequence? The longest increasing subsequence in this example is -3 1 4 5 8 9, which is of length six.

So the output of our algorithm on this instance is six. Now let's try to design a dynamic programming algorithm for this longest increasing subsequence problem.

Now let's look at the recipe for designing a dynamic programming algorithm. The first step is to define

algorithm. The first step is to define the subproblem in words.

To see what I mean by this, let's look back at the simple example of Fibonacci numbers. In that example, our subproblem

numbers. In that example, our subproblem definition was f of i is the ith Fibonacci number. The second step in our

Fibonacci number. The second step in our recipe is to state a recursive relation.

We want to express the solution to the ith subproblem in terms of smaller subproblems. So for the instance of Fibonacci numbers, we want to express f

of i in terms of f1 through fi -1.

Because if you recall our dynamic programming algorithm for computing the Fibonacci numbers, we computed f1 up through fi -1.

So those will be stored in our table and then we can use those to compute f of i.

Now for the case of the Fibonacci numbers, it was straightforward to express f of i in terms of smaller subproblems, namely f of i is the sum of

the previous two Fibonacci numbers. Now

let's figure out how to follow this recipe for the longest increasing subsequence problem.

Now let's follow the first step in our recipe. We want to define the subproblem

recipe. We want to define the subproblem in words. Our first attempt is always

in words. Our first attempt is always going to be to use the identical problem on a prefix of the input. In this case, that means we're going to look at the longest

increasing subsequence on the first i elements of the input array. Therefore,

we're going to make a new function L, which is the length of the longest increasing subsequence on the first i elements of the input. Now we want to figure out how to express L of i in

terms of L1 through Li -1, smaller subproblems. To do this, let's take a look back at our earlier example and see if we can gain some intuition.

Recall our subproblem definition is L of i is the length of the longest increasing subsequence on the first i elements of the input array. And our goal is to express L of i

array. And our goal is to express L of i in terms of the solution to smaller subproblems. So now let's recall our earlier example. Here is our earlier

earlier example. Here is our earlier example which had n equals 12. Now let's

look at L on this example.

To start with, for L of 1, we're looking at the longest increasing subsequence on the one element array. That's length one for five itself. Then for L of 2, we're

looking at the two element array 5 7.

The longest increasing subsequence is 5 7 itself, which is length two.

Then for 5 7 4, 5 7 is still the longest. Then we add on three,

longest. Then we add on three, it's still length two is the longest.

For nine, we can append it onto the longest solution, we get a length three.

With one, stays three. We can when we add on 10,

stays three. We can when we add on 10, we can append 10 onto the longest solution.

We get length four.

Now let's pay attention to the case i equals nine. What is L of nine?

equals nine. What is L of nine?

Well, we cannot append on eight onto the end of this current longest solution. But in fact, there's a different solution,

-3 1 4 5 -3 1 4 5, for which we can append eight onto the end and we get a solution

of length five.

So the problem is, how can we compute L of nine using L1 through L8?

How do we know whether we can append eight onto the end of the current solution or not?

We're not maintaining the current solution, but even if we maintain the current solution, how do we know that we can append eight onto the end of it?

For this solution, we couldn't maintain it. We couldn't append it onto the end.

it. We couldn't append it onto the end.

But for this solution, we could append eight onto the end of it. So suppose we kept track of the current solution. Or

actually, what do we need to know? We

need to know the ending character of the current solution.

And what's the key fact? We want to know the longest increasing subsequence with the minimum ending character.

So we want to know the smallest ending character.

Because a smallest ending character gives us the most possibilities for appending on a new character onto the end.

So in this case, in order to compute L of nine using L1 through L8, we need to keep track of the longest increasing subsequence solution with the minimum

ending character. And in this case, it's

ending character. And in this case, it's five and then we realize we can append eight onto the end of it and we can increase the solution length from four.

Let's go back to i equals eight and we'll start to see the complication in this solution. Previously, our solution

this solution. Previously, our solution was 5 7 9 10. But actually, with our new formulation, what we want to maintain is

-3 1 4 5 because this is also of length four and it ends in a smaller character. But

now let's go back to i equals seven.

For i equals seven, the longest increasing subsequence is 5 7 9 10.

But note, when i equals eight, we need to have this sequence -3 1 4. Now this is only length three, so it's a suboptimal

solution. But we need to maintain it in

solution. But we need to maintain it in order to realize in the next step that we can append five onto the end of it and then we obtain a length four solution for i

equals eight. So how do we maintain this

equals eight. So how do we maintain this suboptimal solution? The key is that for

suboptimal solution? The key is that for every possible ending character, we want to maintain the length of the longest increasing solution with that ending

character. We need to know the length of

character. We need to know the length of the longest increasing subsequence for every possible ending character. If we

know that for every possible ending character, then when we get a new character, in this case five, we can try all possible ending characters and we can try to add on five. We can

see whether it is allowed to add on five onto the end of it. Now, how many possible ending characters are there? What are the possible ending characters? Well, the

ending characters must be an earlier element in the input array. So in this case, it's 5 7 4 -3 up to four.

Okay, those are the possible ending characters. So they're not

characters. So they're not limitless. There's a finite small

limitless. There's a finite small number, actually i -1 possible ending characters. So this actually gives us an

characters. So this actually gives us an idea for how to modify our subproblem formulation. We want to know the length

formulation. We want to know the length of the longest increasing subsequence for every possible ending character. We

just noticed that the possible ending characters are the earlier elements in the array. Therefore, we want to

the array. Therefore, we want to maintain the length of the longest increasing subsequence for each element of the array. This gives us an idea for the new sub problem formulation. We're

going to modify the length of the longest increasing subsequence on A1 through AI and includes AI.

Okay? So, this will give us the longest increasing subsequence, which ends at the ith element of the array.

In this case, five.

And then, we have that for L1 through LI - 1.

And then, we can use that to decide what is the longest sequence ending at eight, because we can see which characters allow us to append eight onto the end of it. Let's go back and

formulate this more precisely, and then we'll see the recurrence. We now have a new sub problem formulation. Let L of I denote the length of the longest increasing subsequence

on the first I elements of the array, input array, A1 through AI, and which includes AI itself. This is

the extra restriction that we added into our sub problem formulation.

Okay? It requires that AI is included in the subsequences that you consider. Now,

it'll speak straightforward to express a recurrence, which formulates L of I in terms of L1 through LI - 1. Let's go

back and look at our earlier example, and now we'll see the straightforward recurrence that arises.

Here's our earlier example, and let's look at L for this new sub problem formulation.

In this case, L of 1 is 1, because we're looking at the length of the longest increasing subsequence on an input of size one, just five itself, and it has to include five. Then, for I

equals two, it's of length two, from the subsequence 5 7. Now, we start to see a difference when I equals three.

What is the length of the longest increasing subsequence in 5 7 4, which includes four?

That's just four itself. So, that's of length one.

Okay? Recall in our earlier definition of L, it was length, it was three.

This entry.

Once again, for I equals four, L of 4 is 1, because of minus three itself. For I

equals five, now the length is three, from 5 7 9.

For I equals six, the length is two, from minus three one.

For I equals seven, the length is four, from 5 7 9 10.

Finally, let's look at the case I equals 10, which is the case which caused problems in the earlier definition of L.

Now, in this case, we want to see which sub problems allow us to append eight onto the end of it. Now, notice eight can be appended onto subsequences ending

at 5 7 4 -3, but nine it cannot get appended onto.

Cuz that won't be increasing. It cannot

get appended onto 10, either. But, the

others allow it to be appended onto the end. So, we're going to take the longest

end. So, we're going to take the longest of those, and we're going to add plus one for adding eight onto the end of it.

So, whatever is the longest increasing subsequence ending at five, we can append eight onto the end of it.

We don't have to know the subsequence itself, we just have to know it's of length four, and it ends at five, and then we can append eight onto the end, and we obtain a sequence of of length

five. Therefore, L of 10 is five.

five. Therefore, L of 10 is five.

Now, this highlights the recurrence for the solution of L of I in terms of smaller sub problems, L1 through L - 1, I - 1. Now, let's formally state the

recurrence for L of I in terms of smaller sub problems. L of I requires that AI is included in the subsequence. Therefore, we get

one for including element AI in it, and then we take the longest subsequence that we can append onto the beginning.

So, we're going to take the max over all earlier indices of the length of the subsequence ending at that character AJ.

Now, that earlier subsequence allows us to append AI onto the end of it only if AJ is strictly smaller than AI.

So, you only want to consider J's where AJ is strictly smaller than AI, and then we can take that earlier subsequence ending at AJ and append AI onto the end

of it, and we get L of J for that earlier subsequence, plus one for AI.

And of course, we need that J is earlier in the input array than AI. Just in case the mathematical notation is confusing for anybody, let me re-express it with slightly different notation and

re-explain what it's saying in words.

So, L of I, the length of the longest increasing subsequence on the first I elements, which includes AI, so we get one for that element AI, and then we're taking

We have AI here.

Then, we're going to take the longest increasing subsequence that we can put at the beginning.

It's going to end at some element AJ.

Okay? So, we're going to try all possibilities for that J.

Now, we need that that index J is earlier in the input array. So, we're

going to try J's between I - 1 and 1.

And we only want to try J's where AJ is strictly smaller than AI. So, we're

doing a max over J.

J is a variable that we're varying.

We're trying J's where it's between 1 and I - 1, and such that AJ is strictly smaller than AI. And we're we're taking the

than AI. And we're we're taking the value L of J.

Finally, we have our sub problem definition, and we have our recursive relation that these sub problems satisfy. Now, it'll be straightforward

satisfy. Now, it'll be straightforward to detail our dynamic programming algorithm. So, let's give the pseudo

algorithm. So, let's give the pseudo code for our dynamic programming algorithm, and then analyze its running time, and then we'll have completed this problem.

Now, let's state the pseudo code for the dynamic programming algorithm for the longest increasing subsequence problem.

And I kept the recurrence from the previous slide about the L of I in terms of smaller sub problems as a sort of crib notes for ourselves. Here's the

pseudo code for our dynamic programming algorithm for the LIS problem. The input is A1 through AN. Our solutions are in

through AN. Our solutions are in one-dimensional array L, and we're going to fill the table L from bottom up. So,

we're going to start at index I equals 1 and go up to I equals N. So, we're going to have a single for loop for I going from 1 to N.

Now, our sub problem formulation requires that AI is included in the solution for L of I. That's the plus one term. Therefore, we start by setting L

term. Therefore, we start by setting L of I equal to 1, and then we're going to do the max over J. So, we're going to have another for loop, which varies J from 1 to I - 1.

Now, we need to check that AJ is strictly smaller than AI.

If AJ is strictly smaller than AI, then we need to check if the solution we can obtain by appending AI onto the end of the solution ending at AJ is longer than

our current best solution.

So, if AJ is strictly smaller than AI, and and our current best solution, L of I, is strictly smaller than the new solution we can obtain by appending AI

onto the end of L of J. In this case, we want to update our current best solution, which is now the solution that we obtained by appending AI onto the end

of the solution that ends at AJ. Now,

we've given an algorithm which defines our table L. But, what is the solution that we're trying to output from this algorithm? For the case of Fibonacci

algorithm? For the case of Fibonacci numbers, it was the last entry in the table.

In this case, the last entry of the table is the longest increasing subsequence ending at AN. That's not

necessarily the solution that we're trying to obtain. We're trying to find the longest increasing subsequence, regardless of where it ends at. So, what

we need to do is try to look through L and find the maximum entry in the entire one-dimensional array. So, let's go

one-dimensional array. So, let's go ahead and do that. We'll make a variable max, which will maintain the index with the largest entry of the table. We'll

start max at one, and then we'll go through the entries of the table to see if we find a larger entry than the current max.

This for loop simply finds the largest entry of the table and stores the index for that entry in the variable max.

Finally, what do we return? We return

the entry at index max.

This completes the formulation of our dynamic programming algorithm. Now,

let's take a look at the running time of our algorithm.

We have one for loop, which is varies over order n elements, and we have another nested for loop, which varies over at most n elements. Within these

two nested for loops, we have a if then statement, which takes order one time.

Therefore, the total time for these nested for loops is order n squared time.

Finally, we have another for loop, which finds the max entry in the table. This

is one for loop, it's not nested. This

is order n time. Therefore, the total run time of our algorithm is order n squared time.

This completes the formulation of our dynamic programming algorithm and the analysis of its running time. But now,

let's go back and take a look at some important aspects of our algorithm design. What was the first step in our recipe for designing a dynamic programming algorithm? It was to

to the sub problem in words. In this

case, define L of I in words. Our

initial attempt was to use a prefix of the input. Was to define the length of

the input. Was to define the length of the longest increasing subsequence on the first I elements of the array. Then,

our second step in our recipe is to find a recurrence relation that the solution subproblems satisfy.

In that case, for that definition, we were unable to do so. So, what did we do? We went back and we reformulated our

do? We went back and we reformulated our subproblem definition. We added an extra

subproblem definition. We added an extra condition into it and then we were able to write a recurrence for the subproblems. Now, the intuition for why we wanted to

strengthen the subproblem definition. It

goes back to, if you recall perhaps from a discrete math class way long ago, when you were trying to prove some statement by induction.

How did you go about it?

Well, you would first state an inductive hypothesis. Usually, the inductive

hypothesis. Usually, the inductive hypothesis is of the same form as the statement that you're trying to prove.

Then, you try to prove that hypothesis using induction.

But, sometimes you run into difficulties and what do you do? You go back and you alter your inductive hypothesis.

Typically, what you do is you try to strengthen your inductive hypothesis by adding extra conditions in. That's

exactly what we did here. We added the extra condition that the subproblem has to include A I itself. Okay? And then,

you strengthen the inductive hypothesis and you prove that stronger statement.

And that's what we're doing here. We're

proving a We're giving an algorithm for this stronger problem. We're finding the

stronger problem. We're finding the length of the longest increasing subsequence with the specific character at the end.

Using that solution to that stronger problem, we can then solve the weaker problem where we don't care what is the ending character. So, a lot of the

ending character. So, a lot of the intuition for what we're doing in dynamic programming comes from some ideas from induction proofs.

Our next dynamic programming example is longest common subsequence, which we'll use the shorthand LCS.

The input to the problem is two strings which we'll denote as X and Y and for simplicity for now, we'll keep them both of the same length N.

Our goal is to find the length of the longest string which appears as a subsequence in both X and Y. And notice

that we're trying to find a subsequence, not a substring, and we're simply trying to output the length of the string. And if we can find the length, we can use that to find an

actual string which appears as a subsequence. And we'll see how to do

subsequence. And we'll see how to do that at the end. Let's take a look at an example to make sure you're okay with the terminology.

Here's an example with two strings of length seven. Let's do a quick check to

length seven. Let's do a quick check to make sure you understand the problem definition.

In this example, what's the longest common subsequence?

Go ahead and mark the the longest common subsequence in this example and also indicate the length of it.

So, the solution is the substring B C B A B C B A which is of length four. Why do we

care about it? Well, I mean, first off, it's a it's a nice um example which illustrates a slightly different flavor of dynamic programming solution. That's

the main motivation here.

Uh but also, this actually this simple problem is used in Unix diff.

If you want to compare two files, you have this Unix script diff which compares two files and looks at differences and it this utilizes the longest common subsequence dynamic

programming algorithm. So, let's dive

programming algorithm. So, let's dive into the first two steps in our recipe for designing a dynamic programming algorithm. Our first step is to define

algorithm. Our first step is to define the subproblem in words.

Recall our subproblem definition for some of our earlier examples. For

Fibonacci numbers, we said F of I to be the I'th Fibonacci number. In the

longest increasing subsequence problem, we said L of I to be the length of the longest increasing subsequence on the first I numbers in the input. What are we going to do here? Our first attempt is always

to try the same problem on a prefix of an input. So, it's key. It's just

an input. So, it's key. It's just

identical to the original problem and it's just on a prefix. So, all we've changed is from doing it on length N to length I.

First I characters. So, let's formalize that. So, we're going to

that. So, we're going to we're going to have a variable I which is the prefix length.

And the prefix length varies between zero, corresponding to the empty string, and length N, which is our original input.

And we define a new function L of I which is the length of the longest common subsequence in the first I characters of X and the first I characters of Y.

Our second step is to define a recurrence.

We want to express L of I in terms of L1 through L I minus 1.

So, let's take a look at how to define the recurrence in this example that we saw earlier. Let's detail the subproblem

saw earlier. Let's detail the subproblem definition we proposed. We have a parameter I which corresponds to the prefix length.

I is going to vary between zero and N. I

equals zero corresponds to the empty string.

I equals N corresponds to the original input. Now, we're going to define a

input. Now, we're going to define a function L of I. This will be the length of the longest common subsequence in a prefix of X of length I and a prefix of

Y of length I. So, X1 through XI and Y1 through YI.

Note, this is analogous to the original problem except on a prefix of the input.

One other notable difference, this does not store the subsequence itself. It

simply stores the length.

We want our table to store our number or true false. Now, let's take a look back at our earlier example.

Now, this was our earlier example. We're

trying to find a recursive relation for L of I. We're trying to express L of I in terms of smaller subproblems, L1 through L I minus 1. Let's try to gain some insight from this example. In order

to get a smaller subproblem, we're going to look at the last character. So, we're

going to look at XI and YI. We're going

to look at how XI and YI are used in the solution to L of I and then we can use the solution to the subproblem of size I minus 1.

We take the optimal solution for the subproblem of size I minus 1 and then we append on the solution for XI and YI. Now, there

are two cases to consider. Either these

last characters are different in this case or they're the same. We're going to consider these two cases separately. The

first case is when the last characters XI and YI are the same. The second case is when the last characters XI and YI are different. We're going to do this

are different. We're going to do this case first. XI equals YI. The last

case first. XI equals YI. The last

characters are the same.

This turns out to be the easy case. Now,

let's modify our example so that the last characters are the same. So, I

append on character C onto the end of both strings.

Now, in this case where the last character is the same, what do we know about the longest common subsequence?

Well, we know it must include it must end in this common character. Why? Well,

give me a common subsequence and suppose it does not include this last character.

Well, then I can append on this common character and I get a longer subsequence.

So, therefore, the longest common subsequence must include this last character.

So, in this case where XI equals YI, what do we know about L of I? We know

that the longest common subsequence includes this last character. So, we get one in the length for that common character. And then, we can simply drop

character. And then, we can simply drop this last character. And then, we can take this input sequence of length I minus 1 and we can take the longest common subsequence in this input

sequence of length I minus 1 and append on this common character C. What is the length of the longest common subsequence in this input? It's simply L of I minus 1.

So, we have a recursive relation. We can

express L of I in terms of L of I minus 1. This handles the case when XI equals

1. This handles the case when XI equals YI. Now, let's take a look at the case

YI. Now, let's take a look at the case when XI is not equal to YI. Let's take a look now at the case when the last characters are different.

This is the situation in our original example.

XI is not equal to YI. A is not equal to B. Now, in this case when XI is not

B. Now, in this case when XI is not equal to YI, the last character of the longest common subsequence can either be A or B or neither. Certainly cannot be

both. Now, suppose it's A.

both. Now, suppose it's A.

For example, suppose this is the last character in the longest common subsequence. Then, what do we know about

subsequence. Then, what do we know about YI?

B. Well, B has nothing left to match with in X. Therefore, we know the LCS does not include B, YI. Similarly, if

the last character is B, say it's matched with this B, then the LCS cannot include A because it has nothing left to match with in Y. The key point is that

the longest common subsequence for this prefix of length I either does not include XI or it does not include YI or both. So, either XI is

dropped or YI is dropped or both of them are dropped. Now, let's consider the

are dropped. Now, let's consider the three cases. If both of them are

three cases. If both of them are dropped, then we can simply take the longest common subsequence in this prefix of length I minus 1. So, it's

similar to the equal case except we don't get this plus one here. Now, what

happens if just XI is dropped? Well,

then we have a prefix of length I minus 1 in X and a prefix of length I in Y.

So, we have no way of looking this up in our table. The solution to this

our table. The solution to this subproblem is not in our table because the prefixes are of different length in X and Y. And notice, even if we knew how YI is matched up with in X. For

instance, if we knew this B was matched with this B, then we have a prefix of length three in X and we have a prefix of length six in Y. So, they're still of different length. And similarly, if YI

different length. And similarly, if YI is not included, so we drop this last character from Y, then we have prefix of length seven in X and a prefix of length

six in Y. So, the prefixes are of different length in X and Y. And once

again, the solution to this subproblem is not in our table because these prefixes are of different length. So,

for this case where YI is dropped, we need to look up the longest common subsequence in the prefix of length I in X with the prefix of length I minus one in Y. Now, this isn't in our table

in Y. Now, this isn't in our table presently.

And similarly, when we try to solve this subproblem, well, then we might chop off the last character from Y, and then we get even shorter prefix in length Y. So, for this

subproblem definition, we are unable to define a recurrence. We are unable to express L of I in terms of smaller subproblems. But, we got some insight about what is a valid What is a good

subproblem definition? The difficulty

subproblem definition? The difficulty here was that the prefixes are of the same length for X and Y, but we need to allow them to be different lengths. So,

how do we achieve that? We're going to change from a single parameter I to a pair parameters I and J. I will

correspond to the length of the prefix in X, and J will correspond to the length of the prefix in Y. And our table will now be a two-dimensional table. So,

L of I, J will be the length of the longest common subsequence in X1 through XI with Y1 through YJ. And we're going to try all possibilities for I and J.

So, let's go back and revise our subproblem definition with the insight that we just gained. The key insight was that we're going to need a prefix of X and a prefix of Y of possibly different lengths. Therefore, we're going to have

lengths. Therefore, we're going to have two indices, I and J, which are going to correspond to the length of the prefix in X and the length of the prefix in Y.

And as a consequence, we're going to end up with a two-dimensional table. In all

our previous examples, we had a one-dimensional array or table, and now we're going to have a two-dimensional table or array because we have two indices, I and J. So, let's go ahead and

formalize our subproblem definition. For

indices I and J, where once again, I varies between between zero and N, and similarly, J varies between zero and N.

We're going to define the function We're going to define the function L of I, J, which is the length of the longest common subsequence in the first I characters of X and the first J

characters of Y. The key is that X is of length I and Y is a prefix of length J.

Now, let's go ahead and see if we can define a recurrence for this new subproblem definition. Let's start off

subproblem definition. Let's start off with the base cases. Base cases are going to be when I is zero or J zero.

Let's start with considering the case when J is zero. So, what is L of I, zero? And what is L of zero, J for the

zero? And what is L of zero, J for the case when I is zero? Well, for L I, zero, so there Here, J is zero. That

means that Y is the empty string. So,

what is the longest common subsequence Well, in both Well, Y is the empty string, so there's no subsequence in it.

So, the length of it is of length zero.

Similarly, if we're taking an empty string for X, then the longest common subsequence is the empty string itself, which is of length zero. So, those are

the two base cases. Let's move on to the more interesting cases. So, let's go ahead and try to define the recurrence for our new subproblem definition, the length of the longest common subsequence in the first I characters of X and the

first J characters of Y. And let's go back and look at our earlier example.

Here's our earlier example, and notice that here they're both of the same length. And just to illustrate our new

length. And just to illustrate our new subproblem definition, let's add in one more character to Y, so they are now of different length. And if you recall our

different length. And if you recall our approach from before, what we're going to do is we're going to look at the last character of both sequences, and we're going to condition on whether they're the same or different. If they're the

same, then we can possibly match them together. If they're different, there's

together. If they're different, there's no way we can match them together. So,

let's do the case where they're different first. Our key insight is that

different first. Our key insight is that in this case where the last characters are unequal, then the longest common subsequence either ends in A, the last

character of X, or in the last character of Y, which in this case is D, or it ends in neither.

Now, if it ends in A, that means it does not end in It does not end in D. It does

not include D in the final solution.

Okay? There might be other occurrences of D, but we're differentiating the multiple occurrences of this character.

This character is not included in the final solution, or this character is not included in the final solution, or

both of these final characters are not included in the optimal solution.

So, there are three cases to consider.

Either the last character of X is not used in the optimal solution, the last character of Y is not used in the optimal solution, or the last character of both is not used in the optimal solution. If the last character of both

solution. If the last character of both is not used, we can get there by dropping the last character of X and then dropping the last character Y, or vice versa, dropping the last character Y and then X. So, there's really only

two cases to consider. Either we drop the last character of X or the last character of Y, and we're going to take the best of those two. So, let's recap.

So, if we drop the last character of X, and XI is not used in the optimal solution, then L of I, J is the same as L of I minus one, which this is just

dropped XI from it, and J. The other

scenario is that we drop the last character of Y, and in this case, L of I, J is L of I, J minus one. We just

dropped YJ from Y. How do we know which of these two is the better solution? We

just take the larger of the two. So,

that's going to be our recurrence. Our

recurrence is L of I, J is going to be the max of these two possible solutions. Let's recap. In this

possible solutions. Let's recap. In this

case where XI and YJ are different, so the last characters of the two prefixes are different, then we have our recurrence. L of I, J is going to be the

recurrence. L of I, J is going to be the best of the two possible scenarios.

Either that we drop the last character of X, and therefore we have the solution for I minus one characters of X and J characters from Y, or we drop the last

character from Y, and we get the solution L of I, J minus one. And which

of the two are we going to take? We're

going to take the better of the two, which means we're going to take the one which has larger length, which is the max. So, this defines our recurrence for

max. So, this defines our recurrence for the case when XI is not equal to YJ.

Now, let's do the case where XI equals YJ.

So, for our new subproblem definition, we've defined the recurrence for the case when the last characters of the two prefixes are different. Now, let's go look at the case where the last characters of the two prefixes are the

same. So, I've modified our example so

same. So, I've modified our example so that this is the case. Here, they both end in A. We're looking now at the case where XI equals YJ, so the last characters of the two prefixes are the

same. And now in this case, there are

same. And now in this case, there are three possibilities to consider. As in

the unequal case, we can either not include XI in the optimal solution, in which case we drop XI, or we drop YJ.

Notice actually those two are the same in this scenario because XI and YJ are the same. So, if we're dropping XI,

the same. So, if we're dropping XI, we're also dropping YJ.

It's going to foreshadow a little bit the solution, the recurrence. The other

possibility, which didn't exist in the unequal case, is that the optimal solution ends in the common character XI, YJ. As in the unequal case, what

XI, YJ. As in the unequal case, what we're going to do is we're going to look at these three scenarios, and we're going to take the best of the three. Now, in the first case where we

three. Now, in the first case where we drop XI, notice that L of I, J is equal to L of I minus one, J, where we just dropped XI from the solution, just like

in the unequal case. Similarly, when we drop YJ, L of I, J equals L of I, J minus one. Now, the interesting case,

which didn't exist before in the unequal case, is that the optimal solution ends in this common character. And in this

case, L of I, J is one plus The one is for the common character that we're appending on the end. And then we're going to take the optimal solution which drops

XI and YJ from there, and we take the optimal solution to these smaller prefixes.

So, this is L of I minus one and J minus one.

We take the length of that optimal solution for that smaller problem, add one for this common character which we append at the end, and that gives us the

length of the longest common subsequence in this new subproblem.

So, let's recap our recurrence for the case where XI equals YJ. The last

characters are the same in the two prefixes. Here, we have three

prefixes. Here, we have three possibilities, and we're going to take the best of the three. Therefore, we

take the max. We have L of I minus one, J, which corresponds to dropping XI, L of I, J minus one, which corresponds to dropping YJ,

or we include XI, YJ, the common character at the end, and we get a plus one for that, and then we take the optimal solution to this smaller subproblem, L of I minus one, J

minus one.

And we take the max of these three.

Some of you may have noticed that in fact, the recurrence in this case can be simplified even further. We only need to consider the last case where we append on XI, YJ, the common character onto the

end.

Let me give you some brief intuition about why that's the case. Notice, if

the solution doesn't include either of these characters, then we can just add them on, and we get a longer. So, therefore,

it wasn't optimal length. So, it's got to include either XI or YJ. Now, it may be the case that XI is matched with some

earlier occurrence of that character. In

this case, it's Y1. But, any solution which we obtain by matching XI with an earlier occurrence of that character, we could have obtained by instead matching

XI with this latter solution. Any

subsequence which occurs in that smaller prefix of Y also is a subsequence in this larger prefix of Y.

Okay? It's a super set of it. Therefore,

we only need to consider this case and we get this simpler recurrence for this case where they're equal. Okay? And this

completes our definition of the recurrence.

Let's recap the recurrence that the L of I J satisfies. Now, we're looking at the case where the two strings are non-empty. So, I is at least one and J

non-empty. So, I is at least one and J is at least one. Now, we had two cases here. We had the case

here. We had the case XI is not equal to YJ. The last

characters are different. And we had the case where the last characters are the same. In the case where they're the

same. In the case where they're the same, we had this simple recurrence.

We append on XI YJ and therefore get a plus one for that and then we take the optimal solution to the smaller subproblem with one less character in each string. Now, in the case where

each string. Now, in the case where they're not equal, we took the best of two scenarios.

We either drop the last character from X or we drop the last character from Y.

And we take the larger of these two solutions. And we also had the base

solutions. And we also had the base cases where one of the two strings was empty, in which case the length is zero.

Finally, now we can state our dynamic programming algorithm, the pseudo code for the algorithm. And now, notice we we have a two-dimensional table now. L is a two-dimensional array.

How we going to fill it up? We're going

to fill it up row by row.

Okay? And now, when we're looking at this entry L I J, what are the entries that we're going to need for it?

We're going to need either this diagonal, which is right here, L I minus one J minus one, which will be there because we filled in the previous row,

or we'll need the entry just above, or we'll need the entry just to the left.

So, we're just going to look at these three entries, which will all be there because we're filling it up row by row.

So, earlier in this row will be completed and the previous row will be completed. And now, we can go ahead and

completed. And now, we can go ahead and state our dynamic programming algorithm.

Finally, let's take a look at the running time of our algorithm.

The two base cases are each order one per step and then they're an order N sized for loop.

Therefore, they take order N total time.

Then, we have a for loop of size order N and a nested for loop of size order N.

And inside, it takes order one time.

So, the total time is order N squared for these nested for loops and the total run time of our algorithm is dominated by the order N squared.

So, we get order N squared total time.

This completes the dynamic programming algorithm for longest common subsequence problem. The interesting thing that

problem. The interesting thing that arose in the solution was that we needed to use a two-dimensional table. This came about

two-dimensional table. This came about because we needed to consider prefixes of X of different length than prefixes of Y.

Now, we can state the pseudo code for our dynamic programming algorithm for the longest common subsequence problem.

The input are these two strings X and Y.

Now, let's start with the base cases, which are the top row and the first column.

We first set L I 0 to be 0. This

corresponds to setting the first column to zeros.

Then, we set the first row to all zeros.

These are our two base cases. Now, we

can fill the interior of our table. As

we said earlier, we're going to go row by row. Index I is going to correspond

by row. Index I is going to correspond to the current row. Then, we go along this row. This is the index J. Now, we

this row. This is the index J. Now, we

have two cases to consider. Either the

current last characters of X and Y are the same or they're different. So, if XI equals YJ, we have one recurrence. And

if XI is not equal to YJ, then we have a different recurrence. In the case where

different recurrence. In the case where XI equals YJ, the recurrence is one plus the one comes from the appending XI and YJ to the end

and then taking the optimal solution for the prefix of length I minus one with length J minus one.

In the case where they're not equal, the recurrence is the best of the two scenarios. Either we drop the last

scenarios. Either we drop the last character from Y, giving us L of I J minus one, or we drop the last character from X, giving us L of I minus one J,

and we take the max of these two.

Finally, what is the output of our algorithm? It's the entry in the

algorithm? It's the entry in the bottom right of our matrix.

L of N N is the length of the longest common subsequence for all of X with all of Y.

At this point, I suggest you try some practice dynamic programming problems. There are a lot of great practice problems in the Dasgupta book.

Let me suggest a few problems for you.

Now, these are problems from the textbook Algorithms by Dasgupta, Papadimitriou, and Vazirani. There's

problem 6.1, which is about finding a contiguous subsequence of maximum sum.

Now, note a contiguous subsequence is the same as a substring.

Now, whenever I assign you a homework problem, I'm always going to tell you some little blurb about what the problem is about so you can identify it.

Because some of the online versions of this textbook have different numbering.

So, you should always make sure it's the correct problem if you have an online version. The next problem is 6.2, where

version. The next problem is 6.2, where you're planning a trip and you want to figure out the hotel stops to minimize the penalty.

Problem 6.3 is about Yuk Donald's.

In 6.4, you're given a string and you want to see if you can break up that string into a set of words.

Now, 6.11 is longest common subsequence.

We already did that in this lecture.

But for practice, you might try the variant where you do the longest common substring. It's useful to look at how

substring. It's useful to look at how dynamic programming solutions vary.

What's the difference when you have substring versus subsequences?

Once again, at this point, you should be able to do these practice problems: 6.1, 6.2 6.3 6.4 and 6.11 or this variant of 6.11 where you do substrings instead of

subsequences.

Let me give you a quick summary of the approach we use for designing a dynamic programming algorithm. And you can

programming algorithm. And you can implement this approach when you try these practice problems. The first step is to define the subproblem in words.

How do you do that? Well, you should take the same problem, the original problem, on a prefix of the input. So, the

subproblem should be of the same form as the original problem, but instead of being on an input of length N, try it on a prefix of the input. So, an input of length I. The second step is to define a

length I. The second step is to define a recurrence relation. If you have a

recurrence relation. If you have a one-dimensional table, then you want to express T of I, or the Ith entry of this one-dimensional table, in terms of smaller subproblems,

T1 through TI minus one. This is what we did for LCS, though in that case it was a two-dimensional table. Now, when we did LIS, longest increasing subsequence, we were unable to do this. And what we

needed to do was strengthen the subproblem. So, we had to go back and

subproblem. So, we had to go back and redefine the subproblem. So, we

strengthened the subproblem by adding the constraint. Typically, we add the

the constraint. Typically, we add the constraint that the last element, element I, is required to be included in the solution to this subproblem. So, for

LIS, we said L of I was the longest increasing subsequence in the prefix of the input of size I, but the last element AI had to be

included in that solution. Now, one

thing to keep in mind is typically when we add in this constraint, then the final output is no longer the last element in the table, but instead we're going to have to do a max or a min,

but we're going to have to go over the whole table and look for the best, the optimal solution in the table. Now, I

want to show you how I solve these practice problems. So, I'm going to show you how I approach this problem 6.1. But

to get the most out of it, I suggest that you try the problem first.

And then if you're having difficulty, you can watch the next slide to see how to solve it. Now, the input to this problem is A1 through AN. Our goal is to find the contiguous subsequence. Notice

that a contiguous subsequence is the same as a substring. We want to find the substring with maximum sum. Now, the

first step is to define the subproblem in words. I'm going to try the same

in words. I'm going to try the same problem on a prefix of the input. So,

I'm going to have a parameter I, which is the length of the prefix. So, I'm

going to have I and this is going to vary between 0 and N. And now, I'm going to define S of I in words first it's going to be the max sum that I can obtain.

This is the same form as the original problem, but instead of considering the whole input, I'm going to consider the first I numbers. So, it's the max sum

numbers. So, it's the max sum from a substring of A1 through AI.

So, it's the first I characters of the input. Now, we want to try to find a

input. Now, we want to try to find a recurrence relation. We want to express

recurrence relation. We want to express S of I in terms of S1 through SI minus one, smaller subproblems. Let's take S of I-1.

This is the max sum that we can obtain from a substring of A1 through AI-1. So,

let's take that sum. Now, there's two possibilities that I would consider.

Either I'll add on AI onto the end of it or not. First off, can I add on AI onto

or not. First off, can I add on AI onto the end of this solution? Well, I have to maintain that it's a substring that is contiguous. I don't know where this

is contiguous. I don't know where this one ends. So, I don't know whether I can

one ends. So, I don't know whether I can add on AI onto the end of this solution.

So, I need to know where this one ends.

With this current definition, there's no way. I don't know how to express S of I

way. I don't know how to express S of I in terms of these smaller sub problems. But, I notice that if I knew where this solution ended

at, so if it included A of I-1, then I know that if it includes AI-1, then I can add on AI and maintain that it's a substring. So, I have to go back

and strengthen my sub problem definition.

Here's a solution to problem 6.1. Let's

reformulate our condition that the sub problem had to include AI. So, we define S of I as

the max sum which we can obtain from a substring of A1 through AI with the extra restriction that AI has to be included in that substring. Now,

we will be able to express a recurrence for S of I. First off, let's handle the base case. That's I equals 0. What's S

base case. That's I equals 0. What's S

of 0? We have the empty string, so that's of course 0. Now, let's look at S of I for I at least 1. Well, we are required to use AI.

So, let's add in AI. So, by including AI, this sum is at least AI plus what do we append onto it? Well, there are two

onto it? Well, there are two possibilities. Either we just use AI by

possibilities. Either we just use AI by itself or we append it on to the longest substring from A1 through AI-1. And we're going to

take the best of those two possibilities. So, if we have AI by

possibilities. So, if we have AI by itself, then we get 0 for the rest, for A1 through AI-1. Or if we take the optimal

through AI-1. Or if we take the optimal substring for A1 through AI-1, what's the sum from that? Well, it's S of I-1.

And we're going to take the best of these two scenarios. Now, clearly if this is negative, then we're going to just use AI by itself. And if this is positive, then we're going to take this solution and append on AI to it. So,

this gives us the recurrence. It's easy

to fill the table by going from I equals 0 up to N.

And what's the final output of the algorithm? It's not necessarily S of N

algorithm? It's not necessarily S of N because that's the longest, the maximum sum from a substring which includes AN.

But, we're just looking for the maximum sum we can obtain from any substring. We

don't care what the last character is.

So, we need to try all possibilities for the last character or number. So, we do a max over I of S of I. So, we take our one-dimensional table and we look for the max entry in that table. And that's

the output. And what's the running time of this algorithm? Well, each entry of the table takes order one time because we just have to look at two numbers. And

how many entries in the table are there?

There's order N. So, the total run time is order N.