Dynamic Programming

Created Apr 10, 2023

Recap:

Greed: process the input in some order, myopically making irrevocable decisions.
Divide-and-conquer: break up probelms into independent subproblems; solve them; and combine individual solutions to form solution to original problem
Dyanmic programming (caching intermediate results in a table for later reuse): break up a problem into a series of overlapping subproblems; combine solutions to smaller subproblems to form solutions to a large subproblem

Bellman pioneered the systematic study of DP in 1950s. Etymology

Dynamic programming = programming over time
Named this to avoid fear of mathematical research

Weighted Interval Scheduling

Recall the interval scheduling problem. We modify it so that jobs have weights.

A job $j$ starts at $s_j$ , finishes at $f_j$ , and has weight $w_j>0$ .
Two jobs are compatible if they don't overlap.
Goal: find the max-weight subset of mutually compatible jobs.

The greedy algorithm is correct if all weights are 1, but fails spectaculary for the weighted version.

Recall: it considers jobs in ascending order of finish time, and adds the job to the subset if its compatible with the previously chosen jobs.

Dynamic programming: binary choice

Definition: $OPT(j)$ = max weight of any subset of mutually compatible jobs for subproblem consisting only of jobs $1,2, \dots, j$ . Goal: $OPT(n)$ = max weight of any subset of mutually compatible jobs Case 1: $OPT(j)$ does not select job $j$ .

There must be an optimal solution to problem consisting of remaining jobs $1,2,\dots,j-1$ . Case 2: $OPT(j)$ selects job $j$ .
Collect profit $w_j$
Can't use incompatible jobs $\{p(j)+1, p(j)+2, \dots, j-1\}$
Must include optimal solution to problem consisting of remaining
compatible jobs $1,2,\dots, p(j)$ .

Bellman equation:

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

Brute force:

Brute-force( $n,s_1,\dots,s_n,f_1,\dots,f_n, w_1,\dots,w_n$ ):

sort jobs by finish time so that $f_1 \leq f_2 \leq \dots \leq f_n$
Compute $p[1],p[2], \dots, p[n]$ via binary search
Return Compute-Opt(n)

Compute-Opt(j):

If (j=0)
- Return 0
Else
- Return max $\{Compute-Opt(j-1), w_j + Compute-Opt(p[j])\}$

Observation: recurisve algorithm is slow because of the overlapping subproblems $\Rightarrow$ exponential-time algorithm.

E.g., the numbe of recursive calls for family of "layered" instances grows like the fibonacci sequence.

Memoization

Top-down dp (memoization).

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

Top-Down( $n,s_1,\dots,s_n,f_1,\dots,f_n, w_1,\dots,w_n$ )

sort jobs by finish time so that $f_1 \leq f_2 \leq \dots \leq f_n$
Compute $p[1],p[2], \dots, p[n]$ via binary search
$M[0] \gets 0$
Return M-Compute-Opt(n)

M-Compute-Opt(j):

If ( $M[j]$ $M [j]$ is uninitialized)
- $M[j] \gets \{M-Compute-Opt(j-1), w_j + M-Compute-Opt(p[j])\}$
Return $M[j]$

Running time analysis The memoized version of the algorithm takes $O(n \log n)$ time. Proof:

sort by finish time with mergesort: $O(n \log n)$ .
compute $p[j]$ for each $j$ : $O(n \log n)$ via binary search
$M-Compute-Opt(j-1)$ : each invocation takes $O(1)$ time and either
- 1. returns an initialized value $M[j]$
- 1. initializes $M[j]$ and makes two recursive calls.
Progress measures $\Phi=\#$ initialized entires among $M[1..n]$ .
- Initially $\Phi=0$ ; throughout $\Phi \leq n$
- 1. decreases $\Phi$ by $1 \Leftarrow \leq 2n$ recursive calls.
Overall running time of $M-Compute-Opt(n)$ is $O(n)$ .

Those who cannot remember the past are codemned to repeat it.

So now that we have a DP algorithm that computes the optimal value, how do you find the optimal solution?

Find-Solution( $j$ )

If $j=0$ $j = 0$
- return $\varnothing$
Else if ( $w_j + M[p[j]] > M[j-1])$ $w_{j} + M [p [j]] > M [j - 1])$
- Return $\{j\} \cup Find-Solution(p[j]))$
Else
- Return $Find-Solution(j-1)$ .

$M[j] = max \{M[j-1], w_j + M[p[j]]\}$

Botton-up DP

Unwind recursion Buttom-Up( $n,s_1,\dots,s_n,f_1,\dots,f_n, w_1,\dots,w_n$ )

sort jobs by finish time so that $f_1 \leq f_2 \leq \dots \leq f_n$
Compute $p[1],p[2], \dots, p[n]$ via binary search
$M[0] \gets 0$
For $j=1$ $j = 1$ to $n$ $n$ :
- $M[j] \gets max \{M[j-1], w_j + M[p[j]]\}$

Those are previously computed value.

The running time of the button-up version takes $O(n \log n)$ time.

Maximum subarray problem

Given an array $x$ of $n$ integer (pos/neg), find a contiguous subarray whose sum is a maximum.

Let OPT(i) be teh maximum possible sum for any subarray ending at $i$ .
$max\{ v_i, v_i + OPT(i-1)\}$ .

The brute-force algorithm involves computing the sum for each i to j of $a[i]+a[i+1] + \dots + a[j]$ .

This takes $\Theta(n^3)$ time.

Apply the "cumulative sum" trick

precompute cumulative sums: $S[i] = a[0] + \dots + a[i]$ .
Now $a[i] + a[i+1] + \dots + a[j] = S[j] - S[i-1]$
Improves running time to $\Theta(n^2)$ .

Kadane's algorithm: $OPT(i) =$ max sum of any subarray of $x$ whose rightmost index is $i$

The goal: max $OPT(i)$ .

Bellman equation:

\left\{ \begin{array}{lr} x_i, & \text{if } i = 0\\ max\{x_i, x_i + OPT(i-1)\}, & \text{if } i>0 \end{array} \right.

in the max statement, we want to either take only element $i$ or take the element $i$ together with the best subarray ending at index $i-1$ .

This makes the running time $O(n)$ .

Segmented Least Squares

This is a multi-choice problem in the sense that you're mkaing the best choice out of many options.

Least square is a foundational problem in statistics.

Given $n$ points in the plane; $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ .
Find a line $y=ax+b$ that minimizes the sum of the squared error. $SSE = \sum^n_{i=1} (y_i - ax_i - b)^2$

Solution: calculus $\Leftarrow$ min error is acheived when...

Segmented least squares: points lie roughly on a squence of several line segments. Given $n$ points in the plane: $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ , find a sequence of lines that mimimizes $f(x)$ . What is the reasonable choice for $f(x)$ to balance accuracy (goodness of fit) and parsimony (number of lines)?

The goal is to mimimize $f(x) = E + cL$ $f (x) = E + c L$ for some constant $c > 0$ $c > 0$ , where
- $E$ = sum of the sums of the squared errors in each segment
- $L$ = the number of lines.

Dynamic programming: multiway choice (as compared to binary choice until now). Notation:

$OPT(j)$ = minimum cost for points $p_1, p_2, \dots, p_j$ .
$e_{ij}$ = SSE (sum of squared errors) for the points $p_i, p_{i+1}, \dots, p_j$ for some $i \leq j$ .

To compute $OPT(j)$ :

last segment uses points $p_i, p_{i+1}, \dots, p_j$ for some $i \leq j$ .
cost = $e_{ij} + c + OPT(i-1)$ .

Bellman equation:

\begin{equation} OPT(j) = \begin{cases} 0 & \text{if $j=0$}\\ min_{1 \leq i \leq j}\{e_{ij} + c + OPT(i-1)\} & \text{if $j>0$}\\ \end{cases} \end{equation}

$i$ ranges from $1$ to $j$ , making it multiway.

Algorithm

segmented-least-squares( $n,p_1, \dots, p_n, c$ )

For $j=1$ to $n$ :
- For $i=1$ $i = 1$ to $j$ $j$ ,
  - compute the SSE $e_{ij}$ for the points $p_1, p_{i+1}, \dots, p_j$
$M[0] \gets 0$
For $j=1$ to $n$
- $M[j] \gets min_{i\leq i\leq j} \{e_{ij} + c + M[i-1]\}$ where $M[i-1]$ is the previous previously computed value.
return $M[n]$ .

Analysis

Theorem: DP algorithm solves the segmented least squares problem in $O(n^3)$ time and $O(n^2)$ space.

Proof:

the bottleneck comes from computing SSE $e_{ij}$ for each $i$ and $j$ .
It takes $O(n)$ to compute $e_{ij}$ .

It can be improved to $O(n^2)$ time

for each $i$ : pre compute the comulative sums, which can be used to 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$

For example, the subset $\{1,2,5\}$ has value $35$ and weight $10$ .

Assume that all values and weights are integral.

Define $OPT(i,w)$ = optimal value of knapsack problem with items $1, \dots, i$ , subject to weight limit $w$ . We want to find $OPT(n,W)$ meaning that we use all $n$ items and are subject to weight limit $W$ .

In case 1: $OPT(i,w)$ does not select item $i$ . (possibily because $w_i>w$ ).

Then $OPT(i,w)$ selects the best of $\{ 1, 2,\ dots, i-1\}$ subject to weight limit $w$ .

In case 2: $OPT(i,w)$ selects item $i$ .

collect the new value $v_i$ .
new weight limit = $w-w_i$ .
$OPT(i,w)$ selects bets of $\{1,2,\dots, i-1\}$ subject to the new weight limit.

Bellman equation:

\begin{equation} OPT(i-1) = \begin{cases} 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{cases} \end{equation}

Algorithm

Knapsack( $n, W, w_1, \dots,w_n, v_1, \dots, v_n$ )

For $w=0$ $w = 0$ to $W$ $W$
- $M[0,w] \gets 0$ .
For $i=1$ $i = 1$ to $n$ $n$
- For $w=0$ $w = 0$ to $W$ $W$ ,
  - If ( $w_i>w$ ) $M[i,w] \gets M[i-1, w]$
  - Else $M[i,w] \gets max\{M[i-1,w], v_i + M[i-1, w-w_i]\}$
Return $M[n,W]$ .

Analysis

Theorem: the DP algorithm solves the knapsack problem with $n$ items and max weight $W$ in $\Theta(nW)$ time and $\Theta(nW)$ space. Where weights are integers between $1$ and $W$ .

Proof:

Take $O(1)$ time per table entry
There are $\Theta(nW)$ table entries
After computing optimal values, can trace back to find solutions: $OPT(i,w)$ takes item $i$ iff $M[i,w] > M[i-1, w]$ .

Remarks:

algorithm depends critically on assumptions that weights are integral
assumption that values are integral was not used

Bellman Ford Algorithm

Djikstra's algorithm does not work with edges with negative weight. This is beacuse greedy algorithms do not do backtracking and there could be a shorter path but would not be the smallest initially, which is how greedy algorithms work.

In graphs with negative cycles, the shortest path can be infinitely small, which is why the path must not have negative cycels.

Bellman Ford Algorithm finds the shortest path when there are negative values.

Theorem: If $G$ has no negative cycles, then there is a sortest path from $S$ to $t$ that is simple, i.e., it has nor epeated nodes, and hence at most $n-1$ edges.

We define the bellman equation as OPT(n-1, s) which represents the shortest path from s to t.

Define $OPT(i, v)$ as the minimum cost of a path from $v$ to $t$ using at most $i$ edges.

If $i>0$ then $OPT(i,v) = min \{OPT(i-1, v), min_{w\in V}(c_vw + OPT(i-1,w))\}$

Algorithm

Shortest-Path( $G,s,t$ )

$n \gets$ number of nodes in $G$
Array $M[0\dots n-1, V]$
Define $M[0,t]=0$ and $M[0,v]=\infty$ for all other $v \in V$ .
For $i=1, \dots, n-1$
- For $v \in V$ $v \in V$ in any order
  - Compute $M[i,v]$ using recurrence
- Endfor
Endfor
Return $M[n-1,s]$ .t

Linked from Algorithms