CS6515 - Exam 1 Questions with Verified Correct
Answers
What is the running time for Longest Increasing Subsequence (LIS)
O(n^2)
What is the recurrence for Longest Increasing Subsequence (LIS)?
L(i) = 1 + max{ L(j) | xj < xi}
This reads as the answer to index I is 1 + the maximum over all j's between 1 and i where xj
is less than xi
What is the recurrence for Longest Common Subsequence (LCS)
L(i,j) = 1 + L(i-1, j-1) if xi = yj
L(i,j) = max(L(i-1,j),L(i,j-1)) otherwise
What is the running time for Longest Common Subsequence (LCS)
O(n^2)
What are the dimensions of the array for solving the knapsack problem WITHOUT
repetition?
2-D array
What is the recurrence for knapsack w/o repetition?
K(i,b) = max((vi + K(i-1,bi-wi)),K(i-1,b) if wi < b)
K(i,b) = K(i-1,b) otherwise
What are the base cases for knapsack w/o repetion?
, K(0,b) = 0 & K(i,0) = 0 which is when we have no objects and no knapsack, respectively
What is the running time of the knapsack w/o repetition algorithm?
It is pseudopolynomial O(nB)
What are the dimensions of the array for solving the knapsack problem WITH
repetition?
1-D array
What is the recurrence for knapsack w/ repetition?
K(b) = max(vi + K(b-wi)) for all items i with a weight less than or equal to current capacity b
What is the running time of the knapsack w/ repetition?
O(Bn)
What is the time complexity for multiplying two matrices A (dimensions n x m) and B
(dimensions m x k)
O(nmk)
If we have n matrices, A1, A2... An how can we define each of their sizes?
mi-1 x mi since the inner dimensions of a matrix product must match
Whats the most likely base algorithm to use if problem only has a single array?
LIS
What is the most likely algorithm if problem is comparing to iself
LIS
Answers
What is the running time for Longest Increasing Subsequence (LIS)
O(n^2)
What is the recurrence for Longest Increasing Subsequence (LIS)?
L(i) = 1 + max{ L(j) | xj < xi}
This reads as the answer to index I is 1 + the maximum over all j's between 1 and i where xj
is less than xi
What is the recurrence for Longest Common Subsequence (LCS)
L(i,j) = 1 + L(i-1, j-1) if xi = yj
L(i,j) = max(L(i-1,j),L(i,j-1)) otherwise
What is the running time for Longest Common Subsequence (LCS)
O(n^2)
What are the dimensions of the array for solving the knapsack problem WITHOUT
repetition?
2-D array
What is the recurrence for knapsack w/o repetition?
K(i,b) = max((vi + K(i-1,bi-wi)),K(i-1,b) if wi < b)
K(i,b) = K(i-1,b) otherwise
What are the base cases for knapsack w/o repetion?
, K(0,b) = 0 & K(i,0) = 0 which is when we have no objects and no knapsack, respectively
What is the running time of the knapsack w/o repetition algorithm?
It is pseudopolynomial O(nB)
What are the dimensions of the array for solving the knapsack problem WITH
repetition?
1-D array
What is the recurrence for knapsack w/ repetition?
K(b) = max(vi + K(b-wi)) for all items i with a weight less than or equal to current capacity b
What is the running time of the knapsack w/ repetition?
O(Bn)
What is the time complexity for multiplying two matrices A (dimensions n x m) and B
(dimensions m x k)
O(nmk)
If we have n matrices, A1, A2... An how can we define each of their sizes?
mi-1 x mi since the inner dimensions of a matrix product must match
Whats the most likely base algorithm to use if problem only has a single array?
LIS
What is the most likely algorithm if problem is comparing to iself
LIS
