CS6515 - Algorithms- Exam 1 Complete Questions And Solutions

CS6515 - Algorithms- Exam 1 Complete Questions And Solutions DC: Geometric Series - ANSWER -Given r = common ratio and a = first term in series => a + ar + ar^2 + ar^3 + ... + ar^(n-1) => a * [(1 - r^n) / (1-r)] DC: Arithmetic Series - ANSWER -Given d = common difference and a = first term in series => a + (a + d) + (a + 2d) + ... + (a + (n-1)d Sum = n/2 * [2*a + (n-1)d] DC: Solving Recurrences - Master Theorem - ANSWER -If T(n) = aT([n/b]) + O(n^d) for constants a>0, b>1, d>=0: T(n) = { O(n^d) if d > logb(a) O((n^d)logn) if d = logb(a) O(n^(logb(a))) if d < logb(a) } Nth roots of Unity - ANSWER -(1, 2*PI*j/n) for j = 0, 1, ..., n-1 *Around the Unit Circle! Steps to solve for FFT - ANSWER -1) Write out Matrix Coefficient Form based on n (size of input) Mn(w) = [ 1 1 ... 1 1 w ... w^n-1 ... 1 w^n-1 ... w^((n-1)*(n-1)) ] 2) Find value for w = e^(2*PI*i)/n, Substitute in Mn(w). 3) For the input coefficients into nx1 matrix. I.E. [4 0 1 1], let known as B. 4) Evaluate FFT: a) FFT of Input = Mn(w) x B b) Inverse FFT of Input = 1/n * Mn(w^-1) x B Euler's Formula - ANSWER -e^ix = cosx + isinx Imaginary Number Multiples - ANSWER -i = i, i^2 = -1, i^3 = -i, i^4 = 1 i = -i, i^2 = -1, i^3 = i, i^4 = 1 Omega(w) - ANSWER -w = (1, 2*PI / n) = e^(2*PI*i/n) DC Algorithms and Runtimes (6) - ANSWER -MergeSort: O(nlogn) - Split the input array into two halves and recursively sort and merge at the end. QuickSort: O(nlogn) - Same splitting strategy as MergeSort. QuickSelect: O(n) BinarySearch(S, x): O(logn) - Split array into 2 sub-arrays, if x < current mid, recursively split and search the left sub-array. Otherwise, recursively split and search the right subarray. Median: O(nlogn) Selection(S, x): O(n) - Split the input array into 3 sub-arrays where elements are < x, > x and = x. Recurse until x is found or not. FFT and Inverse FFT Formulas - ANSWER -FFT = Mn(w) x B Inverse FFT = 1/n Mn(w^-1) x B logb(b^x) - ANSWER -x b^(logb(x)) - ANSWER -x logb(b) - ANSWER -1 loga (uv) - ANSWER -loga (u) + loga (v) loga (u / v) - ANSWER -loga (u) - loga (v) loga (u)^n - ANSWER -n * loga (u) Knapsack without repetition - ANSWER -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 - 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