CS 6515 EXAM 1
PREP/COMPREHENSIVE GUIDE
ACTUAL EXAM QUESTIONS WITH
COMPLETE SOLUTION GUIDE (A+
GRADED 100% VERIFIED) LATEST
VERSION 2025!!
Save
Terms in this set (74)
k(0) = 0
Knapsack for w = 1 to W:
without if w_j >w: k(w,j) = k(w, j - 1)
repetition else: K(w,j) = max{K(w, j -1),K(w - w_j, j
-1) + v_i}
, knapsack repeat(w_i....w_n, w_i... w_n,
B)
knapsack with k(0) = 0
repetition 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)
LIS(a_1.... a_n)
for i = 1 to n
L(i) = 1
for j = 1 to n -1
Longest
if a_j < a_i & L(i) < 1 + L( j)
Increasing
L(i) = 1 + L( j)
Subsequence
max = 1
for i = 2 to n
if L(i) > L(max) then max = i
return(L(max))
, 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
longest common
for j = 1 to n
subsequence
if X_i == Y_j:
algo
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
what is Big oh of O(n**2)
LCS?
what is big Oh of O(mn)
longest common
substring?
PREP/COMPREHENSIVE GUIDE
ACTUAL EXAM QUESTIONS WITH
COMPLETE SOLUTION GUIDE (A+
GRADED 100% VERIFIED) LATEST
VERSION 2025!!
Save
Terms in this set (74)
k(0) = 0
Knapsack for w = 1 to W:
without if w_j >w: k(w,j) = k(w, j - 1)
repetition else: K(w,j) = max{K(w, j -1),K(w - w_j, j
-1) + v_i}
, knapsack repeat(w_i....w_n, w_i... w_n,
B)
knapsack with k(0) = 0
repetition 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)
LIS(a_1.... a_n)
for i = 1 to n
L(i) = 1
for j = 1 to n -1
Longest
if a_j < a_i & L(i) < 1 + L( j)
Increasing
L(i) = 1 + L( j)
Subsequence
max = 1
for i = 2 to n
if L(i) > L(max) then max = i
return(L(max))
, 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
longest common
for j = 1 to n
subsequence
if X_i == Y_j:
algo
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
what is Big oh of O(n**2)
LCS?
what is big Oh of O(mn)
longest common
substring?
