CS6515 ALGORITHMS EXAM SCRIPT 1 2026
SOLVED QUESTIONS AND VERIFIED ANSWERS
◉ Longest Increasing Subsequence. 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. 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:
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. Answer:
◉ what is Big oh of LCS?. Answer: O(n**2)
◉ what is big Oh of longest common substring?. Answer: O(mn)
◉ what is important to remember when calculating longest common
subsequence as opposed to substring?. Answer: 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.
Answer:
◉ 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?. Answer:
https://www.youtube.com/watch?v=Y0ZqKpToTic
◉ how to calculate longest increasing substring. Try it using the
following:
541208563. Answer: 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?.
Answer: - 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?. Answer: increasing for sure!!! O(n**2)
◉ explain minimum distance algorithm: perform it using
"abcdef"
and
"a3ced". Answer: the minimum number of edits and deletes to have
to two strings match
SOLVED QUESTIONS AND VERIFIED ANSWERS
◉ Longest Increasing Subsequence. 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. 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:
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. Answer:
◉ what is Big oh of LCS?. Answer: O(n**2)
◉ what is big Oh of longest common substring?. Answer: O(mn)
◉ what is important to remember when calculating longest common
subsequence as opposed to substring?. Answer: 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.
Answer:
◉ 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?. Answer:
https://www.youtube.com/watch?v=Y0ZqKpToTic
◉ how to calculate longest increasing substring. Try it using the
following:
541208563. Answer: 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?.
Answer: - 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?. Answer: increasing for sure!!! O(n**2)
◉ explain minimum distance algorithm: perform it using
"abcdef"
and
"a3ced". Answer: the minimum number of edits and deletes to have
to two strings match
