10/14/25, 6:22 PM CS6515 - Algorithms- Exam 1 2025 (Actual Exam) Questions with verified Answers (Latest Update 2025) UPDATE!! Flashcards | …
CS6515 - Algorithms- Exam 1 2025 (Actual Exam)
Questions with verified Answers (Latest Update
2025) UPDATE!!
Save
Terms in this set (92)
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
Steps to solve a Dynamic subproblem to the main problem. (hint: use a prefix of
Programming Problem 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...
Input = x1, x2, ..., xn
1) Subproblem = x1, x2, ..., xi ; O(n)
2) Subproblem = xi, xi+1, ..., xj ; O(n^2)
DP: Types of Subproblems Input = x1, x2, ..., xn; y1, y2, ..., ym
(4) 1) Subproblem = x1, x2, ..., xi; y1, y2, ..., yj ; O(mn)
Input = Rooted Binary Tree
1) Subproblem = Smaller rooted binary tree inside the
Input.
https://quizlet.com/1092618707/cs6515-algorithms-exam-1-2025-actual-exam-questions-with-verified-answers-latest-update-2025-update-flash-cards… 1/13
, 10/14/25, 6:22 PM CS6515 - Algorithms- Exam 1 2025 (Actual Exam) Questions with verified Answers (Latest Update 2025) UPDATE!! Flashcards | …
Given r = common ratio and a = first term in series
=> a + ar + ar^2 + ar^3 + ... + ar^(n-1)
DC: Geometric Series
=> a * [(1 - r^n) / (1-r)]
Given d = common difference and a = first term in
series => a + (a + d) + (a + 2d) + ... + (a + (n-1)d
DC: Arithmetic Series
Sum = n/2 [2a + (n-1)d]
If T(n) = aT([n/b]) + O(n^d) for constants a>0, b>1, d>=0:
T(n) = {
DC: Solving Recurrences -
O(n^d) if d > logb(a)
Master Theorem
O((n^d)logn) if d = logb(a)
O(n^(logb(a))) if d < logb(a)
}
(1, 2PIj/n) for j = 0, 1, ..., n-1
Nth roots of Unity
*Around the Unit Circle!
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^(2PIi)/n, Substitute in Mn(w).
Steps to solve for FFT
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 e^ix = cosx + isinx
Imaginary Number i = i, i^2 = -1, i^3 = -i, i^4 = 1
Multiples i = -i, i^2 = -1, i^3 = i, i^4 = 1
https://quizlet.com/1092618707/cs6515-algorithms-exam-1-2025-actual-exam-questions-with-verified-answers-latest-update-2025-update-flash-cards… 2/13
CS6515 - Algorithms- Exam 1 2025 (Actual Exam)
Questions with verified Answers (Latest Update
2025) UPDATE!!
Save
Terms in this set (92)
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
Steps to solve a Dynamic subproblem to the main problem. (hint: use a prefix of
Programming Problem 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...
Input = x1, x2, ..., xn
1) Subproblem = x1, x2, ..., xi ; O(n)
2) Subproblem = xi, xi+1, ..., xj ; O(n^2)
DP: Types of Subproblems Input = x1, x2, ..., xn; y1, y2, ..., ym
(4) 1) Subproblem = x1, x2, ..., xi; y1, y2, ..., yj ; O(mn)
Input = Rooted Binary Tree
1) Subproblem = Smaller rooted binary tree inside the
Input.
https://quizlet.com/1092618707/cs6515-algorithms-exam-1-2025-actual-exam-questions-with-verified-answers-latest-update-2025-update-flash-cards… 1/13
, 10/14/25, 6:22 PM CS6515 - Algorithms- Exam 1 2025 (Actual Exam) Questions with verified Answers (Latest Update 2025) UPDATE!! Flashcards | …
Given r = common ratio and a = first term in series
=> a + ar + ar^2 + ar^3 + ... + ar^(n-1)
DC: Geometric Series
=> a * [(1 - r^n) / (1-r)]
Given d = common difference and a = first term in
series => a + (a + d) + (a + 2d) + ... + (a + (n-1)d
DC: Arithmetic Series
Sum = n/2 [2a + (n-1)d]
If T(n) = aT([n/b]) + O(n^d) for constants a>0, b>1, d>=0:
T(n) = {
DC: Solving Recurrences -
O(n^d) if d > logb(a)
Master Theorem
O((n^d)logn) if d = logb(a)
O(n^(logb(a))) if d < logb(a)
}
(1, 2PIj/n) for j = 0, 1, ..., n-1
Nth roots of Unity
*Around the Unit Circle!
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^(2PIi)/n, Substitute in Mn(w).
Steps to solve for FFT
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 e^ix = cosx + isinx
Imaginary Number i = i, i^2 = -1, i^3 = -i, i^4 = 1
Multiples i = -i, i^2 = -1, i^3 = i, i^4 = 1
https://quizlet.com/1092618707/cs6515-algorithms-exam-1-2025-actual-exam-questions-with-verified-answers-latest-update-2025-update-flash-cards… 2/13
