CS6515 ALGORITHMS FINAL EXAM 1 2026
COMPLETE QUESTIONS AND VERIFIED
SOLUTIONS
◉ What is the recurrence for Longest Increasing Subsequence (LIS)?
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
◉ What is the recurrence for Longest Common Subsequence (LCS)
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
◉ What is the running time for Longest Common Subsequence (LCS)
Answer: O(n^2)
◉ What are the dimensions of the array for solving the knapsack
problem WITHOUT repetition? Answer: 2-D array
◉ What is the recurrence for knapsack w/o repetition? 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
, ◉ What are the base cases for knapsack w/o repetion? Answer:
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? Answer: It is pseudopolynomial O(nB)
◉ What are the dimensions of the array for solving the knapsack
problem WITH repetition? Answer: 1-D array
◉ What is the recurrence for knapsack w/ repetition? Answer: 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? Answer:
O(Bn)
◉ What is the time complexity for multiplying two matrices A
(dimensions n x m) and B (dimensions m x k) Answer: O(nmk)
◉ If we have n matrices, A1, A2... An how can we define each of their
sizes? Answer: mi-1 x mi since the inner dimensions of a matrix
product must match
COMPLETE QUESTIONS AND VERIFIED
SOLUTIONS
◉ What is the recurrence for Longest Increasing Subsequence (LIS)?
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
◉ What is the recurrence for Longest Common Subsequence (LCS)
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
◉ What is the running time for Longest Common Subsequence (LCS)
Answer: O(n^2)
◉ What are the dimensions of the array for solving the knapsack
problem WITHOUT repetition? Answer: 2-D array
◉ What is the recurrence for knapsack w/o repetition? 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
, ◉ What are the base cases for knapsack w/o repetion? Answer:
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? Answer: It is pseudopolynomial O(nB)
◉ What are the dimensions of the array for solving the knapsack
problem WITH repetition? Answer: 1-D array
◉ What is the recurrence for knapsack w/ repetition? Answer: 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? Answer:
O(Bn)
◉ What is the time complexity for multiplying two matrices A
(dimensions n x m) and B (dimensions m x k) Answer: O(nmk)
◉ If we have n matrices, A1, A2... An how can we define each of their
sizes? Answer: mi-1 x mi since the inner dimensions of a matrix
product must match
