Sun, Jul 23, 2017

Sums of geometric series

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). \]

Read more about Sums of geometric series
Sat, Jul 22, 2017

Infinite Number of Primes

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\).

Read more about Infinite Number of Primes
Sat, Apr 22, 2017

Recurrences

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}. \]

Read more about Recurrences
Fri, Apr 21, 2017

Converging series

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

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

Read more about Converging series
Wed, May 4, 2016

Polynomial-time approximation schemes

PTAS

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

Read more about Polynomial-time approximation schemes
Wed, Apr 27, 2016

Equivalence of 3SUM problems

Reducing 3SUMx1 to 3SUMx3

???

Reducing 3SUMx3 to 3SUMx1

\[ (a, 3), (b, 4), (c, -7) \]

Read more about Equivalence of 3SUM problems
Thu, Apr 14, 2016

Log Log Log

Theorem

\[ \frac{\log n}{\log \log n}! = \Theta(n) \]

Read more about Log Log Log
Tue, Apr 12, 2016

VC-dimension

Definition 1 (Espilon net)

Let \(X\) be a set, let \(\mu\) be a probability measure on \(X\), let \(\mathcal{F}\) be a system of \(\mu\)-measurable subsets of \(X\), and let \(\varepsilon \in [0,1]\) be a real number. A subset \(N\subseteq X\) is called an \(\varepsilon\)-net for \((X,\mathcal{F})\) with respect to \(\mu\) if \(N \cap S \neq \emptyset\) for all \(S \in \mathcal{F}\) with \(\mu(S) \ge \varepsilon\).

Read more about VC-dimension
Sun, Jan 17, 2016

\(d\) hyperplanes intersection bounds

We bound the position of the \(0\)-cells of an arrangement of hyperplanes in \(\mathbb{R}^d\). This allows, for example, to build an hypercube that intersects all cells of the arrangement. Such an hypercube must contain at least one point of each cell of the arrangement. When \(q > 0\), in order to fix which point of a \(q\)-cell we want to include in the hypercube, it suffices to add the \(n\) hyperplanes of equation \(x_i = 0\) to the arrangement. With those additional hyperplanes, the arrangement is such that each \(q\)-cell of the arrangement with \(q > 0\) contains a \(0\)-cell of the arrangement, hence, we only need the hypercube to intersect, for each \(0\)-cell \(\nu\) of the arrangement, an hypersphere of center \(\nu\) and arbitrarily small radius. The inequalities of the polyhedral set defining our hypercube will thus only depend on the position of the \(0\)-cells of our arrangement.

Read more about \(d\) hyperplanes intersection bounds