MATRIX-CHAIN-MULTIPLICATION This problem is NOT find a fast way to multiply two matrices. The problem is to find a parenthesization of a matrix chain to minimize the running time of the actual matrix multiplication. If A is an mxn matrix and B is an nxp matrix, AB is an mxp matrix. There is a classic algorithm that runs in THETA (mnp) time where you combine each row of A with each column of B. There ARE better algorithms than the classic, the most famous being Strassen's which is very clever...but we're not talking about it today. Let's suppose we have three matrices ABC A is mxn, B is nxp and C is pxq. ABC will end up being mxq. There are two ways to do it (AB)C and A(BC). The first way will take mnp+mpq time. The second way will take npq+mnq time. So which way is the best way? Which way will minimize the number of computations? And really, the only way to tell is to actually compute mnp+mpq and npq+mnq and see which value is smaller. THERE IS NO SLICK TRICK. Dynamic Programming is not about finding a "slick trick." It's about "intelligent trial-and-error." You essentially try all possible combinations, but you do it in an intelligent fashion so that you don't work out the same combination more than once, and so you can still do it reasonably efficiently. How many ways are there to parenthesize ABCD ? ((AB)C)D (A(BC))D (AB)(CD) A((BC)D) A(B(CD)) If I work out AB and BC, I then know the best way for ABC. This reduces the first two options to a single option: (ABC)D. If I work out CD, then I know the best for BCD, which combines the last two options. So now I have three choices (ABC)D (AB)(CD) and A(BCD). And I can then work out which is the best of these three. A B C D A 0 252 171 93 B 0 108 72 C 0 36 D 0 A: 7x3 B: 3x12 C: 12x3 D: 3x1 (AB)C A(BC) 252 + 7x12x3 7x3x3 108 504 171 (BC)D B(CD) 108+3x3x1 3x12x1 36 117 72 (ABC)D (AB)(CD) A(BCD) 171+7x3x1 192 252+36+7x12x1 7x3x1+ 72 93 An nxn upper triangular matrix contains n(n+1)/2 non-zero values. The first n would be the first row. The next n-1 would be the second row. We have to do zero tests for matrix chains of length 1. (The answer is 0.) For matrix chains of length 2, we have to one "product" meaning one (mxnxp) sort of computation. For matrix chains of length 3, we have to do two such products (and a compare). For length 4, we have to do three such products (and compares). For length 5, we have to do four such products, and so on. So, with THETA(n^2) blanks in the table to be filled, this will take us THETA (n^3) time. But if tried all possible combinations of parenthesizations, that would take exponential time. MAXIMUM-COMMON-SUBSEQUENCE. A substring and a subsequence of a string are different concepts. Both involve a subset of the characters in the string in the same order in which they appear in the string, but a string is a contiguous subset of the original string, and a subsequence need not be contiguous. So, for the string "CAT": the substring are "C" "A" "T" "CA" "AT" "CAT" and "". The subsequences are the same as the substrings; however, "CT" is also a subsequence. Given two strings, the MAXIMUM-COMMON-SUBSEQUENCE is the longest subsequence common to both. "BATMAN" "BRUCEWAYNE" what is the maximum common subsequence? "BAN" Naively, this looks to be a rather challenging problem to solve, but the code for it is pretty straightforward and reasonably efficient. BECAUSE we use dynamic programming. "" B R U C E W A Y N E "" 0 0 0 0 0 0 0 0 0 0 0 B 0 1 1 1 1 1 1 1 1 1 1 A 0 1 1 1 1 1 1 2 2 2 2 T 0 1 1 1 1 1 1 2 2 2 2 M 0 1 1 1 1 1 1 2 2 2 2 A 0 1 1 1 1 1 1 2 2 2 2 N 0 1 1 1 1 1 1 2 2 3 3 The symbols on this table should be construed to mean the substring starting from the beginning and ending with the character. So, the "T" in the table actually refers to the string "BAT". And the "W" refers to "BRUCEW". If the last letter of the substrings are identical. If A[1..m] and B[1..n] agree on the last letter (A[m]=B[n]) then the maximal subsequence is the same as A[1..m-1],B[1..n-1] with A[m] appended to it. If the last letters do not match, it's still easy! Look at the MCS of A[1..m-1] and B[1..n] And at the MCS of A[1..m] and B[1..n-1] and pick the larger of those two. "" B A N A N A "" 0 0 0 0 0 0 0 B 0 1 1 1 1 1 1 A 0 1 2 2 2 2 2 T 0 1 2 2 2 2 2 M 0 1 2 2 2 2 2 A 0 1 2 2 3 3 3 N 0 1 2 3 3 4 4 BAAN