Blog Archives

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

Pseudorandom Generators and Derandomization

Definition of Pseudorandom Generators Two distributions \(X\) and \(Y\) over \(\{0,1\}^n\) are \((s, \epsilon)\)-indistinguishable if, for any circuit \(C\) of size at most \(s\), \[ \left| \Pr_X[C(X) = 1] – \Pr_Y[C(Y) = 1] \right| \leq \epsilon. \] A pseudorandom generator

Tagged with: , ,
Posted in Theory

Randomness

Randomness is an important computational resource, just as running time and memory space. Randomness sometimes is essential for designing algorithms. Randomness is useful! Quick Select In quick sort, a random pivot selection has the property that, for any input data,

Tagged with: , , ,
Posted in Algorithm, Java