ISE 390 -- Programming Challenges -- Week 10 Notes This Week's Goals: To review the basic principles of dynamic programming. Don't Be Greedy Many problems call for finding the "best" solution satisfying certain constraints. For example, the backtracking problems often asked for the largest, smallest, or highest scoring configuration. Backtracking searches all possible solutions, picking the best one, and hence *has* to return the correct answer. But this can be too slow for large problems. For many important problems in graph algorithms, efficient procedures are known to find the optimal solution, including shortest paths, minimium spanning trees, and matchings. It is important to know what these problems are so you can recognize when you can just plug in an appropriate solution. There is a temptation to use some intuitive or "greedy" procedure to identify the best solution, such as making the best local choice at each decision point. In the absence of a proof of correctness, such algorithms are almost certainly wrong. Dynamic programming is a way to design custom algorithms for a wide variety of problems which systematically searches all possibilties (hence guaranteeing correctness) but which stores results to avoid recomputing (hence permitting efficiency) Dynamic Programming: Dynamic Programming is a technique for computing recurrence relations efficiently by sorting partial results. The first trick is to describe the solution to the entire problem in terms of solutions to smaller problems. This defines a recursive algorithm. The second trick is to see that the recursive algorithm tries to repeatedly compute the same subproblems over and over and over again, so storing them in a table can lead to an efficient algorithm. How Do We Reconstruct the Path The dynamic programming recurrence typically returns the cost of the optimal solution, but how does one get the correct path? To reconstruct the solution (instead of just the cost) we must keep track of which decision we made at each local point, and then trace backwards from the optimal solution to reconstruct the path. Example: Multiplying a Sequence of Matrices Suppose we want to multiply a long sequence of matrices $A * B * C * D \ldots$. Multiplying an $X * Y$ matrix by a $Y * Z$ matrix (using the common algorithm) takes $X * Y * Z$ multiplications. We would like to avoid big intermediate matrices, and since matrix multiplication is {\em associative}, we can parenthesise however we want. Matrix multiplication is {\em not communitive}, so we cannot permute the order of the matrices without changing the result. Consider $A * B * C * D$, where $A$ is $30 * 1$, $B$ is $1 * 40$, $C$ is $40 * 10$, and $D$ is $10 * 25$. There are three possible parenthesizations: ((AB)C)D=30 * 1 * 40+30 * 40 * 10+30 * 10 * 25 = 20,700 (AB)(CD)=30 * 1 * 40+40 * 10 * 25+30 * 40 * 25 =41,200 A((BC)D)=1 * 40 * 10+1 * 10 * 25+30 * 1 * 25 = 1400 The order makes a big difference in real computation. How do we find the best order? Let $M(i,j)$ be the {\em minimum} number of multiplications necessary to compute $\prod_{k=i}^{j}A_{k}$. The key observations are: (1) The outermost parentheses partition the chain of matricies $(i,j)$ at some $k$. (2) The optimal parenthesization order has optimal ordering on either side of $k$. M(i,j) = Min_{i\leq k \leq j-1}[M(i, k)+M(k+1, j)+d_{i-1}d_{k}d_{j}] M(i,i) = 0 The following code fragments have been lifted from Sedgewick's "Algorithms in C++" book: /* Matrix chain multiplication */ for (i = 1; i <= N; i++) for (j = i+1; j <= N; j++) cost[i][j] = INT_MAX; for (i = 1; i <= N; i++) cost[i][i] = 0; for (j = 1; j < N; j++) for (i = 1; i <= N-j; i++) for (k = i+1; k <= i+j; k++) { t = cost[i][k-1]+cost[k][i+j] +r[i]*r[k]*r[i+j+1]; if (t < cost[i][i+j]) { cost[i][i+j] = t; best[i][i+j] = k; } } order(int i, int j) { if (i == j) cout >> name(i); else { cout >> '('; order(i, best[i][j]-1); order(best[i][j], j); cout >> ')'; } } Assigned Problems: 116 -- Find the shortest LR path across a weighted grid. Can this be done with Dijkstra's algorithm? Is there a simpler algorithm because the graph is a circular grid? 147 -- How many ways can you make change of a given value with a specific set of denominations? This is a classic DP problem -- find a recurrence relation to do the counting and use DP to implement it. 164 -- Find the minimum edit distance (or approximate string matching, or Levenstein distance) between two strings, with the output in a pecular format. 231 -- Find the longest decreasing subsequence of a stream of numbers. Can you do this with a simple variation of string edit distance? 357 -- How many ways to make change again, with different denominations. Can you easily reuse your program from problem 147?