CS341 Study Guide - Longest Common Subsequence Problem, Memoization, Subsequence
Document Summary
Announcement: the midterm is tuesday, october 21 2014, 7 pm - 9 pm, in mc 2065 (190 seats), mc 2066 (192 seats), and mc 2034 (96 seats). We mentioned memoization before; now let"s look at it again in the context of the best order for matrix multiplication. The basic idea is that we simply code up the recursive version recursive-cost, but whenever we ask for. Recursive-cost(i,j), we first look up to see whether we"ve already computed it. If we have, we use it instead of a recursive call. Otherwise, when we compute it, we store it for later use. Here memoization will have the same o(n3) running time as the dynamic programming approach, but in some languages that offer a memoization option (such as. If your language does not have a memoization option, then you will need to code it directly. For example: for j := 1 to n do.
