Multiplying Two Polynomials with Fast Fourier Transform

Polynomial multiplication is one of the most important problems in mathematics and computer science. It can be formally defined as follows:

You are given two polynomials roughly of equal size$A(x)=a_0+a_1x+\dots+a_{n-1}x^{n-1}$$B(x)=b_0+b_1x+\dots+b_{n-1}x^{n-1}$find a polynomial $C(x)=c_0+c_1x+\dots+c_{2n-2}x^{2n-2}$ such that $$A(x)\cdot B(x)=C(x)$$. At first, this may look like an easy problem, Continue reading Multiplying Two Polynomials with Fast Fourier Transform

Generating All Subsets of Size k in Python

Suppose you are given a set $$S$$ with $$n$$ elements and you need to generate every subset of size $$k$$ from it. For instance, if $$S=\{3,4,5\}$$ and $$k=2$$, then the answer would be $$\{3,4\}$$, $$\{3,5\}$$, $$\{4,5\}$$. So, how would you do that in Python?

First of all, this is a really simple exercise. Stuff like this often comes up when someone writes a moderately large script. I wanna talk about this one in particular because it has a combinatorial solution. Continue reading Generating All Subsets of Size k in Python