Archive for November, 2009

Algorithmic Question : 1

November 30, 2009

String A can be chained with string B , if the last letter of  A matches with the first letter of  B. For example “GIRI” can be chained with “IDLE”. This can be generalized to a list of strings, string1 chains with string2 which in turn chains with string3 and so on.

Now, Given a list of n strings find if they can be chained together . Note that this is YES/NO question, i.e; you need not come up with the actual order of chaining.

Try to come up with O(n) solution.

Probability Question : 2

November 21, 2009

Using Random5 function ( which returns a integer k \in [1,5]  with probability \frac{1}{5} ) , design Random7 function ( which returns a integer k \in [1,7]  with probability \frac{1}{7} ).

Probability Question : 1

November 5, 2009

Consider the set { 1, 2 ,…, n} of n nodes that attach to each other in the following way. Node 2 attaches to node 1. Node 3 attaches to node 1 with probability \frac{1}{2} and to node 2 with probability \frac{1}{2} . In general, node k ( k = 2, 3 ,.., n) attaches to a uniformly selected node from the previous ones, independently of previous attachments. The process of n steps produces a random rooted tree in which each vertex is one of the nodes and such that j being attached to i means that j is a child of i. The resulting trees are called recursive trees. Let size denote the number of vertices in the recursive tree.

Let X_m be a random variable which denotes the size of the subtree of a randomly chosen vertex in recursive tree of size m. Show that

1) For m\geq{1} , P( X_m = m ) = \frac{1}{m}

and, for m\geq{ 2},

2) P( X_m = k ) = \frac{1}{ k(k+1) }, if 1 \leq{k} \leq{m-1}.

PS:: This result is proved in following paper : ” Breakage and Restoration in Recursive Trees ” . I am looking for different approach. Any Ideas ??