CS6515 - Exam 1 Complete Questions And Answers

CS6515 - Exam 1 Complete Questions And Answers What are the dimensions of the array for solving the knapsack problem WITHOUT repetition? - ANSWER -2-D array What is the recurrence for knapsack w/o repetition? - ANSWER -K(i,b) = max((vi + K(i-1,biwi)),K(i-1,b) if wi < b) K(i,b) = K(i-1,b) otherwise What are the base cases for knapsack w/o repetion? - ANSWER -K(0,b) = 0 & K(i,0) = 0 which is when we have no objects and no knapsack, respectively What is the running time of the knapsack w/o repetition algorithm? - ANSWER -It is pseudopolynomial O(nB) What are the dimensions of the array for solving the knapsack problem WITH repetition? - ANSWER -1-D array What is the recurrence for knapsack w/ repetition? - ANSWER -K(b) = max(vi + K(b-wi)) for all items i with a weight less than or equal to current capacity b What is the running time of the knapsack w/ repetition? - ANSWER -O(Bn) What is the time complexity for multiplying two matrices A (dimensions n x m) and B (dimensions m x k) - ANSWER -O(nmk) If we have n matrices, A1, A2... An how can we define each of their sizes? - ANSWER -mi-1 x mi since the inner dimensions of a matrix product must match Whats the most likely base algorithm to use if problem only has a single array? - ANSWER - LIS What is the most likely algorithm if problem is comparing to iself - ANSWER -LIS What is the most likely alg if problem only looks back one elemnt at a time (not a window, or a bag) - ANSWER -LIS What are the two most common LIS variations? - ANSWER -O(n) lookback O(1) lookback What is most likely alg if problem is comparing between two arrays? - ANSWER -LCS What is most likely alg if problem is looking for something in common? - ANSWER -LCS Describe the process for LCS (substring variation) - ANSWER -Add 1 to L(i-1,j-1) and set to 0 otherwise. Solution is max(L) Describe the process for LCS (subsequence variation) - ANSWER -If ending characters are same: L(i-1,j-1) + 1 If ending characters are different: max{ L(i-1,j), L(i,j-1) } Solution is L(n,m) or L(n,n) What is most likely alg if problem is looking to minimize differences? - ANSWER -Edit Distance What is the most likely alg if the problem assigns some penalty to differences? - ANSWER - Edit Distance What is the most likely alg if problem assigns some points to matches? - ANSWER -Edit Distance What is the most likely alg if you are aligning two arrays? - ANSWER -Edit Distance What is the traditional size of subproblem table for an edit distance problem? - ANSWER -2-D What is the most likely alg if your problem needs to check if something can fit or can add up to - ANSWER -Knapsack What is the most likely alg if your problem needs a max value for a specific budget - ANSWER -Knapsack What is the most likely alg if your problem needs to find the min budget needed for a specific value - ANSWER -Knapsack What are the two variations of knapsack? - ANSWER -1. With repeat of items 2. Without repeat of items What algorithm is used to determine the shortest path from each vertex to every other vertex? - ANSWER -Floyd-Warshall What algorithm is used to determine the shortest path from a single vertex to every other vertex? - ANSWER -Bellman-Ford What logarithmic property allows you to still use a shortest path algorithm even if edge weights are supposed to be multiplied? - ANSWER -Log(ab) = Log(a) + Log(b). Therefore you can take the log of every edge weight Runtime complexity of binary search - ANSWER -O(logn) Runtime complexity of Mergesort - ANSWER -O(nlogn)