Cs6515 - Algorithms- Exam 1 Complete Questions And Solutions

loga (u / v) {Ans: loga (u) - loga (v)}Euler's Formula {Ans: e^ix = cosx + isinx}Omega(w) {Ans: w = (1, 2*PI / n) = e^(2*PI*i/n)}Steps to solve for FFT {Ans: 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}DC: Solving Recurrences - Master Theorem {Ans: 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) }}loga (uv) {Ans: loga (u) + loga (v)}Nth roots of Unity {Ans: (1, 2*PI*j/n) for j = 0, 1, ..., n-1 *Around the Unit Circle!}Steps to solve a Dynamic Programming Problem {Ans: 1. Define the Input and Output. 2. Define entries in table, i.e. T(i) or T(i, j)