CS6515 ALGORITHMS ACTUAL EXAM SHEET 2025/2026
QUESTIONS WITH ANSWERS GRADED A+
✔✔what is important to remember when calculating longest common subsequence as
opposed to substring? - ✔✔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 - ✔✔
✔✔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? - ✔✔https://www.youtube.com/watch?v=Y0ZqKpToTic
✔✔how to calculate longest increasing substring. Try it using the following:
541208563 - ✔✔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? - ✔✔- 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? - ✔✔increasing for sure!!! O(n**2)
✔✔explain minimum distance algorithm: perform it using
"abcdef"
and
"a3ced" - ✔✔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? - ✔✔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? - ✔✔-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 - ✔✔O(n**3)
✔✔WHat is the algorithm for merge sort? And what is its running time? - ✔✔
✔✔What are the components of the master theorem and when can you use it? - ✔✔
✔✔In terms of the master theorem, what would be a result that would provide O(nlogn)
time? - ✔✔
✔✔Consider w_16. For what power k is (ω_16)^k = -1? - ✔✔(ω_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? -
✔✔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? - ✔✔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? - ✔✔k == 15
This is because (ω_16)^16 == (ω_16)^0
✔✔For what power k is (ω_16)^k = (ω_8)^2? - ✔✔k == 4
✔✔In terms of radians, what is the imaginary axis? - ✔✔
✔✔what is the significance of z = a + bi - ✔✔it can describe a point in a cartesian plane
✔✔How do you convert the cartesian coordinates (a,b) to polar coordinates? - ✔✔(a,b)
= rcos(theta), rsin(theta)
✔✔what is euler's formula? - ✔✔cos(theta) + isin(theta) = e^(i*theta)
✔✔what degree is -1 in terms of polar coordinates? what are the polar coordinates? -
✔✔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? - ✔✔- (r,theta)
- (r, theta) * (1,pie)
QUESTIONS WITH ANSWERS GRADED A+
✔✔what is important to remember when calculating longest common subsequence as
opposed to substring? - ✔✔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 - ✔✔
✔✔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? - ✔✔https://www.youtube.com/watch?v=Y0ZqKpToTic
✔✔how to calculate longest increasing substring. Try it using the following:
541208563 - ✔✔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? - ✔✔- 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? - ✔✔increasing for sure!!! O(n**2)
✔✔explain minimum distance algorithm: perform it using
"abcdef"
and
"a3ced" - ✔✔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? - ✔✔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? - ✔✔-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 - ✔✔O(n**3)
✔✔WHat is the algorithm for merge sort? And what is its running time? - ✔✔
✔✔What are the components of the master theorem and when can you use it? - ✔✔
✔✔In terms of the master theorem, what would be a result that would provide O(nlogn)
time? - ✔✔
✔✔Consider w_16. For what power k is (ω_16)^k = -1? - ✔✔(ω_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? -
✔✔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? - ✔✔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? - ✔✔k == 15
This is because (ω_16)^16 == (ω_16)^0
✔✔For what power k is (ω_16)^k = (ω_8)^2? - ✔✔k == 4
✔✔In terms of radians, what is the imaginary axis? - ✔✔
✔✔what is the significance of z = a + bi - ✔✔it can describe a point in a cartesian plane
✔✔How do you convert the cartesian coordinates (a,b) to polar coordinates? - ✔✔(a,b)
= rcos(theta), rsin(theta)
✔✔what is euler's formula? - ✔✔cos(theta) + isin(theta) = e^(i*theta)
✔✔what degree is -1 in terms of polar coordinates? what are the polar coordinates? -
✔✔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? - ✔✔- (r,theta)
- (r, theta) * (1,pie)
