- | Page
CS6515 - EXAM 1 COMPLETE
QUESTIONS AND ANSWER S
Question 1: What is the running time for Longest
Increasing Subsequence (LIS)
CORRECT ANSWER: O(n^2)
Question 2: What is the recurrence for Longest Increasing
Subsequence (LIS)?
CORRECT ANSWER: 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
Question 3: What is the recurrence for Longest Common
Subsequence (LCS)
CORRECT ANSWER: 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
Question 4: What is the running time for Longest
Common Subsequence (LCS)
CORRECT ANSWER: O(n^2)
- | Page
Question 5: What are the dimensions of the array for
solving the knapsack problem WITHOUT repetition?
CORRECT ANSWER: 2-D array
Question 6: What is the recurrence for knapsack w/o
repetition?
CORRECT ANSWER: 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
Question 7: What are the base cases for knapsack w/o
repetion?
CORRECT ANSWER: K(0,b) = 0 & K(i,0) = 0 which is
when we have no objects and no knapsack, respectively
Question 8: What is the running time of the knapsack w/o
repetition algorithm?
CORRECT ANSWER: It is pseudopolynomial O(nB)
- | Page
Question 9: What are the dimensions of the array for
solving the knapsack problem WITH repetition?
CORRECT ANSWER: 1-D array
Question 10: What is the recurrence for knapsack w/
repetition?
CORRECT ANSWER: K(b) = max(vi + K(b-wi)) for all
items i with a weight less than or equal to current capacity b
Question 11: What is the running time of the knapsack w/
repetition?
CORRECT ANSWER: O(Bn)
Question 12: What is the time complexity for multiplying
two matrices A (dimensions n x m) and B (dimensions m x k)
CORRECT ANSWER: O(nmk)
- | Page
Question 13: If we have n matrices, A1, A2... An how can
we define each of their sizes?
CORRECT ANSWER: mi-1 x mi since the inner
dimensions of a matrix product must match
Question 14: Whats the most likely base algorithm to use
if problem only has a single array?
CORRECT ANSWER: LIS
Question 15: What is the most likely algorithm if problem
is comparing to iself
CORRECT ANSWER: LIS
Question 16: What is the most likely alg if problem only
looks back one elemnt at a time (not a window, or a bag)
CORRECT ANSWER: LIS
Question 17: What are the two most common LIS
variations?