[algogeeks] Re: Division into 2 sets
Should the difference be = 0 always ?
On Fri, Aug 14, 2009 at 6:57 PM, fundoonick fundoon...@yahoo.co.in wrote:
Problem:
I have a set of positive integers. I have to divide it into 2 sets such
that the difference of the sums of both sets is minimum.
For ex, the given set of +ve integers is: 1,2,3,4
I divide it into 2 sets {1,4} and {2,3} such that the difference of their
sum (1+4=)5 - (2+3=)5 = 0
This is the least possible difference.
Pls help.
--
Ciao,
Ajinkya
--~--~-~--~~~---~--~~
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: Division into 2 sets
sorry i meant =0 .. or are negative differences allowed ?
On Fri, Aug 14, 2009 at 7:02 PM, Ajinkya Kale kaleajin...@gmail.com wrote:
Should the difference be = 0 always ?
On Fri, Aug 14, 2009 at 6:57 PM, fundoonick fundoon...@yahoo.co.inwrote:
Problem:
I have a set of positive integers. I have to divide it into 2 sets such
that the difference of the sums of both sets is minimum.
For ex, the given set of +ve integers is: 1,2,3,4
I divide it into 2 sets {1,4} and {2,3} such that the difference of their
sum (1+4=)5 - (2+3=)5 = 0
This is the least possible difference.
Pls help.
--
Ciao,
Ajinkya
--
Ciao,
Ajinkya
--~--~-~--~~~---~--~~
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: Missing numbers
use hashing. On Wed, Jul 29, 2009 at 4:50 PM, Vijayasarathy K vijaykan@gmail.comwrote: Consider an array of 'n' elements which contains all except 2 numbers from 1(n + 2). How can we find the 2 missing elements? -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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: permuting the elements of an array
Yeah c++ STL nextpermutation api will do it .. good solution Miroslav! On Tue, Jun 23, 2009 at 10:25 PM, Miroslav Balaz gpsla...@googlemail.comwrote: It is also so easy, but maybe requires more lines of code you only need count number of used number for each 1..n and then...(repeat recursive approach) ONE LINE SOLUTION IN C++ ok use next permutation from STL, read how it works for other language and initialize array 11223344, and do while next_permutaion()... it actualy gives you always next lexicographical permutation of sequence you can also view source code of it in libraries 2009/6/23 Ralph Boland rpbol...@gmail.com I have an array of objects and I need to generate all permutations. e.g. for [1,2,3] I get: [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] This problem is actually easy to solve and in fact there is a purely iterative solution. However in my case I also need to solve a variant of this problem. In this variant the array has 2n elements grouped into n groups of two elements where each 2 element pair are equal. For example for array [1,1,2,2] I get: [1,1,2,2] [1,2,1,2] [1,2,2,1] [2,1,1,2] [2,1,2,1] [2,2,1,1] Note that in the first case I get n! permutations whereas in the second case I get (2n)! / 2^n permutations. I want to generate the permutations efficiently. I particular it is unacceptable to generate the (2n)! combinations and then remove the duplicates. I have come up only with complicated ways of doing this but I am hoping someone can post or reference a simpler solution. A solution that generalizes in various ways would be nice but not important to my particular problem. I will be implementing the final solution in Smalltalk (Squeak) and eventually in other languages as part of an implentation of the spine tree decomposition data structure. It will be released (in Squeak at least) under the MIT license. Thanks for any help provided. Ralph Boland -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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:
Hey I have the answer but i dont have office 2007 so cant open the xlsx file .. I dont have any MS office version ... can you use something like google spreadsheets ? On Tue, Jun 2, 2009 at 3:00 PM, Aminooo~ amin...@gmail.com wrote: *Dear Friends,* * * *A question for the genius, the one who solve the problem will write the name in the attached file.* *IF; 2+3=10* * 7+2=63* * 6+5=66* * 8+4=96* *THEN;* * 9+7=???* *The answer is the password to open the file attached* * * * * *Best Regards* *Aminooo.com* http://www.aminooo.com -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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:
Yeah :) On Tue, Jun 2, 2009 at 3:22 PM, Arun arunm...@gmail.com wrote: Spammers have really become smarter and smarter... On Tue, Jun 2, 2009 at 2:44 AM, Vaibhav Jain vaibhav...@gmail.com wrote: Hi dude...i solved it and sending u back with my name. On Tue, Jun 2, 2009 at 3:00 PM, Aminooo~ amin...@gmail.com wrote: *Dear Friends,* * * *A question for the genius, the one who solve the problem will write the name in the attached file.* *IF; 2+3=10* * 7+2=63* * 6+5=66* * 8+4=96* *THEN;* * 9+7=???* *The answer is the password to open the file attached* * * * * *Best Regards* *Aminooo.com* http://www.aminooo.com -- Thanks Regards Vaibhav Jain | Product Engineer, Technology @ Rediff.Com India Limited | | E-mail :: vaibh...@rediff.co.in | | Cell :: +91-97691 67938| -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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: Semaphore
did you try the wiki : http://en.wikipedia.org/wiki/Semaphore_(programming)? On Sun, May 31, 2009 at 4:57 PM, Miroslav Balaz gpsla...@googlemail.comwrote: Does anybody know how to simulate semaphore by binary semaphore?I think it is easy, but i cant find it on internet. thanks -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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: Deciding on a project
Yeah .. I am a programmer too and industry coding sucks most of the times.. You should not opt for real world programming at this age .. make your basics strong. If you are really interested in algorithms and want to go ahead and do research in algorithms and their complexity then you should learn complexity theory or theory of computation which will build a really strong foundation at this age ! On Thu, May 28, 2009 at 8:20 PM, prajwal suhas p prajwalp...@gmail.comwrote: On Sun, May 24, 2009 at 4:35 PM, Albert albert.xtheunkno...@gmail.comwrote: Hi, I'm 15 years old and I'm interested in algorithms, data structures, computational geometry and general coding. What sort of projects could I do in my spare time that fuels my interests and is something I can go on with? Other than competing in USACO... Thanks Albert From my experience, I suggest you to begin by *keep on solving* more riddles, puzzles, unsolved problems. This would improve your thinking power greatly. Then start up with discrete maths, make your *math* foundation strong. And most important is, during this journey try to be *independent* as far as possible in arriving to the logic to the problems you solve. You can improve your coding skills overtime by incorporating these changes. Good luck, cheers! -- There is little difference in people, but that little difference makes a big difference. The little difference is attitude. The big difference is whether it is positive or negative. -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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: Deciding on a project
Dude give the guy a break .. he is just 15 ! He needs to get his fundamentals strong first before optimizing the codec to minimize the power consumption .. What do you mean by indusrty coding vs real time coding and when did i compare them !? fyi - I was comparing theoretics to applications :) On Thu, May 28, 2009 at 9:59 PM, sharad kumar aryansmit3...@gmail.comwrote: brother could u pls tell how to optimise the codec to minimise the power consumption by ur processor in ur mobile .the best solution is given by MS engineers and its in msdn.pls read it .industry coding and rea ltime code a || tracks.never ever insult industry programmers.. On Thu, May 28, 2009 at 8:48 PM, Ajinkya Kale kaleajin...@gmail.comwrote: Yeah .. I am a programmer too and industry coding sucks most of the times.. You should not opt for real world programming at this age .. make your basics strong. If you are really interested in algorithms and want to go ahead and do research in algorithms and their complexity then you should learn complexity theory or theory of computation which will build a really strong foundation at this age ! On Thu, May 28, 2009 at 8:20 PM, prajwal suhas p prajwalp...@gmail.comwrote: On Sun, May 24, 2009 at 4:35 PM, Albert albert.xtheunkno...@gmail.comwrote: Hi, I'm 15 years old and I'm interested in algorithms, data structures, computational geometry and general coding. What sort of projects could I do in my spare time that fuels my interests and is something I can go on with? Other than competing in USACO... Thanks Albert From my experience, I suggest you to begin by *keep on solving* more riddles, puzzles, unsolved problems. This would improve your thinking power greatly. Then start up with discrete maths, make your *math* foundation strong. And most important is, during this journey try to be *independent* as far as possible in arriving to the logic to the problems you solve. You can improve your coding skills overtime by incorporating these changes. Good luck, cheers! -- There is little difference in people, but that little difference makes a big difference. The little difference is attitude. The big difference is whether it is positive or negative. -- Ciao, Ajinkya -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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: Deciding on a project
Try some open source projects .. thats the best place to start. You may want to take a look at Apache's page ... On Mon, May 25, 2009 at 11:58 AM, Albert albert.xtheunkno...@gmail.comwrote: Miroslav Balaz wrote: you should register on www.topcoder.com!!! and according to your skill you should try to solve some problems fromhttp://www.spoj.pl/or acm.sgu.ru Okay, but I'd like an idea of real-world programming and not just trying to solve hard problems under timed conditions. Any ideas? -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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: Deciding on a project
And also try your hand at www.projecteuler.net On Sun, May 24, 2009 at 5:57 PM, Miroslav Balaz gpsla...@googlemail.comwrote: you should register on www.topcoder.com !!! and according to your skill you should try to solve some problems from http://www.spoj.pl/ or acm.sgu.ru If you were from Slovakia or czech i'd recomend you www.ksp.sk 2009/5/24 Albert albert.xtheunkno...@gmail.com Hi, I'm 15 years old and I'm interested in algorithms, data structures, computational geometry and general coding. What sort of projects could I do in my spare time that fuels my interests and is something I can go on with? Other than competing in USACO... Thanks Albert -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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: crossword solver using the exact cover problem (algorithm X)
Check the references in the wiki page of Algorithm X On Tue, May 19, 2009 at 9:53 PM, std...@gmail.com std...@gmail.com wrote: Hello! I'm trying to implement a crossword solver. My intuition is telling me that the problem can be modeled with the exact cover problem and can thus be solved with algorithm X (implementing dancing links.). I haven't found any useful resources while searching on the net so I'm wondering weather anyone knows if there is any translation of the crossword problem to the exact cover problem? Any hints/resources are appreciated! Thanks. -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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: Algorithmic challenge?
It is working if you remove the space bet // and ilpubs here you go : http://ilpubs.stanford.edu:8090/750/1/2003-29.pdf On Thu, May 7, 2009 at 8:44 PM, Miroslav Balaz gpsla...@googlemail.comwrote: the link is not working http:// ilpubs.stanford.edu:8090/750/1/2003-29.pdf 2009/5/6 UKuser spiderc...@yahoo.co.uk As per my previous post, is there anybody who can explain section 3 to me from the PDF mentioned in this link: http://groups.google.com/group/algogeeks/t/6ccc544529b01d10 Any help would be great. A -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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: exact solution to this recursion equation
Yes you are right Miroslav ... that was a pretty dumb mistake i made :) On Wed, Apr 1, 2009 at 9:25 PM, Miroslav Balaz gpsla...@googlemail.comwrote: I am not sure if you can use such approach for example given T(n)=2*T(n/2)+n can be expanded also that way, but it is Omega(n log n),like merge sort T(n)=2T(n/2)+n=2(2T(n/4)+n/2 )+n=4T(n/4)+2n=4(2T(n/8)+n/4 )+2n=8T(n/8)+3n there will be always only contains linear terms, however ... 2009/4/1 Ajinkya Kale kaleajin...@gmail.com The intuitive proof maybe that if you try to expand the recursion over a few steps such that it tends to go towards T(1) then you never see a term greater(in order) than O(n^2) .. On Wed, Apr 1, 2009 at 2:56 PM, Miroslav Balaz gpsla...@googlemail.comwrote: but you need some kind of proof, for that.i alsow see from first sight that it is O(n^2), but i wane just fo verify that. 2009/4/1 Ajinkya Kale kaleajin...@gmail.com I dont think you even need to solve the recursion .. by looking at it it seems to be O(n^2) right ? On Wed, Apr 1, 2009 at 2:18 PM, Miroslav Balaz gpsla...@googlemail.com wrote: no that is just asymptotic recursion. the answer is between n^2 and n^2log n of coure the answer is n^2; T(n)=n^2/2-n^2/4+n^2=n^2/4+n^2=T(n/2)+n^2=by master theorem n^2 T(n) B(n)=2B(n/2)+n^2 what is by master theorem n^2 log n n n/2 n/2 n/4 n/4 n/4n/4 T(n/2)=2T(n/4)-4T(n/8)+n^2/4 T(n)=4T(n/4)-8T(n/8)+n^2/2-4T(n/4)+n^2=-8T(n/8)+3n^2/2 you may pick up what is solution 2009/3/31 Arunachalam arunachala...@gmail.com What is the base value of this recursion? Without a base value the recursion is not solvable? There should be some base value like T(x) = 1 where x = 1. regards, Arun. On Mon, Mar 30, 2009 at 12:35 AM, nikoo shaker.far...@gmail.comwrote: Hello everybody I need the solution to the following recursion equation T(n) = 2 T (n/2) - 4 T (n/4) + n^2 does anybody know how to solve this equation? I appreciate any help thanks nikoo -- === want to know more about me http//ww.livejournal.com/users/arunachalam -- Ciao, Ajinkya -- Ciao, Ajinkya -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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: exact solution to this recursion equation
I dont think you even need to solve the recursion .. by looking at it it seems to be O(n^2) right ? On Wed, Apr 1, 2009 at 2:18 PM, Miroslav Balaz gpsla...@googlemail.comwrote: no that is just asymptotic recursion. the answer is between n^2 and n^2log n of coure the answer is n^2; T(n)=n^2/2-n^2/4+n^2=n^2/4+n^2=T(n/2)+n^2=by master theorem n^2 T(n) B(n)=2B(n/2)+n^2 what is by master theorem n^2 log n n n/2 n/2 n/4 n/4 n/4n/4 T(n/2)=2T(n/4)-4T(n/8)+n^2/4 T(n)=4T(n/4)-8T(n/8)+n^2/2-4T(n/4)+n^2=-8T(n/8)+3n^2/2 you may pick up what is solution 2009/3/31 Arunachalam arunachala...@gmail.com What is the base value of this recursion? Without a base value the recursion is not solvable? There should be some base value like T(x) = 1 where x = 1. regards, Arun. On Mon, Mar 30, 2009 at 12:35 AM, nikoo shaker.far...@gmail.com wrote: Hello everybody I need the solution to the following recursion equation T(n) = 2 T (n/2) - 4 T (n/4) + n^2 does anybody know how to solve this equation? I appreciate any help thanks nikoo -- === want to know more about me http//ww.livejournal.com/users/arunachalam -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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: exact solution to this recursion equation
The intuitive proof maybe that if you try to expand the recursion over a few steps such that it tends to go towards T(1) then you never see a term greater(in order) than O(n^2) .. On Wed, Apr 1, 2009 at 2:56 PM, Miroslav Balaz gpsla...@googlemail.comwrote: but you need some kind of proof, for that.i alsow see from first sight that it is O(n^2), but i wane just fo verify that. 2009/4/1 Ajinkya Kale kaleajin...@gmail.com I dont think you even need to solve the recursion .. by looking at it it seems to be O(n^2) right ? On Wed, Apr 1, 2009 at 2:18 PM, Miroslav Balaz gpsla...@googlemail.comwrote: no that is just asymptotic recursion. the answer is between n^2 and n^2log n of coure the answer is n^2; T(n)=n^2/2-n^2/4+n^2=n^2/4+n^2=T(n/2)+n^2=by master theorem n^2 T(n) B(n)=2B(n/2)+n^2 what is by master theorem n^2 log n n n/2 n/2 n/4 n/4 n/4n/4 T(n/2)=2T(n/4)-4T(n/8)+n^2/4 T(n)=4T(n/4)-8T(n/8)+n^2/2-4T(n/4)+n^2=-8T(n/8)+3n^2/2 you may pick up what is solution 2009/3/31 Arunachalam arunachala...@gmail.com What is the base value of this recursion? Without a base value the recursion is not solvable? There should be some base value like T(x) = 1 where x = 1. regards, Arun. On Mon, Mar 30, 2009 at 12:35 AM, nikoo shaker.far...@gmail.comwrote: Hello everybody I need the solution to the following recursion equation T(n) = 2 T (n/2) - 4 T (n/4) + n^2 does anybody know how to solve this equation? I appreciate any help thanks nikoo -- === want to know more about me http//ww.livejournal.com/users/arunachalam -- Ciao, Ajinkya -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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: Need Help in a new problem
I think there is a 4^k kernel for TSP .. On Sat, Mar 14, 2009 at 4:49 PM, Miroslav Balaz gpsla...@googlemail.comwrote: I don't know any concrete real life problem, of course everyting real life problem that is in NP can be reducet to this problem. That includes timetable sheduling. | think there is no such problem in networks, because you need to know topology ad it has to be fixed. And if you want to make multicast, than it is faster if you do it in parallel way. There is still to few people in this group, you should encourage more people to yoin, if you want it to be usefull. The metric TSP is somewhat approximable, and euclidean has PTAS 2009/3/14 Amina Maarouf amina.maar...@gmail.com I found a number of real life applications for the problem, like garbage collection, a version of postman problem, gas system construction.. I am looking for applications for the problem in networks, if any one can help. On 3/14/09, Miroslav Balaz gpsla...@googlemail.com wrote: NP what? 2009/3/13 Amina Maarouf amina.maar...@gmail.com this problem was proved to be NP in a conference paper published recently. On Fri, Mar 13, 2009 at 10:44 AM, Miroslav Balaz gpsla...@googlemail.com wrote: maybe you are not wrong. but with high probability you are wrong. In general case, this problem cannot ba approximated for any polynomialy computable function f. You can tell me the algorithm or give me reason why trirvial reduction from TSP does not work here? 2009/3/13 Ajinkya Kale kaleajin...@gmail.com If i am not wrong there is a parameterized algorithm for this which is in P On Fri, Mar 13, 2009 at 3:40 AM, Miroslav Balaz gpsla...@googlemail.com wrote: Ok this is NP-comlete... so no fast algorithm is known 2009/3/12 Amina Maarouf amina.maar...@gmail.com Dear All; I need some help on the following problem: Given a weighted graph ( v, e) and a set of marked vertices v' subset to v and a source node n. Find a cycle to that visits all vertices in v' and returns to n, such that the total cost is minimum. if anyone has ideas of algorithms, or applications that may map to this problem, it will be a great help to me. thanks amiiina -- Ciao, Ajinkya -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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 SquareRoot of a number
We wont suggest you to use sqrt() function but we will suggest that you do your homework on your own...else atleast post what problem are you facing in implementing the same. Here is a pointer for your problem. You can use any of the approximation methods mentioned here : http://en.wikipedia.org/wiki/Methods_of_computing_square_roots On Mon, Feb 9, 2009 at 11:12 PM, rakesh sathu rakesh2...@gmail.com wrote: Can anybody help me for writing code in 'c'-language to find the square root of a number? Plz dont suggest me to use 'sqrt()' function -- Thank you, Rakesh Reddy.S -- Ciao, Ajinkya --~--~-~--~~~---~--~~ 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: Backtracking algorithm
Can you be a bit more specific ? On Tue, Nov 4, 2008 at 9:12 AM, Luciano Pinheiro [EMAIL PROTECTED]wrote: Please, help me people ! I need understand and develop a backtracking algorithm to include into a program and I don't nkow where find these. Someone have any document, or URL to indicate to me ? Sincerely, Luciano Soares Pinheiro Jr. Analista desenvolvedor Sr. -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: recurrence relation
A friend asked me this question ... Also asked me another modification , T(n) = T[ *mod*(n-2^( ceil(log n) )) ] +O(n) Can we find the complexity for such a recurrence ? On Mon, Sep 15, 2008 at 9:17 AM, Ashesh [EMAIL PROTECTED] wrote: You should agree with the fact that log(n-1) = ceil(log(n-1)) log(n-1)+1, which would mean that n-1 = 2^(ceil(log(n-1))) 2(n-1), thus, 2-n n-2^ceil(log(n-1)) = 1. Thus, unless 2-n1, there are no such possible values. We must therefore have that n1. Moreover, as long as the base of the logarithm is less than or equal to 2, n-2^ceil(log(n)) =0, and the second case shall hold. Where did you get this question from, if I may ask? On Sep 14, 10:00 pm, Ajinkya Kale [EMAIL PROTECTED] wrote: Actually there is one more condition to it but i thought it will be more complicated to mention it, at each step we subtract 2^(ceil(log n) if n-2^( ceil(log n) ) 0 else we subtract n-2^( ceil(log (n-1)) ) So, T(n) = T[ n-2^( ceil(log n) ) ] +O(n)for n-2^( ceil(log n) )0 = T[ n-2^( ceil(log (n-1)) ) ] + O(n) for n-2^( ceil(log n) )0 On Sun, Sep 14, 2008 at 9:51 AM, Ashesh [EMAIL PROTECTED] wrote: In such a case, ceil(log(n)) log(n), and if the base of the logarithm is 2 or less, then 2^(ceil(log(n)) n, and the question fails to be valid. The base of the logarithm has to be greater than 2. On Sep 14, 9:26 pm, Ajinkya Kale [EMAIL PROTECTED] wrote: Sorry i forgot, it is ceil(log n) so n-2^( ceil(log n) ) is not equal to zero.. On Sun, Sep 14, 2008 at 8:57 AM, Karthik Singaram Lakshmanan [EMAIL PROTECTED] wrote: Isn't n-2^logn = 0? since 2^logn = n if you are talking about log base 2 -- Ciao, Ajinkya -- Ciao, Ajinkya -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: recurrence relation
Sorry i forgot, it is ceil(log n) so n-2^( ceil(log n) ) is not equal to zero.. On Sun, Sep 14, 2008 at 8:57 AM, Karthik Singaram Lakshmanan [EMAIL PROTECTED] wrote: Isn't n-2^logn = 0? since 2^logn = n if you are talking about log base 2 -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: finding whether the number is prime or not ...
There are a few really good randomized algorithms on primality testing.
The AKS algorithm is i guess the best know deterministic primality testing
algo.
On Sat, Jun 28, 2008 at 1:22 PM, Sumedh Sakdeo [EMAIL PROTECTED]
wrote:
u can refer this site... its very cool...
http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm
On 6/27/08, Arunachalam [EMAIL PROTECTED] wrote:
What is the maximum value of number that you need to find out?
A 32 bit number is prime if it satisfies the Fermat's theorem for 2,3,5,7
and 11. This is the fastest way to find out whether a number is prime or
not.
regards,
Arunachalam.
On Fri, Jun 27, 2008 at 12:46 AM, rowdy ranga [EMAIL PROTECTED]
wrote:
hello sir,
ya it is possible in o(n).dnt worry
first we use a principle of sieve of erasthones
printf(nter no);
scanf(%d,num);
if((num%2)==0||(num%3)==0||(num%5)==0||(num%7)==0)
printf(notprime);
else
int i=2;
for(;inum/2;i++)
{
if((num%i)==0)
printf(not prime );
else printf(prime);
--
===
want to know more about me
http//ww.livejournal.com/users/arunachalam
--
Ciao,
Ajinkya
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: algo for finding the union of two sets ...
Yup there are . Refer horowitz sahani book on algorithms called fundamentals of algorithms On Mon, Jun 23, 2008 at 4:36 PM, zee [EMAIL PROTECTED] wrote: do we have an algo for finding the union of two sets ??? data structure suitable for set operations -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] recurrence equation
How do we solve recurrence relations of the form: T(c) = T( | c - 2^ceil(log_2(c)) | ) + O( 2^ceil(log_2c) ) What will be the approximate outcome of this equation if not exact ? -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: recurrence equation
Its ceiling so it will not always be zero. basically ceil(log_2(c)) gives the no. of bits of C. eg: C = 7 then ceil(log_2(c)) = 3 so | c - 2^ceil(log_2(c)) | = | 7-2^3| = 1 On Wed, Jun 4, 2008 at 2:31 PM, Nat Padmanabhan [EMAIL PROTECTED] wrote: looks like | c - 2^ceil(log_2(c)) | will be 0 if log is base 2. Obviously I am missing something, could you throw some light on that expression? On Wed, Jun 4, 2008 at 10:26 AM, Ajinkya Kale [EMAIL PROTECTED] wrote: How do we solve recurrence relations of the form: T(c) = T( | c - 2^ceil(log_2(c)) | ) + O( 2^ceil(log_2c) ) What will be the approximate outcome of this equation if not exact ? -- Ciao, Ajinkya -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Empty Binary tree???
On Tue, Jun 3, 2008 at 1:35 PM, Dave [EMAIL PROTECTED] wrote: The definition is recursive. The empty binary tree is the base case for the recursion. If a binary tree couldn't be empty, then all binary trees would have to be infinite. One way to think of this is that the left and right subtrees of the leaf nodes of the tree are empty trees. Don't confuse the nodes with any values associated with the nodes. The nodes are divided into three disjoint subsets, but duplicate values do not have to be divided correspondingly. Think of a tree describing family relationships. I have a second cousin whose name is the same as mine. There would be two nodes distinct nodes in the tree with value David S Dodson. These nodes would have different parents and grandparents, but the same great-grandparents. Nice example. Nevertheless family tree are suitable examples for general trees rather than binary trees , isnt it ? Dave On Jun 3, 5:55 am, Vinodh [EMAIL PROTECTED] wrote: Started reading about Binary Trees and got the following questions in mind. Please help. Definition of a Binary Tree from Data Structures using C and C++ by Tanenbaum goes like this, A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the 'Root' of the tree. The other two subsets are themselves binary trees, called the 'Left' and 'Right' subtrees of the original tree. My Questions: 1) Why they talk about a binary tree that is totally empty? I mean a binary tree with Zero elements? 2) A binary tree is partioned into three disjoint subsets. That means all the elements in a binary tree should be unique? Duplicate elements are allowed within a subtree? Any significance of this? Thanks, Vinodh -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Empty Binary tree???
Yup thats perfectly true. Its just that he is new to the concept so I added that family trees are usually not binary trees. In fact they may not even be trees ..they may be graph as Dave suggested ! On Tue, Jun 3, 2008 at 3:58 PM, Dave [EMAIL PROTECTED] wrote: Does that aspect of his question matter as to whether the tree is a binary tree or a general tree? The point is that the node and the value associated with the node are entirely different things. For that matter, my uncle's family tree is not a tree at all, since he has two paths up the tree to the same ancestor. This happened because someone in one subtree of that person married someone in anther subtree many generations later. Dave On Jun 3, 10:48 am, Ajinkya Kale [EMAIL PROTECTED] wrote: On Tue, Jun 3, 2008 at 1:35 PM, Dave [EMAIL PROTECTED] wrote: The definition is recursive. The empty binary tree is the base case for the recursion. If a binary tree couldn't be empty, then all binary trees would have to be infinite. One way to think of this is that the left and right subtrees of the leaf nodes of the tree are empty trees. Don't confuse the nodes with any values associated with the nodes. The nodes are divided into three disjoint subsets, but duplicate values do not have to be divided correspondingly. Think of a tree describing family relationships. I have a second cousin whose name is the same as mine. There would be two nodes distinct nodes in the tree with value David S Dodson. These nodes would have different parents and grandparents, but the same great-grandparents. Nice example. Nevertheless family tree are suitable examples for general trees rather than binary trees , isnt it ? Dave On Jun 3, 5:55 am, Vinodh [EMAIL PROTECTED] wrote: Started reading about Binary Trees and got the following questions in mind. Please help. Definition of a Binary Tree from Data Structures using C and C++ by Tanenbaum goes like this, A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the 'Root' of the tree. The other two subsets are themselves binary trees, called the 'Left' and 'Right' subtrees of the original tree. My Questions: 1) Why they talk about a binary tree that is totally empty? I mean a binary tree with Zero elements? 2) A binary tree is partioned into three disjoint subsets. That means all the elements in a binary tree should be unique? Duplicate elements are allowed within a subtree? Any significance of this? Thanks, Vinodh -- Ciao, Ajinkya- Hide quoted text - - Show quoted text - -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Empty Binary tree???
On Tue, Jun 3, 2008 at 6:02 PM, Vinodh [EMAIL PROTECTED] wrote: Wow...Got it. My refined understanding, 1) An empty tree is haveing zero nodes. Fine. Case (a) == I have only 1 node in a binary tree. That means it is a binary tree with 2 empty subtrees. Case (b) == I have only 2 nodes in a binary tree. That means it is a binary tree with 1 left subtree and 0 right subtree. Fine. Got a question here. Why one always makes the left node first and then the right node? It is just a convention I guess. For traversing the tree also we consider left subtree first then the right. But it is not always necessary that there will be a non empty left subtree. 2) In literature they talk about Nodes. Nodes can have anything stored on them. Thanks Dave for explaining with a nice example. On Jun 3, 8:58 pm, Dave [EMAIL PROTECTED] wrote: Does that aspect of his question matter as to whether the tree is a binary tree or a general tree? The point is that the node and the value associated with the node are entirely different things. For that matter, my uncle's family tree is not a tree at all, since he has two paths up the tree to the same ancestor. This happened because someone in one subtree of that person married someone in anther subtree many generations later. Dave On Jun 3, 10:48 am, Ajinkya Kale [EMAIL PROTECTED] wrote: On Tue, Jun 3, 2008 at 1:35 PM, Dave [EMAIL PROTECTED] wrote: The definition is recursive. The empty binary tree is the base case for the recursion. If a binary tree couldn't be empty, then all binary trees would have to be infinite. One way to think of this is that the left and right subtrees of the leaf nodes of the tree are empty trees. Don't confuse the nodes with any values associated with the nodes. The nodes are divided into three disjoint subsets, but duplicate values do not have to be divided correspondingly. Think of a tree describing family relationships. I have a second cousin whose name is the same as mine. There would be two nodes distinct nodes in the tree with value David S Dodson. These nodes would have different parents and grandparents, but the same great-grandparents. Nice example. Nevertheless family tree are suitable examples for general trees rather than binary trees , isnt it ? Dave On Jun 3, 5:55 am, Vinodh [EMAIL PROTECTED] wrote: Started reading about Binary Trees and got the following questions in mind. Please help. Definition of a Binary Tree from Data Structures using C and C++ by Tanenbaum goes like this, A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the 'Root' of the tree. The other two subsets are themselves binary trees, called the 'Left' and 'Right' subtrees of the original tree. My Questions: 1) Why they talk about a binary tree that is totally empty? I mean a binary tree with Zero elements? 2) A binary tree is partioned into three disjoint subsets. That means all the elements in a binary tree should be unique? Duplicate elements are allowed within a subtree? Any significance of this? Thanks, Vinodh -- Ciao, Ajinkya- Hide quoted text - - Show quoted text -- Hide quoted text - - Show quoted text - -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: A pair-selecting problem
On Wed, May 28, 2008 at 1:53 PM, Zeratul [EMAIL PROTECTED] wrote: On a board there are N * 2 pins colored with either black or white. The number of black pins is equal to that of white ones. Each pin has a location x, y, and x y are all integers (there are no more than one pins on the same location) We can pair a white pin located at x1, y1 with a black pin located at x2, y2 if x1 x2 and y2 y2. you mean y1 y2 right ? Now the problem is to find out the maximum number of pairs and print them (any two pairs cannot contain the same pin). My idea is to first find all the pins that can make a pair, and do a maximum bipartie matching. But it will cost O(N ^ 3) time. can you please explain how this will work ? Is there any better solution for this problem? The hint says that a greedy algorithm will be efficient. Sorry for my poor English. many thanks -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Enumerating trees
. On 5/14/08, pramod [EMAIL PROTECTED] wrote: Let's say we have E number of edges and V number of vertices. Any subgraph which is a tree with V vertices will have V-1 edges. So we need to retain V-1 edges and eliminate the rest E-(V-1). So in a brute force manner if we retain any set of V-1 edges and see if the resultant graph is indeed a tree or not. So we need to test for E C (V-1) such cases. This is definitely an upper bound. We may optimize the above exponential algorithm by not considering those edges which are not part of any cycles since they can't be removed. We can use the kircofs law. We will have to deal with only fundamental circuitrs and not other circuits And in the middle of removing the edges if we encounter an edge with vertex having a degree of only 1 then we can't remove that edge. On May 13, 10:51 pm, Bruno Avila [EMAIL PROTECTED] wrote: Yes, you're right. It depends on the topology of the graph. Do you have any references for the upper or lower bound? Or even an asymptotic of form O(2^k)? Bruno On Tue, May 13, 2008 at 12:28 PM, Geoffrey Summerhayes [EMAIL PROTECTED] wrote: On May 12, 8:20 pm, brunotavila [EMAIL PROTECTED] wrote: Hi people, How to calculate the number of binary trees that are subgraphs of a given connected, undirected, unweighted and simple (no parallel edges nor loops) graph? Haven't given it too much thought, but I believe the number is dependant on the actual topology of the graph. It should be possible to calculate an upper and lower bound, but for an accurate number for a given graph I think you're stuck with counting them. --- Geoff -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Red Black trees
Grab a copy of introduction to algorithm - Cormen,Rivest,Leiserson,Stein. It deals with Red Black trees in detail. On Sat, May 3, 2008 at 1:13 PM, Arunachalam [EMAIL PROTECTED] wrote: Search in the net. Red Black trees are explained here http://en.wikipedia.org/wiki/Red_black_tree If you have doubts in understanding the topic, please pose your specific question and doubt. Don't try to ask a general question for which it is easy to find the answer in the internet. regards, Arunachalam. On Sat, May 3, 2008 at 10:36 AM, Jothi [EMAIL PROTECTED] wrote: Hi All, I am new to this group, Can anyone of you please tell me wen will we go for rotations in RedBlack Trees while inserting a new node apart from recoloring. Is there anyway to easily determine which Rotation to be used ? Right or left ??? Regards, Bindhiya -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: An interesting graph problem
On 2/24/08, Sticker [EMAIL PROTECTED] wrote: I have a graph problem, which is different from the standard salesman problem. I say it is more difficult. In a graph, I have many vertexes with different colors. It is more easier to think of each vertex as a shop selling only one goods and vertexes with the same color selling the same goods. There are edges between any two vertexes, with different distances. You start at a specific position (different from any vertex), and have a list of goods you need to buy. Figure out an optimal path with shortest distance so you can get all the goods from the shops on the path. You are not required to start and end at the same position and edges and vertexes can be visited more than once if you want. If there is no color on vertex, or in other words, each vertex sells a distinct goods, then the above problem is identical to salesman problem. I dont think that makes is identical to TSP. Cause in TSP you have to visit every node. But in this case you are given a list of goods and each vetex sells unique good. Also in TSP we have to return to the start point , but this is not the case here ! But now we have colors on vertexes and once a vertex with a color is visited, you don't want to visit vertex with the same color (which will only increase the total distance). Since this problem is an extension of the standard salesman problem, the practical solution is probably heuristic. The key is, what heuristic strategy are you going to use. I think the problem a bit and come up with a very naive solution: For each vertex, calculate its distances to the closest vertexes with other colors. For vertexes with the same color, choose the one with the minimum total/average such distances. Then, only one vertex with a color is remained in the graph. Then use heuristic strategy for salesman problem. any other idea? -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: permuttaion
I think this is a homework question. Any algorithm book will give you an algorithm for permutation.Try google first. On Thu, Feb 21, 2008 at 3:44 AM, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: hi, can some one help me in writing an algorithm for finding permuttaion of 'n' numbers??..i have tried it many times.but not getting it...can anyone help me.. -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Frog Problem
Here is the link which discusses the porblem but instead of stones the problem talks of steps. But the problem is exactly the same. http://groups.google.com/group/programming-challenges/browse_thread/thread/cd2b733400989439/bb50217ab89c3f42?lnk=gstq=Steps#bb50217ab89c3f42 Check out the discussion on the above link. On 2/11/08, Abhijeet Singh [EMAIL PROTECTED] wrote: I have stones numbered from A-K and I have a Frog which can make a jump of one stone at a time or two stones at a time but no more then that. I will explain , assumes my stones are ABCDEFG K At any point say A, the frog can jump from A-B or from A-C but not from A-D or otherwise, when it reaches J, it can only make a hop of 1 as there are no more stones after that. Frog can not jump backwards. In how many ways can he reach from A-K, give a recursive formula for that. Print all possible paths that the Frog can choose while moving from A-K -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: a non-recursive algorithm that prints all the nodes of a binary tree in O(n)
I personally dont think so.
2008/2/11 Pradeep Muthukrishnan [EMAIL PROTECTED]:
Is it even possible to do taht in constant space?
2008/2/11 [EMAIL PROTECTED] [EMAIL PROTECTED]:
Thanks for all the effort. Sorry, I should have mentioned it earlier.
But, we are asked to do it without modifying the tree in any manner
and using no more than a constant space outside the tree.
On Feb 11, 8:17 am, phani bandaru [EMAIL PROTECTED] wrote:
Use inorder traversal without recursion.
On 2/11/08, James Fang [EMAIL PROTECTED] wrote:
Use a queue, assume the root of the binary tree : pRoot;
Below is the pseudo code:
enQueue(pRoot);
While( queue not empty )
{
pNode = outQueue();
print(pNode);
if(pNode-left)
{
enQueue(pNode-left);
}
if(pNode-right)
{
enQueue(pNode-right);
}
}
-邮件原件-
发件人: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED]
代表
[EMAIL PROTECTED]
发送时间: 2008年2月11日 8:13
收件人: Algorithm Geeks
主题: [algogeeks] a non-recursive algorithm that prints all the nodes
of a
binary tree in O(n)
This is an exercise problem in the book Introduction to Algorithms
by CLR. Could any one come up with an algorithm to do it.
--
pUrNamadah pUrNamidam
pUrNAt pUrNamudachyate
pUrNasya pUrNamAdAya
pUrNamevAvashiShyate- Hide quoted text -
- Show quoted text -
--
Ciao,
Ajinkya
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: road traffic
Hey I am interested too...pls do let me know what do we have to do.. On 1/24/08, Albert Sanchez [EMAIL PROTECTED] wrote: Hi, Anyone interested in road traffic strategies? Flow optimization, time dependent shortest paths problems? Albert -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: 8 puzzle problem
Check out any AI bookA good dynamic algo is illustrated in Horwitz Sahani book Fundamentals of Algorithms On Jan 10, 2008 10:03 AM, monu [EMAIL PROTECTED] wrote: Hi guys! i am working on 8puzzle problem, but i am not getting any Heuristic function to solve the problem. Can anyone suggest something? -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: How is the Big O actually calculated, time wise?
Big Oh notation only gives the proportionality of the time required for that particular algorithm. For an approximation you can assume some hypothetical machine and calculate the time taken using the costs for loads,stores,etc. And you can also find the total time for execution using the platform specific time commands. This gives a good comparison bet the expected and practical timings. But it is imp to note that in the practical timings the lower order terms also come into play for the complexity proportionality, hence the expexted and practical times mostly vary a bit. On 11/22/07, Sherry [EMAIL PROTECTED] wrote: I know how the complexity of an algorithms is calculated, but how would this relate to the time it takes? Let's say I have 25000 random numbers I'd like to sort with the selection sort. Now how could I use Big O notation to calculate the time taken to sort these numbers?? I mean I understand it's a O(n^2) sort, but how do you approximate time taken?? Thanks in advance. -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: array of 0s and 1s
A simple modification to quicksort will do the trick ! On 11/13/07, geekko [EMAIL PROTECTED] wrote: you are given an array of integers containing only 0s and 1s. You have to place all the 0s in even positions and 1s in odd position. And if suppose, no. of 0s exceeds no. of 1s or vice versa keep them untouched. Do in ONE PASS without taking extra memory.(modify array in place) -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Algo.. phone book
How about using a Red-Black tree ? On 11/9/07, Andrey [EMAIL PROTECTED] wrote: I thought about trie first but then I've change my mind and decided that I'd rater use a simple binary tree or even an sorted array. As we have quite limited set of first names and surnames we can easily index them i.e. store them in sorted array and use an index in the array indead of the entire name/surname (the array like this can also be easily compressed). Then we store pairs (surname_index, name_index) in sorted array and perform binary search by request. The complexity will be. log(S) - to find the index of surname where S is number of different surnames + log(N) - to find the index of name where N is number of different names + log(10 000 000) - to find pair (surname_index, name_index) The memory consumption estimate is clear. Can you estimate complexity and memory consmption of trie? That would be interesting!!! On Nov 9, 2:59 pm, Varun S V [EMAIL PROTECTED] wrote: I was asked the same question in my google interview!! The best solution for this is to use the TRIE data structure!! Google TRIE data structure for more details. It also gives an optimized search complexity. On Nov 8, 2007 11:40 AM, Rajat Gogri [EMAIL PROTECTED] wrote: If you have to implement a phone book of 10 millin people in NYC, what data structure would you use and why ? Show the implementation if HashTable or Binary Trees? Thanks, Raj -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Finding the n integers given the set of sums.
check out : http://groups.google.co.in/group/programming-challenges/browse_thread/thread/f9e5436fbc6dbc56?hl=en # On 11/7/07, anvera [EMAIL PROTECTED] wrote: I have not developed entirely the idea, but I am sure it works. Just write the corresponding linear system. You will have n unknowns and n(n-1)/2 equations. Provided that the system is consistent you can find a solution by Gaussian elimination. For the complexity, you can do it in less than n^3/3 +O(n^2) operations, because it is simpler than just inverting a nxn matrix. Inverting the matrix can let you solve the problem for many instances. It would be interesting to exploit the special structure of this matrix in order to speed up the computation. Please post if you find such an improvement. Best Regards, Antonio On Nov 7, 5:16 pm, Andrey [EMAIL PROTECTED] wrote: Any set of n integers form n(n - 1)/2 sums by adding every possible pair. The task is to find the n integers given the set of sums. Any ideas? I've found out the solution but I doubt it the best one... -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Finding the n integers given the set of sums.
On 11/7/07, anvera [EMAIL PROTECTED] wrote: Why not? Does order really matters here? Look at the symmetry of the problem. Put 3,4,5,5 and then 4,5,6,7 at the right side. Look at the solutions. How they differ? Is this natural? Though the order is not imp you cant tell which 2 variables for a particular equation. On Nov 7, 6:55 pm, Andrey [EMAIL PROTECTED] wrote: Won't work. You just can't build such a system, because you don't know in which order values should appear in right part of system. Say, we have the follwing input of 6 numbers: 3, 4, 5, 5, 6, 7 and we are supposed to find 4 values (4 * (4 - 1) / 2 = 6) x1, x2, x3, x4 What the system will look like? x1 + x2 = ? x1 + x3 = ? x1 + x4 = ? x2 + x3 = ? x2 + x4 = ? x3 + x4 = ? On 7 нояб, 20:16, anvera [EMAIL PROTECTED] wrote: I have not developed entirely the idea, but I am sure it works. Just write the corresponding linear system. You will have n unknowns and n(n-1)/2 equations. Provided that the system is consistent you can find a solution by Gaussian elimination. For the complexity, you can do it in less than n^3/3 +O(n^2) operations, because it is simpler than just inverting a nxn matrix. Inverting the matrix can let you solve the problem for many instances. It would be interesting to exploit the special structure of this matrix in order to speed up the computation. Please post if you find such an improvement. Best Regards, Antonio On Nov 7, 5:16 pm, Andrey [EMAIL PROTECTED] wrote: Any set of n integers form n(n - 1)/2 sums by adding every possible pair. The task is to find the n integers given the set of sums. Any ideas? I've found out the solution but I doubt it the best one... -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Summation formules
On 10/22/07, Allysson Costa [EMAIL PROTECTED] wrote: I have some doubts about summation notation 1) Is there a formule like: SUM (LOG i) i=1 to i=n is equivalent to LOG (N)! This formule is true? Yes it is true . = 2) What is relationship betweenLOG(N)! and NLOGN? nlog n = log(n^n) = log( n x n x n x .n times) log(n!) = log( n x n-1 x n-2 x ...x 2 x 1) I dont think there is any relation between the 2. Atleast i am not aware of any till now. = Thanks Allysson -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Spiral number
Check out these 2 links which discuss the same problem. Some codes are also posted. http://groups.google.com/group/programming-challenges/browse_thread/thread/88bcbea02029c2bf http://groups.google.com/group/programming-challenges/browse_thread/thread/9acf71cb87e9ffd3 This is a good group discussing some of the ACM problems too. On 10/21/07, Dhyanesh (ધયાનેશ) [EMAIL PROTECTED] wrote: Use the property that one of the diagonals has squares of odd numbers. So given a co-ordinate in that diagonal you know the number at that position. For positions not on that diagonal you can add/subtract appropriately and obtain the number you need. -Dhyanesh On 10/18/07, mukesh tiwari [EMAIL PROTECTED] wrote: Hello everybody , i am trying to solve this(http://online- judge.uva.es/ p/v9/903.html) problem and input constrants are such that it is not possible to store the the numbers in the array and print those numbers. So i use the algorithm 1)get the number and return its coordinate 2) take the input all adjacent coordiantes and return the number belonging to that coordinate . i am facing the problem in second part that is if i have given coordiante how to get the number belonging to that coordinate, lets consider the spiral 21 22 23 24 25 26 20 7 8 9 10 19 6 1 2 11 18 5 4 3 12 17 16 15 14 13 let the coordinate of 1 is (0,0) ie origin then coordinate of 11 will be (2,0) and so on . now my problem is if i give coordiante (2,-1) then my program should return 12 . thnkx in advance -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Doubt with summation
let n - 2i = 2mie 2i = n-2m
hence
SUM { lg (n-2i) } = SUM { lg (2m) }
no the limits
upper limit = i = n/2-1 ie 2i = n-2 ie n-2m = n-2 ie m=1
lower limit = i = 0ie 2i = 0 ie n-2m = 0ie m=n/2
therefore the summation is
SUM { lg((2m) } where m = 1 to n/2
now the variable is not important in the summation hence substituting i for
m we get :
SUM { lg(2i) } where i = 1 to n/2 which is your
expression on the left side.
what say ?
On 10/19/07, Allysson Costa [EMAIL PROTECTED] wrote:
Anyone can give a explanation how I get the equation below true?
Why lg(n-2i) became lg(2i)?
Thanks in advance.
Allysson
--
Ciao,
Ajinkya
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
image/jpeg
[algogeeks] Re: Doubt with summation
substitute n-2i = 2m in firsst equationyou will get the left one on reducing the terms in terms of m. On 10/19/07, Allysson Costa [EMAIL PROTECTED] wrote: Anyone can give a explanation how I get the equation below true? Why lg(n-2i) became lg(2i)? Thanks in advance. Allysson -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~--- image/jpeg
[algogeeks] Re: Programing problem
On 10/7/07, macharla pradeep [EMAIL PROTECTED] wrote: Hi, if ( commnad sequence is bad ) whether to include it area calculation or not?? It is mentioned that command sequence is never bad. On 10/5/07, piruk [EMAIL PROTECTED] wrote: Hi. How to solve this task? Areameter is a turtle-like self-propelled vehicle controlled by sequences of commands transmitted over a radio channel. Initially the vehicle is oriented in some fixed direction, let's say to the North. Commands instruct Areameter how far to move in the current direction and where to turn after the move. Allowed turns are +90 or -90 degrees relative to the current direction. By positive turn we mean turning to the right (clockwise). A command sequence is good if it brings the vehicle to the starting point and starting orientation after tracing a closed non self- intersecting path. On coming back to the starting point Areameter should emits the area (number of square units) of the territory walked around. Write a program to perform Areameter's task of calculating the area from the sequence of received commands. Input The standard input stream contains a sequence of test cases specified as follows: The first line contains a positive integer n, number of test cases. A test case is simply one good command sequence spread over one or more lines. Each command sequence consists of alternating move and turn commands. Move command is represented by a positive integer; turn command is represented by single character '+' or '-'. End of command sequence is coded by giving 0 for move command. Commands are separated by at least one white-space character. You can assume the input is well-formed and contains only good command sequences. There are no a priori constraints on the sequence length. The values of moves and the resulting area are all within integer representation. Output For each test case the program should output one text line containing a number: the area in square units. Example Input 3 3 + 3 + 3 + 3 + 0 2 + 2 + 3 - 3 - 1 + 2 + 3 + 3 + 1 - 3 + 2 - 1 + 0 2 + 2 - 1 - 1 + 1 + 3 + 3 + 2 - 2 - 4 - 4 + 2 + 2 + 1 - 1 - 2 + 1 + 1 - 1 + 7 + 2 - 1 + 0 Output 9 16 27 -- PRADEEP MACHARLA Ph:08040141194 -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
