Re: [algogeeks] Re: aai + bj + ck =0
Spotted a mistake in my approach. Heaps are not good for searching purpose [:|] Can anybody shed light on building Red-Black trees from a random array and the search time for an element ? On Tue, Nov 3, 2009 at 3:49 PM, anilkumarmyla wrote: > I propose another solution with O(N LogN) Time Complexity and O(N^2) Space > complexity (not sure if it would count towards space or time) > > Space > 1) Generate all possible combinations of A[i] + B[j] and maintain them in > an array D (N^2 array) ---> O(N^2) > 2) Build a min or max heap out of D array using bottom up building ---> > O(N^2) > > Now D contains all possible sums of A[i] and B[j] in heap formation and the > maximum height of the heap is O( Log N^2) = O(Log N) > > Time > 1) For each C[k] search for -C[k] in the D heap. Search takes time atmost > the height of the heap ---> O(N Log N) > > Please correct me if I'm wrong. > -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: aai + bj + ck =0
I propose another solution with O(N LogN) Time Complexity and O(N^2) Space complexity (not sure if it would count towards space or time) Space 1) Generate all possible combinations of A[i] + B[j] and maintain them in an array D (N^2 array) ---> O(N^2) 2) Build a min or max heap out of D array using bottom up building ---> O(N^2) Now D contains all possible sums of A[i] and B[j] in heap formation and the maximum height of the heap is O( Log N^2) = O(Log N) Time 1) For each C[k] search for -C[k] in the D heap. Search takes time atmost the height of the heap ---> O(N Log N) Please correct me if I'm wrong. -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: aai + bj + ck =0
That way your solution takes more than O(N^2), because of the AGAIN loop. On Sun, Nov 1, 2009 at 1:09 PM, daizi sheng wrote: > with all arrays sorted firstly, if you enumerate ai, bj in ascedning order, > ck will be sure in descending order. > > foreach(ai in A) > ck = largest element in C > foreach(bj in B) >AGAIN: > if(ai + bj + ck == 0) algorithm over > if(ai + bj + ck > 0) ck change to its neighbor in C and goto AGAIN > if(ai + bj + ck < 0) continue checking next bj > -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: aai + bj + ck =0
No matter whatever i could think of, I am unable to do better than N^3 @daizi sheng I don't get your algorithm "2. enumerate ai, bj both in ascending order," Will that really help ? In what way ? -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Interesting array multiplication problem
Nice solution Ramaswamy... --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: search your friend
Anyway the solution is O(d) [:)] which is asked to be proved. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: search your friend
This is a simple extension of finding a friend on a single road without knowing his position. 1) n=0 2) Travel 2^n distance on the first road. If you find your friend DONE else return back to the crossing 3) Travel 2^n distance on the second road. If you find your friend DONE else return back to the crossing 4) Travel 2^n distance on the third road. If you find your friend DONE else return back to the crossing 5) Travel 2^n distance on the fourth road. If you find your friend DONE else return back to the crossing 6) n = n+1 GOTO STEP 2 Lets analyze the algo Assume d can be written as 2^a for some a ( can be extended to cases when d is not the form of 2^a) Assume the worst case of your friend being in the fourth road. Then the total distance travelled by you till you find your friend is = 4 * 2 * ( 2^0 + 2^1 + 2^2 + ... + 2^a) // The factor of 2 at the beginning is for your returning back = 8 * (2^a+1 - 1) = 8 * (2d-1) which is O(d) --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: random number [a....b]
Another way of doing... Random number between [a,b] = a + Random number between [0,b-a] c = a + (rand( )%(b-a+1)) ; --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: find triangle in a graph
On Sun, Sep 6, 2009 at 5:47 PM, kunzmilan wrote: > This problem can be solved by finding polynomial of the graph. > kunzmilan > @kunzmilan : What do you mean by polynomial of the graph ? Is it the cube of the adjacency matrix? --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Cut your mobile bill.
For God's sake, this is no advertising group... Please stop such mails. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: puzzle any answers
Listing all the 6 possibilities, we can rule out 3 of them 1. C L A 2. L C A 3. L A C 4. C A L --- violates Linda having red hair, given the third one had black hair 5. A L C --- violates Amy had no musical capabilities , given the winner was a musician. 6. A C L --- same as above --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: puzzle any answers
Cindy(C) Linda(L) Amy(A) The three possible solutions are : 1st to 3rd position in order 1. C L A Cindy is a musician, Linda is a math-major and has red hair, Amy has black hair 2. L C A Linda is a musician and has red hair, Cindy is a math-major, Amy has black hair 3. L A C Linda is a musician, Amy is a math-major and has black hair, No qualities for Cindy --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: puzzle any answers
Sorry, the third one should be3. L A C Linda is a musician, Amy is a math-major , Cindy has black hair On Thu, Jul 2, 2009 at 10:33 AM, anilkumarmyla wrote: > Cindy(C) Linda(L) Amy(A) > The three possible solutions are : 1st to 3rd position in order > > 1. C L A > Cindy is a musician, Linda is a math-major and has red hair, Amy has black > hair > > 2. L C A > Linda is a musician and has red hair, Cindy is a math-major, Amy has black > hair > > 3. L A C > Linda is a musician, Amy is a math-major and has black hair, No qualities > for Cindy > --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re:
Even a fourth grade student can solve that... --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
