MIT 6.006 - Dynamic programming Flashcards
(25 cards)
What’s dynamic programming about?
how to come up with a brand new polynomial algorithm to solve a problem, but specifically recursive algorithms design.
It’s recursion + memoization
What does the acronym SRTBOT stand for?
It’s a recursive algorithm design paradigm:
Subproblems
Relations
Topological order
Base case
Original problem
Time
This will help me remember stuff that will be explained later.
We will solve problems by breaking them into subproblems, and so we want to define what a subproblem is.
-Relate subproblems recursively
Topological order - on the subproblems, if we think about the subproblems as a graph there were cycles, then we wouldn’t terminate
base cases of recursive relations
Original problem - solve by subproblems
Time analysis
Decompose mergesort into the titles of srtbot
Example: Mergesort(A)
Subproblem - sort array for i to j indexes we will define this as S(i,j)
Original problem: S(0,n)
Relations: S(i,j) = merge(S(i,m),s(m,j)) where m=(i+j)//2
Topological order: |j-i|, the length of the sub array, is increasing
Base case: S(i,i) = []
Time: T(n) = 2*T(n/2)+O(n) = O(nlogn)
Given the Fibonacci number problem,
Fn=F(n-1)+F(n-2)
F1=F2=1
Phrase it using the SRTBOT framework in a naive way (even though I never want to do that recursively because of horrible time).
Original problem: Calculate F(n)
Subproblems: S(i)=F(i) between 1 and n
Recurrence Relations: S(n)=S(n-1)+S(n-2)
Base: T(0)=T(1)=1
Topology order: increasing i,for i in range(0,n+1)..
Time: T(n)=T(n-1)+T(n-2) + 1 addition
T(n)>=F(n) and fibonnaci numbers grow very fast =>Time is exponential,so that would be a terrible way to compute fibonnaci numbers
Given the Fibonacci number problem,
Fn=F(n-1)+F(n-2)
F1=F2=1
Use memoization and the SRTBOT framework to phrase this problem in a sensible way (in terms of running time)
Notice it’s not memorization but memization, we’re going to write things in a memo pad - remember and reuse the solutions to sub problems
Maintain a dictionary like a hashtable or array, map subproblems to their solutions (the ones which were solved).
Recursive problem returns stored solution or if doesn’t exist, compute the usual way and store it.
Now for fibonnaci the running time will be O(n) as calling F(n) will call F(j) only once for js less than n.
Why? In general, to know the running time with an algorithm with a memo table, we just count how many sub problems are there (and how much time it takes to solve every sub-problem), because once we solve a problem we never solve it again.
As a side note, it takes O(n) additions, but since those are Fibonnaci numbers which grow exponentially and therefore, in the number of bits, linearly (each addition will cost O(n)),
then the n additions will cost O(n/w*n) =O(n^2/w)
Why doesn’t memoization help improve mergesort?
Looking at the tree of subproblems of mergesort, the indices at all lower branches are distinct from one another, so solving S(0,1) doesn’t help with,for example, S(n-2,n-1).
When using the sum of subproblems over the amount of time it takes for each non-recursive operation, what’s the bound we reach when analyzing mergesort?
Merge(i,j) -> there are O(n^2) subproblems.
Each non-recursive call merges between two merged arrays which takes O(n) =>
O(n^3) is an upper bound.
Of course, we know that it actually takes O(n^3), but this way we can get an upper bound on the runtime of a problem which will be polynomial if number of problems if polynomial and the run time of each non-recursive call is polynomial, and from there we can optimize our estimate.
Frame the DAG shortest path problem using the SRTBOT framework
Problem: Given a graph (V,E) and
w:E->Z and a source node s, find, for each v in V, the shortest distance delta(s,v)
Subproblems: S(s,v) for all v in V
Base: delta(s,s)=0
Topological order:
G’s topological order
Recursive relation:
delta(s,v) = infinite or min (delta(s,u)+w(u,v)) for all u adjacent to v
Time: O(|V|+|E|)
Bowling:
We have n pins 0…n-1
Pin i has Vi value
I can choose to shoot one exact pin, or if I shoot between two pins, I will knock down both.
If I hit one pin exactly I get Vi points, but when I hit two pins I get their product points Vi*V(i+1).
Goal is to maximize score with as many tries as I want.
Solve via dynamic programming using the SORTBOT template
B(i) = max score on Vi….Vn-1
When I define the subproblem, don’t just say how to calculate it, but explicitly say what I’m trying to do
Original problem: B(0)
B(i) =max between:
B(i+2)+vi*vi+1,
B(i+1)+vi,
Bi
Topological order: decreasing i
Time: O(n) *O(1)
Base: B(0)=O(n)*O(1)
Here’s my initial draft for future reference:
The problem: bowling problem given the full array of n values , A
Subproblems: Given values array A’ (of size less or equal to n), solve S(A’), getting the maximum value
Base:
For array of size 0 return 0
For array of size 1, if negative then return v0 if positive otherwise return 0
For array of size 2:
If both negative return their multiplication.
If one negative and one positive, return the value of the positive
If both are positive, return the maximum between V0+V1 and V0*V1
Recursion relation: (a bad choice that I made at first and is a good example of why not to choose subsequence):
I can hit either 1 or 2, return the maximum between hitting 1 and hitting 2, which is the max on all of the following n+n-1 terms:
Term1: For each positive Vi, return vi+S(v0…vi-1)+S(vi+1…vn-1)
Term 2: For each i-1,i n>=i>=1
return vi-1*vi+S(v0…vi-2),S(vi+1..vn-1)
Topology: every subgroup
Time: all subgroups of v0…vn-1 so O(2^n) sub problems, and O(1) operations for the non-iterative step
Alternate solution(I don’t like 2^n solutions):
Either I want to knock down vn-1 single, I want to knock it with vn-2 or I don’t want to knock it down. Therefore:
S(n)= max between the following:
S(A[0:n-1])+S(A[n-1]),
S(A[0:n-2]+S(A[n-2:n])
Notice that the first term will be automatically resolved to 0 if I don’t want to knock it down by my base case.
Topology: i=0…n-1
O(n) base cases with O(1) operations as the non-recursive operation.
Much better :D
Dynamic programming: If the input is a sequence, what are some good subproblems to consider?
- prefix/postfix (X[:i] or X[:i]
- substrings (X[i:j]) ->not to confuse with subsequences, as there are exponential number of subsequences
Bowling:
We have n pins 0…n-1
Pin i has Vi value
I can choose to shoot one exact pin, or if I shoot between two pins, I will knock down both.
If I hit one pin exactly I get Vi points, but when I hit two pins I get their product points Vi*V(i+1).
Goal is to maximize score with as many tries as I want.
Solve via dynamic programming using bottom up. Why do we want to use bottom us?
Bottom up:
BASE: B(n)=0
TOPOLOGY : For i=n,n-1…0:
RELATE: B(i) = max(B(i-1),B(i-1)+vi,B(i-2)+vi*vi+1)
ORIGINAL PROBLEM: return B(0)
I want the bottom up approach because it’s super fast if I write it in code (also easier to debug than recursive functions etc)
When solving DP, what do I need to think about when thinking about the hard part (taking the problem and breaking it down to subproblems)
“What do I need to know in order to solve this problem”, if I can identify that and the number of choices for what i need to know is polynomial, then I’ll get a polynomial solution.
Subproblems DAG - define it
a DAG where vertices are subproblems, if B needs A then there’s an edge (A,B)
Frame the following using the SRTBOT framework:
Longest common subsequence:
Given two strings A and B, find the longest SUBSEQUENCE C which is a subsequence of both A and B.
a subsequence means any monotone series of indices for both strings, eg, it’s not necessary for the subsequences to be continuous.
For example, “HELLO” is a subsequence of the string
“SDFHNKGESDFLSDFLO”
Given two strings,
s1 of length n1
s2 of length n2
I will define LCS(i,j) to be the LCS for s1[:i],s2[:j].
main idea:
Either the rightmost characters in both strings are equal, in which case the answer is just the strings without it concatenated with that character, or lcs without one of them.
Subproblems definition:
LCS(i,j) = the LCS of s1[:i],s2[:j]
recurrent relation:
LCS(i,j) =
if s1[i-1]==s2[j-1]:
return LCS(i-1,j-1) + s1[i-1]
return max length (LCS(i-1,j),LCS(i,j-1))
Time: We’re thankfully using memoization,otherwise runtime would be O(2^n). There are n1*n2 subproblems, since there are only n1 different values for i and n2 different values for j
Topology: i,j increasing to n (if I want to start was unsolved subproblems and want to advance to the full solution)
Base: i==0 or j==0 -> return ‘’
Original problem: LCS(len(s1),len(s2)).
Frame the following using the SRTBOT framework:
Longest increasing subsequence:
Given one sequence:
CARBOHYDRATE
find the longest subsequence in this sequence which is increasing
(in this case ABORT).
In the lecture he defined:
L(i) = max subsequence that starts with s[i] exactly
and the relation:
L(i) = max(L(j) such that s[j]>s[i],j>i))
Subproblem definition:
LIS(i,last_value): given the sequence s[i:], and last_value_used which is the value of the last character that I’ve used when producing the current subsequence, produce the largest LIS such that every value that greater than last_value
Original problem: LIS(0, None)
Basecase: LIS(n,x)=’’
LIS(n-1,None) = s[n-1]
Recursive relation:
LIS(i,last_value)=
if s[i]<last_value -return LIS(i+1,last_value)
if s[i]>last_value - return max {
LIS(i+1,last_value),
s[i]+LIS(i+1),s[i])
}
Topology (index,last_value) where index is decreasing, and last_value is also decreasing
Time:
Number of subproblems:
|S|*|alphabet| so if our alphabet is a constant, then time complexity is O(|S|), but what if in reality it’s a huge number?
But that last_value is taken from s, and therefore it’s actually O(n^2) different subproblems.
Frame the following using the SRTBOT framework:
Alternating coin game:
It’s a 2 player game.
Given a series of coins (or values), say (5,10,100,25), each player has to pick a coin from either the beginning of the sequence of the end of the sequence.
A greedy algorithm won’t work: For example, if player A take coin 25, then player B will take 100 and win the game on the spot.
but if player A takes 5, then he wins (player B will take either 10 or 25 and then player A will take 100).
Here are the lecturer definitions, my answer before looking at it is given for a reference.
It’s a substring problem.
Subproblem: X(i,j) the value of the best strategy if the game is played only with S[i:j+1]…
Subproblem: Strategy(A) = given array A of coin values, output the value of the best strategy that I can play from that position,alongside the move (left or right)
Base: If A is empty, output ‘‘,0, if A has one element, output either ‘left’ or ‘right’ and the value of that one element
Relation: Either I take the leftmost coin or the rightmost coin,so:
value_left = A[0] - S(A[1:])[‘value’]
value_right=A[-1]-S([:-1][‘value])
if value_left > value right:
Strategy(A) = ‘left’,value_left
otherwise
Strategy(A) = ‘right’,value_right
Number of different subproblems:
Since there are O(n^2) different subarrays of any length that are contiguous, there are O(n^2) subproblems, each problem’s non-recursive part runs at O(1) so therefore the entire algorithm will run at O(n^2)
Original problem will run at O(n^2)
Topology - increasing contiguous subarrays of A.
Frame the following using the SRTBOT framework: SSSP in a general graph, which might contain negative cycles.
This is the original way in which
Bellman introduced Bellman-Ford’s algorithm.
SSSP in a general graph: Given a source s, in a weighted directed graph which might contain negative cycles, find the shortest path to any v in V.
Subproblem: delta(s,v,k): Weight of the shortest path from s to v using at most k edges. (in the lecture he used deltak(s,v)).
Recurrence relation:
delta(s,v,k) =min ( delta(s,u,k-1)+w(u,v) for all incoming edges to v) union delta(s,v,k-1).
Topological order: increasing k…
Base cases:
delta(s,s,0) = 0
delta(s,u,0) = infinite for all u!=s
Original problem: mindelta(s,u,|V|-1) and use delta(s,u,|V|) for cycle detection.
Time: Sum(all v)(all edges) = O(|V|*|E|)
Frame the following using the SRTBOT framework: MSSP in a general graph, which might contain negative cycles (the non-DP solution was Johnson).
Notice that the third term is an index, and the second term is a vertex
Floyd-Warshall:
Number the vertices 1…|V|.
Subproblems: d(u,v,k) = weight of shortest s->v path using only vertives {u,v,1,2….k}
How many subproblems are there?
u,v,k all can be any vertex (or vertex index) so v^3
Recurrence relation:
d(u,v,k) = min {
d(u,v,k-1), #not use the kth vertex
d(u,k,k-1)+d(k,v,k-1)#use the kth vertex
}
Topological order: k=1…|v|
Base: d(u,v,0) =
0 if u=v
w(u,v) if (u,v) exists,infinite otherwise
original problem d(u,v,|v|) for all u,v (assuming no negative cycles)
Time: v^2 relations, O(v) for each non-recurrence relation, so O(v^3).
(Solving MSSP) Floyd-Warshall:
What’s the main idea in limiting the sub-problems to use only k vertices?!
With Bellman-Ford for MSSP (even phrased as a DP problem), it will take O(|V|^2*|E|). That |E| comes from us having to go through all of the edges of the graph. Limiting the number of vertices used instead of limiting the number of edges used will save us time in the case of a dense graph (where E can be O(V^2).
Frame the following using the SRTBOT framework:
Arithmetic parenthesization:
Given a formula:
a0S1a1s2a2…sn-1an-1
Where a0…an-1 are numbers from Z and s1…sn-1 are one of the operations {+,*}.
My goal is to place parentheses to maximize the result.
This is the official solution, my initial solution (which is correct only if the numbers were all not negative as I didn’t calculate both max and min) will be given next as a reference.
Idea: Guess which operation is at the root of the calculation tree.
It’s not enough to maximize the right and left sides of the root operator, since we might want to minimize one of them or both of them (multiplication of two negatives or one negative…).
Subproblem:
X(i,j,opt) where opt is min or max…
Relation:
X(i,j,opt) = opt{
X(i,k,optL)SkX(k,j,optR)
where j>k>i and optR,OptL are {min,max} (consider all options, it’s true that we know for example that if opt is max then we want max of both but whatever-it won’t affect the asymptotic time of the entire function)
}
Topology: Increasing j-i
Base: one number, output it (whatever opt is).
Subproblem:
Parentheses(a0,s1,a1…an) = output the original series alongside the parentheses which maximize the expression’s value.
Recurrence relation:
Parentheses(a0,s1,a1….sn,an)=
max {
a0s1parentheses(a1…sn,an),# I don’t put parentheses to the left of a0,
(parentheses(a0…aj)) sj+1 parentheses(aj+1…an) #I put parentheses between a0 and aj for some j
j=1…n
}
Base: a series of length 1, a0,
output a0.
Time: Amount of subproblems is n choose 2 (For every two indices I can calculate Parentheses (ai….aj)).
Amount of work inside each non-recurrence call is finding the max between n+1 different numbers so O(n).
Therefore in total the amount of work is O(n^3).
Topology- (i,j) where either i is decreasing or j is increasing between (0,n) until (i,j) is exactly (0,n)
Original problem: Parenthesis (original series).
If I want the output to adhere to the fact that multiplication has priority over addition, then I need to make the following changes:
For the case when I don’t put parentheses to the left of a0, instead of outputting a0s1parentheses(a1…an), I need to do the same output is s1 is addition, or (a0s1a1…smam) sm+1 parenthesis(am+1…an) where m is the index just before the first addition (sm…s1 are all multiplications)
Frame the following using the SRTBOT framework:
Piano fingering:
Given a sequence of single notes-
t0,t1…tn-1
and given fingers 1,2…F
Metric d(t,f,t’,f’) of difficulty of going from playing note t with finger f to playing note t’ with finger f’.
Goal: Given a series of notes T = to…tn-1 and a metric d, I want to compute a series of fingers fi
min(sum(d(ti,fi,ti+1,fi+1)))
Subproblems:
Main point: Use f as a constraint/memory so that I can write a proper recurrence that I will actually go over all of the different options.
X(i,f) = min total of d from i if at index i we play with finger f
Relation:
X(i,f) = min d(t[i],f,t[i+1],f’)+opt(i+1,f’) over all f’=1..F
Original problem:
min X(i,f) over all F for each i.
Time:
There are F fingers and N indices, so FN subproblems, each problem goes over F numbers so it’s O(F^2n) = O(n).
Frame the following using the SRTBOT framework:
Rod cutting:
Given Rod of length L,and value v(l) of rod of length l, for all l in 1..L,
What’s the best way to split the rod into various rods of different length such that I get the max sum value of those lengths,eg the max value partition of the rod
Mprofit(L) = the maximum profit I can get from selling the best partition of length L.
Mprofilt(L)=max{
v(i)+Mprofit(L-i)
i=1…L
}
Base: Mprofit(x non positive) = 0
Topology: increasing values of L
l=1…L.
Time:
L different subproblem: O(L). Each subproblem considers up to L different solutions (O(L)).
In total I get O(L^2) runtime
We get an array of size L as an input so this is polynomial in the size of the input.
Original problem: simply Mprofit(L)
Frame the following using the SRTBOT framework:
Subset sum:
Given multiset (=can repeat an element) A of numbers, A={5,9,5,200…} ={a0,a1,a2,a3} of n integers, and given a target sum T, and I want to know: does any subset sum to the target sum?
Subproblem definition:
CanSum(i,v): Using the multiset A[i:], can I reach the value v?
Recurrence relation:
CanSum(i,v)= or{
CanSum(i+1,v-a0)#i will use the a0 element,
CanSum(i+1,v) #I will not use the a0 element
}
Base: Cansum(Anything,0) = True
Cansum(n,anything not 0) =False
Time: The number of subproblems:
Number of sets created from A:
since I always take out the element with the lowest index, there are n different possibilities.
Number of values: If I allow negative numbers in A, i take the initial value, then I either keep it or decrease it by a0, then I either keep or decrease by a1 etc…so this will be up to 2^n number of different values.
In total, I’ll have 2^n*n different subproblems, which is not polynomial in the input size.
If all numbers in A are positive, then v has to be in the range [0…T] so in total I will have O(n*T) subproblems
Original problem:CanSum(A,T).
Topology: increasing size of A, decreasing v (unless negative numbers are allowed in A and then it’s unbounded)
We’ve seen an algorithm,subset_sum, which gets a set of size n, and some number T, and solves the problem in O(n*T). Is this a polynomial running time?
No, since T is in a word of our machine, and we know that it fits in a word of our machine, just like n, so we know that logw>=n, but w can be much bigger than n. For example it can be n. And so, that running time O(nT) can be potentially n2^n).
However it is pseudopolynomial eg polynomial in the input,and input integers.
