Video 3-2: Recap: Dynamic programming

0:03 In the next section, I want to briefly recap dynamic programming as an algorithm design paradigm. Uh, this will certainly have been part of some undergrad algorithms module. So, I'll go quick. Um, but I think it's it's worth first of all, I like the the template that I'm going to show you. I think it's worth to reiterate that. And it also means for the other algorithms, we can stop at a certain level, leave out the automatic part.

0:30 I think overall that makes the presentation still more concise and more more enjoyable. Maybe uh the way I I teach this I say dynamic programming has these six steps and I'll show you on on the example of edit distance. What I mean by these um we always have to define what sub problems are of the original problem and we have to somehow solve the original problem as a special case of one of these sub problems. Then to make progress we do a local brute force step which usually means guessing one part of a solution but then trying all possible guesses and from these two things we can formulate a recurrence for the cost of the solution or the quality of the solution in general. The other the other three steps then once you've done this and you understood the general recipe are automatic. You can turn the recurrence into a simple implementation that just memorizes the values. You can also replace this by uh in practice certainly more efficient bottom-up table filling algorithm.

1:36 And um so far these two algorithms just give you the quality of the best solution. If you want to compute the actual solution, that also is always a mechanic process uh called back tracing. That's essentially a a meta algorithm. It's an algorithm that generates an algorithm and that one finds you the best solution.

1:59 Okay. So the first three steps are where the creativity and insight into the problem are needed. The rest is automatic. If you want to prove correctness, you do this at the level of the recursion. Um, and you can also guess what the final time is here. Like that statement is true if you stick to the recipe precisely. Uh, we'll see some cases where you can modify then the algorithms by using well additional knowledge about the problem. um and uh kind of beat the trivial solution, the trivial algorithm that comes out of the recipe. Uh but in general, the time you get from just following the the cookie cutter approach, you get the number of sub problems times the time you need to find uh to go through all the guesses in one of these sub problems. And that product gives you the overall time and uh often times also the space. Let's see this in action. So, uh for edit distance, assuming you've seen this before, maybe it doesn't come as a big surprise.

3:11 Uh if if you have a prefix of the two sequences already aligned, so you've constructed a prefix of the alignment or edit script, then the question is what what will this next column look like? And really, there's only three options. It can either be one that looks at the next character in in each of the two strings or it could be an insertion or it could be a deletion.

3:43 And you have to pick the best out of these three options. And because the overall cost of an alignment is additive, we count the number of edit operations. Each of these contributes a certain amount. These always contribute one. This contributes one if the two characters differ. Uh in each case, you know what to do. So if you um map this onto the six steps, what you do for the sub problems is take prefixes of the two strings. So any positions uh in in the range of the strings give you a a a certain prefix. And these are all our sub problems. The gas as I said is what the last column of the alignment looks like. And I guess at this point we can also say the original problem is or i= n m and n= j i j j= n.

4:45 That solves our original problem because then I've taken the whole strings and that gives us a recurrence for computing the edit distance that directly follows uh this uh the sub problem uh structure if one of the two indices is zero. So I'm taking nothing from one of the two strings but there's some parts from the other string. Well let's take the first one. If I take nothing from the second string then I have to delete all the characters I'm taking from the first string. So if I is is given that's I deletions.

5:29 And the symmetric case if I don't take anything from the first string I have to insert everything in the second string that I have. And in both cases these are the number of operations. um that's what we get as the cost. If we're not in these uh degenerate cases where I have no letters from one of the two strings, then I can always do the three options for the last step. This one says I'm taking one more character from the top string, but I leave the bottom one alone. So that's essentially like um uh shouldn't have drawn it like this I guess. Uh I'm uh deleting this character. In this case I'm inserting one in the second string. That's why this is plus one. This is for a deletion. This plus one is for an insertion. And the third case is I'm taking the last string of both characters and then I get a cost of one if and only if they're different. So here again um this notation I know it as Iverson bracket that's how Don can calls it. It's one if the condition is true and zero otherwise.

7:04 that's a concise way to write the recursion. Um these are the three options I have for the last column of the alignment and I take the best. That's essentially all for uh for the experts that know dynamic programming. The rest is completely mechanic. Let's go through it uh one one time. At this level, we can already uh estimate what the final running time will be because uh the number of sub problems is fixed. Now that's all of those n * m. Uh that's an n. Um sorry, which one was the n? Second. Uh the time to optimize one specific sub problem is to find the minimum of these three items. So I can do that in constant time. So the overall time is n * m n * m hard to say clearly in the trivial solution that's also going to be my space requirement and this is something we'll come back to. Um as I said the first step is to just compute the cost but we can do a back trace to find the actual edit script.

8:13 Uh just to illustrate the four steps very briefly. If you have this recursive equation, maybe you're concerned that it's im it's costly to compute. But fear not, in the case where we have dynamic programming uh templates apply, we can always do this. Uh we can always compute the recursion in a way that uh I don't have to recomputee many things. If I memorize I guess that's always possible. It's just the number of sub problems that's not too big. So uh the convenient way to do this is to have two mushially recursive functions. One that computes the actual value and another one that wraps it and says oh have I computed this sub problem? If yes return the cached result otherwise call the first function to compute the result. [snorts] And for our concrete problem this is what it looks like. The edit distance that's the function that does the actual work follows very closely the recurrence. You see the if statements exactly mirror the case distinction.

9:23 Uh then I have to find this minimum of three things. So okay here I can just compute all three and take the minimum. It's really boring. Uh and then the memorization part is to have a second function that's the cached version of this computation. it it starts you have to at some point initialize this array of storing all the sub problem values. I'm doing this outside of this function and just assume this is already given. I somehow have a global variable storing this and then in each step um I'm just going to check if my entry for this sub problem has already been computed then I return it otherwise I first compute it.

10:10 Again, the code is supposed to bore you to death because it's really showing we can stop at the level as soon as we have this recurrence. We don't need to write down this code each time. It's very schematic and uh looks the same each time. This is often not the most efficient way to do it in practice because you're uh essentially doing un unstructured random accesses to this uh two-dimensional array and for cache locality that's not perfect. Um you often do slightly better if you just fill up all the entries in this table bottom up. Uh that's replacing recursive functions with four loops. And so that's another benefit in practice. It's not a a huge factor. I don't know if uh maybe a factor two is already optimistic for this. Okay. But still um because it's always possible. Uh it's it's kind of nice to uh spell it out. The general form means you're building a DAC over all the sub problems. the edges in the DAC come from which sub problem uses which other sub problem in one of the uh the guesses and uh it has to be a DAC otherwise your recurrence wouldn't work. You would cycllically depend on each other. So it has a topological order and you can fill the entries following this this topological order. In most cases, the subpros are tpples of of numbers and then uh if you pick the right order to iterate through them, you follow a topological order. But I think it's nice to keep in mind that this is um it works in in full generality.

12:03 Here much much simpler. Uh the sub problems were just the prefixes. I'm taking the first I characters from the first string A, the first J characters from the second string B. And the way they depend on each other um you can visualize if you think about this this uh matrix um that we compute DIG.

12:31 Uh make it a bit nicer. So that's the matrix Dig that we're filling. Say I'm writing this in the way mathematicians would write a matrix. So 0 0 is the top left corner. Then uh if I'm computing a certain entry, the three subpros that it that the sub problem J depends on around it. namely the one with ius one, jus one, the one with i and j minus one and the one with that's one and the one with uh ius one and j. They correspond to the insert, delete and replace slashmatch.

13:18 So the edges in the graph would would look like this. And that's all edges. So you can do many things in this case to get a topological order. But one way to do it is to go row by row and then within each row by increasing columns. Okay, [snorts] it's a long way to say lexographic by i inj.

13:38 And here's here's the code for doing that. Uh lexographic is very nice because that maps into two nested for loops. We first go over the rows and then we go over the columns and the inner part again is literally copying in what the recurrence tells us. Uh there's the two two base cases where we take uh the special starting conditions and then there's the other case where I couldn't be bothered to write out finding the minimum again. I just left it as a formula. But you would probably want to substitute the code from the previous slide.

14:19 The magic here from the topological order is that whenever I'm using array values here, the topological order ensures that they've been computed before I reach this point. So I'm never accessing null pointers. That's what we have to make make sure of where the initialization to infinity is irrelevant. Also, it's inconsistent with the comments. I think um we don't use any of the values. We overwrite every single one of them. So, it doesn't even need to be initialized.

15:00 Okay, I think so far is super easy. Uh the second the last step is uh to fill fill in compute the actual uh edit script at this point. Of course um you can analyze this algorithm and it's two nested for loops. I'm sure you could do it. uh it's the same theta class as the memorized recursive function but it tends to be faster as I said um for essentially hardware reasons but also the code I guess is a bit cleaner um to write the last last step is now we know from this table like uh okay I didn't emphasize this the we return at the end the bottom right bottom right corner of the of the matrix that contains the edit distance of the act of the full strings. Um that gives us the cost of the overall gives us the edit distance or the cost of the optimal edit script but not a script or the alignment itself. If we wanted to get that we can do again a very schematic and uh automatic translation to get a back tracing algorithm.

16:11 Yeah, it's I couldn't fully track down where the name back tracing comes from and it's not even always consistent. Sometimes people call this backtracking and this is horribly wrong. Like don't do that. There's no backtracking happening. So, uh I'm I'm strict on back tracing because we just retrace our steps, the steps we took to compute the optimal value. You can always write this as a cute recursive function. And here's the example for our edit script. U I'm assuming I already have all the edit distance values computed and I'm assuming I keep all of them around. So here we really need this um m * n space.

16:57 Then I'm have a recursive function that starts with the outermost. So I would call it with m and n the uh the largest values for the entire sub problem. And the function is recursive. It has these uh conditions mirroring the um recurrence. I regret I didn't have a small picture of the recurrence. We could we could have it, but maybe we can just puzzle it together again. If I is zero, I'm not taking any uh letters from the first string. So if I want to get to J letters from the second string, I have to insert them all. So I do that in my edit script. Similarly, if J is zero, then I have to get rid of all the I strings, I characters in the first string. So, I'm doing that. The other cases that can happen is uh the last column in my alignment could be one of the three things. And here I have to distinguish if it's a match or a mismatch because the operation in the edit script is different.

17:57 First case is if my edit distance if the com the minimum I'm computing for dig came from this option. So um I'm going back in the J column. I'm red getting rid of one character there. So that was an insertion. I kept the uh I characters from the first string but I add one more in the second string. Well, if that was the best choice, that means the last operation in the edit script has to be the insertion of that last character in the second string. And how do I get the rest of the edit script? Well, recursively. So, I've just called trace back on this sub problem that I'm uh picking the cost off here and append this one more operation at the end. and the rest is uh is completely symmetric. If the last if the minimum came from choosing a deletion, then I'm I'm doing that with the appropriate trace back. If the last characters I mean if if I'm not in either of these cases uh that means I could have had this one uh I uh had a match in the last case then I'm doing a trace back for all those but I don't do any operation for the match because the edit script does nothing otherwise the only option that's left is I did not do an insertion or deletion but it wasn't a match then it was a mismatch I'm adding the replacement operation Okay, if instead of producing the edit script, you wanted to produce the alignments, that's an easy exercise. The same kind of code, you just replace these edit script operations with appropriate pairs of characters.

19:52 Um, we could do that as an exercise, but I feel that's even even too boring um to do it. The time for doing the back trace if I if I have all the values stored is dominated by computing the values. So I can always do it almost for free.

20:18 And so um computing the optimal cost and the actual solution have the same bet theta class complexity.