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
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
