100 days of algorithms

Median is just a special case of searching for k-th element. For today, let’s just focus on arrays with distinct elements, hence each value needs to be unique.

While straightforward solution would be to sort the array in O(n.log(n)) and pick k-th position in O(1), we can do…

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…

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.

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 say we want to find roots of the polynomial, e.g. x⁵+x⁴+x³+x²+x+1.

While there’s no analytical solution for higher order polynomials, numerical solution is just an application of linear algebra. All we need is to construct a matrix whose…

Determinants are of those functions that make absolutely no sense when you meet them for the first time. Multiply all the values in a column or row with all values in other columns or row, sum them up … and it works!

Graph is bipartite if the nodes can be split into two disjoint sets such that there is no edge between nodes inside the same set.

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…