- | Page
CS6515 - ALGORITHMS- EXAM 1
COMPLETE QUESTIONS A ND
SOLUTIONS
Question 1: What are the steps to solve a Dynamic
Programming Problem?
CORRECT ANSWER: 1. Define the Input and Output.
- Define entries in table, i.e. T(i) or T(i, j) is...
- Define a Recurrence relationship - Based on a
subproblem to the main problem. (hint: use a prefix of the
original input 1 < i < n).
- Define the Pseudocode.
- Define the Runtime of the algorithm. Use Time
Function notation here => T(n) = T(n/2) + 1...
Question 2: What are the types of subproblems in
Dynamic Programming?
CORRECT ANSWER: Input = x1, x2, ..., xn
1) Subproblem = x1, x2, ..., xi ; O(n)
- | Page
2) Subproblem = xi, xi+1, ..., xj ; O(n^2) Input = x1, x2, ..., xn; y1, y2, ..., ym 1) Subproblem = x1, x2, ..., xi; y1, y2, ..., yj ; O(mn) Input = Rooted Binary Tree 1) Subproblem = Smaller rooted binary tree inside the Input.
Question 3: What is the formula for a Geometric Series?
CORRECT 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)]
Question 4: What is the formula for an Arithmetic Series?
CORRECT ANSWER: Given d = common difference
and a = first term in series => a + (a + d) + (a + 2d) + ... + (a + (n-1)d)
- | Page
Sum = n/2 [2a + (n-1)d]
Question 5: How do you solve recurrences using the
Master Theorem?
CORRECT 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) }
Question 6: What are the Nth roots of Unity?
CORRECT ANSWER: (1, 2PIj/n) for j = 0, 1, ..., n-1
*Around the Unit Circle!
Question 7: What are the steps to solve for FFT?
- | Page
CORRECT ANSWER: 1) Write out Matrix Coefficient
Form based on n (size of input) Mn(w) = [ 1 1 ... 1
- w ... w^n-1
- w^n-1 ... w^((n-1)*(n-1)) ]
...
2) Find value for w = e^(2PIi)/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
Question 8: What is Euler's Formula?
CORRECT ANSWER: e^ix = cosx + isinx
Question 9: What are the multiples of the imaginary
number i?