For the 100th algorithm I chose a segmented Eratosthenes sieve for primes up to 10⁹ implemented in Cython. And this time the goal is to provide an algorithm that is as fast as possible. There are several reasons why I diverged from Python and the usual type of implementation. Among…

Linear programming is an area of mathematics that deals with the simplest form of constrained optimization problem — linear program. And simplex should definitely be in your toolbox if you are serious about algorithms. Here is an example of a linear program [in standard form]. maximize: -x + 3y +…

Romberg’s method to find a definite integral combines two formulas, extended trapezoidal rule and Richardson extrapolation, to get a good approximation in relatively low number of steps. Let’s explain how it all works without causing a serious headache. The simplest way to find a definite integral of function f on…

Locally weighted regression is a very powerful non-parametric model used in statistical learning. To explain how it works, we can begin with a linear regression model and ordinary least squares.

Floyd-Steinberg dithering is a truly magical technique. It is supposed to fool your eye and brain to make you think that you see more than there really is to be seen. In general, dither is method to reduce color space of an image by adding an artificial noise. …

We say that two nodes U and V in a directed graph belong to the same strongly connected component [SCC], if there exists path from U to V and path from V to U. The algorithm that finds all SCCs is surprisingly simple and quite clever. run a depth-first search…

Yesterday I have implemented an algorithm that directly relates to an implementation of parser for formal grammars. Today I have implemented the parser itself. However, I have no use for yesterday’s work since the parser is not SLR [as you might have expected]. …

If you plan to implement own parser for a context-free grammar, construction of FIRST and FOLLOW sets will be the first algorithm you will have to spend your time on. And since definition of formal languages and grammars is much more complicated than we need at the moment, I’ll stick…

Principal Component Analysis [PCA] is incredibly useful when you need [among others] to visualise high-dimensional data. It’s also very simple to implement, but requires plenty of work beforehand. A friend of mine, Pavel, has complained that I often don’t dive deep into the topic. …