Reservoir sampling is super useful when there is an endless stream of data and your goal is to grab a small sample with uniform probability.

The math behind is straightforward. Given a sample of size K with N items processed so far, the chance for any item…

Aho-Corasick is a string searching algorithm running in linear time and my heart would be broken if I missed this one in the series.

I already spent a day on string searching, so what’s the difference to day 29? Aho-Corasick uses a finite state automaton to search…

When you multiply two numbers on the paper, you probably follow the good old [and naive] way. Using Master theorem it is pretty straightforward to show that this algorithm requires O(n²) multiplications. But there’s actually very clever way to speed the things up.

Sometimes I read that one-time pad is an unbreakable cipher. And of course, completely broken example is usually attached.

The problem is, people confuse the definition of perfect cipher for unbreakable. If the cipher is perfect (according to Shannon), the…

LCS is an algorithm built in tools you probably use every day. One example for all, Git wouldn’t be able to work the way it works without LCS.

A few facts:

• it is a textbook case of dynamic programming technique

I used to play this game as a kid and never won as far as I can remember. Writing a program to guess the secret and to make computer play against itself is the least satisfaction.

If you ever come to conclusion there’s only a little to study on this problem, read…

Given a set of 2D points, the mission is to find the closest pair.

Naive strategy would be to examine all the pairs and choose the closest one. But naive is also expensive, leading to O(n²) time complexity.

Convex hull is a way to capture a set of points using another set of points that is preferable. In this case a continuous set that is convex and minimal, since convex and minimal is a property that’s always good to have.

PageRank is an algorithm to determine what is called centrality in egonets. There are other ways to measure centrality, e.g. betweenness, closeness or hubs and authorities.

However, PageRank is quite useful for huge graphs due to its relation to Markov Chains…