15-451 Algorithms 10/07/04 * Dynamic Programming, contd * Depth-first-search * Topological sorting ===================================================================== One more example of Dynamic Programming: Matrix product parenthesization Say we want to multiply 3 matrices X, Y, and Z. And we're going to use the usual algorithm, not Strassen. We could do it like this: (XY)Z or like this X(YZ). Which way doesn't affect final outcome but *does* affect running time to compute it. E.g., say X is 100x20, Y is 20x100, and Z is 100x20. So, end result will be a 100x20 matrix. If we multiply using usual algorithm, then to multiply lxm matrix by an mxn matrix takes time O(lmn). So in this case, which is better, doing (XY)Z or X(YZ)? Answer: X(YZ) is better because computing (YZ) takes 20x100x20 steps, and produces a 20x20 matrix, then multiplying this by X takes another 20x100x20 steps, so total is just 2x20x100x20. But, doing the other way, (XY) takes 100x20x100 steps, so already right there you've spent more, and then multplying this with Z takes another 100x20x100 steps. Question: suppose we need to multiply a series of matrices: A_1 x A_2 x A_3 x ... x A_n. What is the best way to parenthesize them? There are an exponential number of different possible parenthesizations: {2(n-1) choose n-1}/n. So don't want to search through all of them. DP gives us a better way. Idea: if you were going to do it recursively, what would the subproblems be? -> For each i,j, what is the best way to multiply A_i x ... x A_j. So, let's start by solving the small subproblems and saving our results, and then using those results to help us solve the bigger subproblems. How can you solve one subproblem given that you've already solved all the smaller subproblems? -> To figure out how to multiply A_i x ... x A_j, consider all possible middle points k. -> For each such k, our cost if we decided to split there would be: cost-to-multiply(A_i x ... x A_k) <- already computed + cost-to-multiply(A_{k+1} x ... x A_j) <- already computed + cost to multiply the results. <- get right from the dimensions. -> So, just chose the k that minimizes this sum. What is the time? -> O(n^2) subproblems. -> O(n) time per subproblem (because you need to consider O(n) choices of k). => O(n^3) time total. ============================================================================== TOPOLOGICAL SORTING. A "DAG" or directed-acyclic-graph is a directed graph without any cycles. E.g., A----->D--->E |\ ^ | \ | | \ | | | / V V/ C<--B<----F Given a DAG, the "topological sorting" problem is: find an ordering of the vertices such that all edges go forward in the ordering. Typically comes up when given a set of tasks to do with precedence constraints (need to do A and F before you can do B), and want to find a legal ordering of performing the jobs. How can we solve this problem? Here is a method you might come up with: 1. find a node v with no in-edges and output it. 2. remove v and its outedges 3. goto 1. If we have the graph stored as an adjacency list, with each node also having a count of its in-degree, then Steps 1 and 2 take O(n) time [in step 2, you just decrement the counts of all of v's out-neighbors]. So overall this takes O(n^2) time. Can improve this using a heap data structure to store in-degree [when we remove v, we do decrease-key on its neighbors]. This costs O(log m) for each outedge removed in step 2, so O(m log m) overall. [n = number of vertices. m = number of edges]. But here's a neat linear-time algorithm based on depth-first search: How to solve Topological Sorting #2: 1. Do depth-first search of G, and output the nodes as you *exit* them. 2. reverse the order. To be specific, by "DFS of G" we mean "pick a node and do DFS from there. If the whole graph hasn't been visited, then pick an unvisited node and repeat the process. Continue until everything is visited". E.g., DFS_main(G): For v=1 to n: if v is not yet visited, do DFS(v). DFS(v): mark v as pre-visited. for each unmarked out-neighbor w of v: do DFS(w). postvisit(v). // <-- output here! Claim: If there is an edge from u to v, then v is exited first. (This implies that when we reverse the order, we have a topological sorting.) Proof of claim: [Think of u=B, v=D above.] Easy to see if our DFS started at u before starting at v. What if we started at v first? In this case, we would finish v before even starting u since there can't be a path from v to u (else wouldn't be acyclic). Note: can use same alg to tell if graph has any cycles.