Monthly Archives: December 2012

Azuma’s Inequality

The Chernoff bound gives the concentration of sums of independent random variables. The concentration result can be generalized to martingales. Martingales and Azuma’s Inequality A sequence of random variables \(X_0, X_1, \ldots, X_n\) is called a martingale if \[ {\bf

Tagged with: ,
Posted in Probability

Read and Write Text Files in Java

An I/O Stream represents an input source or an output destination. A stream can represent many different kinds of sources and destinations, including disk files, devices, other programs, and memory arrays. A file is identified by its path through the

Tagged with: , ,
Posted in Java

Debugging in Java

A software bug is a mistake in a program. Debugging is to find and correct the mistakes (introduced by yourself). Programmers usually spend 20% of time for coding, and 80% of time for debugging. In 1996, the European Space Agency’s

Tagged with: ,
Posted in Java


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