University of Michigan at Ann Arbor
Last Edit Date: 06/15/2023
Disclaimer and Term of Use:
We do not guarantee the accuracy and completeness of the summary content. Some of the course material may not be included, and some of the content in the summary may not be correct. You should use this file properly and legally. We are not responsible for any results from using this file
This personal note is adapted from Professor Marcus Darden and David Paoletti. Please contact us to delete this file if you think your rights have been violated.
This work is licensed under a Creative Commons Attribution 4.0 International License.
A primary advantage of a typical recursive algorithm is to divide the domain into independent sub-problems
Some recursive problems do not divide into independent sub-problems
Use Dynamic Programming (DP)
Bottom-up
Top-down
Dynamic Programming is applicable if:
You have a large problem that can be broken into smaller subproblems
The subproblems are NOT independent; the same subproblems recur in the course of solving the larger problem (hopefully many times)
Reduce the run time of a recursive function
Change complexity class, often from $O(c^n)$ to $O(n^c)$
Use memory to avoid computing values which have already been computed
This technique is called memoization (derived from the Latin word memoradum (to be remembered))
Different word than "memorization" (although they are cognate words)
Start with a recursive function and modify it
On exit:
On entry:
Check the inputs and determine if they have been seen before
If they have, retrieve the result from memory rather than recomputing it
Often done with only minor code changes
Example: Fibonacci Sequence
Naive Implementation:
1 uint64_t findFib(uint32_t i) {
2 if (i == 0 || i == 1)
3 return i;
4 return findFib(i - 1) + findFib(i - 2);
5 } // findFib()
Spectacularly inefficient recursive algorithm
Expoential running time $O(1.618^n)$
Top-Down DP
1 uint64_t fib(uint32_t n) {
2 // Array of known Fibonacci numbers. Start out with 0, 1,
3 // and the rest get automatically initialized to 0.
4 // MAX_FIB + 1 used to account for 0-indexing
5 static uint64_t fibs[MAX_FIB + 1] = { 0, 1 };
6 // Doesn't fit in 64 bits, so don't even bother computing
7 if (n > MAX_FIB)
8 return 0;
9 // Is already in array, so look it up
10 if (fibs[n] > 0 || n == 0)
11 return fibs[n];
12 // Currently unknown, so calculate and store it for later
13 fibs[n] = fib(n - 1) + fib(n - 2);
14 return fibs[n];
15 } // fib()
16
17 static const size_t MAX_FIB = 93;
18 uint64_t fib(uint32_t n);
19
20 int main() {
21 for (size_t i = 0; i <= MAX_FIB; i++)
22 cout << "fib(" << i << "): " << fib(i) << endl;
23 return 0;
24 }
Buttom-Up DP
1 uint64_t fibBU(uint32_t i) {
2 uint64_t f[MAX_N];
3 i = min(i, MAX_N – 1);
4 f[0] = 0;
5 f[1] = 1;
6 for (size_t k = 2; k <= i; k++)
7 f[k] = f[k - 1] + f[k - 2];
8 return f[i];
9 } // fibBU()
Evaluate function by
Starting at smallest function value
Using previously computed values at each step to compute current value
Must save all previously computed values
f[] grow exponentiallySimple technique has converted an exponential algorithm ($O(1.618^n)$) to a linear one ($O(n)$).
Example: Binomial Coefficient
Definition: $\binom{n}{m} = \frac{n!}{m!(n - m)!}$, where $n \ge m \ge 0$ and $m \in \mathbb{Z}$
Naive Appoach
Solve for $n!$ (iteratively or recuesively)
fact(n) = n * fact(n - 1)Solve for $(n - m)!$
Solve for $m!$
Integer overflow is a major issue:
$13!$ causes overflow of a 32-bit integer
$21!$ causes overflow of a 64-bit integer
$35!$ causes overflow of a 128-bit integer
Rewrite Binomial Coefficient
Base case, for $n \ge 0$: $\binom{n}{0} = \binom{n}{n} = 1$
Recursive definition, for $n > m \ge 1$: $\binom{n}{m} = \binom{n - 1}{m - 1} = \binom{n - 1}{m}$
Top-down approach
unint64_t binomHelper(uint32_t n, uint32_t m, vector<vector<uint_64>>& memo) {
if (m == 0 || m == n) {
memo[m][n] = 1;
return 1;
}
if (memo[m][n] > 0)
return memo[m][n];
memo[m][n] = binomHelper(n - 1, m - 1, memo) +
binomHelper(n - 1, m, memo);
return memo[m][n];
}
uint64_t binomTD(unsigned int n, unsigned int m) {
vector<vector<uint64_t>> memo(m + 1, vector<uint64_t>(n + 1));
return binomHelper(n, m, memo);
}
Bottom-up approach
uint64_t biCoeffBU(uint32_t n, uint32_t m) {
vector<vector<uint64_t>> c(m + 1, vector<uint_64>(n + 1));
for (size_t i = 0; i <= m; i++) {
for (size_t j = 0; j <= n; j++) {
if ((i == j) || (i == 0))
c[i][j] = 1;
else
c[i][j] = c[i - 1][j - 1] + c[i][j - 1];
}
}
return c[m][n];
}
Base cases: (i == j) and (j == 0)
Only finding values for half of 2D vector (j starts out equal to i)
Clearly, algorithm calculates approximate (nm) / 2 integers in vector c
Therefore the time complexity is $O(mn)$
| Top-down | Buttom-up |
|---|---|
|
|
|
Nuances
Time and space requirements for dynamic programming may become prohibitively large
Memo space used for either approach
Additional stack space used for top-down approach
Bottom-up approach can recycle / collapse previous memeo steps
Fibonacci really only needs the previous 2 values, not all previous values
With top-down you cannot eliminate these, because you do not know order of evaluation
Common Subproblems
Input is $x_1,x_2,...,x_n$; a subproblem is $x_1, x_2,...,x_i$
Number of subproblems is $O(n)$
Example: Fibonacci
Input is $x_1,x_2,...,x_n$; a subproblem is $x_i, x_{i + 1},...,x_j$
Number of subproblems is $O(n^2)$
Example: Pipe welding and positive subset sum
Input is $x_1,x_2,...,x_n$, and $y_1,y_2,...,y_m$; a subproblem is $x_1,x_2,...,x_i$ and $y_1,y_2,...,y_j$
Number of subproblems is $O(nm)$
Example: Binomial Coefficient, Edit Distance
Input is a rooted tree; a subproblem is a rooted subtree
Top-down or Buttom-up?
Some problems the base cases are easy to see
Some problems it is hard to see which subproblems need to be computed