Exam 4: Dynamic Programming

Algorithmic Paradigms

• Greedy: Make the best local choice at each step

• Divide & Conquer: Split into independent subproblems, solve, then combine

• Dynamic Programming: Solve overlapping subproblems and reuse results (build up solutions)

Divide and Conquer Approach

• Approach: Split into smaller independent subproblems → solve → combine

• Subproblems: Non-overlapping (independent)

• Examples: QuickSort, MergeSort, Binary Search

• Performance: Analyzed with recursion trees + induction

• Memory: No need to store subproblem results (unlike DP)

Dynamic Programming Approach

• Approach: Solve overlapping subproblems (top-down memoization or bottom-up tabulation)

• Subproblems: Overlapping → reuse stored results

• Examples: Fibonacci, Knapsack, Longest Common Subsequence

• Performance: Avoids recomputation → much faster than brute force

• Memory: Uses extra space to store subproblem solutions

Divide and Conquer vs Dynamic Programming Key Differences

• Subproblems:

  • D&C → Non-overlapping

  • DP → Overlapping

• Memory:

  • D&C → No storage of subproblem results

  • DP → Stores results (memoization/tabulation)

• Use Cases:

  • D&C → Sorting, searching, large number multiplication

  • DP → Optimization + counting problems

Weighted Interval Scheduling Basics

• Job j

• Start time sj

• Finish time fj

  • Label jobs by finishing time f1 <= f2 <= … <= fn

• Weight/Value vj

p(j) = the index of the latest non-overlapping job before j

Two jobs are compatible if they DON’T overlap

Goal: Find maximum weight subset of mutually compatible jobs

Why can’t we use greedy algorithm for weighted interval scheduling?

Greedy fails if arbitrary weights are allowed.

• Earliest Finish Time doesn’t work anymore.

WIS Recurrence Equation + Cases

OPT(j) = Optimal value using job requests 1…j

Case 1: OPT selects job j

• Add profit vj

• Can't pick incompatible jobs between p(j)+1 and j-1

• Add OPT(p(j))

Case 2: OPT skips job j

• Take OPT(j-1)

Recurrence:

Key idea: For each job, decide whether to take it or leave it, combining with best compatible previous jobs

Weighted Interval Scheduling Algorithm: Brute Force

Input: n, s1, … sn, f1, …, fn, v1, …, vn

Sort jobs by finish times in ascending order

Compute p(1), p(2), …, p(n)

Compute-OPT(j){

• if j == 0: return

• else:

• return max(vj + OPT(p(j), OPT(j-1))

}

PROBLEM: redundant sub-problems => exponential algorithms

Weighted Interval Scheduling Algorithm: Memoization

Key Idea: store results of each sub-problem in a cache

• Sort jobs by finish times in ascending order

• Compute p(1), p(2), … p(n)

• Create an empty global array

• If M[j] is empty, compute:

  • Either take job j → add its value + best value of compatible previous jobs (M[p(j)])

  • Or skip job j → take best value without it (M[j-1])

WIS: Running Time - Memoization

Claim: Memoized Algorithm takes O(n log n) time

• Sort jobs by finish time → O(n log n)

• Compute compatibility p(j)p(j)p(j) → O(n log n)

• DP (memoized):

  • Each subproblem solved once → O(2 recursive calls *n) total

• Overall: O(n log n)

ALREADY SORTED? O(n)

Weighted Interval Scheduling: Finding a Solution

Recover chosen jobs? Post-Processing

• Start at j = n

• If vj + M[p(j)] > M[j-1]:
  → take job j, go to p(j)

• Else:
  → skip job j, go to j-1

• Repeat until j = 0

• Reconstructs jobs in O(n)

Weighted Interval Scheduling: Bottom Up

Compute DP table iteratively

• Sort jobs by finish time

• Compute p(j) for each job (last compatible job)

• Initialize M[0] = 0

• For j = 1 to n:
  → M[j] = max(vj + M[p(j)], M[j-1])

• Table M[1..n] stores optimal values iteratively

• Reconstruct solution using take vs skip logic

Algorithm for Dynamic Programming Steps

• Define OPT — what the optimal value represents

• Define helper functions — e.g., p(j), compatibility checks

• Write recursive OPT using these definitions

• Decide data structures — arrays/tables to store subproblem results; initialize base cases

• Pseudocode:

  • Base case

  • General case (use recursive formula or table update)

• Optional: Determine if you need to reconstruct the solution from the DP table

Knapsack Problem

• n objects

• knapsack can carry W kilograms

• Item i weighs wi > 0

• Item i has value vi > 0

• Goal: fill snapsack to maximize total value

Greedy: add maximum ratio of vi/wi, BUT NOT OPTIMAL

Dynamic Programming: False Start

• Define OPT(i) = max profit subset of items 1…i

• Case 1: OPT does not select item i → best of {1…i-1}

• Case 2: OPT selects item i → can’t tell which previous items were chosen; may not fit

• Conclusion: Need more subproblems to track additional info (e.g., remaining capacity)

Knapsack Recurrence Equation

• Define OPT(i, w) = max profit using items 1…i with weight limit w

• Case 1: Do not select item i → OPT(i–1, w)

  • Item too heavy

• Case 2: Select item i → MAX(OPT(i–1, w – wi) + vi, OPT(i-1, w)}

  • New weight limit = w - wi

  • OPT selects best

Knapsack Algorithm: Bottom Up

• Input: n items, max weight W, each item has weight and value

• Make a table M[i, w] = best value using first i items and weight ≤ w

• Base case: 0 items → value 0

• For each item:

  • If it’s too heavy, skip it

  • Else, pick the better of skipping or taking it

• M[n, W] gives the maximum value achievable

Knapsack Algorithm: Finding a Solution

Post Processing

• After filling table M, start at i = n, w = W

• Compare M[i, w] to M[i-1, w]:

  • If equal → item i not included, move to M[i-1, w]

  • If M[i, w] = vi + M[i-1, w-wi] → item i included, output it,

  • move to M[i-1, w-wi]

• Repeat until i = 0 or w = 0

• This traces which items are part of the optimal solution

Knapsack Problem: Running Time

• Bottom-up DP table: Θ(n × W)

• Not polynomial in input size (depends on numeric W) → called pseudo-polynomial

• Decision version of Knapsack is NP-complete

• There are polynomial-time approximation algorithms that can give solutions very close to optimal (e.g., within 0.01%)

Least Segmented Squares: Basics, How?, Objectives, Tradeoff function

• n points: (x1, y1), (x2, y2), … (xn, yn)

• Goal: find a line (y = mx+b) that minimizes the sum of the squared error (SSE)

• How?

  • Partition points into segments

  • Fit a line to each segment

• Objective:

  • Minimize E = total squared errors across all segments

  • Minimize L = number of line segments

• Tradeoff Function:

  • E + cL, where constant c > 0

LSS Recurrence Equation

Notation:

• OPT(j) = min cost for points p1 to pj

• e(i, j) = min sum of squares for points pi to pj = error of fitting one line to points p1 to pj

• c: penalty for adding a new line segment

To compute OPT(j):

• Last segment = points pi, …, pj

Cost:

• Cost = e(i, j) + c + OPT(i-1)

Recurrence:

• In image

Segmented Least Squares: Algorithm

Input: n, p1, …, pn, c

Step 1: pre-compute least squares errors (of fitting a single line to points pi, …, pj)

• Equals e(i, j), the cost of a segment from i to j

Step 2: DP array

• minimum total cost for points p1 to pj

• Compute recurrence equation: consider all starting points i for the last segment ending at pj

• For each i, the total cost = error + penalty + optimal cost of prev points

Step 3: Return M[n]

Running time: O(n³)

• O(n²) pairs × O(n) per e(i,j)

• Return: M[n] = minimum total cost

String Similarity - gaps vs mismatches

Mismatch = wrong letter

Gap = missing or extra letter

these values will vary for different alignments

Sequence alignment Goals - Edit Distance Model

Measures the similarity between two strings

Uses two penalties:

• Gap penalty δ

• Mismatch penalty α_pq​

  • p = char from first string

  • q = char from second string

  • penalty for aligned p WITH q

Cost = gap penalty + mismatch penalty

Goal: find alignment with the minimum total cost

Sequence Alignment Basics

Goal: given two strings X = x1 ×2 … xm and Y = y1 y2 … yn, find an alignment of minimum cost

Alignment (M):

• Set of matched pairs xi - yj

• Each character used at most once

• No crossings allowed

Crossing:

• If i < i’ but j > j’

Cost (M) = sum of mismatch penalties + sum of gap penalties in x + sum of gap penalties in y

Sequence Alignment: Recurrence Relation

OPT(i, j)

• i = num of characters of X = x1​,x2​,...,xi​

• j = num of characters of Y = y1​,y2​,...,yj​

• minimum cost to align the first i chars of X with first j chars of Y

Case 1: Match/Mismatch xi with yi

• Cost = α_xi​yj​​ + OPT(i-1, j-1)

Case 2a: Leave xi unmatched, Gap in Y

• Cost = δ + OPT(i−1,j)

Case 2b: Leave yj unmatched, Gap in X

• Cost = δ + OPT(i−1,j)

TAKE MIN OF ALL CASES

Sequence Alignment: Algorithm

• Iterate through all of i

  • M[i, 0] = i*δ

• Iterate through all of j

  • M[0, j] = j *δ

• Recurrence (for i = 1 to m and for j = 1 to n)

  • M [ i, j] = min of {…}

• Return M[m, n]

Sequence Alignment: Algorithm Runtime and Space

θ(mn) time and space

Solution: Hirschberg’s algorithm (1975)

• Time: O(m·n)

• Space: O(m + n)

• Method:

  • Compute OPT(i, •) from OPT(i-1, •) → only store one row at a time

RNA Secondary Structure Basics

RNA: String B = b1, b2, … bn over alphabet {A, C, G, U}

Secondary Structure = set of base pairs formed within the same RNA strand = S = { (bi, bj) }

• Watson-Crick pairing: A-U, U-A, C-G, G-C

• No sharp turns: Paired bases must be separated by ≥ 4 bases → i < j - 4

• Non-crossing: Pairs cannot cross → if (bi, bj) and (bk, bl) in S, then NOT i < k < j < l

  • i < k : second pair starts after first pair starts

  • k < j : second pair starts before before first pair ends

  • j < l : first pair ends before the second pair ends

Free energy: RNA folds to minimze total free energy

Goal: Find S that maximizes the number of base pairs

RNA Secondary Structure: First Attempt and Subproblems

First Attempt:

• OPT(j) = max number of base pairs in substring b1 b2 … bj

• Difficulty: naive approach splits problem into two subproblems:

  1. Left part: b1…bt−1 = OPT(t-1)

  2. Right part: bt+1…bn-1

• Problem: leads to too many subproblems → inefficient

RNA Secondary Structure: Recurrence

OPT(i, j) = max number of base pairs in substring bi bi+1 … bj

Case 1: Too short to pair (no-sharp-turn)

• if i >= j - 4

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

Case 2: Base bj unpaired

• OPT(i, j) = OPT (i, j-1)

Case 3: bj pairs with bt (i ≤ t < j-4)

• starting point i is less than or equal to t (earlier base) and is 4 away from j

• bt and bj must be Watson-Crick complements

• OPT(i, j) = 1 + max over t { OPT(i, t-1) + OPT(t+1, j-1) }

Intuition:

• “Try all valid earlier bases bt to pair with bj”

• “Pick the one that results in the most base pairs overall”

RNA Secondary Structure: Pseudocode + Running Time

Input: b1 to bn

Loop over interval lengths k=5, 6, …n−1

Loop over start positions i=1… n-k

• End position → j = i + k

• Compute M[i, j]

Return M[1, n]

Plain language intuition

• Look at the last base of your current substring:

  1. Leave it alone → best structure = M[i, j-1]

  2. Pair it with an earlier base → add 1 + best possible pairs on left and right

• Pick whichever choice gives more base pairs

Running time → O(n³)

Types of DP

DP Techniques / Patterns:

• Binary choice: weighted interval scheduling

• Multi-way choice: segmented least squares

• Adding a variable: knapsack

• Over intervals: RNA secondary structure

Cookie Needs a Break / Cover Distance formula

OP T (d) = OP T (d − 1) + OP T (d − 2) + OP T (d − 3)