15-451 Algorithms 7 October 2003 Manuel & Avrim Blum 1. Matrix multiplication: another way to view it: Instead of A*B = C, write: * B A C This has the advantage that the dot product of matrix A row i and matrix B column j becomesthe single ij entry in matrix C. Example: column j \/ 0 1 2 2 3 4 4 5 6 6 7 8 1 3 5 9 80 98 116 row i> 2 4 6 8 80 100 120 /\ Cij 2. Dynamic Programming: how can one tell if a problem is a good candidate for dynamic programming? It has to do with the fact that dynamic programming is a powerful extension of divide and conquer. Dynamic programming gives a way to solve all problems that COULD be solved by divide and conquer if only there were a "birdie" to tell you where to split the problem instance. The clue that dynamic programming is called for is that the help of an imaginary birdie could split the given problem of length n into two smaller problems of length n1, n2 satisfying n = n1 + n2. Dynamic programming gives a clever way to simulate the birdie. EXAMPLE 1: recall the longest common subsequence problem: given two strings S1, S2 over some common alphabet SIGMA, find a longest ordered string a1 a2 ... ak that appears in both S1 and S2. This problem could be solved by divide and conquer if only there were a birdie to pinpoint a location in string S2 that corresponds to the halfway point in string S1. For example: S1 = rabbit S2 = habitat /\ /\ In the absence of a birdie, dynamic programming looks at all possible locations at which to split S2. EXAMPLE 2: Parenthesizing (odd-size) matrix multiplication. The goal is to parenthesize a string of not-necessarily-square matrices so that ordinary (not Strassen) row x column matrix multiplication will make the fewest possible elementary (element by element rather than matrix by matrix) multiplications. Thus multiplying lxm by mxn takes l*m*n elementary multiplications. The product of an lxm matrix A and an mxn matrix B is an lxn matrix whose l*n elements are each computed doing m element multiplications. Let A = 2x7 B = 7x3 C = 3x8 matrices. How would you parenthesize the product A*B*C so as to do the fewest possible elementary mulitiplications? (A*B)*C requires 2*7*3 + 2*3*8 = 90 element multiplications. A*(B*C) requires 7*3*8 + 2*7*8 = 280 element multiplications. It follows that some parenthetizations are better than others! In general, to multiply (odd-size) matrices A1 x A2 x ... x Ak, how does one determine the optimal parenthetization? The clue that dynamic programming applies is that one could split this problem if only a birdie would tell you... ___________ what? A: where best to split the product: (A1 x ... x Aj) x (Aj+1 x... x Ak), 3. Graphs are the bread and butter of theoretical computer science. Matrices are the bread and butter of numerical analysis. Actually, the two fields are studying the same objects: graphs are matrices. matrices are graphs. More precisely, matrices are weighted directed graphs. The entry aij in row i column j of matrix A represents a directed edge of weight aij from vertex i to vertex j in the associated graph. Unweighted undirected graphs are represented by 0-1 symmetric matrices. The two fields (Numerical Analysis and Theoretical Computer Science) are starting to inform each other: For example, Strassen's fast matrix multiplication algorithm is being used by numerical analysts, while eigenvalues are being used by theoretical computer scientists to analyse graphs. 4. Depth First Search. The recursive algorithm for Depth First Search is astonishingly simple. The iterative algorithm, while relatively more complicated, clarifies what recursion is doing. You saw something like this with The Towers of Hanoi Problem. It is solved by an utterly simple recursion, but it's hard to imagine how Buddhist Monks could do it in their heads.. until it is turned into an iterative algorithm. We do the same for Depth First Search, turning the almost trivial recursion into a much more complicated but completely iterative algorithm. Tarjan's recursive depth-first search: procedure dfs (vertex v, graph G = ) previsit (v) */first visit to v/* ; for in E, if not visited(w) then dfs(w,G-{all visited vertices of G}) end for. postvisit (v) */last visit to v/* end dfs Our iterative depth-first search of G starting at vertex s is described by a "bread-crumb dropping" or "threading" algorithm. The "thread" is a spool of (possibly directed) breadcrumbs that is used to mark which vertices and edges have been visited. Each edge is threaded exactly twice, once in each direction. As a consequence, it is easy to see that depth-first search runs in linear time: iterative dfs(s, G). For simplicity, assume that G is connected. 1. the start vertex s is unthreaded: drop a breadcrumb on it. if s has no incident edges, then halt. 2. select any arbitrary (necessarily unthreaded) edge out of s and start threading it. REPEAT CASE: 3. when threading an edge e for the first time into a vertex v: 3.1. if v has (previously) been visited, then turn around and thread back along e without revisiting v. 3.2. if v has never been visited, then visit it: 3.2.1. if v has no other edges (besides e), then thread back along e; else 3.2.2. if v has another edge (necessarily unthreaded), then choose such an edge arbitrarily and start threading it. 4. when threading an edge e for the second time (in the opposite direction of its first threading) into a vertex w (that has necessarily been visited earlier): 4.1. if some edge incident to w has never been threaded, then choose one such edge arbitrarily and start threading it. 4.2. if every edge incident to w has been threaded twice (once in each direction), then halt. 4.3. in the only remaining case, all but one edge incident to w have been threaded twice; and the one remaining edge incident to w has been threaded once (into w): thread that last edge out of w. End-REPEAT Examples of dfs by iterative threading algorithm applied to both an undirected and directed graph. The thread is shown dotted (breadcrumbs):