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".