CS6515 ALGORITHMS ACTUAL
CERTIFICATION ONE 2026 ANSWERS
GRADED A+
⩥ DP: Types of Subproblems (4). Answer: Input = x1, x2, ..., xn
1) Subproblem = x1, x2, ..., xi ; O(n)
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.
⩥ 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).
CERTIFICATION ONE 2026 ANSWERS
GRADED A+
⩥ DP: Types of Subproblems (4). Answer: Input = x1, x2, ..., xn
1) Subproblem = x1, x2, ..., xi ; O(n)
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.
⩥ 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).
