2.1.1 Recursive solution Let c[i,j] be the length of the LCS of Xi and Yj. Based on Theorem 2.1, we can write the following recurrence: c[i, j] = if i = 0 or j = 0 c[i 1, j - 1] +1 if i, j> 0 and Xi = y; max{ci 1, 3), c[i, j - 1]} if i, j > 0 and 2; + y; This is nicethe optimal substructure property allows us to write down an elegant recursive algo- rithm. The way this algorithm works is shown in a simplified form in the tree below. Now one can see that the cost of this algorithm is still far too great we can see that there are N(2min{m,n}) nodes in the tree, which is still a killer. But at least we have an algorithm. 2.2 Overlapping subproblems What saves us is that there really aren't that many distinct nodes in the tree. In fact, there are only (mn) distinct nodes. Its just that individual nodes tend to occur lots of times. Figure 3 shows a slightly simplified picture of the DAG corresponding to an longest common sub- sequence problem. There really should be an edge from (3,3] to (2,2], for instance. We left it out. But the point in any case is that lots of the nodes really occur many times, over and over. 14,3) (3,311 14,2] 2,31 13,2 (3,2 [4,1] (1,3) (2,2] (3,1] (2,2] (3,1] [3,1] [1,0] [0,3] (1,2 (1,2) [2,1] [1,2] [2,1] 2,1] (3,0 (1,2 (2,1] 2,1] (3,0) (2,1) (3,0) Figure 3: A typical longest common subsequence DAG. (And it really is a DAG; we've just left out some edges so it looks like a tree.) 2.3 Exercise Write pseudo-code for a memoized version of the recursive algorithm outlined above. Please note two things: 1. The recursive algorithm outlined above is a recursive mathematical formula. I am asking for pseudo-code. 2. What you need to write to do this problem is not the pseudo-code presented in the book. That's not recursive. 2.4 Exercise Show that the cost of doing all this is (mn)