Dynamic Programming

XKCD

http://www.geeksforgeeks.org/travelling-salesman-problem-set-1/

What is Dynamic Programming?

• Finding overlapping subproblems
• Store subproblems in a table
• So you don’t need to solve them over and over again

​

• Simple example, naive Fibonacci - O(2ⁿ)
• With memoization - O(n)
• Exponential speedup!

History of Dynamic Programming

• Coined by Richard Bellman to describe his mathematics research in 1950s

“We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I'm not using the term lightly; I'm using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical.”

• programming: planning resource allocation (a la 'Linear Programming')
• dynamic: refers to a multi-stage process
• plus “It's impossible to use the word, dynamic, in a pejorative sense.”

Boyer-Moore String Matching

• Search right to left
• Create a table of how far forward you can jump after n-matches then bad.
• O(n+m) instead of O(nm)
• Consider: find AAAAB in AAAAAAAAAAAAAAAAAAB
• Or ABABABc in ABABABABABABABABABABABABABABABc

Needleman–Wunsch String Edit Distance

• https://web.stanford.edu/class/cs124/lec/med.pdf
• Find "edit distance" between two strings
• Build a table: rows are index into one string, columns are index into other string
• Dynamic programming corresponds to choosing between matching (diagonal), skipping a letter in one string or the other (horizontal and vertical).

Common variant: Smith-Waterman, which doesn't assume the start and end points are aligned. This is useful in nucleotide sequencing.

Needleman-Wunch Edit Distance Table

Optimization for a single variable

• Input variables subject to physical constraints (e.g., factory floorspace)

​

• Independent utility functions for activities (nonlinear, nonmonotonic)

​

• Find maximum utility for input (the single variable we're optimizing for is "utility")

Discrete optimization dynamic programming

• Enumerating X unique values for each of N variables takes O(X^N)
• But, utility from each variable is independent
• Let’s add each new activity in one at a time

​

​

• Calculating each F_k is O(X²)
• O(X) for each sample of F_k(x), O(X) samples
• Total: O(NX²) time, O(X) space

Discrete optimization - pseudocode

N=product types

R=amount of production available

F=profit from producing the best thing(s)

+ g_i(k) )

// Add variables one at a time

// Check each possible total

// Try out x_i == k

RNA Folding

Goal: use existing RNA fabrication to build functional nanostructures.

Need to find the lowest energy state to predict how RNA will fold.

RNA types of folds

RNA energy states

• We can organize substructures as a matrix
• Energy of a loop depends on energy of substructures
• Interior loops is the largest search space - O(N²)

Dynamic Programming + inner loops

• The size of the inner loop is constant on a diagonal
• The ‘loop’ energy term drops out

​

• Diagonals are shared
• O(N) search space
• O(N⁴) -> O(N³)