CS6515 - ALGORITHMS- EXAM 1 | 98 QUESTIONS AND ANSWERS | 2026 UPDATE | WITH
COMPLETE SOLUTION
Steps to solve a Dynamic Programming Problem - (ANSWER)1. Define the Input and Output.
2. Define entries in table, i.e. T(i) or T(i, j) is...
3. Define a Recurrence relationship - Based on a subproblem to the main problem. (hint: use a prefix of
the original input 1 < i < n).
4. Define the Pseudocode.
5. Define the Runtime of the algorithm. Use Time Function notation here => T(n) = T(n/2) + 1...
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
,CS6515 - ALGORITHMS- EXAM 1 | 98 QUESTIONS AND ANSWERS | 2026 UPDATE | WITH
COMPLETE SOLUTION
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
, CS6515 - ALGORITHMS- EXAM 1 | 98 QUESTIONS AND ANSWERS | 2026 UPDATE | WITH
COMPLETE SOLUTION
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
COMPLETE SOLUTION
Steps to solve a Dynamic Programming Problem - (ANSWER)1. Define the Input and Output.
2. Define entries in table, i.e. T(i) or T(i, j) is...
3. Define a Recurrence relationship - Based on a subproblem to the main problem. (hint: use a prefix of
the original input 1 < i < n).
4. Define the Pseudocode.
5. Define the Runtime of the algorithm. Use Time Function notation here => T(n) = T(n/2) + 1...
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
,CS6515 - ALGORITHMS- EXAM 1 | 98 QUESTIONS AND ANSWERS | 2026 UPDATE | WITH
COMPLETE SOLUTION
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
, CS6515 - ALGORITHMS- EXAM 1 | 98 QUESTIONS AND ANSWERS | 2026 UPDATE | WITH
COMPLETE SOLUTION
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
