Re: [algogeeks] Re: Function Name Mismatch
Thanx for reply can you provide some code snippet here? or some link for it. On Tue, Feb 7, 2012 at 11:30 PM, Prem Krishna Chettri hprem...@gmail.comwrote: This is a simple implementation to Factory Design Pattern. What you have to do is make an arbitrary class (Your Adapter) and always call this. However, the implementation of this class should be smart enough to route your call accordingly. As suggested by DON , its the c++ implementation of Factory Class. However , if you are designing in any other language, It is alwasyz advisable to have a sample implementation of Factory design pattern. On Tue, Feb 7, 2012 at 11:23 PM, Don dondod...@gmail.com wrote: Provide an interface class for the client to access. The client needs to know the name of the method in the interface, but only the interface needs to know the name of the function in the server. Don On Feb 7, 8:38 am, Aman Kumar amanas...@gmail.com wrote: Hii to all If client want to make a function call to a server(vice versa), but it doesn't know exact name . so we need a adapter. for this i have to design a adapter (middleware) so that client can make a call and adapter make that call to exact match. please help me for same. how to design adapter? -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] determining if frequency is greater than n/2
But in this post, we don't have prior information about what can be possible majority element. According to my question, we know that either x is the majority element or there is no majority element. Can we use that information to reduce complexity to O(log n)..??? -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] determining if frequency is greater than n/2
i guess can be done using binary indexed tree. On Thu, Feb 9, 2012 at 2:07 PM, Prakhar Jain jprakha...@gmail.com wrote: But in this post, we don't have prior information about what can be possible majority element. According to my question, we know that either x is the majority element or there is no majority element. Can we use that information to reduce complexity to O(log n)..??? -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] determining if frequency is greater than n/2
log n is impossible. the other solution i thought was of building a tree where each node contains value and its count. and then building a heap out of these counts, but this will be overkill. the fact that rest of the n/2 elements are not unique is the killer in the logic otherwise only n/2+1 elements are sufficient Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Feb 9, 2012 at 2:53 PM, atul anand atul.87fri...@gmail.com wrote: i guess can be done using binary indexed tree. On Thu, Feb 9, 2012 at 2:07 PM, Prakhar Jain jprakha...@gmail.com wrote: But in this post, we don't have prior information about what can be possible majority element. According to my question, we know that either x is the majority element or there is no majority element. Can we use that information to reduce complexity to O(log n)..??? -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] determining if frequency is greater than n/2
ignore my comment... On Thu, Feb 9, 2012 at 4:15 PM, Ashish Goel ashg...@gmail.com wrote: log n is impossible. the other solution i thought was of building a tree where each node contains value and its count. and then building a heap out of these counts, but this will be overkill. the fact that rest of the n/2 elements are not unique is the killer in the logic otherwise only n/2+1 elements are sufficient Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Feb 9, 2012 at 2:53 PM, atul anand atul.87fri...@gmail.comwrote: i guess can be done using binary indexed tree. On Thu, Feb 9, 2012 at 2:07 PM, Prakhar Jain jprakha...@gmail.comwrote: But in this post, we don't have prior information about what can be possible majority element. According to my question, we know that either x is the majority element or there is no majority element. Can we use that information to reduce complexity to O(log n)..??? -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] determining if frequency is greater than n/2
http://www.geeksforgeeks.org/archives/4722 O(logn) soln... Regards, PAYAL GUPTA, NIT-B On Thu, Feb 9, 2012 at 5:33 PM, atul anand atul.87fri...@gmail.com wrote: ignore my comment... On Thu, Feb 9, 2012 at 4:15 PM, Ashish Goel ashg...@gmail.com wrote: log n is impossible. the other solution i thought was of building a tree where each node contains value and its count. and then building a heap out of these counts, but this will be overkill. the fact that rest of the n/2 elements are not unique is the killer in the logic otherwise only n/2+1 elements are sufficient Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Feb 9, 2012 at 2:53 PM, atul anand atul.87fri...@gmail.comwrote: i guess can be done using binary indexed tree. On Thu, Feb 9, 2012 at 2:07 PM, Prakhar Jain jprakha...@gmail.comwrote: But in this post, we don't have prior information about what can be possible majority element. According to my question, we know that either x is the majority element or there is no majority element. Can we use that information to reduce complexity to O(log n)..??? -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] determining if frequency is greater than n/2
i dont think its possible for unsorted array in O(logn).. Regards, PAYAL GUPTA , NIT-B On Thu, Feb 9, 2012 at 6:02 PM, atul anand atul.87fri...@gmail.com wrote: @payal : this will work for only sorted array not for unsorted. On Thu, Feb 9, 2012 at 5:50 PM, payal gupta gpt.pa...@gmail.com wrote: http://www.geeksforgeeks.org/archives/4722 O(logn) soln... Regards, PAYAL GUPTA, NIT-B On Thu, Feb 9, 2012 at 5:33 PM, atul anand atul.87fri...@gmail.comwrote: ignore my comment... On Thu, Feb 9, 2012 at 4:15 PM, Ashish Goel ashg...@gmail.com wrote: log n is impossible. the other solution i thought was of building a tree where each node contains value and its count. and then building a heap out of these counts, but this will be overkill. the fact that rest of the n/2 elements are not unique is the killer in the logic otherwise only n/2+1 elements are sufficient Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Feb 9, 2012 at 2:53 PM, atul anand atul.87fri...@gmail.comwrote: i guess can be done using binary indexed tree. On Thu, Feb 9, 2012 at 2:07 PM, Prakhar Jain jprakha...@gmail.comwrote: But in this post, we don't have prior information about what can be possible majority element. According to my question, we know that either x is the majority element or there is no majority element. Can we use that information to reduce complexity to O(log n)..??? -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: How many ways n points can be connected
@Terence: The DP approach is nice. if we have constraint likewhile choosing the first 3 edges if it makes a triangle so we will require n edges to connect the graph completely...in the same fashion...after selecting 2 more edgesagain we have to check that is it making more trianglethen no. of total edges will increase by 1 and now we will require total n+1 edges. So in such a scenario how we can compute the sample space for every cases. so for all the all the valid m what should be the sample space for f(n,m). if M(m1,m2,...) is all the vaild m. Then how we can calcualte the dependency between sample space for f(n,m1) and f(n,m2). @Terence On Feb 9, 8:22 am, Terence technic@gmail.com wrote: Here is an DP solution: (consider only simple graph, with at most 1 line between any 2 distinct points, and no point connect to itself) Suppose f(n,m) is the number of ways m lines can connect n points. Then f(n,m) = 0 when m n-1 or m n(n-1)/2; For graph with n vertices and m edges (connected or disconnected), the overall count is C(n*(n-1)/2, m). There are 2 types: 1) connected: The number is f(n,m) that to be computed. 2) disconnected: Consider the connected component containing vertex 1, suppose it has n' vertices and m' edges. Then: a. there are C(n-1, n'-1) ways to select the points in the component b. there f(n',m') ways to connect the n' points using m' edges c. the rest n-n' vertices and m-m' edges can be arbitrarily placed. In summary, f(n,m) = C(n*(n-1)/2, m) - ∑(∑C(n-1, n'-1) * f(n', m') * C((n-n')*(n-n'-1)/2, m-m') for m' in [n'-1,m]) for n' in [1, n-1] (C(N, K) is binomial coefficient choosing K from N) The overall time complexity is O(m^2*n^2), and space complexity is O(mn) On 2012-2-8 12:03, rspr wrote: Hi All, can there be a formulato which we can estimate how many ways (n-1) lines can connect n points in the same way how many ways n lines can connect n points and so onthere is one way that we store the information in adjacency list or in adjacency matrixand will check for the same for every event in sample space.is there any other way that can optimize this calculation or may it possible that we can directly calculate it. . rspr- Hide quoted text - - Show quoted text - -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Finding pre order representation of expression
From the following options, select the correct pre-order representation of the following expression. – 16 – – 14 / – 12 - 2 * 8 Please do answer how you arrived at the answer! Answers -–16--/14–12*28 -–16--/-1412*28 -–16-/–14–12*28 */--–16-14–1228 -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Spoj Domino Tiling
I am solving spoj problem Tiling a Grid With Dominoes.(http://www.spoj.pl/problems/GNY07H/).. I am not able to come up with a recurrence relation.. One of my friend said it has the recurrence relation as f(n) = f(n-1) + 5*f(n-2) + f(n-3) - f(n-4). I am not convinced and have trouble deriving this formula from given data..Can somebody help?? -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Finding pre order representation of expression
I think all the answers are wrong. Also pre-order is probably the wrong term here. The conventional term is prefix or Polish notation. You'd break up this expression at the level of lowest precedence as: (A - B) - C where A = ~16, B = ~14 / ~12, and C = 2 * 8 . Note I'm using ~ for unary negation because prefix notation is ambiguous if you can't tell a unary minus from a binary minus (and you aren't using parentheses like lisp). In prefix this is - - A B C. Term A is already in prefix. Term B in prefix is / ~14 ~12 Term C is * 2 8. Substituting you get - - ~16 / ~14 ~12 * 2 8 Now if you instead broke up the top level as A - (B - C) the prefix is - A - B C so you'd get the third answer - ~ 16 - / ~14 ~12 * 2 8 But for this to be correct the problem would have to say that subtraction is _right_ associative. Normally it's not. I.e. 1 - 2 - 3 is -4, not 2. On Feb 9, 8:28 am, Rahul Menon menonrahul1...@gmail.com wrote: From the following options, select the correct pre-order representation of the following expression. – 16 – – 14 / – 12 - 2 * 8 Please do answer how you arrived at the answer! Answers - –16--/14–12*28 - –16--/-1412*28 - –16 - / –1 4 –1 2 *28 */--–16-14–1228 -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Binary Search Tree Question
What does this function do?
void function(Node **node){
if(*node!=NULL){
function((*node)-Left);
Node *temp;
temp = (*node)-Left;
(*node)-Left= (*node)-Right;
(*node)-Right = temp;
function((*node)-Right);
}
}
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Binary Search Tree Question
It appears to be an attempt to reverse the tree. However, there is a
problem. It reverses the left sub-tree, then swaps the left and right
sub-trees. Then it reverses the right sub-tree. But wait! The original
left sub-tree which we reversed is now the right sub-tree, so we
actually unreversed it. And the left sub-tree has never been reversed
at all. So I don't think that it will work. The actual result will be
that left and right will be swapped in the root node. Beyond that,
there will be no change.
To make it work as intended, either do the two recursive calls one
after the other, or change the second one from Right to Left.
Don
On Feb 9, 8:38 am, Rahul Menon menonrahul1...@gmail.com wrote:
What does this function do?
void function(Node **node){
if(*node!=NULL){
function((*node)-Left);
Node *temp;
temp = (*node)-Left;
(*node)-Left= (*node)-Right;
(*node)-Right = temp;
function((*node)-Right);
}
}- Hide quoted text -
- Show quoted text -
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Binary Search Tree Question
Thanks!
I knew that it wont reverse the tree but was not sure about how it
reversed just the root.
On Feb 9, 7:57 pm, Don dondod...@gmail.com wrote:
It appears to be an attempt to reverse the tree. However, there is a
problem. It reverses the left sub-tree, then swaps the left and right
sub-trees. Then it reverses the right sub-tree. But wait! The original
left sub-tree which we reversed is now the right sub-tree, so we
actually unreversed it. And the left sub-tree has never been reversed
at all. So I don't think that it will work. The actual result will be
that left and right will be swapped in the root node. Beyond that,
there will be no change.
To make it work as intended, either do the two recursive calls one
after the other, or change the second one from Right to Left.
Don
On Feb 9, 8:38 am, Rahul Menon menonrahul1...@gmail.com wrote:
What does this function do?
void function(Node **node){
if(*node!=NULL){
function((*node)-Left);
Node *temp;
temp = (*node)-Left;
(*node)-Left= (*node)-Right;
(*node)-Right = temp;
function((*node)-Right);
}
}- Hide quoted text -
- Show quoted text -
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Binary Search Tree Question
How come it just reversed the root? I still dont get it!
Rahul
On Feb 9, 7:57 pm, Don dondod...@gmail.com wrote:
It appears to be an attempt to reverse the tree. However, there is a
problem. It reverses the left sub-tree, then swaps the left and right
sub-trees. Then it reverses the right sub-tree. But wait! The original
left sub-tree which we reversed is now the right sub-tree, so we
actually unreversed it. And the left sub-tree has never been reversed
at all. So I don't think that it will work. The actual result will be
that left and right will be swapped in the root node. Beyond that,
there will be no change.
To make it work as intended, either do the two recursive calls one
after the other, or change the second one from Right to Left.
Don
On Feb 9, 8:38 am, Rahul Menon menonrahul1...@gmail.com wrote:
What does this function do?
void function(Node **node){
if(*node!=NULL){
function((*node)-Left);
Node *temp;
temp = (*node)-Left;
(*node)-Left= (*node)-Right;
(*node)-Right = temp;
function((*node)-Right);
}
}- Hide quoted text -
- Show quoted text -
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Binary Search Tree Question
Because it reverses one side twice and the other side not at all.
It does a lot of work to accomplish nothing.
Don
On Feb 9, 9:06 am, Rahul Menon menonrahul1...@gmail.com wrote:
How come it just reversed the root? I still dont get it!
Rahul
On Feb 9, 7:57 pm, Don dondod...@gmail.com wrote:
It appears to be an attempt to reverse the tree. However, there is a
problem. It reverses the left sub-tree, then swaps the left and right
sub-trees. Then it reverses the right sub-tree. But wait! The original
left sub-tree which we reversed is now the right sub-tree, so we
actually unreversed it. And the left sub-tree has never been reversed
at all. So I don't think that it will work. The actual result will be
that left and right will be swapped in the root node. Beyond that,
there will be no change.
To make it work as intended, either do the two recursive calls one
after the other, or change the second one from Right to Left.
Don
On Feb 9, 8:38 am, Rahul Menon menonrahul1...@gmail.com wrote:
What does this function do?
void function(Node **node){
if(*node!=NULL){
function((*node)-Left);
Node *temp;
temp = (*node)-Left;
(*node)-Left= (*node)-Right;
(*node)-Right = temp;
function((*node)-Right);
}
}- Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text -
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: determining if frequency is greater than n/2
It can't be done in O(log n) unless the array is sorted or there is some other special property, for example, if all values x are known to be contiguous, allowing you to use a binary search to find the first and last location of x. In the general case it is impossible in O(log n) because you have to examine at least n/2 elements to reach a conclusion. In some cases you must examine all n elements. Don On Feb 8, 1:45 pm, Prakhar Jain jprakha...@gmail.com wrote: Hello everyone, suppose we have an array of size n and a number, say x, and we have to determine whether the number x is present in the array more then n/2 times or not? can we have an O(log n) algo for determining it..?..pls help...!!! -- -- Prakhar Jain IIIT Allahabad B.Tech IT 3rd Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Spoj Domino Tiling
well i have used three recurrences :P formed them by following a traditional approach f[i] = f[i-1] + 2*g[i-1] + h[i-1] + f[i-2]; g[i] = f[i-1] + g[i-1]; h[i] = f[i-1] + h[i-2]; On Thu, Feb 9, 2012 at 7:19 PM, Kunal Patil kp101...@gmail.com wrote: I am solving spoj problem Tiling a Grid With Dominoes.(http://www.spoj.pl/problems/GNY07H/).. I am not able to come up with a recurrence relation.. One of my friend said it has the recurrence relation as f(n) = f(n-1) + 5*f(n-2) + f(n-3) - f(n-4). I am not convinced and have trouble deriving this formula from given data..Can somebody help?? -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Subset Generation
Hi All, Anyway to implement this in a good manner http://www.spoj.pl/ARHN/problems/PRINCESS, solution is simple, check for ones and then generate numbers is an increasing number... so if a number n = 22(10110) then for k = 1, ans = 2(10) then for k = 2, ans = 4(100) then for k = 3, ans = 6(110) Shady -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Binary Search Tree Question
What about just the root being reversed?
Why is it different only in case of root?
Rahul
On Feb 9, 10:52 pm, Don dondod...@gmail.com wrote:
Because it reverses one side twice and the other side not at all.
It does a lot of work to accomplish nothing.
Don
On Feb 9, 9:06 am, Rahul Menon menonrahul1...@gmail.com wrote:
How come it just reversed the root? I still dont get it!
Rahul
On Feb 9, 7:57 pm, Don dondod...@gmail.com wrote:
It appears to be an attempt to reverse the tree. However, there is a
problem. It reverses the left sub-tree, then swaps the left and right
sub-trees. Then it reverses the right sub-tree. But wait! The original
left sub-tree which we reversed is now the right sub-tree, so we
actually unreversed it. And the left sub-tree has never been reversed
at all. So I don't think that it will work. The actual result will be
that left and right will be swapped in the root node. Beyond that,
there will be no change.
To make it work as intended, either do the two recursive calls one
after the other, or change the second one from Right to Left.
Don
On Feb 9, 8:38 am, Rahul Menon menonrahul1...@gmail.com wrote:
What does this function do?
void function(Node **node){
if(*node!=NULL){
function((*node)-Left);
Node *temp;
temp = (*node)-Left;
(*node)-Left= (*node)-Right;
(*node)-Right = temp;
function((*node)-Right);
}
}- Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text -
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: How many ways n points can be connected
@rspr: Are you talking about dependencies in my approach? or adding new constraints? In my DP approach, f(n,m) only depends on f(n-1,m'), f(n-2, m') ,..., f(1,m') (m' = m) Using s(n,m) denoting the number of all graphs of n vertices and m edges, obviously s(n,m) = C(n(n-1)/2, m) Instead of counting connected graphs f(n,m), I count the number of the disconnected graphs g(n,m) = s(n,m)-f(n,m) 1. choose the n' (n'n) points in the first connected component (containing 1st vertex): C(n-1, n'-1) 2. count the number of ways to connect those n' vertices with m' (m'=m) edges: f(n',m') 3. count the number of ways to place the rest (m-m') edges among the reset (n-n') vertices: s(n-n', m-m') Total number of disconnected graphs of this type is: C(n-1, n'-1) * f(n',m') * s(n-n', m-m') Sum it over all (n',m') (n'n, m'=m), we get g(n,m), then f(n,m) = s(n,m)-g(n,m) On 2012-2-9 16:52, rspr wrote: @Terence: The DP approach is nice. if we have constraint likewhile choosing the first 3 edges if it makes a triangle so we will require n edges to connect the graph completely...in the same fashion...after selecting 2 more edgesagain we have to check that is it making more trianglethen no. of total edges will increase by 1 and now we will require total n+1 edges. So in such a scenario how we can compute the sample space for every cases. so for all the all the valid m what should be the sample space for f(n,m). if M(m1,m2,...) is all the vaild m. Then how we can calcualte the dependency between sample space for f(n,m1) and f(n,m2). @Terence On Feb 9, 8:22 am, Terencetechnic@gmail.com wrote: Here is an DP solution: (consider only simple graph, with at most 1 line between any 2 distinct points, and no point connect to itself) Suppose f(n,m) is the number of ways m lines can connect n points. Then f(n,m) = 0 when m n-1 or m n(n-1)/2; For graph with n vertices and m edges (connected or disconnected), the overall count is C(n*(n-1)/2, m). There are 2 types: 1) connected: The number is f(n,m) that to be computed. 2) disconnected: Consider the connected component containing vertex 1, suppose it has n' vertices and m' edges. Then: a. there are C(n-1, n'-1) ways to select the points in the component b. there f(n',m') ways to connect the n' points using m' edges c. the rest n-n' vertices and m-m' edges can be arbitrarily placed. In summary, f(n,m) = C(n*(n-1)/2, m) - ∑(∑C(n-1, n'-1) * f(n', m') * C((n-n')*(n-n'-1)/2, m-m') for m' in [n'-1,m]) for n' in [1, n-1] (C(N, K) is binomial coefficient choosing K from N) The overall time complexity is O(m^2*n^2), and space complexity is O(mn) On 2012-2-8 12:03, rspr wrote: Hi All, can there be a formulato which we can estimate how many ways (n-1) lines can connect n points in the same way how many ways n lines can connect n points and so onthere is one way that we store the information in adjacency list or in adjacency matrixand will check for the same for every event in sample space.is there any other way that can optimize this calculation or may it possible that we can directly calculate it. . rspr- Hide quoted text - - Show quoted text - -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Binary Search Tree Question
@Rahul : if you check the flow properly ,(lets concentrate on the root node
, call other as left and right subtree) you will find that after done with
reversing root-left-left subtree , it reaches root(backtrack to root)
node and then swap root-left and root-right.
now because it is inorder way of traversal , we are done with
function((*node)-Left); now next recursion for root node is
function((*node)-Right);.
function((*node)-Right); --- this will again do reversing steps in
root-right subtree.(reverting back the old state).
after backtracking it reaches root.
but wait there is no swapping part after function((*node)-Right) , but it
is after function((*node)-Left);
but we have as discussed before function((*node)-Right) is the only
recursion root needs to complete in order move out of the function.
hence root-left and root-right remain swapped.
but program is similar to swapping root-left and root-right which can be
done in constant time but taken O(n) to do the same.
hope you have understood it :)
On Fri, Feb 10, 2012 at 10:16 AM, Rahul Menon menonrahul1...@gmail.comwrote:
What about just the root being reversed?
Why is it different only in case of root?
Rahul
On Feb 9, 10:52 pm, Don dondod...@gmail.com wrote:
Because it reverses one side twice and the other side not at all.
It does a lot of work to accomplish nothing.
Don
On Feb 9, 9:06 am, Rahul Menon menonrahul1...@gmail.com wrote:
How come it just reversed the root? I still dont get it!
Rahul
On Feb 9, 7:57 pm, Don dondod...@gmail.com wrote:
It appears to be an attempt to reverse the tree. However, there is a
problem. It reverses the left sub-tree, then swaps the left and right
sub-trees. Then it reverses the right sub-tree. But wait! The
original
left sub-tree which we reversed is now the right sub-tree, so we
actually unreversed it. And the left sub-tree has never been reversed
at all. So I don't think that it will work. The actual result will be
that left and right will be swapped in the root node. Beyond that,
there will be no change.
To make it work as intended, either do the two recursive calls one
after the other, or change the second one from Right to Left.
Don
On Feb 9, 8:38 am, Rahul Menon menonrahul1...@gmail.com wrote:
What does this function do?
void function(Node **node){
if(*node!=NULL){
function((*node)-Left);
Node *temp;
temp = (*node)-Left;
(*node)-Left= (*node)-Right;
(*node)-Right = temp;
function((*node)-Right);
}
}- Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text -
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
