Exam 1 - Dynamic Programming Flashcards
What’s the general strategy for finding a DP solution?
Define the subproblem in words
State the recursive relation
What’s the difference between a subsequence and a substring?
A substring is consecutive elements, a subsequence is just in increasing order
What is the LIS algorithm?
It takes an array a of n numbers and finds the length of the longest increasing subsequence
What is the subproblem of the LIS algorithm?
L(i) = length of LIS in a_1, … , a_i that includes a_i
Why does the subproblem of the LIS algorithm include the condition that the LIS for L(i) includes a_i?
it keeps the subproblem from getting stuck on a suboptimal solution for an earlier value of i
What is the recursive relation for LIS?
Given this recursive relation for LIS, what is the algorithm to find the LIS for a?
Given this algorithm for LIS, what is its runtime?
What is the LCS algorithm?
Given two input strings X and Y, it finds the longest string which is a subsequence of both X and Y
What is the subproblem of the LCS algorithm?
For i and j where 0 <= i or j <= n, let L(i,j) = length of LCS in x_1, … , x_i and y_1, … , y_j
What are the base cases of the LCS algorithm recurrence?
L(i,0) = 0 for all i
and
L(0,j) = 0 for all j
For LCS, in the case that x_i = y_j , what is the recurrence?
L(i,j) = 1 + L(i-1, j-1)
For LCS, in the case that x_i != y_j, what is the recurrence?
L(i,j) = max { L(i-1,j) , L(i, j-1) }
For LCS, in the case that x_i != y_j, why doesn’t the max include a branch of L(i-1,j-1)?
Because L(i-1,j-1) can be reached by either L(i-1,j) or L(i,j-1)
Given this recurrence of LCS, what is an algorithm for it?
Given this algorithm for LCS, what is its runtime?
How can we extract the chars of the LCS from the L(i,j) table generated by the LCS algorithm?
Start at the max L(i,j), and find where i and j both decrement to a smaller L(i,j) value
What are the inputs to the knapsack algorithm?
n objects
with integer weights w_1, … , w_n
and integer values v_1, … , v_n
and total capacity B
What is the goal of the knapsack algorithm?
Find subset S of objects that:
fit in backpack – total weight <= B
maximizes total value
What is the subproblem for nonrepeating knapsack?
Given this subproblem for nonrepeating knapsack, what is the recurrence?
What are the base cases for the nonrepeating knapsack recurrence?
k(0,b) = 0 for all b
k(i,0) = 0 for all objects i
Given this recurrence for nonrepeating knapsack, what is the algorithm?
Given this algorithm for nonrepeating knapsack, what is its runtime?
