Problem You are given degree sequence $A$, determine the number of possible caterpillars. We say that the graphs are different if they are not isomorphic. Solution Let us prove first prove the following fact: the degree sequence $A = (a_1,\ldots, a_n)$ can form a tree if and only if the sum of degree sequence is equal to $2\cdot (n - 1)$ and that $\forall i\, a_i > 0$. The only if direction is true by the definition of tree....

Here is the list of few probabilistic results. Markov’s inequality If $X$ is a nonnegative random variable and $a>0$, then the probabilty that $X$ is at least $a$ is at most the expectation of $X$ divided by $a$: $$P(X\geq a) \leq \frac{E(X)}{a}.$$ Proof $$ \begin{aligned} E(X) &= \int_{-\infty}^\infty f(x)xdx = \int_0^\infty f(x)xdx\\ &= \int_0^a f(x)xdx + \int_a^\infty f(x)xdx\\ &\geq \int_a^\infty f(x)xdx \\ &\geq \int_a^\infty f(x)dx \\ &=a\int_a^\infty f(x)dx \\ &= aP(X\geq a), \end{aligned} $$ which, as you can see, is quite weak bound and proof itself is quite a troll....

LeetCode’s Sort an Array problem was a push for me to really understand different sorting algorithms. So I decided to implement few sorting algorithms. Bubble sort Bubble sort is considered as the simplest sorting algorithm out there. The idea is to scan through an array and swap consecutive elements if they are in word ordered until the array gets sorted. In Java, we have int[] bubbleSort(int[] a){ int n = a....

The expected value, $\mathbb E[x]$, is the weighted average of possible values of a random variable, with weights given by their respective theoretical probabilities. The variance, $\mathbb D[X]$ (or $\sigma^2,\text{Var}(X)$), is the expectation of the squared deviation of a random variable from its population mean or sample mean. Bernoulli distribution The Bernoulli distribution essentially models a single trial of flipping a weighted coin. It is the probability distribution of a random variable taking on only two values, $1$ and $0$ with complementary probabilities $p$ and $1-p$ respectively....

Suppose we want to generate image of spiral by printing line by line. You are given natural number $n$, where $n$ denotes sidelength of spiral (number of lines). For example, for $n = 11$, program must display following figure on the console: # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # Interestingly enough, this is not as simple as it might seem, especially, when you can only use string concatenation (and not use any arrays, lists, etc)....