Lecture Notes for CS 512, Algorithm Design

5 April 2000, Dynamic Programming

1. matrix M₁ with r₁ rows and c₂ columns

2. the product M₃ = M₁M₂

   1. M₃[i, j] = dot(M₁[i, *], M₂[*, j])

3. matrix multiplication is associative, but order is important

   1. ((10, 5) (5, 12)) (12, 7)	(10, 5) ((5, 12) (12, 7))
      600	420
      (10, 12) (12, 7)	(10, 5) (5, 7)
      840	350
      (10, 7)	(10, 7)
      1440	780

4. how to parenthesize expression to minimize multiplications

   1. try exhaustive search

      1. look at every possible sequence

   2. what is the structure of an optimal solution

      1. if the multiplication (M₁...M_i)(M_i+1, M_n) is optimal, what about M₁...M_i and M_i+1, M_n

      2. mults(M_i...M_j) = mults(M_i...M_k) mults(M_i+1...M_j) + c_ir_ic_j

      3. but, we don't know the dividing point k; we have to look for it

      4. a exponential algorithm

   3. how many subproblems are there?

      1. there are only Theta(n₂) subproblems in an exponential algorithm

      2. doing polynomial things in exponential time means there's repitition

5. the dynamic programming method

   1. the two dynamic programming requirements

      1. optimal subproblems

      2. repeated subproblems

   2. dynamic programming - compute the subproblem once, then recall it

   3. memoization - dynamic programming without the optimal subproblem property

This page last modified on 5 April 2000.