Chapter 6

• In general, most problems do not have a natural greedy algorithm solution that works
• Divide and conquer is often not strong enough to reduce exponential brute-force search down to polynomial time
• Dynamic Programming: one implicitly explores the space of all possible solutions, by decomposing things into a series of subproblems, and then building up correct solutions to larger and larger subproblems

• Each interval has a certain value (or weight), and we want to accept a set of maximum value.

Designing a Recursive Algorithm

• n requests (1,…,n)
• each request i specifies a start time si and finish time fi.
• each request i also has a value or weight (vi)
• compatible intervals: do not overlap
• goal: select a subset of mutually compatible intervals so as to maximize the sum of the values of the selected intervals
• sort requests in order of nondecreasing finish time
• define p(j), for an interval j, to be the largest index i<j such that intervals i and j are disjoint
  • leftmost interval that ends before j begins
• p(j) = 0, if no request i<j is disjoint from j
• Optimal solution O: either interval n belongs to O or it doesn't
  • if it is, no intervals indexed between p(n) and n can belong to O
  • if it is not, O is equal to the optimal solution of request s {1,n-1}
• For any value of j between 1 and n, let Oj denote the optimal solution to the problem consisting of requests {1,…,j} and let OPT(j) denote the value of this solution
• OPT(j) = max(vj + OPT(p(j)), OPT(j-1))
  • request j belongs to an optimal solution on the set {1,2,..,j} if and only if vj + OPT(p(j)) >= OPT)j-1)

• Compute-Opt Subproblems grow very quickly

• we have not achieved a polynomial-time solution

Memoizing the Recursion

• Previous algorithm runs in exponential time because of the redundancy of how many times it issues a compute-opt() call
• Memoization: saving values that have already been computed in a globally-accessible place
  • Have an array M[0…n], where M[j} will start with the value “empty” and then will store the value of Compute-Opt(j) as soon as it is first determined.