Positional notation. An arbitrary precision integer on a computer is represented as a list of digits (limbs). They are just bigger. Today’s computers can hold 64 bits per limb. Modular arithmetic consists in applying addition and multiplication to integers modulo a certain number \(n\). Given an implementation of addition, multiplication, and division over the integers, we can emulate addition or multiplication modulo \(n\) by performing the corresponding operation on integers then taking the result modulo \(n\).

A drunkard is zigzagging home. At every steps forward (or backward) he is making, he also moves \(1\) step to the left with probability \(p\) and \(1\) step to the right otherwise. He starts \(i\) steps to the right of a river. What is the expected number of steps forward before he falls into the river?

Among the identities that are useful in the analysis of algorithms, this one shows how sums of geometric series converge when the ratio is smaller than one (in absolute value). It occurs in divide an conquer schemes. For example, it allows to show that hierarchical cuttings for \(n\) hyperplanes in \(d\) dimensions only need space proportional to \(n^d\).

\[ \sum_{i=0}^{\infty} \binom{i+j}{j} x^i = \frac{1}{ {(1-x)}^{j+1} }, \forall j \in \mathbb{N}, \forall x \in (-1,1). \]

The erroneous proof I hear most often is: Suppose \(P\) is a finite set that contains all the primes, then \(p^* = 1 + \prod_{p \in P} p\) is prime. Indeed, the flaw is that \(p^*\) is not necessarily prime but rather must be a multiple of some prime not in \(P\).

Notes from June 2015 containing the following: Phase kick-back, Deutsch’s algorithm, Fourier sampling, Deutsch-Jozsa algorithm, Bernstein-Vazirani algorithm, Preimage of a function, Simon’s algorithm, Grover’s algorithm, Amplitude amplification, Quantum Fourier Transform, and Shor’s algorithm.

Theorem

Let \(a \in \mathbb{N} \), \(t < a \in \mathbb{N} \), and \(b \in \mathbb{R}\). Defining \(A_t\)to be some real number and

$$ A_N = (1 - \frac{a}{N}) A_{N-1} + b, N > t \in \mathbb{N}, $$

then

$$ A_N = \frac{b}{1+a} (N+1), N \ge a \in \mathbb{N}. $$

Let \(-1 < x < 1\),

$$ 1 + x + x^2 + x^3 + x^4 + \cdots = \frac{1}{1-x}. $$

PTAS

\((1\pm\varepsilon)\)-approximation with complexity \(O(n^{f(\varepsilon)})\).

Are different versions of the 3SUM problem equivalent?

Theorem

$$ \frac{\log n}{\log \log n}! = \Theta(n) $$