CS240 Algorithm Design and Analysis
Lecture 5
Dynamic Programming
Quan Li
Fall 2025
2025.09.25
Algorithmic Paradigms
• Greed. Build up a solution incrementally, myopically optimizing some local criterion
• Divide-and-conquer. Break up a problem into a few sub-problems, solve each sub-problem
independently and recursively, and combine solution to sub-problems to form solution to original
problem
• Dynamic programming. Break up a problem into a series of overlapping sub-problems, and build up
solutions to larger and larger sub-problems
Divide-and-conquer VS. Dynamic Programming
Weighted Interval Scheduling
• Weighted interval scheduling problem
• Job j starts at sj, finishes at fj, and has weight or value vj
• Two jobs compatible if they don’t overlap
• Goal: find maximum weight subset of mutually compatible jobs
Unweighted Interval Scheduling Review
• Recall. Greedy algorithm works if all weights are 1
• Consider jobs in ascending order of finish time
• Add jobs to subset if it is compatible with previously chosen jobs
• Observation. Greedy algorithm can fail spectacularly if arbitrary weights are allowed
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
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
• Cannot 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)
• Case 2: OPT does not select job j
Optimal
• Must include optimal solution to problem consisting substructure
of remaining compatible jobs 1, 2, …, j-1
Weighted Interval Scheduling: Brute Force
• Brute force algorithm
Weighted Interval Scheduling: Brute Force
• Observation. Recursive algorithm fails spectacularly because of redundant sub-problems → exponential
algorithms
• Ex. Number of recursive calls for family of “layered” instances grows like Fibonacci sequence
Weighted Interval Scheduling: Memoization
• Memoization. Store results of each sub-problem in cache; lookup as needed
Weighted Interval Scheduling: Running Time
• Claim. Memorized version of algorithm takes O(nlogn) time
• Sort by finish time: O(nlogn)
• Computing p(⋅): O(n) after sorting by start time how?
• M-Compute-Opt(j): O(n)
• Each entry M[j] is computed only once
• The computation of M[j] invokes M-Compute-Opt twice
• Remark. O(n) if jobs are pre-sorted by start and finish times
Weighted Interval Scheduling: Finding a Solution
• Q. Dynamic programming algorithms computes optimal value. What if we want the solution itself?
• A. Do some post-processing
# of recursive calls <= n → O(n)
Weighted Interval Scheduling: Bottom-Up
• Bottom-up dynamic programming. Unwind recursion
• Top-down vs. bottom-up
• Top-down: May skip unnecessary sub-problems
• Bottom-up: Save the overhead in recursion
Knapsack Problem
Knapsack Problem
• Knapsack problem
• Given n objects and a “knapsack”
• Item i weighs wi > 0 kilograms and has value vi > 0
• Knapsack has capacity of W kilograms
• Goal: fill knapsack so as to maximize total value
Knapsack Problem
• Knapsack problem
• Given n objects and a “knapsack”
• Item i weighs wi > 0 kilograms and has value vi > 0
• Knapsack has capacity of W kilograms
• Goal: fill knapsack so as to maximize total value
• Ex: { 3, 4 } has value 40
• Greedy:
• Repeatedly add item with maximum value vi
• Repeatedly add item with maximum weight wi
• Repeatedly add item with maximum ration vi/wi
Greedy not optimal!
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-1 }
• Case 2: OPT selects item i
• How shall we enforce the weight limit?
• Conclusion. Shall specify the remaining weight capacity in OPT
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
• New weight limit = w – wi
• OPT selects best of { 1, 2, …, i-1 } using this new weight limit
Knapsack Problem: Bottom-Up
• Knapsack. Fill up an n-by-W array
Knapsack Algorithm
Knapsack Algorithm
Knapsack Algorithm
Knapsack Algorithm: Top-down
Knapsack Problem: Running Time
• Running time. Θ(nW)
• Not polynomial in input size!
• “Pseudo-polynomial.”
• Decision version of Knapsack is NP-complete
• Knapsack approximation algorithm. There exists a polynomial algorithm that produces a feasible
solution that has value within 0.01% of optimum.
RNA Secondary Structure
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.
RNA Secondary Structure
• Secondary structure. A set of pairs S = { (bi, bj)} that satisfy:
• [Watson-Crick]. S is 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, bl) are two pairs in S, then we cannot have i < k < j < l
RNA Secondary Structure: Examples
• Examples
RNA Secondary Structure
• Free energy. Usual hypothesis is that an RNA molecule will form the secondary structure with the
optimum 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
RNA Secondary Structure: Subproblems
• First attempt. OPT(j) = maximum number of base pairs in a secondary structure of the substring b1b2…bj
• Difficulty. Results in two sub-problems
• Finding secondary structure in: b1b2…bt-1
• Finding secondary structure in: bt+1bt+2…bj-1 OPT(t – 1)
Need more sub-problems
Dynamic Programming Over Intervals
• Notation. OPT(i, j) = maximum number of base pairs in a secondary structure of the substring bibi+1…bj
• If i >= j – 4
• OPT(i, j) = 0 by no-sharp turns condition
• If i < j – 4: take max of two cases
• Case 1. Base bj is not involved in a pair
• OPT(i, j – 1)
• Case 2. Base bj pairs with bt for some i <= t < j – 4
Non-crossing constraint decouples resulting sub-problems
1 + maxt { OPT(i, t-1) + OPT(t+1, j-1)}
Bottom Up Dynamic Programming Over Intervals
• Q. What order to solve the sub-problems?
• A. Do shortest intervals first
• Running time. O(n3)
Sequence Alignment
String Similarity
• How similar are two strings?
• ocurrance
• occurrence
Edit Distance
• Edit distance. [Levenshtein 1966, Needleman-Wunsch 1970]
• Gap penalty 𝛅; mismatch penalty 𝛂pq
• Cost = sum of gap and mismatch penalties
• Edit distance = min cost
• Applications
• Basis for Unix diff
• Speech recognition
• Computational biology
Sequence Alignment
• Goal. Given two strings X = x1x2…xm and Y = y1y2…yn find alignment of minimum cost
• Def. An alignment M is a set of ordered pairs xi – yj such that each item occurs in at most one pair and
no crossings
• The pair xi - yj and xi’ – yj’ cross if i < i’, but j > j’
• Def. The cost of an alignment
• Ex: An alignment of CTACCG vs. TACATG
M = x2 – y1, x3 – y2, x4 – y3, x5 – y4, x6 – y6
Sequence Alignment: Problem Structure
• Def. OPT(i, j) = min cost of aligning strings x1x2…xi and y1y2…yj
• Case 1: OPT matches xi – yj
• pay mismatch for xi – yj + min cost of aligning two strings x1x2…xi-1 and y1y2…yj-1
• Case 2a: OPT leaves xi unmatched
• pay gap for xi and min cost of aligning x1x2…xi-1 and y1y2…yj
• Case 2b: OPT leaves yj unmatched
• pay gap for yj and min cost of aligning x1x2…xi and y1y2…yj-1
Sequence Alignment: Algorithm
Analysis: Θ(mn) time and space
Sequence Alignment: Example
Sequence Alignment: Example
Sequence Alignment: Algorithm
• Analysis: Θ(mn) time and space
• English words or sentences:
• m, n <= 30. OK
• Computational biology
• m = n = 100,000
• 10 billions ops is OK, but 10GB array is quite large
Sequence Alignment: Linear Space
• Q. Can we avoid using quadratic space?
• Easy. Optimal cost in O(m + n) space and O(mn) time
• Compute OPT(i, ⋅) from OPT(i-1, ⋅)
• No longer a simple way to recover alignment itself
• Theorem. [Hirschberg 1975] Optimal alignment in O(m + n) space and O(mn) time
• Clever combination of divide-and-conquer and dynamic programming
Sequence Alignment in Linear Space
Sequence Alignment: Linear Space
• Edit distance graph
• Let f(i, j) be shortest path from (0, 0) to (i, j)
• Observation: f(i, j) = OPT(i, j)
Sequence Alignment: Linear Space
• Edit distance graph
• Let f(i, j) be shortest path from (0, 0) to (i, j)
• Can compute f(⋅, j) for any j in O(mn) time and O(m + n) space
Sequence Alignment: Linear Space
• Edit distance graph
• Let g(i, j) be shortest path from (i, j) to (m, n)
• Can compute g(⋅, j) by reversing the edge orientations and inverting the roles of (0, 0) and (m, n)
Sequence Alignment: Linear Space
• Edit distance graph
• Let g(i, j) be shortest path from (i, j) to (m, n)
• Can compute g(⋅, j) for any j in O(mn) time and O(m + n) space
Sequence Alignment: Linear Space
• Observation 1. The cost of the shortest path that uses (i, j) is f(i, j) + g(i, j)
Sequence Alignment: Linear Space
• Observation 2. Let q be an index that minimized f(q, n/2) + g(q, n/2)
• Then, the shortest path from (0, 0) to (m, n) uses (q, n/2)
Sequence Alignment: Linear Space
• Divide: find index q that minimizes f(q, n/2) + g(q, n/2) using DP
• Do alignment at (xq, yn/2)
• Conquer: recursively compute optimal alignment in each piece
Sequence Alignment: Running Time Analysis
• Theorem. Let T(m, n) = max running time of algorithm on strings
of length m and n. T(m, n) = O(mn)
• Pf. (by induction on n)
• O(mn) time to compute f(⋅, n/2) and g(⋅, n/2) and find index
q
• T(q, n/2) + T(m – q, n/2) time for two recursive calls
• Choose constant c so that:
• Claim: T(m, n) <= 2cmn
• Base cases: m = 2 or n = 2
• Inductive hypothesis: T(m’, n’) <= 2cm’n’ with m’<m and
n’<n
Next Time:
Dynamic Programming (Cont.)