CS 6515 EXAM 1 PREP QUESTIONS WITH CORRECT ANSWERS LATEST UPDATE 2026
Knapsack without repetition - Answers 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 - Answers 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 - Answers 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 - Answers 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 - Answers
what is Big oh of LCS? - Answers O(n**2)
what is big Oh of longest common substring? - Answers O(mn)
what is important to remember when calculating longest common subsequence as opposed to
substring? - Answers substring is very diagonal and plus 1
subsequence you have to use a max function
Perform longest common substring and subsequence on:
"abcdaf"
"3bcdf"
What are the recurrences? write down the algorithm and results - Answers
if you are presented with a coins (1,5,6,8) and your knapsack is k = 11, what is the minimum number
of coins, what would be the computational time, and what is the recurrence? - Answers
https://www.youtube.com/watch?v=Y0ZqKpToTic
how to calculate longest increasing substring. Try it using the following:
541208563 - Answers It should only require two separate loops:
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
what do you need to remember when it comes to lI subsequence? - Answers - you are work with one
array
- you fill everything out with 1s first based on an array of same size
- the value is compared as well as the index is compared that is why (a_
what takes more time, longest increasing subsequence or longest common subsequence? - Answers
increasing for sure!!! O(n**2)
explain minimum distance algorithm: perform it using
"abcdef"
and
, "a3ced" - Answers the minimum number of edits and deletes to have to two strings match
- To figure it out you need to get the min{ T(i,j-1), T(i-1,j), and T(i-1, j-1)} + 1
In edit distance, what does each of the 4 operations do? - Answers T(i-1, j-1) + 1: diagonal, means
editing
T(i-1, j) + 1: up, means inserting
T(i, j-1) + 1: left, means deleting
How do you backtrack in edit distance? - Answers -start at the end
- if the index values are the same go diagonally
- if they are not, select the min of the diagonal up and left and then move
what is the running time of 2 dim matrix multiplication probelm - Answers O(n**3)
WHat is the algorithm for merge sort? And what is its running time? - Answers
What are the components of the master theorem and when can you use it? - Answers
In terms of the master theorem, what would be a result that would provide O(nlogn) time? - Answers
Consider w_16. For what power k is (ω_16)^k = -1? - Answers (ω_16)^8;
This is because it adds 180*(7/8) to (w_16)^1
Also, zero exponent makes 0, that would be (w_16)^0
Consider the n-th roots of unity for n =16. WHat is ω_16 in polar coordinates? - Answers At point 0,
polar coordinates are (r, theta) == (1, 2pie/2), if n = 16, then it becomes
- (1, 2pie/2)^16 == (1,2pie/16) == (1, pie/8)
Consider ω_16. For what power k is (ω_16)^k = -ω_16? - Answers it is (ω_n)^(1+(n/2)), in the case of
ω_16, n/2 = 8, (ω_16)^(1+8) = (ω_16)^9
Consider ω_16. For what power k (ω_16)^-1 = ω_16^k? In other words, for what k is ω_16 * (ω_16)^k
= 1? - Answers k == 15
This is because (ω_16)^16 == (ω_16)^0
For what power k is (ω_16)^k = (ω_8)^2? - Answers k == 4
In terms of radians, what is the imaginary axis? - Answers
what is the significance of z = a + bi - Answers it can describe a point in a cartesian plane
How do you convert the cartesian coordinates (a,b) to polar coordinates? - Answers (a,b) =
rcos(theta), rsin(theta)
what is euler's formula? - Answers cos(theta) + isin(theta) = e^(i*theta)
what degree is -1 in terms of polar coordinates? what are the polar coordinates? - Answers 180
degrees (positive starts on the right side)
- (1, pie)
- What is the radian coordinates which degree = 0?
- How would we add 180 degrees to it? - Answers - (r,theta)
- (r, theta) * (1,pie)
what is meant by roots of unity? - Answers 1 to be exact
- What numbers can be used when n = 4 for the roots of unity?
- Can you describe why that is the case? - Answers 1,-1,i, -i
At what point does the roots of unity repeat: essential, what does n equal in order to go 360 degrees?
- Answers 8, after 8 it repeats
why is omega increased in the exponent in order to traverse through the roots of unity? - Answers
theta = 2pie/n, and omega_n = (1, 2pie/n). Multiply them together to increase each step
what is the point on the roots of unity circle (using omega) where it is zero degrees? - Answers w^0_n
== 1
why is the point before ω^(n-1) right before w^n? - Answers This describes the step (whether it is in
4ths, 8ths, or 16ths, right before reaching radian 2piei/n, whether is the degree of "0")
what is another way to express -ω_16?? - Answers ω^9_16, this is because it moves 1/16 into the
lower left quartile
what use "n" to describe the subscript of ω? - Answers This is to help describe
what is the opposite of (w_n)^j? For example, (w_16)^2 - Answers 16/2 = 8; 2 + 8 = 10; therefore
opposite is:
(w_16)^10
if you want -ω_16 and you are currently at (w_16)^3, what is k in (w_16)^3+k? - Answers k = (n/2) + 1
- 3 == 6, k = 6!!
what is the derivation of the +/- property? - Answers It is the opposing sides of the nth roots of unity
(ω_n)^0 = -(ω_n)^(n/2)
Knapsack without repetition - Answers 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 - Answers 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 - Answers 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 - Answers 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 - Answers
what is Big oh of LCS? - Answers O(n**2)
what is big Oh of longest common substring? - Answers O(mn)
what is important to remember when calculating longest common subsequence as opposed to
substring? - Answers substring is very diagonal and plus 1
subsequence you have to use a max function
Perform longest common substring and subsequence on:
"abcdaf"
"3bcdf"
What are the recurrences? write down the algorithm and results - Answers
if you are presented with a coins (1,5,6,8) and your knapsack is k = 11, what is the minimum number
of coins, what would be the computational time, and what is the recurrence? - Answers
https://www.youtube.com/watch?v=Y0ZqKpToTic
how to calculate longest increasing substring. Try it using the following:
541208563 - Answers It should only require two separate loops:
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
what do you need to remember when it comes to lI subsequence? - Answers - you are work with one
array
- you fill everything out with 1s first based on an array of same size
- the value is compared as well as the index is compared that is why (a_
what takes more time, longest increasing subsequence or longest common subsequence? - Answers
increasing for sure!!! O(n**2)
explain minimum distance algorithm: perform it using
"abcdef"
and
, "a3ced" - Answers the minimum number of edits and deletes to have to two strings match
- To figure it out you need to get the min{ T(i,j-1), T(i-1,j), and T(i-1, j-1)} + 1
In edit distance, what does each of the 4 operations do? - Answers T(i-1, j-1) + 1: diagonal, means
editing
T(i-1, j) + 1: up, means inserting
T(i, j-1) + 1: left, means deleting
How do you backtrack in edit distance? - Answers -start at the end
- if the index values are the same go diagonally
- if they are not, select the min of the diagonal up and left and then move
what is the running time of 2 dim matrix multiplication probelm - Answers O(n**3)
WHat is the algorithm for merge sort? And what is its running time? - Answers
What are the components of the master theorem and when can you use it? - Answers
In terms of the master theorem, what would be a result that would provide O(nlogn) time? - Answers
Consider w_16. For what power k is (ω_16)^k = -1? - Answers (ω_16)^8;
This is because it adds 180*(7/8) to (w_16)^1
Also, zero exponent makes 0, that would be (w_16)^0
Consider the n-th roots of unity for n =16. WHat is ω_16 in polar coordinates? - Answers At point 0,
polar coordinates are (r, theta) == (1, 2pie/2), if n = 16, then it becomes
- (1, 2pie/2)^16 == (1,2pie/16) == (1, pie/8)
Consider ω_16. For what power k is (ω_16)^k = -ω_16? - Answers it is (ω_n)^(1+(n/2)), in the case of
ω_16, n/2 = 8, (ω_16)^(1+8) = (ω_16)^9
Consider ω_16. For what power k (ω_16)^-1 = ω_16^k? In other words, for what k is ω_16 * (ω_16)^k
= 1? - Answers k == 15
This is because (ω_16)^16 == (ω_16)^0
For what power k is (ω_16)^k = (ω_8)^2? - Answers k == 4
In terms of radians, what is the imaginary axis? - Answers
what is the significance of z = a + bi - Answers it can describe a point in a cartesian plane
How do you convert the cartesian coordinates (a,b) to polar coordinates? - Answers (a,b) =
rcos(theta), rsin(theta)
what is euler's formula? - Answers cos(theta) + isin(theta) = e^(i*theta)
what degree is -1 in terms of polar coordinates? what are the polar coordinates? - Answers 180
degrees (positive starts on the right side)
- (1, pie)
- What is the radian coordinates which degree = 0?
- How would we add 180 degrees to it? - Answers - (r,theta)
- (r, theta) * (1,pie)
what is meant by roots of unity? - Answers 1 to be exact
- What numbers can be used when n = 4 for the roots of unity?
- Can you describe why that is the case? - Answers 1,-1,i, -i
At what point does the roots of unity repeat: essential, what does n equal in order to go 360 degrees?
- Answers 8, after 8 it repeats
why is omega increased in the exponent in order to traverse through the roots of unity? - Answers
theta = 2pie/n, and omega_n = (1, 2pie/n). Multiply them together to increase each step
what is the point on the roots of unity circle (using omega) where it is zero degrees? - Answers w^0_n
== 1
why is the point before ω^(n-1) right before w^n? - Answers This describes the step (whether it is in
4ths, 8ths, or 16ths, right before reaching radian 2piei/n, whether is the degree of "0")
what is another way to express -ω_16?? - Answers ω^9_16, this is because it moves 1/16 into the
lower left quartile
what use "n" to describe the subscript of ω? - Answers This is to help describe
what is the opposite of (w_n)^j? For example, (w_16)^2 - Answers 16/2 = 8; 2 + 8 = 10; therefore
opposite is:
(w_16)^10
if you want -ω_16 and you are currently at (w_16)^3, what is k in (w_16)^3+k? - Answers k = (n/2) + 1
- 3 == 6, k = 6!!
what is the derivation of the +/- property? - Answers It is the opposing sides of the nth roots of unity
(ω_n)^0 = -(ω_n)^(n/2)
