Oleksii Trekhleb Aug 17
Discrete Fourier Transform
Even though Discrete Fourier Transform or DFT is probably not the thing you work with daily it might still be a very interesting algorithm to play with. Not because it is quite complex but because of its interesting meaning.
This algorithm allows you to split the input signal that is spread in time into the number of frequencies of certain length, amplitudes and phases so that all those frequencies together will form the original signal. So it actually converts the domain of time into domain of frequencies and backwards.
It may sound complicated so let's think about it from another angle.
Imagine you have smoothie. DFT then will allow you to split smoothie into its ingredients! Imagine that you provide the bottle of smoothie as an input for DFT function and it splits it out to three smaller bottles of pure carrot, apple and orange juices! This is what DFT does - it splits the whole input into its ingredients.
Or imagine that you want to paint the fence and you've mixed several paints up so that it started to be of homogenous color. DFT function then will be able to split your mixed paint into several pure colors that will together form that initial color! Isn't is sound like a magic, is it?
All algorithm beauty and complexity is hidden in the following formula:
There is a really good article about this topic. I suggest you to read it if you're interesting in learning more since there are many visual and interactive Fourier Transform examples and explanations.
I hope you found this Fourier thing interesting. Have fun with algorithms!