Memoization and Dynamic Programming

Bart Massey

Motivation For M&DP

• In CS 350 you learned about:

  • Greedy algorithms: Fast, but usually no good
  • Recursive algorithms: General, but often not tractable
  • M&DP, but:
    • you may have forgotten
    • not in much depth

• M&DP are techniques for getting tractable recursive algorithms

  • Applicable to many recursive problems
  • Trade tractable performance for tractable memory use
  • Idea: quit solving the same subproblem over and over

• Plan for today:

  • Review M&DP
  • Look at the book problems
  • Discuss the homework problem

Example: Rod Cutting

• Manufacturing problem: You have a rod of length n and want to cut it into rods of length i to maximize the sum of rod prices: rod price function p(i): N -> N

  • Example:

       (length, price, price density):
           (1, 1, 1.0), (2, 5, 2.5), (3, 8, 2.6{6}), (4, 9, 2.25),
           (5, 10, 2.0), (6, 17, 2.83{3}), (7, 17, 2.{428571}),
           (8, 20, 2.5), (9, 24, 2.6{6}), (10, 30, 3.0)
    

  • Greedy solution, n=4: 3 + 1 = 9

  • Better solution, n=4: 2 + 2 = 10

• How do we find the "better solution" for arbitrary n and p?

Rod Cutting: Subproblems Compose

• Basic idea: try one cut in the rod at various places and solve resulting subproblems; pick the smallest sum

  • Must work: if there is someplace the rod is cut, then hitting it will result in an optimal solution
  • Can solve recursively (top-down)
  • Don't need both recursions: cleaner and easier

  • Can return cuts as well as price

    best-cuts(i):
        if i ≤ 1
            return (∅, p(i))
        v ← p(i)
        c ← ∅
        for j ← 1 .. n - 1
            (c1, v1) ← best-cuts(j)
            (c2, v2) ← best-cuts(i - j)
            v′ ← v1 + v2
            if (v′ < v)
                v ← v′
                c ← (c1 ∪ {j} ∪ adjust(c2, j), v′)
        return (c, v)

Rod Cutting: Memoization

• The recursive solution is correct, but slow. How slow?

  • Makes n recursive calls, where n is the length being cut
  • T[n] = 1 + sum(j=0..n-1, T[j]) = 2^n
  • Explores all unique cutting paths, so binary tree of depth n-1

• Idea: Instead of re-calculating each T[i], remember it

     for i <- 0 .. n
         a[i] <- -1
     cut_price(i):
         if a[i] >= 0
             return a[i]
         if i <= 1
             return p(i)
         v <- p(i)
         for j <- 1 .. min(i - 1, 10)
             v' <- p(j) + cut_price(i - j)
             if (v' < v)
                 v <- v'
         a[i] <- v
         return v
  

Rod Cutting: Bottom-Up

• Can solve iteratively (bottom-up)

   for i <- 1 .. n
       v[i] <- p(i)
       for j <- 1 .. i - 1
           v' <- v[j] + v[i - j]
           if (v' < v[i])
               v[i] <- v'
  

• No recursion cost (NBD?)

• Might be cheaper lookup cost

• Might calculate and store un-needed values

Matrix-Chain Multiplication

• Cost of multiplying MxN by NxP matrix = MNP

• For a chain of matrixes (MxN)(NxP)(PxQ)(QxR) ...

  • Associativity matters: (10x100)(100x5)(5x50) = 7500 vs 75000
  • Greedy is eliminate big indices first, doesn't work

• M&DP is same pattern as before. Try to find a breakpoint:

  opt-cost(m[0..n-1]):
      v <- m[0].r * m[0].c * m[1].r + opt-cost(m[1..n-1])
      for i <- 2 .. n - 1
          v' <- opt-cost(m[1..i]) +
                m[i].r * m[i].c * m[i+1].r +
                opt-cost(m[i+1..n-1])
          if v' < v
              v <- v'
      return v
  

  • Memoize or bottom-up

More Problems

• Longest Common Subsequence

• Minimum Binary Search Tree

• Minimum Edit Distance (exercise)

Homework Problem: Rod Joining

• Dual of Rod Cutting: Want to purchase cheapest collection of rods for a given length n

• Given table is boring, since unit rods are cheapest:

  • Add "join cost" of 2, i.e. cost 2(m - 1) for m-rod solution

• Can solve by dynamic programming, for the same reason as rod cutting

• Interesting corollary: How do rods end up priced given an efficient market?