1|Page
CS 6515 EXAM 1 PREP|COMPLETE
EXAM SET- Q&A 2026
Knapsack without repetition - correct-answer -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 - correct-answer -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 - correct-answer -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)
max = 1
for i = 2 to n
if L(i) > L(max) then max = i
return(L(max))
longest common subsequence algo - correct-answer -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:
, 2|Page
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 - correct-answer -
what is Big oh of LCS? - correct-answer -O(n**2)
what is big Oh of longest common substring? - correct-answer -O(mn)
what is important to remember when calculating longest common
subsequence as opposed to substring? - correct-answer -substring is very
diagonal and plus 1
subsequence you have to use a max function
Why are off diagonal entries not equal to one? - correct-answer -In the
original, it is (ω_n)^k * (ω_n)^-k == (ω_n)^0 == 1
However, the off-diagonal entries are:
(ω_n)^k * (ω_n)^-j == (ω_n)^(k-j); so result of 1 is definitely not guaranteed
in degrees, what are the values of the following:
cos(0)
cos(90)
cos(180)
cos(270)
cos(360)
Do the same for sin() - correct-answer -a.) 1
b.) 0
c.) -1
d.) 0
e.) 1
CS 6515 EXAM 1 PREP|COMPLETE
EXAM SET- Q&A 2026
Knapsack without repetition - correct-answer -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 - correct-answer -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 - correct-answer -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)
max = 1
for i = 2 to n
if L(i) > L(max) then max = i
return(L(max))
longest common subsequence algo - correct-answer -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:
, 2|Page
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 - correct-answer -
what is Big oh of LCS? - correct-answer -O(n**2)
what is big Oh of longest common substring? - correct-answer -O(mn)
what is important to remember when calculating longest common
subsequence as opposed to substring? - correct-answer -substring is very
diagonal and plus 1
subsequence you have to use a max function
Why are off diagonal entries not equal to one? - correct-answer -In the
original, it is (ω_n)^k * (ω_n)^-k == (ω_n)^0 == 1
However, the off-diagonal entries are:
(ω_n)^k * (ω_n)^-j == (ω_n)^(k-j); so result of 1 is definitely not guaranteed
in degrees, what are the values of the following:
cos(0)
cos(90)
cos(180)
cos(270)
cos(360)
Do the same for sin() - correct-answer -a.) 1
b.) 0
c.) -1
d.) 0
e.) 1
