## Time and Space Complexity Class

Robust classes are those such that no reasonable changes to the model of computation should change the class; capable of classifying interesting problems. Examples $$\mathsf{L}$$ (contains Formula Value, integer multiplication and division), $$\mathsf{P}$$ (contains circuit value, linear programming, max flow),

Posted in Theory

## Markov’s Inequality

Markov’s inequality provides a bound on the upper-tail probability of non-negative random variables. The bound is expressed with the expectation of the random variable. [Markov’s Inequality] Let $$X$$ be a non-negative random variable. Then, for any $$\lambda > 0$$, \[

Tagged with: , ,
Posted in Probability

## Shuffle an Array or a List in Java

How can we rearrange an array of items in random order? A simple way is to manipulate the array by picking elements randomly. Or we can use Java Collections API. Shuffle an Array Write a loop to go through each

Tagged with: , ,
Posted in Java

## Pairwise Independence

A collection of random variables is pairwise independent if every pair of variables are independent. Given $$k$$ independent bits, we define $$n = 2^k-1$$ random variables each of which is a parity of a non-empty subset of the $$k$$ bits.

Tagged with: , , ,
Posted in Theory