fast fourier transform algorithm

there is no code just pseudo
Q1)
Find all n roots of unity for n= 4.
Q2)
Resolve Q1 for the case n = 8.
Q3)
Draw a complete 1-dimensional, 4-point, FFT diagram (i.e., n= 4).
Q4)
Develop a recurrence relation for the time-complexity of a 1-dimension
FFT of size n elements, where n is a power of 2. Solve this recurrence
to find the time complexity.
notice these question u can use modfiy this algorithm
I wrote algorithm for you to edite
DFS(G,x)
{
mark(x)=’visited’;
for every y in L[x] do
{
if mark(y)==’unvisited’;
}
add edge(x,y) to the edges
DFS(g,y)
—————————
DFSforest(G)
for every node v in V(G) do
mark(v)=’unvisited’
while there is a node x
while mark(x) = unvisited’
do
DFS(G,x);
Q5)
Explain how to apply Depth-first-search method to check if a
given graph is connected. You should present your idea first;
then the algorithms, and state (without proof) the complexity
of your method. (Notice Depth first search method consists of
two parts or functions: DFSforest(G) and DFS(G,x) as covered.)
Q6)
Modify the depth first search method given for digraphs so that
if a back arc is encountered, the algorithm should print the
message “cyclic”.