Cs 6515 Exam 1 Comprehensive Study Guide

CS 6515 EXAM 1 COMPREHENSIVE STUDY
GUIDE


◉ knapsack with repetition.
Answer: 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.
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