2-Interval

The disjoint union of 2 intervals.

Interesting link for 2-interval covering.

Comments on Comments on Estimation of F0 by Alon

Specifically on the 2 inequalities that are combined to give the desired result.

if 2r > cF0 then Prob(Zr > 0) <> 0

Prob(Zr > 0) = Prob (Zr >= 1) <= E(Zr)/1 = F0/2r < zr =" 0)" zr =" 0)">= 1) = 1 – (1 – Prob(Zr <> F0/2r) = Prob(Zr – F0/2r > (F0/2r)1/2(F0/2r)1/2) <= 2r/F0 < 1/c.

Here's perhaps a better intuition as to how the second inequality works. The probability that Zr is 0 is bounded above by the probability that Z deviates from its mean by at least a mean value because clearly Zr being 0 is a subset of the latter case. Hence the rest follows.

MAX-GAP

For n+1 integers c1,c2,…cn, t the integer max gap problem is to answer whether there exists a permutation σ such that cσ(i) <= cσ(i+1) <= cσ(i)+t for all 1 <= i <= n.

Core-Sets

S is a set of points in Rd.
Bc,r = ball of radius r centered at point c in Rd
Given S, the minimum enclosing ball of S, MEB(S) is the unique minimum-radius ball containing S.
Let r* be the radius of MEB(S).
A ball Bc,(1+ε)r is said to be a (1+ε)-approximation of MEB(S) if r <= r* and S is a subset of Bc,(1+ε)r
Given ε > 0, a subset X of S is said to be an ε-coreset (corset) of S if S is a subset of Bc,(1+ε)r where Bc,r = MEB(X). In other words X is a coreset if an expansion by a factor (1+ε) of its MEB contains S.

To see that Alon’s Proof On The Lower Bound on F∞ works for sequences of length greater than 2n as well.

Simply consider that for characteristic vectors x,y instead of having lengths x + y have lengths m/n x + m/n y

And the sequence A of this length is as follows. For every member of subset of N for which x is a characteristic vector, put that member m/n times in the sequence.

Now the rest of the procedure follows except that the second party outputs “disjoint” or 0 if the output of the approximation algorithm is less than 4/3 (m/n) and 1 otherwise. This is the correct value with probability at least 1 – є because the precise value of F∞ is m/n if the sets are disjoint and 2m/n otherwise.

Intution Behind Alon

Intuition behind Alon, Matias and Szegedy’s Algorithm for estimation of Fk

So what might be the intuition behind this algorithm? What they do is define
X = m(rk – (r-1)k)
Here m is the length of the sequence.
r = {q: q>= p, aq = l}
where p is picked uniformly at random from 1,2,…,m and l = ap. Hence q is the number of occurrences of l in the sequence after p.

Now it can be easily seen that E[X] = Fk, but what could possibly be the intuition behind choosing this definition of X? Let’s try to delve deeper into the minds of these 3 people when they wrote this algorithm and try to figure out how they might have come up with it.

Let us say they began thus. I have a sequence of length m and it has n distinct elements that occur in it. Therefore on an average I expect to find (m/n) occurrences of each of the n elements. (Not too unreasonable, is it?)

So if that is the case then my Fk should be:

Fk = n(m/n)k = mk/nk-1=m(m/n)k-1

So from this expression he factors out the term and tries to approximate the (m/n)k-1 term. To put it in a nutshell he does this by rk – (r-1)k.

But to expand the idea a little further. Consider the term rk – (r-1)k more closely. In this term the rk gets cancelled and what remains is a set of terms the highest power term among which is rk-1. So what remains is to make sure r approximates m/n. Maybe it is no coincidence that he calls this term r (for rate).

Somehow r is proportional to m/n.

Now consider another approach. We pick p at random. If ap = l, then this could be the 1st, 2nd, 3rd, …, mlth occurrence of l. If we consider over all m, and all possible values of this occurrence we find that what remains is mlk. But there will be an m in the denominator. Hence the multiplication by m.

Intutition Behind Flajolet and Martin

Intuition behind Flajolet and Martin’s Analysis of Algorithm for Estimation of F0 as presented in Alon’s paper.

This is about the part where they show that the probability that their estimate deviates too much (by a factor of c) from the actual value is less than 2/c.

The idea is – in what way can we go wrong ? We can go wrong in 2 ways.
By Overestimation
By Underestimation

In overestimation it will happen that we estimate Y at a very high value when in fact F0 is indeed quite low. This will happen when we get an element that is mapped to a very-low probability bucket. But the probability of this itself is too low – by Markov’s Inequality.

In underestimation it will happen that we estimate Y at a very low value when in fact F0 is quite high. This will happen when we get a sequence of elements that map to a high probability bucket. But the probability that EVERY element will map to a high probability bucket is quite low – by Chebyshev’s Inequality

Now how the inequalities are applied are a matter of further investigation.

To Delete Temporary Files In Unix

rm .*

NC

Nick's Class

3-coloring an unrooted tree in O(log n . log * n) time
We know that in any tree there are at least a constant fraction of vertices are of degree <= 2. Now in the first step let the set of all vertices of degree <= 2 form a new set V1 and be removed from the original set V. Now again V-V1 is a tree (or a forest) – repeat above step until you get sets of vertices V1, V2, V3, … such that the maximum degree of any vertex in any Vi is 2. Clearly the graph formed by the union of these sets (including the edges) is a disconnected graph with degree at most 2 and each of these vertex sets is disjoint. Also note that there will be O(log n) such sets.

Now color this graph formed by the union of the sets Vi using 3 colors and the Cole Vishkin algorithm in O(log n. log *n) time.

Finally, we need to combine these disjoint graphs. For each follow the procedure given below.
For every color check which vertices in that particular subgraph are colored by it.
Now for every such vertex identified in step 1 color it permanently with the color max{{1,2,3} – set of all colors of neighbors of vertex in partially reconstructed graph}
Do not consider such permanently colored vertices in further iterations.
Once all vertices in a given subgraph are permanently colored include that in the partially reconstructed graph and move on to the next subgraph.

Reference: Parallel Symmetry Breaking In Sparse Graphs - Goldberg

Some Simple (yet useful) Graph Theoretic Stuff

1. Every tree has at least 2 vertices of degree 1.

Proof: http://www.math.cmu.edu/~af1p/Combinatorics/2003/Class03.pdf

2. Every tree has at least a constant fraction of nodes of degree 2 or less

Proof: This proof is by induction. The key point to note here is that the proof is by induction on number of edges, not on the number of vertices although the result is related to the number of vertices.

Clearly the claim is true for a tree with 1 edge, 2 edges, 3 edges as can be seen. Now consider that the claim is true for a tree with k-1 edges. A tree with k-1 edges has k vertices. By our claim at least a.k of these vertices are of degree 2 or less. Now, consider a tree with k edges. This additional edge will consist of an additional vertex and will be connected to only one of the vertices in the original tree. To see this consider that any tree with k+1 vertices has at most k edges. Otherwise there will be a cycle.

Hence in the new tree, the total number of vertices is k + 1. The number of vertices of degree 2 or less will be at least a.k because we are adding a new vertex with degree 1 – even if the edge from this vertex is incident on another vertex possibly increasing its degree from 2, by the addition of the new vertex, the total number of vertices of degree 2 or less remains at least a.k – hence out of k+1 vertices, a.k vertices have degree 2 or less.

Hence proved.