CS 6515 EXAM 1 KNOWLEDGE ASSESSMENT
WITH ANSWER KEY
◉ 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
WITH ANSWER KEY
◉ 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
