Re: [algogeeks] Re: sorted 2-d array
@senthilnathan : very nice indeed -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: sorted 2-d array
On Jun 7, 8:49 am, Senthilnathan Maadasamy senthilnathan.maadas...@gmail.com wrote: We can do it in O(n * log n) by individually binary-searching for zero on each of the rows. Once we get the index of the first position where zero appears, counting the number of negative number is straight-forward. Here is an even better O(N) algorithm which is very elegant: Consider the bottom-left element of the given 2-D array. If it is negative, the whole of first-column is negative. So we can add that count and ignore that column from then onwards. If it is non-negative, the whole of last-row is non-negative. So we can ignore that row without changing the count. Therefore, by just doing one comparison we are able to eliminate one row or one column. We can iteratively follow this approach and it will terminate in exactly 2*N steps. I must say that your algorithm is very clever since I never thought of it. :-) I thought of a different approach that can be combined with yours to, oddly enough, get an even better solution. Consider the bottom-left element of the given 2-D array. If it is negative: Search the bottom row for the first non-negative value. If this element is the kth then it can be found in O(log k) time using a variation of binary search. Now the first k - 1 columns are all negative so we count those. If it is non-negative: Search the first column bottom to top for the first negative value. If this element is the jth from the bottom then it can be found in O(log j) time. Now the last j-1 rows are all non-negative so they need not be counted. Now follow this approach and it will terminate in O(N) steps. This is no better than your approach in the worst case (in fact slightly worse) but can be much better for cases where either most of the elements are positive or most of the elements are negative. For example if all elements are negative the algorithm runs in O(log N) time (actually 2 log N + O(1)). Open problem: I am guessing that my algorithm is optimal in some (reasonable) sense in which your algorithm is not. Define optimal (reasonably) than then prove that my algorithm is indeed optimal or show that some other algorithm is better by your definition. Regards, Ralph Boland -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: Puzzle:
@ dheerraj...u cant measure 8 litre...u hve no additional instrument @mohit...what do u mean by n th stageplzz elaborate -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Explain the output
@jitendra u got it right but parent and child are using the same text region
that's why control is transferring back and forth..
try running this code and see that line numbers are repeating...because of
same text region it is working like a loop...
#includestdio.h
int main() {
int id,i;
if((id=vfork())==0) { //child
printf( %d in child\n,__LINE__);
sleep(3);
printf(%d\n,i);
}
else { //parent
printf( %d in parent\n,__LINE__);
scanf(%d,i);
sleep(1);
printf(%d\n,i);
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: array question
How will it be 12 12 5 6 6?? I can understand that the first number in the list is place first so it could be 12 12 6 6 5. How will it be 12 12 5 6 6? On Jun 6, 7:47 am, divya jain sweetdivya@gmail.com wrote: output willl be 12 12 5 6 6 On 6 June 2010 18:27, souravsain souravs...@gmail.com wrote: @divya: Does your problem require the output to be sorted also? What will be the output required if inout is 12,5,6,12,6? Will it be 12,12,6,6,5 or 12,12,5,6,6,? Sain On Jun 6, 12:01 am, divya sweetdivya@gmail.com wrote: Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. So cant use a dictionary -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] min no of policemen
@sharad.. sorry bt i dint get how to use bellman ford or topological sort here... can u plz explain... On 8 June 2010 05:53, sharad kumar aryansmit3...@gmail.com wrote: for placing police man we can use bellman ford bfs.or even make use of topological sort. On Mon, Jun 7, 2010 at 9:59 PM, divya sweetdivya@gmail.com wrote: consider a tree. policemen is to be placed such that for each edge of tree, there is a policeman on atleast one side of each edge. tell the min no. of policemen and their locatn in time O(n) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Single ordered list
What is the most efficient way of combining 2 separate ordered list into a single ordered list ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Knapsack - 0-1 - Brute force
Why do you want to try a brute force approach, when you have some better algorithms and heuristics available? On Mon, Jun 7, 2010 at 10:07 PM, Jean Carlo Mendes jean.men...@gmail.comwrote: Hello Guys Anyone have a implementation of knapsack 0-1 using brute force approach ? Or… Do you have some link with a sample in C language? Thanks jean -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Variable number of integers
What do you mean by a stack or a queue in which each item is a variable number number of integers? Is it a queue of a queue, queue of a stack etc -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: sorted 2-d array
Actually, this might not always be the best approach. Example: -1 1 2 3 4 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 2*N = 10 steps. With my algo, you'll go: Step 1: top-left: negative, count++, Step2: [0][1] non negative, set limitRow=0 (or 1 depending on how you code) Step3: for([i][j] limitRow) check [1] [0]: non negative, set limitColumn = 0; since i=limitRow, j=limitCol, stop; count =1. We can do it in O(n * log n) by individually binary-searching for zero on each of the rows. Once we get the index of the first position where zero appears, counting the number of negative number is straight-forward. What if there are no zero elements at all? -Minotauraus. Here is an even better O(N) algorithm which is very elegant: Consider the bottom-left element of the given 2-D array. If it is negative, the whole of first-column is negative. So we can add that count and ignore that column from then onwards. If it is non-negative, the whole of last-row is non-negative. So we can ignore that row without changing the count. Therefore, by just doing one comparison we are able to eliminate one row or one column. We can iteratively follow this approach and it will terminate in exactly 2*N steps. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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 nos
@Divya: That was the question i previously asked. If n=3 000,001,010,100,101 are valid. So the solution for this is fib(n+2). If n=4 no. of sequences will be fib(6) i.e 8 On Tue, Jun 8, 2010 at 9:31 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: getting fibonacci nos is trivial using matrix multiplication in almost constant time. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Number of sequences of n binary digits that don't contain two 1's in a row
@saurabh: Hey u're right this is interesting. I checked for n=5 its giving 13 i.e fib(7) On Mon, Jun 7, 2010 at 9:19 PM, saurabh gupta sgup...@gmail.com wrote: it might be referring to no of sequences (say T(n) ) with no consecutive 1's for n = 3, ans would be 5 viz. 000, 001, 010, 100, 101 T(n) = fib(n+2) where fib = Fibonacci series which is interesting. On Sat, Jun 5, 2010 at 11:40 AM, Raj N rajn...@gmail.com wrote: @sharad: What about 101 even it doesn't have two 1's in a row On Sat, Jun 5, 2010 at 8:59 AM, sharad kumar aryansmit3...@gmail.comwrote: @rajn.can it be subsequence doesnt have one's too.hence 000,001,010,100 is required answer. On Sat, Jun 5, 2010 at 12:13 AM, Raj N rajn...@gmail.com wrote: Hi, I came across this question to find the number of sequences of n binary digits that don't contain 2 1's in a row. I wanted to know what exactly this means. Is it like if n=3 then compute all binary numbers having 3 digits which don't have consecutive 1's 110, 011, 111 ?? If not help me understanding it. Thanks!! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Puzzle:
yes even i dont think its possible as there is no n-1th state..ie there is no state from whr u can come to 2 8 5..so plz check On 7 June 2010 20:23, mohit ranjan shoonya.mo...@gmail.com wrote: is it possible ? if we say nth state is [2, 8, 5] I could not find possible (n-1)th state Mohit Ranjan On Mon, Jun 7, 2010 at 2:02 PM, sharad sharad20073...@gmail.com wrote: : Three containers are of 15,10 and 6 ltrs capacity. Initially its in configuration (15,0,0). Make it to configuration (2,8,5) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Pointer to a constant
i think both statements shd give error. as u r trying to change int to const int in 2 and const int to int in 1.. On 7 June 2010 19:59, mohit ranjan shoonya.mo...@gmail.com wrote: @Raj, no they are not same case 1: i is const case 2: ptr is const and whatever is const cann't be modified Mohit Ranjan On Mon, Jun 7, 2010 at 3:01 PM, Raj N rajn...@gmail.com wrote: Can someone tell me the difference between 1) const int i=5; 2) int i=5; int *ptr=i; const int *ptr=i; In the first case i can be modified via ptr i.e *ptr++ is valid. In the second case *ptr++ is illegal. Why is that so? Aren't they same? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] min no of policemen
Can you expain edge of the tree. I could not get that. Anurag Sharma On Tue, Jun 8, 2010 at 5:53 AM, sharad kumar aryansmit3...@gmail.comwrote: for placing police man we can use bellman ford bfs.or even make use of topological sort. On Mon, Jun 7, 2010 at 9:59 PM, divya sweetdivya@gmail.com wrote: consider a tree. policemen is to be placed such that for each edge of tree, there is a policeman on atleast one side of each edge. tell the min no. of policemen and their locatn in time O(n) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Number of sequences of n binary digits that don't contain two 1's in a row
how do u come to this formula T(n)=fib(n+2).. plz explain On 7 June 2010 21:19, saurabh gupta sgup...@gmail.com wrote: it might be referring to no of sequences (say T(n) ) with no consecutive 1's for n = 3, ans would be 5 viz. 000, 001, 010, 100, 101 T(n) = fib(n+2) where fib = Fibonacci series which is interesting. On Sat, Jun 5, 2010 at 11:40 AM, Raj N rajn...@gmail.com wrote: @sharad: What about 101 even it doesn't have two 1's in a row On Sat, Jun 5, 2010 at 8:59 AM, sharad kumar aryansmit3...@gmail.comwrote: @rajn.can it be subsequence doesnt have one's too.hence 000,001,010,100 is required answer. On Sat, Jun 5, 2010 at 12:13 AM, Raj N rajn...@gmail.com wrote: Hi, I came across this question to find the number of sequences of n binary digits that don't contain 2 1's in a row. I wanted to know what exactly this means. Is it like if n=3 then compute all binary numbers having 3 digits which don't have consecutive 1's 110, 011, 111 ?? If not help me understanding it. Thanks!! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Time complexity
What is the time complexity of insertion and deletion in 1. Linked list 2. Queue 3. Queue implemented using a linked list -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Pointer to a constant
@Mohit: If u're saying that in case 2 ptr is const then what is int *const ptr. I thought this is a constant pointer. Constant pointer is one which can't be made to point to any other address rit? How is *ptr++ coming into the way of constant pointer ? On Mon, Jun 7, 2010 at 7:59 PM, mohit ranjan shoonya.mo...@gmail.comwrote: @Raj, no they are not same case 1: i is const case 2: ptr is const and whatever is const cann't be modified Mohit Ranjan On Mon, Jun 7, 2010 at 3:01 PM, Raj N rajn...@gmail.com wrote: Can someone tell me the difference between 1) const int i=5; 2) int i=5; int *ptr=i; const int *ptr=i; In the first case i can be modified via ptr i.e *ptr++ is valid. In the second case *ptr++ is illegal. Why is that so? Aren't they same? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] isomorphic trees
Two binary trees T1 and T2 are isomorphic if T1 can be transformed into T2 swapping left and right children of the nodes in T1.Give an algorithm to report whether 2 given binary trees are isomorphic. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Pointer to a constant
Actually the first statement i gave const int i=5; int *ptr=i is itself giving an error on gcc and a warning on borland. We have to modify it as const int *ptr=i otherwise it gives illegal pointer conversion error. On Tue, Jun 8, 2010 at 12:11 PM, divya jain sweetdivya@gmail.comwrote: i think both statements shd give error. as u r trying to change int to const int in 2 and const int to int in 1.. On 7 June 2010 19:59, mohit ranjan shoonya.mo...@gmail.com wrote: @Raj, no they are not same case 1: i is const case 2: ptr is const and whatever is const cann't be modified Mohit Ranjan On Mon, Jun 7, 2010 at 3:01 PM, Raj N rajn...@gmail.com wrote: Can someone tell me the difference between 1) const int i=5; 2) int i=5; int *ptr=i; const int *ptr=i; In the first case i can be modified via ptr i.e *ptr++ is valid. In the second case *ptr++ is illegal. Why is that so? Aren't they same? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Number of sequences of n binary digits that don't contain two 1's in a row
I just checked out with so many possibilities and it is indeed matching. I may not be correct though. On Tue, Jun 8, 2010 at 7:50 PM, divya jain sweetdivya@gmail.com wrote: how do u come to this formula T(n)=fib(n+2).. plz explain On 7 June 2010 21:19, saurabh gupta sgup...@gmail.com wrote: it might be referring to no of sequences (say T(n) ) with no consecutive 1's for n = 3, ans would be 5 viz. 000, 001, 010, 100, 101 T(n) = fib(n+2) where fib = Fibonacci series which is interesting. On Sat, Jun 5, 2010 at 11:40 AM, Raj N rajn...@gmail.com wrote: @sharad: What about 101 even it doesn't have two 1's in a row On Sat, Jun 5, 2010 at 8:59 AM, sharad kumar aryansmit3...@gmail.comwrote: @rajn.can it be subsequence doesnt have one's too.hence 000,001,010,100 is required answer. On Sat, Jun 5, 2010 at 12:13 AM, Raj N rajn...@gmail.com wrote: Hi, I came across this question to find the number of sequences of n binary digits that don't contain 2 1's in a row. I wanted to know what exactly this means. Is it like if n=3 then compute all binary numbers having 3 digits which don't have consecutive 1's 110, 011, 111 ?? If not help me understanding it. Thanks!! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: constraints satisfied?
Use a n x n array. initialize with -1 (don't care = no constraints). If there is an equality constraint, set to 1, if explicity non-equality constraint is expected, replace with 0. While doing either of these if you come across a situation where 0 has to be overwritten by 1 or 1 has to be overwritten by 0, the system constraints cannot be satisfied, else all is well. Space required = n^2 bytes. Time complexity = O(c) where c= number of constraints for the system. Therefore, independent of the number of variables. You can do this with hash tables too and probably save memory. Here you'll use not store = -1 = don't care. -Minotauraus. On Jun 7, 12:16 pm, divya sweetdivya@gmail.com wrote: Here's a problem that occurs in automatic program analysis. For a set of variables x1; .. ; xn, you are given some equality constraints, of the form xi = xj and some dis equality constraints, of the form xi != xj Is it possible to satisfy all of them? Give an efficient algorithm that takes as input m constraints over n variables and decides whether the constraints can be satisfied. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] circularly sorted array
Check whether the first element in the array is greater than the last element in the array. If it is true, it means the array is rotated after sorting. Now, take the middle element of the array and check whether it is greater than the last element of the array. If true, it means the first half of the array is in sorted ascending order while the second half of the array is the place where the biggest and smallest elements of the array are present. If false, it means the second half of the array is in sorted ascending order while the first half of the array is the place where the biggest and smallest elements of the array are present. Check whether k falls between the sorted ascending half of the array. If yes, it is pretty simple Browse thru all elements or do a binary search within this sub array. If it falls in the sorted largest-to-smallest-containing half of the array, consider this half as your new array and proceed the same steps as above to find out the integer value k. Eg: Following numbers are in ascending order as their indices with k falling between n1 and n2 Index - 01 234 5 6 78 Value - n5, n6, n7, n0, n1,k,n2,n3, n4 According to the above method, 1. Check whether the first element is greater than the last element -- True. So, the array is rotated after sorting 2. Check whether the middle element(n1) is greater than the first element(n5) - False. So, the second half of the array [4-8] are sorted while indices [0-3] are sorted but not ascending. 3. Check whether k lies in between the second half. -- True k n1 and k n4. 4. Do a binary search between indices 4- 8 to get the element k. Index - 01 234 5 6 78 Value - n6, k, n7, n0, n1, n2,n3,n4, n5 On having the above example where the steps 1 2 still hold true 3.Check whether k lies in between the second half of the array [4-8] -- False. So, it falls in the first half of the array. 4. Assume sub array [0-4] as a new array and proceed with step 1. When you just have 3 elements left out (when k is the largest or smallest element), you can do a manual comparison and find k On Tue, Jun 8, 2010 at 7:41 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: You can do binary search for the largest element in log n trivially. And then you know the shift ! -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Luv, S.Antony Vincent Pandian -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Single ordered list
merging as in merge sort. On 8 June 2010 19:59, Raj N rajn...@gmail.com wrote: What is the most efficient way of combining 2 separate ordered list into a single ordered list ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Number of sequences of n binary digits that don't contain two 1's in a row
I found a nice explanation (from some other site) on how to get this formula T(n) = fib(n+2). Consider the set of all binary numbers of length n that end with 0. The first n-1 positions can be anything (0 or 1). So if we take the set of all binary numbers of length n-1 and append 0 to each of its element we get this set. Therefore size of this set is T(n-1). Consider the set of all binary numbers of length n that end with 1. Now, the (n-1)th position has to be 0 (because of the constraint). But there is no constraint on the first n-2 positions. So if we take the set of all binary numbers of length n-2 and append 01 to each of its element we get this set. Therefore size of this set is T(n-2). Therefore T(n) = T(n-1) + T(n-2). Since T(1) = 2 and T(2) = 3 we get T(n) = fib(n+2). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: ds
Actually the solution is best thought of with recursion.
See, for a simple 4 element array: a1 a2 b1 b2, you can get the result
by swapping only the two elements in the middle.
Now think, if you had an 8 element array: a1 a2 a3 a4 b1 b2 b3 b4,
group these into pairs of 2 like: a1 a2 - b1 b2 / a3 a4 - b3 b4
(logical grouping with pos0, pos1 with poslen/2, poslen/2 + 1)
Perform swap as before, you get: a1 b1 a2 b2 a3 b3 a4 b4, of course in
the array it will actually be: a1 b1 a3 b3 a2 b2 a4 b4 (since the
grouping was logical)
Perform same swap, but this time consider pairs as [a1 b1] [a3 b3] /
[a2 b2] [a4 b4]. Think of elements in brackets as one element. Same
swap operation yields
a1 b1 a2 b2 a3 b3 a4 b4.
For larger numbers a1 a2 a3 a4 a5 a6 a7 a8 b1 b2 b3 b4 b5 b6 b7 b8
Step 1: Group as: [a1 a2 a3 a4] [a5 a6 a7 a8] [b1 b2 b3 b4] [b5 b6 b7
b8]
Step 2: swap the two elements in the middle: [a1 a2 a3 a4] [b1 b2 b3
b4] [a5 a6 a7 a8] [b5 b6 b7 b8]
Step3: Group as: group 1 [a1 a2] [a3 a4] [b1 b2] [b3 b4] group 2: [a5
a6] [a7 a8] [b5 b6] [b7 b8]
Step 4: swap: [a1 a2] [b1 b2] [a3 a4] [b3 b4][a5 a6]
[b5 b6] [a7 a8] [b7 b8]
Step 5: Group as: group1: a1 a2 b1 b2 group2: a3 a4 b3 b4 group3 a5 a6
b5 b6 group4 a7 a8 b7 b8
Step6: swap as above: a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7 a8 b8
Since grouping is logical, it has taken only 3 steps to solve a
problem with 16 elements. Total number of steps required for this
solution is
{ln to base 2 (length/2)}. So, for 16 elements, 16/2 = 8, 2^3 = 8. For
64 elements, 64/2 = 32; 2^5 = 32. so 5 steps will be required.
Although, total number of swaps will be larger = (length/4) * number
of steps = 4 * 3 = 12 for a1...a8b1...b8.
Which is still less than O(n) = 16 :-)
-Minotauraus.
On Jun 7, 9:03 pm, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
Of course you should do it via swappings.. why would one think of anything
else :)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14
On Mon, Jun 7, 2010 at 10:39 PM, vadivel selvaraj
gct.vadi...@gmail.comwrote:
Hi guys d soln z quite easy by swapping the variables..
consider a1a2a3a4b1b2b3b4
In the first iteration, swap (a2,b1),(a4,b3) giving a1b1a3b3a2b2a4b4
In the second iteration, swap (a3b3,a2b2) which gives d soln...
a1b1a2b2a3b3a4b4...
Any comments on dis??
On Mon, Jun 7, 2010 at 1:51 PM, Raj N rajn...@gmail.com wrote:
@sain: But the question demands O(n) time
On Mon, Jun 7, 2010 at 3:35 AM, Anand anandut2...@gmail.com wrote:
Here is my approach is o(n).
http://codepad.org/YAFfZpxO
http://codepad.org/YAFfZpxO
On Sun, Jun 6, 2010 at 7:28 AM, sharad kumar
sharad20073...@gmail.comwrote:
this is ques by adobe and they want inplace soln..
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Simplicity is prerequisite for reliability.
– Edsger W. Dijkstra
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Time complexity
Linked List: Insertion O(n) deletionO(n) Queue using linked list : Insertion O(1) deletion O(n). On Tue, Jun 8, 2010 at 1:38 AM, Raj N rajn...@gmail.com wrote: What is the time complexity of insertion and deletion in 1. Linked list 2. Queue 3. Queue implemented using a linked list -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: sorted 2-d array
*What if there are no zero elements at all?* * * *...@minotauraus Very valid question. The terminating condition for the binary search can be modified to return the count of negative numbers in the array instead. * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] isomorphic trees
One approach is to parse the element of the two tree in two arrays and
compare the arrays to fiind if they are isomorphic.
parsing takes O(n).
Comparision takes O(n/2)
for (i=0;in;i++)
{
if(2i+1 n)
break;
if(arr_1[2i] != arr_2[2i+1])
{
break;
}
}
if(i == n/2)
printf(trees are isomorphic\n);
On Tue, Jun 8, 2010 at 8:01 AM, divya sweetdivya@gmail.com wrote:
Two binary trees T1 and T2 are isomorphic if T1 can be transformed
into T2 swapping left and right children of the nodes in T1.Give an
algorithm to report whether 2 given binary trees are isomorphic.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: Puzzle:
@Sharad let's say that it will take n steps to reach from [15,0,0] to [2,8,5] then after nth state will be 2,8,5 and (n-1)th state will be say [x,y,z] from which one transfer will lead to o/p [2,8,5] hope it's clear Mohit Ranjan On Tue, Jun 8, 2010 at 6:54 AM, sharad kumar sharad20073...@gmail.comwrote: @ dheerraj...u cant measure 8 litre...u hve no additional instrument @mohit...what do u mean by n th stageplzz elaborate -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] ds
I dont think so This approach is better than O(nlogn) On Tue, Jun 8, 2010 at 9:10 AM, harit agarwal agarwalha...@gmail.comwrote: @vadivel selvaraj your approach is O(nlogn) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Luv, S.Antony Vincent Pandian -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] identify the recurring part for a given decimal no
You have a Numerator and Denominator. After division you might get a recurring decimal points float as the answer. Problem is: You need to identify the recurring part for a given decimal no? For example 23.34563456 ... return 3456 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] min no of policemen
Min number of police man could be placed on the nodes which does not have leaf nodes. Only things needs to find out is the height of the tree.O(logn). For any given tree: 1. calculate the leaf node: 2^h (h is the height of the tree) 2. Subtract leaft nodes from the total number of nodes ((2^(h+1) -1)-2^h On Mon, Jun 7, 2010 at 10:53 PM, Anurag Sharma anuragvic...@gmail.comwrote: Can you expain edge of the tree. I could not get that. Anurag Sharma On Tue, Jun 8, 2010 at 5:53 AM, sharad kumar aryansmit3...@gmail.comwrote: for placing police man we can use bellman ford bfs.or even make use of topological sort. On Mon, Jun 7, 2010 at 9:59 PM, divya sweetdivya@gmail.com wrote: consider a tree. policemen is to be placed such that for each edge of tree, there is a policeman on atleast one side of each edge. tell the min no. of policemen and their locatn in time O(n) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] isomorphic trees
bool isIsomorphic(List* h1,List* h2)
{
if(!h1 !h2) return true;
if(h1 h2)
return(h1-data == h2-data isIsomorphic(h1-left,h2-right)
isIsomorphic(h1-right,h2-left));
else return false;
}
On Tue, Jun 8, 2010 at 8:31 PM, divya sweetdivya@gmail.com wrote:
Two binary trees T1 and T2 are isomorphic if T1 can be transformed
into T2 swapping left and right children of the nodes in T1.Give an
algorithm to report whether 2 given binary trees are isomorphic.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Simplicity is prerequisite for reliability.
– Edsger W. Dijkstra
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: Variable number of integers
I would say in most situations it is a stack of linked lists (queues). I'd suggest for the sake of simplicity and problem solving, don't think of it that way. Think of it as a stack of 'objects'. These objects can be of any type. Type can be an integer, a float, a pointer or an entire array. Makes it easier to think, design and code. -Minotauraus. On Jun 8, 2:52 am, Raj N rajn...@gmail.com wrote: What do you mean by a stack or a queue in which each item is a variable number number of integers? Is it a queue of a queue, queue of a stack etc -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] matix flipping
This question was asked in a Microsoft interview 2 years back. On Mon, Jun 7, 2010 at 8:05 PM, divya jain sweetdivya@gmail.com wrote: let a[n][n] be the input array nd b[][] be the output for(i=0;in;i++) for(j=0;jn;j++) b[i][j]=a[n-j-1][n-i-1] On 7 June 2010 08:26, sharad sharad20073...@gmail.com wrote: write a c routine to flip an nXn matrix about its non major diagnol 3 4 5 6 7 9 1 2 8 Transpose is: 8 9 5 2 7 4 1 6 3 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: Single ordered list
Divide and Conquer approach works. Look up merge sort. I don't know how the most efficient way. Actually I'm not sure if there are many ways to do this. It will take O(n) time either way (unless there are other specifics given which we can make use of). On Jun 8, 7:29 am, Raj N rajn...@gmail.com wrote: What is the most efficient way of combining 2 separate ordered list into a single ordered list ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] min no of policemen
edge is the link connecting two nodes of a tree On 8 June 2010 11:23, Anurag Sharma anuragvic...@gmail.com wrote: Can you expain edge of the tree. I could not get that. Anurag Sharma On Tue, Jun 8, 2010 at 5:53 AM, sharad kumar aryansmit3...@gmail.comwrote: for placing police man we can use bellman ford bfs.or even make use of topological sort. On Mon, Jun 7, 2010 at 9:59 PM, divya sweetdivya@gmail.com wrote: consider a tree. policemen is to be placed such that for each edge of tree, there is a policeman on atleast one side of each edge. tell the min no. of policemen and their locatn in time O(n) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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 nos
Yeah, I didn't get the question either. Do you want to generate these numbers or do you want to be able to tell if the number input is valid or not? And how does Fibo. fit in the picture either way? On Jun 7, 8:13 pm, Dave dave_and_da...@juno.com wrote: Hmmm. The first few Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... Of these, 3, 13, and 55 have binary representations with two 1-bits in a row. And 9, 10, 17, 18, etc are not included. So what was your question? Dave On Jun 7, 9:28 pm, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: So u want efficient algo for fibonacci numbers? -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Pointer to a constant
@Raj, Sorry for the confusion yes, you are right that 1st one is giving warning/error though for 2nd case int i=5; const int *ptr=i; *ptr++; i am nt getting any error/warning (gcc) and i remains 5 but int i=5; const int *ptr=i; (*ptr)++; is giving error Mohit Ranjan On Tue, Jun 8, 2010 at 9:06 PM, Raj N rajn...@gmail.com wrote: Actually the first statement i gave const int i=5; int *ptr=i is itself giving an error on gcc and a warning on borland. We have to modify it as const int *ptr=i otherwise it gives illegal pointer conversion error. On Tue, Jun 8, 2010 at 12:11 PM, divya jain sweetdivya@gmail.comwrote: i think both statements shd give error. as u r trying to change int to const int in 2 and const int to int in 1.. On 7 June 2010 19:59, mohit ranjan shoonya.mo...@gmail.com wrote: @Raj, no they are not same case 1: i is const case 2: ptr is const and whatever is const cann't be modified Mohit Ranjan On Mon, Jun 7, 2010 at 3:01 PM, Raj N rajn...@gmail.com wrote: Can someone tell me the difference between 1) const int i=5; 2) int i=5; int *ptr=i; const int *ptr=i; In the first case i can be modified via ptr i.e *ptr++ is valid. In the second case *ptr++ is illegal. Why is that so? Aren't they same? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Number of sequences of n binary digits that don't contain two 1's in a row
recursion. for length n if the count is T(n) then T(n) = 1st digit 0 + 1st digit 1 = T(n-1) + 1st digit 1 2nd digit 0 = T(n-1) + T(n-2) QED. On Tue, Jun 8, 2010 at 9:03 PM, Raj N rajn...@gmail.com wrote: I just checked out with so many possibilities and it is indeed matching. I may not be correct though. On Tue, Jun 8, 2010 at 7:50 PM, divya jain sweetdivya@gmail.comwrote: how do u come to this formula T(n)=fib(n+2).. plz explain On 7 June 2010 21:19, saurabh gupta sgup...@gmail.com wrote: it might be referring to no of sequences (say T(n) ) with no consecutive 1's for n = 3, ans would be 5 viz. 000, 001, 010, 100, 101 T(n) = fib(n+2) where fib = Fibonacci series which is interesting. On Sat, Jun 5, 2010 at 11:40 AM, Raj N rajn...@gmail.com wrote: @sharad: What about 101 even it doesn't have two 1's in a row On Sat, Jun 5, 2010 at 8:59 AM, sharad kumar aryansmit3...@gmail.comwrote: @rajn.can it be subsequence doesnt have one's too.hence 000,001,010,100 is required answer. On Sat, Jun 5, 2010 at 12:13 AM, Raj N rajn...@gmail.com wrote: Hi, I came across this question to find the number of sequences of n binary digits that don't contain 2 1's in a row. I wanted to know what exactly this means. Is it like if n=3 then compute all binary numbers having 3 digits which don't have consecutive 1's 110, 011, 111 ?? If not help me understanding it. Thanks!! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: sorted 2-d array
@senthilnathan: Indeed a nice logic. Complexity is O(logn) worst case(if all elements are negative). http://codepad.org/hRbYV287 On Tue, Jun 8, 2010 at 8:18 AM, Minotauraus anike...@gmail.com wrote: Actually, this might not always be the best approach. Example: -1 1 2 3 4 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 2*N = 10 steps. With my algo, you'll go: Step 1: top-left: negative, count++, Step2: [0][1] non negative, set limitRow=0 (or 1 depending on how you code) Step3: for([i][j] limitRow) check [1] [0]: non negative, set limitColumn = 0; since i=limitRow, j=limitCol, stop; count =1. We can do it in O(n * log n) by individually binary-searching for zero on each of the rows. Once we get the index of the first position where zero appears, counting the number of negative number is straight-forward. What if there are no zero elements at all? -Minotauraus. Here is an even better O(N) algorithm which is very elegant: Consider the bottom-left element of the given 2-D array. If it is negative, the whole of first-column is negative. So we can add that count and ignore that column from then onwards. If it is non-negative, the whole of last-row is non-negative. So we can ignore that row without changing the count. Therefore, by just doing one comparison we are able to eliminate one row or one column. We can iteratively follow this approach and it will terminate in exactly 2*N steps. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: constraints satisfied?
Your time complexity is not O(c) but O(n^2) -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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 nos
Fib comes because she wants the number of such sequences -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: ds
which is just the recursive version of the abovementioned iterative solution. P.S. -Please remove this quoted text when you are composing -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
