Matrix Chain Multiplication. Our table gave us the minimum number of multiplications needed in the optimal parenthesization, but how do we actually find that parenthesization from the table? When you build a table in dynamic programming, it might be a good idea to have each entry contain some sort of entry to the table entry that spawned the one you're looking at. 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 A(BC) A(BCD) B 0 108 72 B(CD) C 0 36 D 0 The diagonals of 0 are all 0 and don't reference a previous entry. The diagonals representing pairs also do not need to reference a previous entry. Now the triples: 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 Suppose our table looked like this A B C D E F G H I J (ABCDEF)(GHIJ) If the upper right is something like (ABCDEF)(GHIJ) we then look at the AF entry to see how that was broken up, and the GJ entry to see how that broken up. 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 "" "" "" "" "" "" "" "" B "" "B" "B" "B" "B" "B" "B" A "" "B" "BA" 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 For Maximal Common Subsequence, you can do the same thing, keep pointers to the table you came from. In this specific case, this may be overkill, you can easily traverse the table backwards to find the longest common subsequence. RHYME SCHEME If you have a poem of 0 lines: There is one possibl3 rhyme scheme. A poem of one line: one rhyme scheme. A poem of two lines: two rhyme schemes ab, aa A poem of three lines: aaa, aba, abb, aab, abc Understand that the choice of letters is arbitary, aba and bab are the same rhyme scheme. So, with a poem of n lines, how many rhyme schemes are there? Don't think of it as a function on the number of lines: Think it as a function with two parameters: total lines, number of distinct phonemes (maximum number of mutually unrhymable lines). f(0,0) = 1 f(1,1) = 1 f(2,2) = 1 f(2,1) = 1 f(3,3) = 1 f(3,2) = 3 f(3,3) = 1 f(n,n) = f(n,1) = 1. f(n,r): What is f(n+1,r+1)? This is like adding an extra line that doesn't rhyme with the others? So, you could that extra line anywhere..but that's good enough because there may be other singleton lines in there.