CS 6515 EXAM QUESTIONS WITH CORRECT ANSWERS LATEST UPDATE 2026

CS 6515 EXAM QUESTIONS WITH CORRECT ANSWERS LATEST UPDATE 2026 LIS Sub-problem - Answers Let L(i) = Length of LIS in a[1],..., a[i] which includes a[i] LIS Recurrence - Answers Base Case: L[0] = 0 L(i) = 1 + max(j) { L(j): a[j] a[i] & j i} LIS Analysis 1) # of Sub-problems 2) Running time to fill 3) Extraction 4) Running time to extract - Answers 1) n 2) O(n^2) 3) max(L) 4) O(n) LCS Sub-problem - Answers for i & j where 0 = i = n & 0 = j = m: Let L(i,j) = Length of LCS in X[1]...X[i], Y[1]...Y[j] LCS Recurrence - Answers L(0,j) = 0, L(i,0) = 0 For i = 1, j = 1: L(i,j) = { if x[i] != y[j]: max{L(i-1, j), L(i, j-1)} else: 1 + L(i-1, j-1) LCS Analysis 1) # of Sub-problems 2) Running time to fill 3) Extraction 4) Running time to extract - Answers 1) nm 2) O(nm) 3) L(n,m) 4) O(1) Knapsack: No repetition Sub-problem - Answers for i & b where 0 = i = n & 0 = b = B: let K(i,B) = max value achievable using a subset of objects 1,...,i and a total weight = b Knapsack: No repetition Recurrence - Answers Base Cases: K(0,b) = 0 and K(i, 0) = 0 If w[i] = b: then K(i,b) = max{v[i]+K(i-1, b-w[i]), K(i-1, b)} else: K(i,b) = K(i-1, b) Knapsack: No repetition Analysis 1) # of Sub-problems 2) Running time to fill 3) Extraction 4) Running time to extract - Answers 1) nB 2) O(nB) 3) K(n,B) 4) O(1) Knapsack: Repetition Sub-problem (Simple) - Answers K(b) = max value attainable using weights = b Knapsack: Repetition Recurrence (Simple) - Answers K(b) = Max[i]{v[i] + K(b-w[i]) : 1 = i = n, w[i] = b} Knapsack: Repetition Analysis (Simple) 1) # of Sub-problems 2) Running time to fill 3) Extraction 4) Running time to extract - Answers 1) B 2) O(NB) 3) K(B) 4) O(1) Master Therom - Answers T(n) = aT([n/b]) + O(n^d) Master Therom: if d log_b(a) - Answers O(n^d) Master Therom: if d = log_b(a) - Answers O(n^d * log(n)) Master Therom: if d log_b(a) - Answers O(N^log_b(a)) Windowing/CMM Analysis 1) # of Sub-problems 2) Running time to fill 3) Extraction 4) Running time to extract - Answers 1) O(n^2) 2) O(n^3) 3) min(C) 4) O(n^2) Windowing/CMM Subproblem - Answers for i & j where 1 = i = j = n let C(i,j) = min cost for computing A[i]xA[i+1]x...xA[j] Windowing/CMM Recurrence with Split - Answers Base Case: C(i,i) = 0 C(i,j) = min(l){C(i,l) + C(l+1, j) + M[i-1]M[l]M[j] : i = l = j-1 } DP: Dictionary Lookup - Subproblem - Answers Windowing: Let T(i) = TRUE if S[1], s[2], ... , s[i] can be reconstructed as a sequence of valid words. DP: Dictionary Lookup - Recursion - Answers T(0) = TRUE T(i) = TRUE if any [T(j-1 and dict(s[j..i])] for 1 = j = i = FALSE otherwise where 1 = i = n DP: Dictionary Lookup - Analysis - Answers # SP: O(n) RTF: O(n^2) Extraction: T(n) RTE: O(1) DP: Longest Common SubSTRING - Subproblem - Answers T(i,j) = length of the longest common substring for x and y, ending with x[i] = y[i] DP: Longest Common SubSTRING - Recurrence - Answers T(i, 0) = 0 where 0 = i = n T(0, j) = 0 where 1 = j = m T(i, j) = 1 + T(i-1, j-1) if x[i] = y[j] = 0 if x[i] != y[j] where 1 = i = n where 1 = j = m DP: Longest Common SubSTRING - Analysis - Answers # of Subprobs: O(nm) rtf: O(nm) extraction: max(T(*,*)) rte: O(nm) DP: Making change: II Limited - Subproblem - Answers T(i, j) = max sum at most j using a subset of coins x[1], x[2], ..., x[i] DP: Making change: II Limited - Recurrence - Answers T(i, 0) = 0 for 0 = i = n T(0,j) = 0 for 1 = j = v T(i,j) = max{T(i-1, j), x[i] + T(i-1, j-x[i])} If x[i] = j = T(i-1, j) if x[i] j where 1 = i = n where 1 = j = v DP: Making change: II Limited - Analysis - Answers # of subproblems: O(nv) rtf: O(nv) extraction: True if v = T(n,v), else FALSE rte: O(1) DP: Making change: K Unlimited- Subproblem - Answers T(j) = minimum number of coins needed to make the exact value j using a multiset of coins x[1], x[2], ... ,x[n] if possible, or infinity otherwise DP: Making change: K Unlimited- Recurrence - Answers T(0) = 0 T(j) = min {1 + T(j-x[i]) : 1 = i = n if x[i] = j } = inf otherwise where 1 = j = v DP: Making change: K Unlimited- Analysis - Answers # of Subproblems: O(v) RTF: O(vn) Extraction: TRUE if T(v) = k, else FALSE RTE: O(1) DP: Optimal Binary Search Tree - Subproblem - Answers T(i, j) = minimum cost to look up words i, i+1, ..., j DP: Optimal Binary Search Tree - Recurrence - Answers T(i, i) = p[i], where 1 = i = n T(i, i-1) = 0, where 1 = i = n+1 T(i, j) = sum{p[i...j]} + min{T(i, k-1) + T(k+1, j) : i = k = j} where 1 = i j = n DP: Optimal Binary Search Tree - Analysis - Answers # of subproblems: O(n^2) rtf: O(n^3) Extraction: T(1, n) RTE: O(1) DP: Gene Alignment - Subproblem - Answers T(i, j) = maxiumum score of x[1], x[2], ..., x[i] and y[1], y[2], ..., y[j] DP: Gene Alignment - Recurrence - Answers T(0, 0) = 0 T(i, 0) = T(i-1, 0) + δ(x[i], -), where 1 = i = n T(0, j) = T(0, j-1) + δ(-, y[j]), where 1 = j = m T(i, j) = max { T(i-1, j-1) + δ(x[i], y[j]), T(i-1, j) + δ(x[i], -), T(i, j-1) + δ(-, y[j])} where 1 = i = n where 1 = j = m DP: Gene Alignment - Analysis - Answers # of subproblems: O(nm) RTF: O(nm) Extraction: T(n,m) RTE: O(1) Divide and Conquer Fast Multiplication - Answers Get the alg D&C: Infinite Array A[.] - Algorithm - Answers Starting with index =1 and doubling the index on each iteration, we continue until A[index] = x. This efficiently finds an upper bound for our target value using an exponential search. Perform a black box Binary Search from A[1] to A[index] for the target value of x, and return the result of that search directly. D&C: Infinite Array A[.] - Justification of Correctness - Answers The array is sorted, which allows the use of both the exponential search and the binary search. Bydoubling the index at each step, we can deterministically find an upper bound that must be eitherinfinity or a value greater than the target value we are trying to find. We know the search for thisupper bound must terminate because we exceed either the target value or