CS6515 EXAM 1 PREP QUESTIONS AND ANSWERS GRADED A+ 2026

CS6515 EXAM 1 PREP QUESTIONS AND
ANSWERS GRADED A+ 2026




Knapsack without repetition - ANS k(0) = 0

for w = 1 to W:

if w_j >w: k(w,j) = k(w, j - 1)

else: K(w,j) = max{K(w, j -1),K(w - w_j, j -1) + v_i}



knapsack with repetition - ANS knapsack repeat(w_i....w_n, w_i... w_n, B)

k(0) = 0

for i = 1 to n

if w_i <= b & k(b) <v_i + K(b-w_i)

then k(b) = v_i + K(b-w_i)



Longest Increasing Subsequence - ANS LIS(a_1.... a_n)

for i = 1 to n

L(i) = 1

for j = 1 to n -1

if a_j < a_i & L(i) < 1 + L(j)

L(i) = 1 + L(j)


@COPYRIGHT 2026/2027 ALLRIGHTS RESERVED 1

, max = 1

for i = 2 to n

if L(i) > L(max) then max = i

return(L(max))



longest common subsequence algo - ANS LCS(X,Y)

for i = 0 to n: L(i, 0) = 0

for j = 0 to n: L(0,j) = 0

for i = 1 to n

for j = 1 to n

if X_i == Y_j:

L(i,j) = L(i - 1, j - 1) + 1

else:

L(i,j) = max(L(i - 1, j),L(i,j-1)

return(L(i,j)



longest common substring - ANS



what is Big oh of LCS? - ANS O(n**2)



what is big Oh of longest common substring? - ANS O(mn)



what is important to remember when calculating longest common subsequence as opposed to
substring? - ANS substring is very diagonal and plus 1

subsequence you have to use a max function



@COPYRIGHT 2026/2027 ALLRIGHTS RESERVED 2