Weighted Interval Scheduling Problem

Consider n subjects are sharing a single resources.

• job j: start at s_j and finish at f_j
  • has weight/value w_j > 0
• two jobs are compatible if they do not overlap

Earliest-finish-time-first algorithm

Earliest-finish-time-first.

• Consider jobs in ascending order of finish time f_j.
• Add job to subset if it is compatible with previously chosen jobs.

Recall. Greedy algorithm is correct if all weights are 1.

EFTF extension

Convention. Jobs are in ascending order of finish time: f_1 \le f_2 \le . . . \le f_n.

Def. p(j) = largest index i < j such that job i is compatible with j.

• i is rightmost interval that ends before j begins

Dynamic programming: binary choice

Def. OPT(j) = max weight of any subset of mutually compatible jobs (for subproblem consisting only of jobs 1, 2, ..., j).

Goal. OPT(n) = max weight of any subset of mutually compatible jobs.

DP: binary choice (cont.)

Def. OPT(j) = max weight of any subset of mutually compatible jobs (for subproblem consisting only of jobs 1, 2, ..., j).

Goal. OPT(n) = max weight of any subset of mutually compatible jobs.

Case 1. OPT(j) does not select job j.

Case 2. OPT(j) selects job j.

Bellman equation.

OPT(n) = \left\{ \begin{array}{lcl} 0 & \text{if} & j = 0 \\ \max \{OPT(j-1), w_j + OPT(p(j))\} & \text{if} & j > 0 \\ \end{array}\right.

Brute-force scheduling

BRUTE-FORCE(n, s_1, \ldots, s_n, f_1, \ldots, f_n, w_1, \ldots, w_n)

1. SORT jobs by finish times and renumber so that f_1 \le f_2 \le \ldots \le f_n;
2. Compute p[1], p[2], \ldots, p[n] via binary search;
3. RETURN COMPUTE-OPT(n);

COMPUTE-OPT(j)

1. IF (j = 0): RETURN 0;
2. ELSE:
   1. RETURN \max { COMPUTE-OPT(j – 1), w_j + COMPUTE-OPT(p[j]) };

Quiz: brute-force scheduling

What is running time of COMPUTE-OPT(n) in the worst case?

A. \Theta(n \log n)
B. \Theta(n^2)
C. \Theta(1.618^n)
D. \Theta(2^n)

COMPUTE-OPT(j)

1. IF (j = 0): RETURN 0;
2. ELSE:
   1. RETURN \max { COMPUTE-OPT(j – 1), w_j + COMPUTE-OPT(p[j]) };

Discussed next.

Brute-force scheduling: analysis

Observation. Recursive algorithm is spectacularly slow because of overlapping sub-problems \Rightarrow exponential-time algorithm.

Ex. # recursive calls for family of “layered” instances grows like Fibonacci sequence.

Memoized scheduling

Top-down dynamic programming (memoization).

• Cache result of subproblem j in M[j].
• Use M[j] to avoid solving subproblem j more than once.

Memoized scheduling: analysis

Claim. Memoized version of algorithm takes O(n \log n) time.
Pf.

• Sort by finish time: O(n \log n).

• Compute p[j] for each j: O(n \log n) via binary search.

• M-COMPUTE-OPT(j): each invocation takes O(1) time and either

  • 1. returns an initialized value M[j]
  • 2. initializes M[j] and makes two recursive calls

Memoized scheduling: find a solution

Q. DP algorithm computes optimal value. How to find optimal solution?

Bottom-up DP

Bottom-up dynamic programming. Unwind recursion.

Bottom-up DP: algorithm

BOTTOM-UP(n, s_1, \ldots, s_n, f_1, \ldots, f_n, w_1, \ldots, w_n)

1. SORT jobs by finish times and renumber so that f_1 \le f_2 \le \ldots \le f_n;
2. Compute p[1], p[2], \ldots, p[n] via binary search;
3. M[0] = 0;
4. FOR j = 1 .. n:
   1. M[j] = \max \{ M[j – 1], w_j + M[p[j]] \};

Maximum Sub-array Problem

Goal. Given an array x of n integer (positive or negative), find a contiguous sub-array whose sum is maximum.

Ex.

Applications. Computer vision, data mining, genomic sequence analysis, technical job interviews, etc.

Maximum Sub-array: brute-force

Goal. Given an array x of n integer (positive or negative), find a contiguous sub-array whose sum is maximum.

Ex.

Brute-force algorithm.

• For each i and j : computer a[i] + a[i+1] + \ldots + a[j].
• Takes \Theta(n^3) time.

Kadane’s algorithm

Def. OPT(i) = max sum of any sub-array of x whose rightmost index is i.

Goal. \max_i OPT(i)

Maximum Rectangle Problem

Goal. Given an n-by-n matrix A, find a rectangle whose sum is maximum.

Applications. Databases, image processing, maximum likelihood estimation, technical job interviews, etc.

Bentley’s algorithm

Assumption. Suppose you knew the left and right column indices j and jʹ.

Bentley’s algorithm (cont.)

An O(n^3) algorithm.

1. Pre-compute cumulative row sums: \sum_{k=1}^j A_{ik};
2. For each j < jʹ:
   1. define array x using row-sum differences: x_i = S_{ij'} - S_{ij};
   2. run Kadane’s algorithm in array x;

Open problem. O(n^{3−\epsilon}) for any constant \epsilon > 0.

Least squares

Least squares. Foundational problem in statistics.

• Given n points in the plane: (x_1, y_1), (x_2, y_2) , \ldots, (x_n, y_n).
• Find a line y = ax + b that minimizes the sum of the squared error:

Segmented Least Squares Problem

Segmented least squares.

Dynamic programming: multi-way choice

Notation.

• OPT(j) = minimum cost for points p_1, p_2, \ldots, p_j.
• e_{ij} = SSE for for points p_i, p_{i+1}, \ldots, p_j.

Segmented Least Squares: algorithm

SEGMENTED-LEAST-SQUARES(n, p_1, \ldots, p_n, c)

1. FOR j = 1 .. n:
   1. FOR i = 1 .. j:
      1. Compute the SSE e_{ij} for the points p_i, p_{i+1}, \ldots, p_j;
2. M[0] = 0;
3. FOR j = 1 .. n:
   1. M[j] = \min_{1 \le i \le j} \{e_{ij} + c + M[i-1]\};
4. RETURN M[n];

Segmented Least Squares: analysis

Theorem. [Bellman 1961] DP algorithm solves the segmented least squares problem in O(n^3) time and O(n^2) space.
Pf.

• Bottleneck = computing SSE e_{ij} for each i and j.

a_{ij} = \frac{ n \sum_k x_k y_k - (\sum_k x_k)(\sum_k y_k) }{ n \sum_k x_k^2 - (\sum_k x_k)^2 }, b_{ij} = \frac{ \sum_k y_k - a_{ij} \sum_k x_k }{n}

• O(n) to compute e_{ij}.

Remark. Can be improved to O(n^2) time.

• For each i: pre-compute cumulative sums: \sum_k x_k, \sum_k y_k, \sum_k x_k^2, \sum_k x_k y_k
• Using cumulative sums, can compute e_{ij} in O(1) time.

Knapsack problem

Goal. Pack knapsack so as to maximize total value of items taken.

• There are n items: item i provides value v_i > 0 and weighs w_i > 0.
• Value of a subset of items = sum of values of individual items.
• Knapsack has weight limit of W.

Assumption. All values and weights are integral.

Quiz: Knapsack via greedy

Which algorithm solves knapsack problem?

A. Greedy-by-value: repeatedly add item with maximum v_i.
B. Greedy-by-weight: repeatedly add item with minimum w_i.
C. Greedy-by-ratio: repeatedly add item with maximum ratio v_i / v_i.
D. None of the above.

weight limit W = 11

Quiz: Knapsack via DP

Which sub-problems?

A. OPT(w) = optimal value of knapsack problem with weight limit w.
B. OPT(i) = optimal value of knapsack problem with items 1, \ldots, i.
C. OPT(i, w) = optimal value of knapsack problem with items 1, \ldots, i subject to weight limit W.
D. Any of the above.

Dynamic programming: two variables

Def. OPT(i, w) = optimal value of knapsack problem with items 1, \ldots, i, subject to weight limit w.

Goal. OPT(n, W).

DP: two variables (cont.)

Def. OPT(i, w) = optimal value of knapsack problem with items 1, \ldots, i, subject to weight limit w.

Goal. OPT(n, W).

Case 1. OPT(i, w) does not select item i.

Case 2. OPT(i, w) selects item i.

Bellman equation.

OPT(i, w) = \left\{ \begin{array}{ll} 0 & \text{if}\ i = 0 \\ OPT(i-1, w) & \text{if}\ w_i > w \\ \max \{ OPT(i-1, w), v_i + OPT(i-1, w-w_i) \} & \text{otherwise} \\ \end{array}\right.

DP: two-dimensional table

OPT(i, w) = \left\{ \begin{array}{ll} 0 & \text{if}\ i = 0 \\ OPT(i-1, w) & \text{if}\ w_i > w \\ \max \{ OPT(i-1, w), v_i + OPT(i-1, w-w_i) \} & \text{otherwise} \\ \end{array}\right.

Knapsack problem: bottom-up DP

KNAPSACK(n, W, w_1, \ldots, w_n, v_1, \ldots, v_n)

1. FOR w = 0 .. W: M[0, w] = 0;
2. FOR i = 1 .. n:
   1. FOR w = 0 .. W:
      1. IF (w_i > w): M[i, w] = M[i – 1, w];
      2. ELSE: M[i, w] = \max \{ M[i – 1, w], v_i + M[i – 1, w – w_i] \};
3. RETURN M[n, W];

OPT(i, w) = \left\{ \begin{array}{ll} 0 & \text{if}\ i = 0 \\ OPT(i-1, w) & \text{if}\ w_i > w \\ \max \{ OPT(i-1, w), v_i + OPT(i-1, w-w_i) \} & \text{otherwise} \\ \end{array}\right.

Knapsack problem: bottom-up DP demo

Knapsack size W = 6, items w_1 = 2, w_2 = 2, w_3 = 3.

OPT(i, w) = \left\{ \begin{array}{ll} 0 & \text{if}\ i = 0 \\ OPT(i-1, w) & \text{if}\ w_i > w \\ \max \{ OPT(i-1, w), v_i + OPT(i-1, w-w_i) \} & \text{otherwise} \\ \end{array}\right.

Knapsack problem: analysis

Theorem. The DP algorithm solves the knapsack problem with n items and maximum weight W in \Theta(n W) time and \Theta(n W) space.
Pf.

• Takes O(1) time per table entry.
• There are \Theta(n W) table entries.
• After computing optimal values, can trace back to find solution:
  • OPT(i, w) takes item i iff M [i, w] > M [i – 1, w].

Remarks.

• Algorithm depends critically on assumption that weights are integral.
  • weights are integers between 1 and W

Coin changing: revisit

Problem. Given n coin denominations \{ d_1, d_2, \ldots, d_n \} and a target value V, find the fewest coins needed to make change for V (or report impossible).

Recall. Greedy cashier’s algorithm is optimal for U.S. coin denominations, but not for arbitrary coin denominations.

Ex. { 1, 10, 21, 34, 70, 100, 350, 1295, 1500 }.
Optimal. 140¢ = 70 + 70.

Coin changing: DP solution

Def. OPT(v) = min number of coins to make change for v.

Goal. OPT(V).

Multiway choice. To compute OPT(v),

• Select a coin of denomination c_i for some i.
• Select fewest coins to make change for v – c_i.

Bellman equation.

OPT(v) = \left\{ \begin{array}{ll} \infty & \text{if}\ v < 0 \\ 0 & \text{if}\ v = 0 \\ \min_{1 \le i \le n} \{ 1 + OPT(v-d_i) \} & \text{if}\ v > 0 \\ \end{array}\right.

Running time. O(n V).

RNA secondary structure

RNA. String B = b_1 b_2 \ldots b_n over alphabet { A, C, G, U }.

Secondary structure. RNA is single-stranded so it tends to loop back and form base pairs with itself. This structure is essential for understanding behavior of molecule.

RNA: matching rule

Secondary structure. A set of pairs S = \{ (b_i, b_j) \} that satisfy:

• [Watson–Crick] S is a matching and each pair in S is a Watson–Crick complement: A–U, U–A, C–G, or G–C.

• [No sharp turns] The ends of each pair are separated by at least 4 intervening bases. If (b_i, b_j) \in S, then i < j – 4.

• [Non-crossing] If (b_i, bj) and (b_k, bl) are two pairs in S, then we cannot have i < k < j < l.

RNA: hypothesis

Secondary structure. A set of pairs S = \{ (b_i, b_j) \} that satisfy:

• [Watson–Crick] S is a matching and each pair in S is a Watson–Crick complement: A–U, U–A, C–G, or G–C.
• [No sharp turns] The ends of each pair are separated by at least 4 intervening bases. If (b_i, b_j) \in S, then i < j – 4.
• [Non-crossing] If (b_i, bj) and (b_k, bl) are two pairs in S, then we cannot have i < k < j < l.

Free-energy hypothesis. RNA molecule will form secondary structure with minimum total free energy.

• approximate by # base pairs: more base pairs \Rightarrow lower free energy

Goal. Given an RNA molecule B = b_1 b_2 \ldots b_n, find a secondary structure S that maximizes number of base pairs.

Quiz: matching rule

Is the following a secondary structure?

A. Yes.
B. No, violates Watson–Crick condition.
C. No, violates no-sharp-turns condition.
D. No, violates no-crossing condition.

Quiz: RNA secondary structure

Which sub-problems?

A. OPT(j) = max number of base pairs in secondary structure of the substring b_1 b_2 \ldots b_j.
B. OPT(j) = max number of base pairs in secondary structure of the substring b_j b_{j+1} \ldots b_n.
C. Either A or B.
D. Neither A nor B.

RNA secondary structure: sub-problems

First attempt. OPT(j) = max number of base pairs in secondary structure of the substring b_1 b_2 \ldots b_j.

Goal. OPT(n).

Choice. Match bases b_t and b_j.

DP: intervals

Def. OPT(i, j) = maximum number of base pairs in a secondary structure of the substring b_i b_{i+1} \ldots b_j.

Case 1. If i \ge j – 4.

• OPT(i, j) = 0 by no-sharp-turns condition.

Case 2. Base b_j is not involved in a pair.

• OPT(i, j) = OPT(i, j – 1).

Case 3. Base b_j pairs with b_t for some i \le t < j – 4.

• Non-crossing condition decouples resulting two sub-problems.
  • OPT(i, j) = 1 + \max_t { OPT(i, t – 1) + OPT(t + 1, j – 1) }.

Quiz: DP for RNA

In which order to compute OPT(i, j)?

A. Increasing i, then j.
B. Increasing j, then i.
C. Either A or B.
D. Neither A nor B.

Bottom-up DP over intervals

Q. In which order to solve the sub-problems?
A. Do shortest intervals first—increasing order of |j − i|.

Ex. RNA sequence ACCGGUAGU.

DP for RNA: algorithm

RNA-SECONDARY-STRUCTURE(n, b_1, \ldots, b_n)

1. FOR k = 5 .. n – 1:
   1. FOR i = 1 .. n – k:
      1. j = i + k;
      2. Compute M[i, j] using formula;
2. RETURN M[1, n];

Theorem. The DP algorithm solves the RNA secondary structure problem in O(n^3) time and O(n^2) space.

Dynamic programming summary

Outline.

• Define a collection of (polynomial number of) sub-problems.
• Solution to original problem can be computed from sub-problems.
• Natural ordering of sub-problems from “smallest” to “largest” that enables determining a solution to a subproblem from solutions to smaller sub-problems.

Techniques.

• Binary choice: weighted interval scheduling.
• Multi-way choice: segmented least squares.
• Adding a new variable: knapsack problem.
• Intervals: RNA secondary structure.

Top-down vs. bottom-up DP. recursive vs. iterative.