CS 6515 Exam 1 ACTUAL EXAM QUESTIONS WITH COMPLETE
cs6515 Exam 1 Prep
SOLUTION GUIDE (A+ GRADED 100% VERIFIED) LATEST VERSION
Study online at https://quizlet.com/_6ufsoq
2025!!
1. Knapsack without repetition 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}
2. knapsack with repetition 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)
3. Longest Increasing Subsequence 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))
4. longest common subsequence algo 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:
, cs6515 Exam 1 Prep
Study online at https://quizlet.com/_6ufsoq
L(i,j) = max(L(i - 1, j),L(i,j-1)
return(L(i,j)
5. longest common substring
6. what is Big oh of LCS? O(n**2)
7. what is big Oh of longest common substring? O(mn)
8. what is important to remember when calcu- substring is very diagonal and plus 1
lating longest common subsequence as op- subsequence you have to use a max
posed to substring? function
9. Perform longest common substring and sub-
sequence on:
"abcdaf"
"3bcdf"
What are the recurrences? write down the
algorithm and results
10. if you are presented with a coins (1,5,6,8) and https://www.youtube.com/watch?v=Y0ZqKp
your knapsack is k = 11, what is the minimum ToTic
number of coins, what would be the compu-
tational time, and what is the recurrence?
11. how to calculate longest increasing sub- It should only require two separate
string. Try it using the following: loops:
541208563 one to loop to go through to calculate the
values
- then a separate loop to figure out what
the max is... and then return the max
12. what do you need to remember when it - you are work with one array
comes to lI subsequence? - you fill everything out with 1s first based
cs6515 Exam 1 Prep
SOLUTION GUIDE (A+ GRADED 100% VERIFIED) LATEST VERSION
Study online at https://quizlet.com/_6ufsoq
2025!!
1. Knapsack without repetition 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}
2. knapsack with repetition 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)
3. Longest Increasing Subsequence 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))
4. longest common subsequence algo 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:
, cs6515 Exam 1 Prep
Study online at https://quizlet.com/_6ufsoq
L(i,j) = max(L(i - 1, j),L(i,j-1)
return(L(i,j)
5. longest common substring
6. what is Big oh of LCS? O(n**2)
7. what is big Oh of longest common substring? O(mn)
8. what is important to remember when calcu- substring is very diagonal and plus 1
lating longest common subsequence as op- subsequence you have to use a max
posed to substring? function
9. Perform longest common substring and sub-
sequence on:
"abcdaf"
"3bcdf"
What are the recurrences? write down the
algorithm and results
10. if you are presented with a coins (1,5,6,8) and https://www.youtube.com/watch?v=Y0ZqKp
your knapsack is k = 11, what is the minimum ToTic
number of coins, what would be the compu-
tational time, and what is the recurrence?
11. how to calculate longest increasing sub- It should only require two separate
string. Try it using the following: loops:
541208563 one to loop to go through to calculate the
values
- then a separate loop to figure out what
the max is... and then return the max
12. what do you need to remember when it - you are work with one array
comes to lI subsequence? - you fill everything out with 1s first based
