Dynamic Algorithms


Dynamic Programming is a powerful technique that can be used to solve many problems in time O (n 2) or O (n 3) for which a naive approach would take exponential time. (Usually to get running time below that—if it is possible—one would need to add other ideas as well.) Dynamic Programming is a general approach to solving problems, much like “divide-and-conquer” is a general method, except that unlike divide-and-conquer, the sub problems will typically overlap.
Example 1: Longest Common Subsequence –

The Longest Common Subsequence (LCS) problem is as follows. We are given two strings: string S of length n, and string T of length m. Our goal is to produce their longest common subsequence: the longest sequence of characters that appear left-to-right (but not necessarily in a contiguous block) in both strings.
For example, consider: S = ABAZDC and T = BACBAD

In this case, the LCS has length 4 and is the string ABAD. Another way to look at it is we are finding a 1-1 matching between some of the letters in S and some of the letters in T such that none of the edges in the matching cross each other.
For instance, this type of problem comes up all the time in genomics: given two DNA fragments, the LCS gives information about what they have in common and the best way to line them up.
Let’s now solve the LCS problem using Dynamic Programming. As sub problems we will look at the LCS of a prefix of S and a prefix of T, running over all pairs of prefixes. For simplicity, let’s worry first about finding the length of the LCS and then we can modify the algorithm to produce the actual sequence itself. So, here is the question: say LCS[i,j] is the length of the LCS of S[1..i] with T[1..j]. How can we solve for LCS [i,j] in terms of the LCS’s of the smaller problems?
Case 1: what if S[i] 6= T[j]? Then, the desired subsequence has to ignore one of S[i] or T[j] so
we have: LCS[i, j] = max(LCS[i − 1, j], LCS[i, j − 1]).
Case 2: what if S[i] = T[j]? Then the LCS of S [1...i] and T [1...j] might as well match them up.
For instance, if I gave you a common subsequence that matched S[i] to an earlier location in
T, for instance, you could always match it to T[j] instead. So, in this case we have: LCS [i, j] = 1 + LCS [i − 1, j − 1].
So, we can just do two loops (over values of i and j), filling in the LCS using these rules. Here’s what it looks like pictorially for the example above, with S along the leftmost column and T along the top row.

 
B
A
C
B
A
D
A
0
1
1
1
1
1
B
1
1
1
2
2
2
A
1
2
2
2
3
3
Z
1
2
2
2
3
3
D
1
2
2
2
3
4
C
1
2
3
3
3
4

We just fill out this matrix row by row, doing constant amount of work per entry, so this takes
O (mn) time overall. The final answer (the length of the LCS of S and T) is in the lower-right corner.

How can we now find the sequence?
To find the sequence, we just walk backwards through matrix starting the lower-right corner. If either the cell directly above or directly to the right contains a value equal to the value in the current cell, then move to that cell (if both to, then chose either one). If both such cells have values strictly less than the value in the current cell, then move diagonally up-left (this corresponds to applying Case 2), and output the associated character. This will output the characters in the LCS in reverse order. For instance, running on the matrix above, this outputs DABA.
Example 2: The Knapsack Problem -

Imagine you have a homework assignment with different parts labeled A through G. Each part has a “value” (in points) and a “size” (time in hours to complete). For example, say the values and times for our assignment are:
A
B
C
D
E
F
G
value
7
9
5
12
14
6
12
time
3
4
2
6
7
3
5

Say you have a total of 15 hours: which parts should you do? If there was partial credit that was proportional to the amount of work done (e.g., one hour spent on problem C earns you 2.5 points) then the best approach is to work on problems in order of points/hour (a greedy strategy). But, what if there is no partial credit? In that case, which parts should you do, and what is the best total value possible?

The above is an instance of the knapsack problem, formally defined as follows:
Answer: In this case, the optimal strategy is to do parts A, B, F, and G for a total of 34 points. Notice that this doesn’t include doing part C which has the most points/hour!

Definition 11.2 in the knapsack problem we are given a set of n items, where each item i is specified by a size si and a value vi. We are also given a size bound S (the size of our knapsack).
The goal is to find the subset of items of maximum total value such that sum of their sizes is at most S (they all fit into the knapsack).

We can solve the knapsack problem in exponential time by trying all possible subsets. With
Dynamic Programming, we can reduce this to time O(nS).
Let’s do this top down by starting with a simple recursive solution and then trying to memoize
it. Let’s start by just computing the best possible total value, and we afterwards can see how to actually extract the items needed.

// Recursive algorithm: either we use the last element or we don’t.
Value(n,S) // S = space left, n = # items still to choose from
{
if (n == 0) return 0;
if (s_n > S) result = Value(n-1,S); // can’t use nth item
else result = max{v_n + Value(n-1, S-s_n), Value(n-1, S)};
return result;
}
Right now, this takes exponential time. But, notice that there are only O(nS) different pairs of values the arguments can possibly take on, so this is perfect for memoizing. As with the LCS problem, let us initialize a 2-d array arr[i][j] to “unknown” for all i,j.

Value(n,S)
{
if (n == 0) return 0;
if (arr[n][S] != unknown) return arr[n][S]; // <- added this
if (s_n > S) result = Value(n-1,S);
else result = max{v_n + Value(n-1, S-s_n), Value(n-1, S)};
arr[n][S] = result; // <- and this
return result;
}

Since any given pair of arguments to Value can pass through the array check only once, and in doing so produces at most two recursive calls, we have at most 2n(S + 1) recursive calls total, and the total time is O(nS).

So far we have only discussed computing the value of the optimal solution. How can we get the items? As usual for Dynamic Programming, we can do this by just working backwards: if arr[n][S] = arr[n-1][S] then we didn’t use the nth item so we just recursively work backwards from arr[n-1][S]. Otherwise, we did use that item, so we just output the nth item and recursively work backwards from arr[n-1][S-s n]. One can also do bottom-up Dynamic Programming.
Example 3: Matrix product parenthesization-

Our final example for Dynamic Programming is the matrix product parenthesization problem.
Say we want to multiply three matrices X, Y, and Z. We could do it like (XY) Z or like X(Y Z).
Which way we do the multiplication doesn’t affect the final outcome but it can affect the running time to compute it. For example, say X is 100x20, Y is 20x100, and Z is 100x20. So, the end result will be a 100x20 matrix. If we multiply using the usual algorithm, then to multiply a ℓxm matrix by an mxn matrix takes time O (ℓmn). So in this case, which is better, doing (XY) Z or
X(Y Z)?
Answer: X(Y Z) is better because computing Y Z takes 20x100x20 steps, producing a 20x20 matrix, and then multiplying this by X takes another 20x100x20 steps, for a total of 2x20x100x20. But, doing it the other way takes 100x20x100 steps to compute XY , and then multplying this with Z takes another 100x20x100 steps, so overall this way takes 5 times longer. More generally, what if we want to multiply a series of n matrices?
Definition 11.3 The Matrix Product Parenthesization problem is as follows. Suppose we need to multiply a series of matrices: A1 × A2 × A3 × ... × An. Given the dimensions of these matrices, what is the best way to parenthesize them, assuming for simplicity that standard matrix multiplication is to be used (e.g., not Strassen)?

There are an exponential number of different possible parenthesizations, in fact 2(n−1)
n−1
/n, so we don’t want to search through all of them. Dynamic Programming gives us a better way.
As before, let’s first think: how might we do this recursively? One way is that for each possible split for the final multiplication, recursively solve for the optimal parenthesization of the left and right sides, and calculate the total cost (the sum of the costs returned by the two recursive calls plus the ℓmn cost of the final multiplication, where “m” depends on the location of that split).
Then take the overall best top-level split.
For Dynamic Programming, the key question is now: in the above procedure, as you go through the recursion, what do the subproblems look like and how many are there? Answer: each subproblem looks like “what is the best way to multiply some sub-interval of the matrices Ai × ... × Aj?” So, there are only O(n2) different subproblems.
The second question is now: how long does it take to solve a given subproblem assuming you’ve
already solved all the smaller subproblems (i.e., how much time is spent inside any given recursive
call)? Answer: to figure out how to best multiply Ai ×...×Aj , we just consider all possible middle
points k and select the one that minimizes:

optimal cost to multiply Ai ... Ak ← already computed
+ optimal cost to multiply Ak+1 ... Aj ← already computed
+ cost to multiply the results. ← get this from the dimensions

This just takes O(1) work for any given k, and there are at most n different values k to consider, so overall we just spend O(n) time per subproblem. So, if we use Dynamic Programming to save our results in a lookup table, then since there are only O(n2) subproblems we will spend only O(n
3) time overall.

If you want to do this using bottom-up Dynamic Programming, you would first solve for all subproblems with j − i = 1, then solve for all with j − i = 2, and so on, storing your results in an n by n matrix. The main difference between this problem and the two previous ones we have seen is that any given subproblem takes time O(n) to solve rather than O(1), which is why we get O(n
3) total running time. It turns out that by being very clever you can actually reduce this to O(1) amortized time per subproblem, producing an O(n2)-time algorithm, but we won’t get into that here.

Dynamic programming is used a lot in string problems, such as the string edit problem. You solve a subset(s) of the problem and then use that information to solve the more difficult original problem.
With dynamic programming, you store your results in some sort of table generally. When you need the answer to a problem, you reference the table and see if you already know what it is. If not, you use the data in your table to give yourself a stepping stone towards the answer.



1 comment:

Subscribe to: Posts (Atom)