6.

D YNAMIC P ROGRAMMING I

‣ weighted interval scheduling

‣ segmented least squares
‣ knapsack problem
‣ RNA secondary structure

Lecture slides by Kevin Wayne

Copyright © 2005 Pearson-Addison
Wesley
http://www.cs.princeton.edu/~wayne/kleinberg-tardos

Last updated on Mar 4, 2013 6:19 AM

Algorithmic paradigms

Greedy. Build up a solution incrementally, myopically optimizing

some local criterion.

Divide-and-conquer. Break up a problem into independent

subproblems, solve each subproblem, and combine solution to
subproblems to form solution to original problem.

Dynamic programming. Break up a problem into a series of overlapping

subproblems, and build up solutions to larger and larger subproblems.

fancy name for

caching away intermediate results
in a table for later reuse

2
Dynamic programming history

Bellman. Pioneered the systematic study of dynamic programming in 1950s.

Etymology.
・Dynamic programming = planning over time.
・Secretary of Defense was hostile to mathematical research.
・Bellman sought an impressive name to avoid confrontation.

3
Dynamic programming applications

Areas.

・Bioinformatics.
・Control theory.
・Information theory.
・Operations research.
・Computer science: theory, graphics, AI, compilers, systems, ….

・...
Some famous dynamic programming algorithms.

・Unix diff for comparing two files.

・Viterbi for hidden Markov models.
・De Boor for evaluating spline curves.
・Smith-Waterman for genetic sequence alignment.
・Bellman-Ford for shortest path routing in networks.
・Cocke-Kasami-Younger for parsing context-free grammars.
・...
4
 6. D YNAMIC P ROGRAMMING I

‣ weighted interval scheduling

‣ segmented least squares
‣ knapsack problem
‣ RNA secondary structure

SECTION 6.1-6.2
Weighted interval scheduling

Weighted interval scheduling problem.

・Job j starts at s , finishes at f , and has weight or value v .
j j j

・Two jobs compatible if they don't overlap.

・Goal: find maximum weight subset of mutually compatible jobs.

d
e

h
time
0 1 2 3 4 5 6 7 8 9 10 11
6
 Earliest-finish-time first algorithm

Earliest finish-time first.

・Consider jobs in ascending order of finish time.

・Add job to subset if it is compatible with previously chosen jobs.
Recall. Greedy algorithm is correct if all weights are 1.

Observation. Greedy algorithm fails spectacularly for weighted version.

weight = 999 b

weight = 1 a
h
time
0 1 2 3 4 5 6 7 8 9 10 11
7
Weighted interval scheduling

Notation. Label jobs by finishing time: f1 ≤ f2 ≤ . . . ≤ fn .

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

Ex. p(8) = 5, p(7) = 3, p(2) = 0.

time
0 1 2 3 4 5 6 7 8 9 10 11
8
Dynamic programming: binary choice

Notation. OPT(j) = value of optimal solution to the problem consisting of

job requests 1, 2, ..., j.

Case 1. OPT selects job j.

・Collect profit v . j

・Can't use incompatible jobs { p(j) + 1, p(j) + 2, ..., j – 1 }.

・Must include optimal solution to problem consisting of remaining
compatible jobs 1, 2, ..., p(j).
optimal substructure property
(proof via exchange argument)
Case 2. OPT does not select job j.

・compatible
Must include optimal solution to problem consisting of remaining
jobs 1, 2, ..., j – 1.

 0 if j  0
OPT( j) 

max  v j  OPT( p( j)), OPT( j 1)  otherwise

9
Weighted interval scheduling: brute force

Input: n, s[1..n], f[1..n], v[1..n]

Sort jobs by finish time so that f[1] ≤ f[2] ≤ … ≤ f[n]. Compute p[1], p[2],

Compute-Opt(j) if j = 0
return 0. else
return max(v[j] + Compute-Opt(p[j], Compute-Opt(j–1))).

10
Weighted interval scheduling: brute force

Observation. Recursive algorithm fails spectacularly because of redundant

subproblems  exponential algorithms.

Ex. Number of recursive calls for family of "layered" instances grows like
Fibonacci sequence.

1 4 3

2
3 2 2 1
3

4
1 1 1 0 1 0
5

p(1) = 0, p(j) = j-2 1 0

recursion tree

11
Weighted interval scheduling: memoization

Memoization. Cache results of each subproblem; lookup as needed.

Input: n, s[1..n], f[1..n], v[1..n]

Sort jobs by finish time so that f[1] ≤ f[2] ≤ … ≤ f[n]. Compute p[1], p[2], …,

for j = 1 to n M[j] ← empty.

M[0] ← 0.

M-Compute-Opt(j) if M[j] is empty

M[j] ← max(v[j] + M-Compute-Opt(p[j]), M-Compute-Opt(j – 1)).
return M[j].
global

12
Weighted interval scheduling: running time

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

・Sort by finish time: O(n log n).
・Computing p() : O(n log n) via sorting by start time.
・M-COMPUTE-OPT(j): each invocation takes O(1) time and either
- (i) returns an existing value M[j]
- (ii) fills in one new entry M[j] and makes two recursive calls

・Progress measure Φ = # nonempty entries of M[].

- initially Φ = 0, throughout Φ ≤ n.
- (ii) increases Φ by 1  at most 2n recursive calls.

・Overall running time of M-COMPUTE-OPT(n) is O(n). ▪

Remark. O(n) if jobs are presorted by start and finish times.

13
Weighted interval scheduling: finding a solution

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

A. Make a second pass.

Find-Solution(j) if j = 0
return .
else if (v[j] + M[p[j]] > M[j–1]) return { j }  Find-Solution(p[j]).
else
return Find-Solution(j–1).

Analysis. # of recursive calls ≤ n  O(n).

14
Weighted interval scheduling: bottom-up

Bottom-up dynamic programming. Unwind recursion.

BOTTOM-UP (n, s1, …, sn , f1, …, fn , v1, …, vn)

Sort jobs by finish time so that f1 ≤ f2 ≤ … ≤ fn. Compute p(1), p(2), …, p(n).
M [0] ← 0. FOR j = 1 TO n
M [ j ] ← max { vj + M [ p(j) ], M [ j – 1] }.

15
 6. D YNAMIC P ROGRAMMING I

‣ weighted interval scheduling

‣ segmented least squares
‣ knapsack problem
‣ RNA secondary structure

SECTION 6.3
Least squares

Least squares. Foundational problem in statistics.

・Given n points in the plane: (x , y ), (x , y ) , …, (x , y ).
1 1 2 2 n n

・Find a line y = ax + b that minimizes the sum of the squared error:

n
SSE   ( yi  axi  b)2 y
i1

Solution. Calculus  min error is achieved when

n i xi yi  (i xi ) (i yi ) i yi na i xi

a n xi 
i 2  2 ( xi ) ,b
i
17
Segmented least squares

Segmented least squares.

・Points lie roughly on a sequence of several line segments.
・Given n points in the plane: (x , y ), (x , y ) , …, (x , y ) with
1 1 2 2 n n

x1 < x2 < ... < xn, find a sequence of lines that minimizes f (x).

Q. What is a reasonable choice for f (x) to balance accuracy and parsimony?

goodness of fit number of lines

x 18
Segmented least squares

Given n points in the plane: (x1, y1), (x2, y2) , …, (xn, yn) with x1 < x2 < ... < xn and a
constant c > 0, find a sequence of lines that minimizes f (x) = E + c L:
・E = the sum of the sums of the squared errors in each segment.
・L = the number of lines.

x 19
Dynamic programming: multiway choice

Notation.
・OPT(j) = minimum cost for points p , p , …, p .
1 2 j

・e(i, j) = minimum sum of squares for points p , p i i+1, …, pj.

To compute OPT(j):
・Last segment uses points pi, pi+1, …, pj for some i.
・Cost = e(i, j) + c + OPT(i – optimal substructure property
(proof via exchange argument)

1).

OPT  0 if j  0
( j)   min  e(i, j)  c  OPT(i 1)  otherwise
1  i  j
20
Segmented least squares algorithm

SEGMENTED-LEAST-SQUARES (n, p1, …, pn , c) FOR j = 1 TO n

FOR i = 1 TO j
Compute the least squares e(i, j) for the segment pi, pi+1, …, pj.

M [0] ← 0. FOR j = 1 TO n
M [ j ] ← min 1 ≤ i ≤ j { eij + c + M [ i – 1] }.

RETURN M[n].

21
Segmented least squares analysis

Theorem. The dynamic programming algorithm solves the segmented least

squares problem in O(n3) time and O(n2) space.

Pf.
・Bottleneck = computing e(i, j) for O(n2) pairs.
・O(n) per pair using previous formula. ▪

Remark. Can be improved to O(n2) time and O(n) space by precomputing

various statistics. How?

22
 6. D YNAMIC P ROGRAMMING I

‣ weighted interval scheduling

‣ segmented least squares
‣ knapsack problem
‣ RNA secondary structure

SECTION 6.4
Knapsack problem

・Given n objects and a "knapsack."

・Item i weighs w > 0 and has value v > 0.
i i

・Knapsack has capacity of W.

・Goal: fill knapsack so as to maximize total i vi wi

1 1 1
value.
2 6 2

Ex. { 1, 2, 5 } has value 35. 3 18 5

Ex. { 3, 4 } has value 40. 4 22 6

Ex. { 3, 5 } has value 46 (but exceeds weight limit). 5 28 7

knapsack instance
(weight limit W = 11)

Greedy by value. Repeatedly add item with maximum vi.

Greedy by weight. Repeatedly add item with minimum wi.
Greedy by ratio. Repeatedly add item with maximum ratio vi / wi.

Observation. None of greedy algorithms is optimal.

2
Dynamic programming: false start

Def. OPT(i) = max profit subset of items 1, …, i.

Case 1. OPT does not select item i.

・OPT selects best of { 1, 2, …, i –

optimal substructure property
(proof via exchange argument)
1 }.

Case 2. OPT selects item i.

・Selecting item i does not immediately imply that we will have to
reject other items.

・Without knowing what other items were selected before i,

we don't even know if we have enough room for i.

Conclusion. Need more subproblems!

25
Dynamic programming: adding a new variable

Def. OPT(i, w) = max profit subset of items 1, …, i with weight limit w.

Case 1. OPT does not select item i.

・OPT selects best of { 1, 2, …, i – 1 } using weight limit w.

Case 2. OPT selects item i. optimal substructure property

・New weight limit = w – (proof via exchange argument)

wi.

・OPT selects best of { 1, 2, …, i – 1 } using this new weight limit.

 0 if i  0

OPT(i, w)  OPT(i 1, w) if w  w
i

max OPT(i 1, w), vi  OPT(i 1, w  wi )  otherwise
26
Knapsack problem: bottom-up

KNAPSACK (n, W, w1, …, wn, v1, …, vn )

FOR w = 0 TO W
M [0, w] ← 0.

FOR i = 1 TO n
FOR w = 1 TO W
IF (wi > w)M [ i, w ] ← M [ i – 1, w].

ELSE M [ i, w ] ← max { M [ i – 1, w], vi

+ M [ i – 1, w – wi] }.

RETURN M[n, W].

27
 Knapsack algorithm demo

i vi wi

1 1 1  0 if i  0

2 6 2 OPT(i, w)  OPT(i 1, w) if w  w
i

3 18 5 max OPT(i 1, w), vi  OPT(i 1, w  wi )  otherwise
4 22 6
5 28 7

weight limit w

0 1 2 3 4 5 6 7 8 9 10 11

{} 0 0 0 0 0 0 0 0 0 0 0 0

{1} 0 1 1 1 1 1 1 1 1 1 1 1

subset { 1, 2 } 0 1 6 7 7 7 7 7 7 7 7 7
of items
1, …, i { 1, 2, 3 } 0 1 6 7 7 18 19 24 25 25 25 25

{ 1, 2, 3, 4 } 0 1 6 7 7 18 22 24 28 29 29 40

{ 1, 2, 3, 4, 5 } 0 1 6 7 7 18 22 28 29 34 34 40

OPT(i, w) = max profit subset of items 1, …, i with weight limit w.

28
Knapsack problem: running time

Running time. There exists an algorithm to solve the knapsack problem

with n items and maximum weight W in Θ(n W) time.
・Not polynomial in input weights are integers
between 1 and W
size!
・"Pseudo-polynomial."
・Decision version of knapsack problem is NP-complete.[Chapter 8]

Approximation algorithm. [Section 11.8] There exists a poly-time

algorithm that produces a feasible solution that has value within 0.01% of
optimum.
29
 6. D YNAMIC P ROGRAMMING I

‣ weighted interval scheduling

‣ segmented least squares
‣ knapsack problem
‣ RNA secondary structure

SECTION 6.5
RNA secondary structure

RNA. String B = b1b2…bn 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.

C A

A A

A U
G C

C G U A A G

G
U A U U A
G
A C G C U
G

C G C G A G C
G
A U

RNA secondary structure for GUCGAUUGAGCGAAUGUAACAACGUGGCUACGGCGAGA

31
RNA secondary structure

Secondary structure. A set of pairs S = { (bi, bj) } 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 (bi, bj)  S, then i < j – 4.
・ [Non-crossing.] If (bi, bj)and (bk, b ) are two pairs in S, then
we cannot have i < k < j <ℓ.
ℓ

Free energy. Usual hypothesis is that an RNA molecule will form the
secondary structure with the minimum total free energy.

approximate by number of base pairs

Goal. Given an RNA molecule B = b1b2…bn, find a secondary structure S

that maximizes the number of base pairs.

32
RNA secondary structure

Examples.

G
G G G G
G G
C U C U

C G C G C U

A U A U A G
U A U A U A

base pair

A U G U G G C C A A U G G G G C A U A G U U G G C C A U
U

ok sharp turn crossing

(≤4 intervening bases)

33
RNA secondary structure: subproblems

First attempt. OPT(j) = maximum number of base pairs in a secondary

structure of the substring b1b2 … bj.

Choice. Match bt and bn. match bt and bn

1 t n

Difficulty. Results in two subproblems but one of wrong form.

・Find secondary structure in b1b2 … bt– bn–1.

1.

・Find secondary structure in bt+1bt+2 …

 need more subproblems
OPT(t–1)

34
Dynamic programming over intervals

Notation. OPT( i, j ) = maximum number of base pairs in a secondary

structure of the substring bi bi+1 … bj.

Case 1. If i ≥ j – 4.

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

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

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

Case 3. Base bj pairs with bt for some i ≤ t < j – 4.
・Noncrossing constraint decouples resulting subproblems.
・OPT(i, j) = 1 + max { OPT(i, t – 1) + OPT(t + 1, j – 1) }.
t

take max over t such that i ≤ t < j – 4 and

bt and bj are Watson-Crick complements

35
Bottom-up dynamic programming over intervals

Q. In which order to solve the subproblems?

A. Do shortest intervals first.

j
RNA (n, b1, …, bn )
6 7 8 9 10
FOR k = 5 TO n – 1
4 0 0 0
FOR i = 1 TO n – k
3 0 0
i
j ← i + k. 2 0
Compute M[i, j] using formula. 1
RETURN M[1, n].
order in which to solve subproblems

Theorem. The dynamic programming algorithm solves the RNA secondary

substructure problem in O(n3) time and O(n2) space.

36
Dynamic programming summary

Outline.

・Polynomial number of subproblems.

・Solution to original problem can be computed from subproblems.
・Natural ordering of subproblems from smallest to largest, with an easy-
to-compute recurrence that allows one to determine the solution to a
subproblem from the solution to smaller subproblems.

Techniques.

・Binary choice: weighted interval scheduling.

・Multiway choice: segmented least squares.
・Adding a new variable: knapsack.
・Dynamic programming over intervals: RNA secondary structure.

Top-down vs. bottom-up. Different people have different intuitions.

37