Modulo (aka mod) is an important operation in number theory. Given a positive integer \(m\) as modulo, an arbitrary integer is mapped into a number in \(\mathcal{M} = \{0,1,...m-1\}\) via modulo operation, a -> a % m \(\in \mathcal{M}\). More importantly, common arithmetic operations …
Nowadays, a lot of companies (esp. tech companies) have been embracing data-driven decision making practice. Almost every business decision such as what background color should be used for the company website or whether a new kitty photo filter should be released requires justification with some experimental perf metrics. A …
Bellman-Ford is an algorithm for finding shortest paths from a single source vertex to multiple target vertices in a weighted graph \(G(V,E)\) whose edge weights can be negative. The algorithm can also detect negative cycle (if any) in the graph. Its time complexity is \(O(|V|*|E …
Building on ideas from Part 1, in this part, we explore some lesser-known extensions and applications of BIT.
This is by no means a finished post, and I'll keep updating whenever I find new BIT applications/extensions.
We want the data structure, which …
Binary indexed tree (BIT for short), aka Fenwick tree, is popular data structure in competitive programming (CP)context. I believe it could also be a valuable tool in practical software developers' toolbox. But is it worth yet another BIT tutorial? Yes as my aim is to provide a different …
Reservoir sampling concerns with choosing \(k\) items (i.e., a random sample of size \(k\) or \(k\)-sample for short) from a population of size \(n\) (\(n > k\)) without replacement such that each chosen item is selected randomly with equal chance from the population.
Q1. What is the …
In this note, we look into the problem of estimating various statistics such as mean, quantiles of an unknown distribution from its sample.
More concretely, consider a univariate continuous random variable \(X\) following an unknown distribution with probability density function (pdf) \(p_X (x)\). Given a sample set \(\{x_i\}_ …