Dynamic Programming Flashcards
(17 cards)
What are features of dynamic programming?
Possibly overlapping subproblems, used for optimization, top down is recursive, bottom up is iterative
What are some example problems?
Matrix chain multiplication, rod cutting, longest common subsequence
Given a sequence x of size n, and a sequence y of size m, how many possible subsequences are there?
2^m possible subsequences
What is a brute force approach to finding the longest common subsequence in y that appears in x?
Generating every possible subsequence and linearly checking x to see if it appears
What is one way to use dynamic programming to find the longest common subsequence in y that appears in x?
TopDown, if xn and ym match, then find the LCS of x and y without xn and ym, if they don’t match then find the bigger LCS between the sets x1…xn-1,y and the sets x,y1…y-m
How are the arrows from a handwritten LCS graph actually stored in a coded implementation?
The arrows are encoded as four values, one for each combination of arrows: left, up, diagonal upleft, and left+up
How much memory is actually needed to implement this LCS algorithm?
Only the 2-D array to hold the match data is needed, the other info can be computed using comparisons
How much memory is needed if you only want the score?
If the sequence alignment isn’t needed, only 2 1-D arrays are needed (2 rows)
What are the benefits of alignment?
Also keeps track of replacement cost, also known as edit distance
How long does it take to find the LCS from an S array?
O(nxm)
What is the Rod Cutting problem?
For a rod of length n, cut the rod into subrods such that the subrods are the correct lengths to maximize profits when sold
What is the complexity of a brute force approach to the Rod Cutting problem?
2^n-1, the amount of possible cut combinations
What is the complexity of a dynamic programming bottom up approach to the Rod Cutting problem?
n(n+1)/2
What is the bookkeeping for a bottom up approach to the Rod Cutting problem?
Subrod length, subrod price, subrod profit, optimal cut for subrod length
What is a bottom up approach to the Rod Cutting problem?
Subrod1 profit = subrod1 price
Subrod2 profit = max(subrod2 price, subrod1 price + subrod1 price)
Subrod3 profit = max(subrod3 price, subrod2 price + subrod1 profit, subrod2 profit + subrod1 price)
etc.
What is a top down approach to the Rod Cutting problem?
Log values of subproblems, then if encountered again, treat as base case
Which dynamic programming approach is better for the Rod Cutting problem?
Bottom up, recursion unnecessary, faster to use iterative approach
