[algogeeks] Re: Graph theoretic problem
On Feb 6, 2008 5:42 AM, dor [EMAIL PROTECTED] wrote: independent set). Also, minimum dominating set and maximum independent set are not the same problem (they are not equivalent problems). You Again; I'll have to disagree. Of course they are not the same problem, but they aren't the most incongruous. To quote the fastest resource I can lay my hands on: :-) http://en.wikipedia.org/wiki/Dominating_set Dominating sets are closely related to independent sets: a maximal independent set in a graph is necessarily a minimal dominating set. -- Rajiv Mathews --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: diameter of a graph
On 6/17/07, mirchi [EMAIL PROTECTED] wrote: can some one give me a dynamic programming algorithm to find the diameter of a graph ...(directed acyclic graph) thanx in advance.. Perform a depth-first search with the following state information for each node - distance to farthest pendant vertex. -- Rajiv Mathews --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Why we need prime numbers?
On 6/13/07, Bin Chen [EMAIL PROTECTED] wrote: Many cryptography algorithm used prime to do the modular math, but I don't know why it need to use prime but not many ordinary numbers? I think it the it's the other way around! :-) Since there isn't any really efficient way to prime factorize really large numbers, many cryptography related algorithms base their method around large primes. Quote this (http://en.wikipedia.org/wiki/Prime_factorization_algorithm#Time_complexity) Wikipedia entry, ...The difficulty (large time complexity) of factorization makes it a suitable basis for modern cryptography. -- Rajiv Mathews --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Graph Problem
Could you please explain the question. Typically in a directed graph we talk of in-degree and out-degree for a vertex. So is the question then to minimize the maximum of these in all vertices of the graph? If so what operations are permitted? On 5/16/07, pramod [EMAIL PROTECTED] wrote: Here's a graph problem. We are given a directed graph. We are allowed to change the directions of the edges. Our aim is to minimize the maximum degree in the graph. How do we achieve this? One way is to take the vertex with maximum degree, and take another vertex with least degree reachable from this max-degree vertex and then reverse all the edges' direction along the path. Now the questions with this approach are (1) how do we prove that this will lead to the optimal-graph in the sense, can we get a graph such that it's maximum degree is the best possible? (2) What's the time complexity, is it bound tightly? (3) Is there any better way? Thanks -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the type
On 4/25/07, Ravi [EMAIL PROTECTED] wrote: What is the type of following grammar: S - aXY XY - a Context-sensitive grammar. I'm not sure if context-sensitive grammars have been subclassed to cover something like this in particular. X - b Y - Xb -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Pumping lemma. Where I go wrong?
You've made some very fundamental mistakes. Pumping Lemma is used as an _adversarial_ argument. This has the following implications, 1) _You_ as the one who is trying to prove that a language is NOT regular will not be choosing `n'. The adversary chooses `n'. 2) Once the adversary has chosen `n', you choose a string longer than n, in order to ensure there is a loop (the pumping property). 3) The adversary then chooses the split up, that is, the part of the string you've given him that loop. The way you've defined it, xyz, subject to the constraint that |xy| = n. 4) You pump as many times as you wish to disprove his statement. On 4/6/07, Ravi [EMAIL PROTECTED] wrote: 3)Choose x = 0, y = 0^n-1, z = 1^2b So this is where you go wrong. A _smart_ adversary will not choose x and y the way you have. He could quite easily have choosen x=0^n-2, y=0^2, z=the rest. The basic flaw is that you've ignored the fact that the pumping lemma is used as an adversarial dialogue, between, you, the person trying to prove a language is not regular, and someone, who claims to have a finite state machine that accepts that language. -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: If you see carefully his proof does not assume anything about sections colored continuously. His proof assumes only one thing Half of them are red and half of them are white Half does not mean it should be continuous. So the proof still works correct unmodified even if the halves are not continuous. Could you elaborate please. His proof contains, Quote: If r = R-r, match half1 with Red half of outer disk. Total matching = r + 100 - R + r = 100 - R + 2*r How do you justify this if the sections aren't contiguous? I think the proof elaborated by _stone_ is correct and apt. -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Sorting o(n) time
On 3/16/07, Karthik Singaram L [EMAIL PROTECTED] wrote: How would the median algorithm get the top k elements? I think what he meant was, use the median by parting-in-5 algorithm to find the kth largest element. This can be done in O(n). Then just partition around this element to get the top k elements, O(n). -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: help making regular expression
On 3/15/07, Ravi [EMAIL PROTECTED] wrote:
what will be a regular expression(non-UNIX one please) for the set of
languages which have number of 0s divisible by 5 and number of 1s
divisible by 2. The set of alphabets is {0,1}.
The following is based on `Parallel Regular Expressions'. If I
remember correctly, PREs have been proven to be equivalent to the set
of `Regular Languages'.
So assuming you're equipped with that,
(a) 0s div by 5 --- (0)* -- R_a (Regular expression a)
(b) 1s div by 2 --- (11)* -- R_b
Now PREs define an operator called `shuffle' which basically causes an
`interleave' of strings from both languages.
So based on whatever the notation is for writing down an interleave,
the required PRE will be SHUFFLE(R_a, R_b).
For more information on Parallel Regular Expressions, their
equivalence to Regular Languages refer to
www.cct.lsu.edu/personal/estrabd/papers/paper333final.pdf
PREs basically provide this additional tool of shuffling, which much
like non-determinism (in finite state machines) turns out to NOT
provide any additional power in accepting languages.
--
Regards,
Rajiv Mathews
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: To find a rectangle of max sum
On 3/12/07, Balachander [EMAIL PROTECTED] wrote: How to find the Rectangle of Max sum in a 2D matrix consisting of both +ve and -ve numbers,,, This solution is based on a similar variant of the problem, calculating maximum contiguous sub-array in one dimension. That problem can be solved in O(n) time (time linear to the size of the input array). For an array of dimensions m x n, the rectangle of maximum sum can be computed in O(m^2 * n). The idea is as follows, (A) Along one dimension calculate the cummulative sums, That yields, For each j, CUMM[i][j] = A[1][j] + ... + A[n][j] This step calculates the CUMM[][] array in O(m * n) Having done this we can for any sub-array along this dimension answer queries of the form Sum(A[i1][j] to A[i2][j]) in O(1) time. This is required for the next step. (B) For each pair of start and end points along the precalculated dimension, perform a linear scan similar to the one dimensional version of the problem along the other dimension. The pairs enumerable will work out to O(m*m) and the sweep will be O(n). (Made possible with the help of the precalcuation in the previous step). -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: To find a rectangle of max sum
On 3/12/07, Balachander [EMAIL PROTECTED] wrote: How to find the Rectangle of Max sum in a 2D matrix consisting of both +ve and -ve numbers,,, Is any one aware of any theoretical lower bounds on this problem? I remember reading about this in ``Programming Pearls'' by Jon Bentley, where he had mentioned that the O(m^2 * n) bound was the best any one had done back then. I realize now that ``Programming Pearls'' are pretty outdated and was wondering if any one is aware of anything that has bettered this? -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Interesting Probability Question
On 3/9/07, Nat (Padmanabhan Natarajan) [EMAIL PROTECTED] wrote: 1. We cannot bound the triangle if we don't bound the space...thats the reason why I choose a unit square I think we don't really need to bound anything. I think the question as is phrased can only yield what I guess should be called _limiting_ probabilities. ;-) 2. It is true that there are a lot of points outside the triangle that you cannot choose but they all lie in a finite set of lines Again, I think this is incorrect. Please refer to my argument in my previous post. -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Interesting Probability Question
On 3/8/07, Karthik Singaram L [EMAIL PROTECTED] wrote: If the bound reasoning is correct then we would have a probability of 1 to get a quadrialetral when choosing random points in a plane. The bound reasoning is valid under the condition that size of plane tends to infinity. As I've posted above this still doesn't mean that the probability of getting a quadrilateral hull tends to 1. -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Interesting Probability Question
I came across this interesting probability question recently. Consider an infinite two dimensional plane. 4 points are chosen at random on this plane. What is the probability that the convex hull of the 4 points will be a quadrilateral? -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Permutation with a twist ??
On 2/3/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
I will like to generate following (not sure if this will be called
permutation):
NULL
C
B
A
B C
A C
A B
A B C
I think you're looking to generate all possible combinations of n elements.
Essentially below I'm trying to simulate binary,
Combination(Array Elements, Array Answer)
{
if(Elements.size() == 0) print Answer, return;
for(i in Elements)
//Select the particular element -- equiv to 1 say
Combinations(Elements+1, Answer.push_back(Elements[0])
//Don't select the element -- equiv to 0 say
Combinations(Elements+1, Answer)
}
--
Regards,
Rajiv Mathews
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Permutation with a twist ??
I'm sorry. My algo is terribly wrong!
On 2/3/07, Rajiv Mathews [EMAIL PROTECTED] wrote:
Combination(Array Elements, Array Answer)
{
if(Elements.size() == 0) print Answer, return;
for(i in Elements)
//Select the particular element -- equiv to 1 say
Combinations(Elements+1, Answer.push_back(Elements[0])
//Don't select the element -- equiv to 0 say
Combinations(Elements+1, Answer)
}
It should be,
Combinations(Array Elements, Array Answer, int size)
{
if(size == 0) print(Answer);
//Select element
Answer.push_back(Elements[0]);
Combinations(Elements+1, Answer, size-1);
Answer.pop_back();
//Don't select element
Combinations(Elements+1, Answer, size-1);
}
Sorry for the last post. I shouldn't be typing while sleeping :-)
--
Regards,
Rajiv Mathews
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: hi...can any one have the art of programming by knuth solutions for volume 3
On 11/20/06, subrahmanyam kambala [EMAIL PROTECTED] wrote: hi...can any one have the art of programming by knuth solutions for volume 3 Don't Knuth books have solutions in them? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: check string A and B isPermutation ?
I had written.. So, using a sort the complexity really is O(2n log 2), Isn't it? Oh yeah.. That's terribly bad logic! @Gene Use radix sort to make it O(N W) where W is the bit-width of the characters in the string, hence O(N). I don't really get how a radix pass is going to help here either.. Wouldn't it just order the strings, while we really want to order the characters in the strings? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
