Dynamic programming
Shortest paths in dags
• A dag and its linearization
• To compute the distance from S to D, only need to consider distance to
C and to B (because B and C are two predecessors to D).
• dist (D) = min { dist(B) + 1 , dist(C) + 3 }
• If we compute dist values in the left-to-right order, we can make sure
that when we get to a node v, we already have all the information we
need to compute dist(v).
Shortest paths in dags
• The algorithm solves a collection of subproblems, {dist(u) : u ∈ V}.
• Starting with dist(s), then solve “larger” subproblems.
Dynamic programming
• a very powerful algorithmic paradigm
• a problem is solved by identifying a collection of subproblems and
tackling them one by one
– smallest first
– using the answers to small problems to solve larger ones,
– until the original problem is solved.
Longest increasing subsequences
• Input : a sequence of numbers a1, …, an
• A subsequence is any subset of these numbers taken in order, of the
form ai1, ai2 ,…, aik where 1 ≤ i1 < i2 <... < ik ≤ n
• Goal : to find the increasing subsequence of greatest length.
• E.g.) the longest increasing subsequence of 5, 2, 8, 6, 3, 6, 9, 7 :
– 2, 3, 6, 9
• Find the longest path in the dag!
Longest increasing subsequences
• L(j) : the length of the longest path – the longest increasing
subsequence – ending at j
• Algorithm
• Dynamic programming : To solve the original problem, define a
collection of subproblems { L(j) : 1 ≤ j ≤ n } with the key property (*):
– (*) There is an ordering on the subproblems,
and a relation that shows how to solve a subproblem
given the answers to “smaller” subproblems
(subproblems that appear earlier in the ordering).
Longest increasing subsequences
• Each subproblem is solved using the relation :
– L(j) = 1+ max{L(i) : (i, j) ∈ E}
• How long does this step take?
– To compute L(j) : O(in-degree(j)).
– Total : O(|E|) → O(n2).
• L values only tells us the length of the optimal subsequence. How to
construct the subsequence?
– While computing L(j), record prev(j), the previous node on the
longest path to j.
Recursive vs. dynamic programming
• The formula for L(j) suggests an alternative, recursive algorithm.
• Suppose that the numbers are sorted. Then, L(j) = 1 + max { L(1), L(2),
…, L(j-1)}.
• The following figure unravels the recursion for L(5) :
• The tree for L(n) has exponential size. Many repeated nodes!
• Only small number of distinct subproblems -> DP solve them in the
right order.
Edit distance
• Given two strings, how can we measure how close they are?
• Ex) SNOWY, SUNNY : possible alignments
• - : gap (we may place any number of gaps in either string)
• Cost : the number of columns in which the letters differ
• Edit distance of two strings : the cost of their best possible alignment
= minimum number of edits – insertions, deletions, and substitutions
of characters – needed to transform the first string into the second
Dynamic programming
• What are the subproblems?
• (*) There is an ordering on the subproblems, and a relation that shows
how to solve a subproblem given the answers to “smaller”
subproblems (subproblems that appear earlier in the ordering).
• Input : x[1..m], y[1..n]
• Consider prefixes : x[1..i], y[1..j] -> call this subproblem E(i, j)
• Subproblem E(7, 5)
• Goal : E(m, n)
• Express E(i, j) in terms of smaller subproblems!
• The rightmost column of the best alignment can be one of the
following :
• E(i, j) = min {1 + E(i-1, j), 1+ E(i, j-1), diff(i, j) + E(i-1, j-1) }
where diff(i, j) = 0 if x[i] = y[j] and 1 otherwise.
• Base cases : i=0 or j=0
• The answers to all the subproblems E(i, j) form a two-dimensional
table.
Underlying dag
Common subproblems
• Finding the right subproblem takes creativity and experimentation.
• Standard choices
Common subproblems
Knapsack
• Given a knapsack of capacity W, n items of weight w1,…, wn and value
v1 ,…, vn , choose the most valuable combination of items.
• E.g.) W=10
• Two versions :
– 1) allow unlimited quantities :
pick item 1 and two of item 4 (total $48)
– 2) allow only 1 of each item :
pick items 1 and 3 (total $46).
Knapsack with repetitions
• What are the subproblems?
• Define K(w) = maximum value achievable with a knapsack of capacity
w.
• If the optimal solution to K(w) includes item i, then removing it leaves
an optimal solution to K(w-wi).
• We don’t know which i, so try all possibilities.
• Algorithm
Analysis
• This algorithm fills in a one-dimensional table of length W+1, in left-
to-right order.
• Each entry can take up to O(n) time to compute.
• The overall running time = O(nW).
Knapsack without repetition
• Need to refine the subproblem to carry additional information about
the items being used by adding a second parameter, 0 ≤ j ≤ n.
• K(w, j) = maximum value achievable using a knapsack of capacity w
and items 1,…, j.
• Goal : K(W, n).
• Express K(w, j) in terms of smaller subproblems considering whether
item j is needed or not.
• K(w, j) = max { K(w-wj, j-1) + vj , K(w, j-1) }
• (The first case is invoked only if wj ≤ w)
Analysis
• The algorithm fills out a 2-dimensional table, with W+1 rows and n+1
columns.
• Each table entry takes constant time.
• Running time : O(nW).
Memoization
• In dynamic programming, we use a recursive formula to fill out a table
of solution values in a bottom-up manner, from smallest subproblem to
largest.
• The formula also suggests a recursive algorithm, but naive recursion
can be terribly inefficient, because it solves the same subproblems over
and over again.
• Memoization - record the results of previous invocations to avoid
repetitions!