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?
Why is nonrepeating knapsack not efficient?
The running time is not polynomial on the input size.
Because as B is incremented, its size increments by logB, so an efficient algorithm would be O(n log(B)), whereas nonrepeating knapsack is O(nB)
What is the subproblem for repeating knapsack?
Given this subproblem for repeating knapsack, what is the algorithm?
If I have two matrices,
W of size a x b
and Y of size b x c
How many multiplication operations are needed to calculate Z = W x Y?
Calculating each element in Z requires b multiplications, and Z is of size a * c, so calculating Z takes:
a * c * b multiplications
What is the input for the Chain Matrix Multiplication algorithm?
m_0 , … , m_n
Because we’re finding the cost of multiplying A_1, …, A_n, and A_i is of size m_(i-1) x m_i
What is the base case of the recurrence for Chain Matrix Multiplication?
c(i,j) where i = j is 0, because no computation is needed
What is the general case of the recurrence for Chain Matrix Multiplication?
Given this recurrence for Chain Matrix Multiplication, what is the algorithm?
Given this algorithm for Chain Matrix Multiplication, what is the runtime?
What’s the difference between the output of the Bellman-Ford algorithm and the Floyd-Warshall algorithm?
Bellman-Ford gives the shortest path distance for every vertex from a given source vertex, whereas Floyd-Warshall gives the shortest path distance for every vertex from every other vertex
In a directed graph with no negative weight cycles, the shortest path from one vertex to another visits every vertex no more than ____
once
What is the subproblem in the Bellman-Ford algorithm?
What is the base case of the recurrence in the Bellman-Ford algorithm?
What is the recurrence for the Bellman-Ford algorithm?
Given the recurrence for the Bellman-Ford algorithm, what is the pseudocode?
Given the pseudocode for the Bellman-Ford algorithm, what is the runtime?
How do you find a negative weight cycle with the table generated by the Bellman-Ford algorithm?
If D(n,z) < D(n-1, z) for any z in V, there’s a negative weight cycle
What is the subproblem for the Floyd-Warshall algorithm?
What is the base case for the recurrence of the Floyd-Warshall algorithm?
D(0,s,t) = w(s,t) if there is an edge from s to t , infinity if not
What is the general recurrence of the Floyd-Warshall algorithm?
Given the recurrence of the Floyd-Warshall algorithm, what is the psuedocode?
Given the pseudocode of the Floyd-Warshall algorithm, what is the runtime?
How do you detect negative weight cycles in the Floyd-Warshall algorithm?
There is one if any D(n,y,y) < 0 for any y
