# FREE Course on FFT in Polynomial operations and Advanced Combinatorics

In this Micro course, we will be looking into a really advanced and powerful tool in competitive programming, which is FFT or Fast Fourier Transform, and how we transform the problems of convolutions or polynomial operations into a problem of FFT. If you don't know about FFT at all before this, don't worry we are going to start from the absolute basics of FFT, and then we are going to dive into the polynomial operations/ convolutions we can do with FFT. One area where this tool is required is advanced combinatorics, so I'll also be going into what is a factorial of a number and Stirling numbers, and then looking at how to compute them efficiently with FFT, i.e, **LOG-LINEAR** time for Stirling numbers and **SUB-LINEAR** time for a factorial.

#### FFT and Convulutions

This is the 1st class in the micro course "FFT in Polynomial operations and Advanced Combinatorics". In this class we are going to be looking at what is FFT or Fast Fourier Transform, and how is it used to solve the problem of efficient polynomial multiplication and convulutions. Specifically we are also going to be looking at a variant of FFT called NTT or Number Theoretic Transform, and seeing how do we come from FFT to NTT.

Jan 11, 2021 • 2h 0m

Nishchay Manwani

#### Polynomial operations and Multipoint evalualtion

This is the 2nd class in the micro course "FFT in Polynomial operations and Advanced Combinatorics". Having covered ploynomial multiplication using FFT in the previous class, we are now going to cover the various other stuff FFT allows us to do efficiently. We are going to be looking at various polynomial operations, specifically polynomial inverse and polynomial division, and we are also going to look at how we can evaluate a polynomial efficiently at many different points.

Jan 13, 2021 • 2h 0m

Nishchay Manwani

#### Stirling number of Second kind

This is the 3rd class in the micro course "FFT in Polynomial operations and Advanced Combinatorics". In this class, we are first going to look at what does stirling number of second kind actually means, and how can it be used in various combinatoric problems. We are also going to be looking at many different properties surrounding it. Then we are going to use the knowledge of solving convolutions from FFT that we learned in the previous class, to efficiently compute these numbers.

Jan 15, 2021 • 2h 0m

Nishchay Manwani