Cs6515 Exam 1 Prep || 100% Correct Answers.

Cs6515 Exam 1 Prep || 100% Correct Answers.
Knapsack without repetition correct 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 correct 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 correct 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 correct 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 correct answers

what is Big oh of LCS? correct answers O(n**2)

what is big Oh of longest common substring? correct answers O(mn)

what is important to remember when calculating longest common subsequence as opposed to
substring? correct 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 correct 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? correct
answers https://www.youtube.com/watch?v=Y0ZqKpToTic

how to calculate longest increasing substring. Try it using the following:
541208563 correct 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? correct 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? correct
answers increasing for sure!!! O(n**2)

explain minimum distance algorithm: perform it using
"abcdef"
and
"a3ced" correct 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? correct 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? correct 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 correct answers O(n**3)

WHat is the algorithm for merge sort? And what is its running time? correct answers

What are the components of the master theorem and when can you use it? correct answers

In terms of the master theorem, what would be a result that would provide O(nlogn) time?
correct answers

Consider w_16. For what power k is (ω_16)^k = -1? correct answers (ω_16)^8;