CS6515 - ALGORITHMS- EXAM 1
2026/2027 ACTUAL QUESTIONS
WITH VERIFIED ANSWERS.
What does the following represent?
1.) A = M_n(ω_n)a = FFT(a,ω_n)
2.) how would you calculate the inverse?
3.) What would the function call be for the inverse? - correct
answer-1.) THis represents the result of a regular FFT function.
You are trying to get the function A or values by using the FFT
function with inputs the coefficients and ω_n
2.) a.) M_n(ω_n)^-1 *A = a
b.) (1/2) * M_n((ω_n)^-1)
3.) a = (1/2)FFT(A, (ω_n)^n-1)
What is the direction of roots of unity calculation with FFT vs
inverse FFT? - correct answer-inverse FFT ==
counterclockwise
FFT == clockwise
,For (ω_n)^2, what is its multiplicative inverse?
More precisely, for what power k is (ω_n)^k × (ω_n)^2 = 1? -
correct answer-k = (n-2)
It is whatever it takes to get to 0, which becomes one
so if applied: For (ω_16)^2 *(ω_16)^(16-2) == (ω_16)^16 ==
(ω_16)^0 == 1
1.) what is the product of the roots of unity?
2.) What about the sum?
3.) What is the sum of Aeven?
4.) what is the sum of Aodd? - correct answer-1.) if it is even,
then it is == 1
if it is odd, then it is == -1
2.) The sum is == 0. This is because (ω_n)^0 == 1 and
(ω_n)^(n/2) == -1. These cancel each other out. So if you go
through the whole sequence.. it eventually becomes 0.
, 3.) (n/2) * 1
4.) (n/2) * -1
Why are off diagonal entries not equal to one? - correct
answer-In the original, it is (ω_n)^k * (ω_n)^-k == (ω_n)^0 == 1
However, the off-diagonal entries are:
(ω_n)^k * (ω_n)^-j == (ω_n)^(k-j); so result of 1 is definitely not
guaranteed
in degrees, what are the values of the following:
cos(0)
cos(90)
cos(180)
cos(270)
cos(360)
Do the same for sin() - correct answer-a.) 1
b.) 0
2026/2027 ACTUAL QUESTIONS
WITH VERIFIED ANSWERS.
What does the following represent?
1.) A = M_n(ω_n)a = FFT(a,ω_n)
2.) how would you calculate the inverse?
3.) What would the function call be for the inverse? - correct
answer-1.) THis represents the result of a regular FFT function.
You are trying to get the function A or values by using the FFT
function with inputs the coefficients and ω_n
2.) a.) M_n(ω_n)^-1 *A = a
b.) (1/2) * M_n((ω_n)^-1)
3.) a = (1/2)FFT(A, (ω_n)^n-1)
What is the direction of roots of unity calculation with FFT vs
inverse FFT? - correct answer-inverse FFT ==
counterclockwise
FFT == clockwise
,For (ω_n)^2, what is its multiplicative inverse?
More precisely, for what power k is (ω_n)^k × (ω_n)^2 = 1? -
correct answer-k = (n-2)
It is whatever it takes to get to 0, which becomes one
so if applied: For (ω_16)^2 *(ω_16)^(16-2) == (ω_16)^16 ==
(ω_16)^0 == 1
1.) what is the product of the roots of unity?
2.) What about the sum?
3.) What is the sum of Aeven?
4.) what is the sum of Aodd? - correct answer-1.) if it is even,
then it is == 1
if it is odd, then it is == -1
2.) The sum is == 0. This is because (ω_n)^0 == 1 and
(ω_n)^(n/2) == -1. These cancel each other out. So if you go
through the whole sequence.. it eventually becomes 0.
, 3.) (n/2) * 1
4.) (n/2) * -1
Why are off diagonal entries not equal to one? - correct
answer-In the original, it is (ω_n)^k * (ω_n)^-k == (ω_n)^0 == 1
However, the off-diagonal entries are:
(ω_n)^k * (ω_n)^-j == (ω_n)^(k-j); so result of 1 is definitely not
guaranteed
in degrees, what are the values of the following:
cos(0)
cos(90)
cos(180)
cos(270)
cos(360)
Do the same for sin() - correct answer-a.) 1
b.) 0
