The algorithm does consume a lot of memory. When we calculate b(n), the values b(0) to b(n) are stored in main memory. Can this be improved? Yes it can, although the O(1) running time of subsequent calls are obviously lost since the values Since the value of b(n) only depends on b(n-1) and b(n-2) we aren't stored. can discard the other values by going bottom-up. If we want to calculate b(n), we rst calculate b(2) = b(0) + b(1). Then we can calculate b(3) by adding b(1) and b(2). After that, b(0) and b(1) can be discarded, since we don't need them to calculate any more values. From b(2) and b(3) we calculate b(4) and discard b(2), then we calculate b(5) and discard b(3), etc. etc. The code goes something like this: function fib(integer n): integer if n == 0 or n == 1: return n fi let u := 0 let v := 1 for i := 2 to n: let t := u + v u := v v := t repeat return v end This code sample is also available in Adaa a

Implementation 52 Longest Common Subsequence (DP version) We can modify the code to store the values in an array for subsequent calls, but the point is that we don't have to. This method is typical for dynamic programming. First we identify what subproblems need to be solved in order to solve the entire problem, and then we calculate the values bottom-up using an iterative process. 6.2 Longest Common Subsequence (DP version) This will remind us of the backtracking version and then improve it via memoization. Finally, the recursive algorithm will be made iterative and be full-edged DP. [TODO: write this section]

6.3 Matrix Chain Multiplication Suppose that you need to multiply a series of n matrices M1, . . . , Mn together to form a product matrix P : P = M1 M2 Mn1 Mn This will require n 1 multiplications, but what is the fastest way we can form this product? Matrix multiplication is associative, that is, (A B) C = A (B C) for any A, B, C, and so we have some choice in what multiplication we perform rst. (Note that matrix multiplication is not commutative, that is, it does not hold in general that A B = B A.) Because you can only multiply two matrices at a time the product M1 M2 M3 M4 can be paranthesized in these ways: ((M1M2)M3)M4 (M1(M2M3))M4 M1((M2M3)M4) (M1M2)(M3M4) M1(M2(M3M4)) 53

Dynamic Programming Two matrices M1 and M2 can be multiplied if the number of columns in M1 equals the number of rows in M2. The number of rows in their product will equal the number rows in M1 and the number of columns will equal the number of columns in M2. That is, if the dimensions of M1 is a b and M2 has dimensions b c their product will have dimensions a c.