[algogeeks] JAVA/J2EE TUTIONS With PROJECTS for MCA, BCA, B.E at RAJAJINAGAR.
Professionals with extensive knowledge and experience, both in training and development are a part of our team of trainers. Single minded dedication, effective work culture and dynamic decision making under impossible situations are our strengths. Quality without compromise is our motto. SL.NOCOURSESFEE STRUCTURE 1 JAVA,J2EE,ORACLE,HTML,JAVASCRIPT5000 2 STRUTS 2000 3 EJB 2000 4 HIBERNATE 1500 5 DIPLOMA IN HR MANAGEMENT6000 6 C,C++,VC++,MFC 7000 6 SOFT SKILLS PERSONALITY DEVELOPMENT 1500 7 PROJECTS RATE DEPEND ON PROJECT -- 8 XML 2000 9 JAVA/J2EE, STRUTS, EJB, XML, HIBERNATE, ORACLE, ANT, LOG4J, JAVASCRIPT, HTML,WEBLOGIC. 1 10 JBOSS/TOMCAT/WEBLOGIC 2000 11 STADPRO(CIVIL,MECH) 8000 12 SAP SD MODULE 12000 13 HTML,JAVASCRIPT 1000 CONTACT PERSONS :- 9986978008 9845543101 --~--~-~--~~~---~--~~ 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] are you ready earn dollar indaily $100 inhome
are you ready earn dollar indaily $100 inhome logon to http://www.kazariangpt.com/index.php?ref=sivakumar http://www.kazariangpt.com/index.php?ref=sivakumar http://www.kazariangpt.com/index.php?ref=sivakumar * --~--~-~--~~~---~--~~ 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] are you ready to earn dollar inhome witout risk invesment
are you ready to earn dollar inhome witout risk invesment log on to http://www.AWSurveys.com/HomeMain.cfm?RefID=allgunkumar http://www.AWSurveys.com/HomeMain.cfm?RefID=allgunkumar http://www.AWSurveys.com/HomeMain.cfm?RefID=allgunkumar --~--~-~--~~~---~--~~ 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] GLOBTECH SOLUTIONS PROVIDES TRAINING, PROJECTS, SOFT SKILLS PLACEMENT ASSISTANCE REGULAR WEEKEND.
Professionals with extensive knowledge and experience, both in training and development are a part of our team of trainers. Single minded dedication, effective work culture and dynamic decision making under impossible situations are our strengths. Quality without compromise is our motto. SL.NOCOURSESFEE STRUCTURE 1 JAVA,J2EE,ORACLE,HTML,JAVASCRIPT5000 2 STRUTS 2000 3 EJB 2000 4 HIBERNATE 1500 5 C,C++ 2500 6 MFC,VC++3000 7 SOFT SKILLS PERSONALITY DEVELOPMENT 1500 8 PROJECTS RATE DEPEND ON PROJECT NGO 9 XML 2000 10 JAVA/J2EE, STRUTS, EJB, XML, HIBERNATE, ORACLE, ANT, LOG4J, JAVASCRIPT, HTML,WEBLOGIC. 12000 11 JBOSS/TOMCAT/WEBLOGIC 2000 12 STADPRO(CIVIL,MECH) 8000 13 SAP SD MODULE 12000 14 HTML,JAVASCRIPT 1000 Training and placement highlights: » 100% Placement assistance and on the job support during projects. » Excellent placement track record. » Training by highly qualified, industry-experienced certified consultants. » Assistance from our training experts in selecting the right course certification. » Very convenient weekend as well as week day classes. » Limited seats only, to provide individual attention to each candidate. » Resume preparation, brainstorm sessions and mock-interviews with senior consultants. » Continuous support and guidance until placed on projects. CONTACT PERSONS :- 9986978008 9845543101 E-Mail : [EMAIL PROTECTED] [EMAIL PROTECTED] --~--~-~--~~~---~--~~ 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] GLOBTECH SOLUTIONS PROVIDES TRAINING, PROJECTS, SOFT SKILLS PLACEMENT ASSISTANCE REGULAR WEEKEND.
Professionals with extensive knowledge and experience, both in training and development are a part of our team of trainers. Single minded dedication, effective work culture and dynamic decision making under impossible situations are our strengths. Quality without compromise is our motto. SL.NOCOURSESFEE STRUCTURE 1 JAVA,J2EE,ORACLE,HTML,JAVASCRIPT5000 2 STRUTS 2000 3 EJB 2000 4 HIBERNATE 1500 5 C,C++ 2500 6 MFC,VC++3000 7 SOFT SKILLS PERSONALITY DEVELOPMENT 1500 8 PROJECTS RATE DEPEND ON PROJECT NGO 9 XML 2000 10 JAVA/J2EE, STRUTS, EJB, XML, HIBERNATE, ORACLE, ANT, LOG4J, JAVASCRIPT, HTML,WEBLOGIC. 12000 11 JBOSS/TOMCAT/WEBLOGIC 2000 12 STADPRO(CIVIL,MECH) 8000 13 SAP SD MODULE 12000 14 HTML,JAVASCRIPT 1000 Training and placement highlights: » 100% Placement assistance and on the job support during projects. » Excellent placement track record. » Training by highly qualified, industry-experienced certified consultants. » Assistance from our training experts in selecting the right course certification. » Very convenient weekend as well as week day classes. » Limited seats only, to provide individual attention to each candidate. » Resume preparation, brainstorm sessions and mock-interviews with senior consultants. » Continuous support and guidance until placed on projects. CONTACT PERSONS :- 9986978008 9845543101 E-Mail : [EMAIL PROTECTED] [EMAIL PROTECTED] --~--~-~--~~~---~--~~ 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: combinations problem
isn't it an application of association rule mining. http://en.wikipedia.org/wiki/Association_rule just that ARM will mostly result multiple solution depending on your data. Its up to you to decide a strategy for breaking ties. On Aug 15, 1:19 am, Geoffrey Summerhayes [EMAIL PROTECTED] wrote: On Aug 14, 4:25 am, sfl [EMAIL PROTECTED] wrote: Hi, Let's suppose we search into a table for N parameters, starting from a maximized key. If we do not find anything we start to generalize the key by take off one parameter. We do this until we find something. Stop. This is a poor specification, give this to 5 different programmers and expect 5 programs that give different results. Let's try with an example, 3 parameters: Database table MyTable code | state | color | size rule1 california blue large rule2 california yellow medium rule3 california yellow - rule4 california - small rule5 - - small rule6 - yellow medium Now suppose our key K is composed from K(california, red, small) We have to find the rule by search into MyTable. step1: search MyTable for (california,red,small) we do not find anything step2: search MyTable for K(california,red, null) ( we have reduced the key). Why? If you get an answer set that matches [california,red] you end up ignoring the answers to [california,small] and [small,red] both of which match using the same number of criteria but return a different set of rules. What makes the [california,red] answer set deserve special treatment? we do not find anything step3: use the K(null,red,small), we do not find anything again, step over step4: use the K(california, null, small) we finally find rule4, stop! We got to the end, but let's now suppose this row in our table: rule7 - red small step3 would find the rule7 and step4 would find rule4, which is right? If parameters has no weight, the algorithm returns 2 solution. So, suppose I give a grid of combination, ordered. ord state color size 1 x x x 2 x x - 3 x - x 4 - x x 5 - x - 6 x - - 7 - - x 8 - - - I search for K(x,x,x), then K(x,x,null) etc until I find a rule. Complexity is O(2^n) where n= number of parameters #(state,color,size)=3 If it was O(2^n) then adding 500 rules to that database wouldn't change anything, right? So, to keep it short, how would you solve this problem? Probably by going through the rules in one pass, keeping the best matching set. Which is the class of this problem? n,p,np,np-c,etc... If n is the total number of elements considered, that is the number of rules multiplied by the number of parameters, it's linear. --~--~-~--~~~---~--~~ 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] PLZ ANS....
The simplest way of computing the time complexity --~--~-~--~~~---~--~~ 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] you need money without invesment earn weekly$5000to$10000
you need money without invesment earn weekly$5000to$1 otherinformations logonto * http://www.AWSurveys.com/HomeMain.cfm?RefID=sureshrania http://www.AWSurveys.com/HomeMain.cfm?RefID=sureshrania http://www.AWSurveys.com/HomeMain.cfm?RefID=sureshrania *** --~--~-~--~~~---~--~~ 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: Judging whether a URL exists among millions, insert if not
I think you better set unique constraint on URL column and generate a index with URL. All the methods above has to search the table at least once anyway and if so adds constraint and let DB handle it is most efficient. --~--~-~--~~~---~--~~ 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: programming problem
Regular expressions ? --~--~-~--~~~---~--~~ 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: Is it base 2 or base 10
It doesn't matter ... On May 15, 4:19 pm, Vinodh [EMAIL PROTECTED] wrote: On any algorithm book they often specify the speed of the algorithm. I often see many algorithms having speed factor O(nlogn). **Is it log base 2 n ? Or Is it log base 10 n?** Thanks, Vinodh --~--~-~--~~~---~--~~ 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: Algorithm Question Help Please!!!
Any chance I could get a copy of that as well? :)
On Mar 21, 3:49 am, Ashesh [EMAIL PROTECTED] wrote:
Done.
On Mar 20, 4:45 pm, VRC [EMAIL PROTECTED] wrote:
I am also interested to know about the solution? Would you please
email me? Thanks.
On 3月16日, 下午8時56分, Ashesh [EMAIL PROTECTED] wrote:
I have emailed you the solution. Please check our email and ensure
that it has not been marked as spam (gmail's spam filters are
effective but hyperactive).
Ashesh.
On Mar 16, 4:21 am, BillyBob123 [EMAIL PROTECTED] wrote:
Hi,
I'm new here and have an algorithm question that I need to solve. If
you are not able to solve, please point me in the right direction so I
can get started. Thank you.
Suppose it's nearing the end of the semester and you're takingn
courses, each with a final project that still has to be done. Each
project will be graded on the following scale: It will be assigned an
integer number on a scale of 1 to g 1, higher numbers being better
grades. Your goal, of course, is to maximize your average grade on
thenprojects. You have a total of H nhours in which to work on
thenprojectscumulatively, and you want to decide how to divide up
this time. For simplicity, assume H is a positive integer, and you'll
spend an integer number of hours on each project. To figure out how
best to divide up your time, you've come up with a set of functions
{fi : i = 1, 2, ...n} (rough estimates of course) for each of yourn
courses; if you spend h = H hours on the project for course i, you'll
get a grade of fi(h). You may assume that the functions fi are
nondecreasing: i.e., if h h`, then fi(h) = fi(h`). So the problem
is: Given these functions fi, decide how many hours to spend on each
project (in integer values only) so that your average grade, as
computed according to the fi, is as large as possible. In order to be
efficient, the running time of your algorithm should be polynomial in
n, g, and H; none of these quantities should appear as the exponent in
your running time.
Thank you very much for all your help.- 隱藏被引用文字 -
- 顯示被引用文字 -
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: finding kth smallest node in binary search tree
If the tree is balanced, and if you store the number of nodes in the subtree rooted at each node in the tree, it can be achieved in O(log n). It is tree to verify that this extra information can be maintained with all insert, del operations at no extra cost. On Feb 28, 11:36 am, Lego Haryanto [EMAIL PROTECTED] wrote: If the BST is balance, you could do it better in O(lg n). I believe some setup should be involved, such as storing how many nodes in a subtree. Best, -Lego On 2/28/08, Dave [EMAIL PROTECTED] wrote: Do an inordertraversal. Stop when you get to the kth node. O(k). Dave On Feb 28, 12:30 am, yash [EMAIL PROTECTED] wrote: Binary search Tree was given. Find kth smallest element. and also find complexity. -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~-~--~~~---~--~~ 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: factorial
thanks for ur reply's..i understood them.. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] permuttaion
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.. --~--~-~--~~~---~--~~ 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: without modifying the tree in any manner and using no more than a constant space outside the tree?
Please ignore this message. This is supposed to be e reply of some other message. On Feb 11, 10:47 am, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: 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. --~--~-~--~~~---~--~~ 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] without modifying the tree in any manner and using no more than a constant space outside the tree?
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. --~--~-~--~~~---~--~~ 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] 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. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Help
GOOD ONE- Data Structures , Algorithms and Applications in C++ by Sartaj Sahani On Feb 7, 1:58 pm, Atul Aggarwal [EMAIL PROTECTED] wrote: Hello Everybody, I am beginner in Algorithms. Which book I should prefer for understanding basic algos? Also tell me some good book for graph Theory and its basic algos. Thanx in advance. Atul Aggarwal --~--~-~--~~~---~--~~ 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] Need Help - Constrained linear least square optimization C code
Hi I need to find x that will minimize Ax-b=0, under the inequality constraints Cxd. Actually the constraints in my problem are only upper and lower bounds to x values. x is 4x1 vector, A is about 100x4 (and b is of course 100x1(. What is the appropriate algorithm? Is there any C / C++ code available? I succeeded solving the non-constrained problem with SVD, but some times it give non-legal solution. Thanks a lot in advance Ariel --~--~-~--~~~---~--~~ 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] LIVE PROJECTS FOR FINAL YEAR STUDENTS FOR B.E(CSE/ISE/ECE)/M.Tech/BCA/MCA/M.SC/B.SC
RAYLOGIX TECHNOLOGIES is now providing LIVE PROJECTS for M.TECH/MCA/ BCA/B.Sc/M.Sc/B.E (CSE/ISE/ECE)final year candidates.Interested candidates can directly come to the company. WE GOT LIVE�� PROJECTS ON JAVA/J2EE/STRUTS/EJB. WE GOT LIVE�� PROJECTS ON EMBEDED FOR ECE CANDIDATES. WE GOT LIVE�� PROJECTS ON ASP.NET �� ALONG WITH PLACEMENT GUIDANCE FOR FINAL YEAR CANDIDATES. CONTACT: RAYLOGIX TECHNOLOGIES #737,2nd FLOOR DR. RAJ ROAD RAJAJINAGAR 6TH BLOCK BANGALORE-560010 Ravi.S.M: 9845311916 E-mail :- [EMAIL PROTECTED] OFFICE: (080)-41731643/44 WEBSITE: www.raylogix.com --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] I challenge you to cheat in the Numbrosia Puzzle by computer
Hi, Can you come up with an effective heuristic search that often beats the median number of moves in the Numbrosia Puzzle? http://numbrosia.com Amir --~--~-~--~~~---~--~~ 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] LIVE PROJECT FOR FINAL YEAR STUDENTS WITH REAL TIME EXPERIENCE
RAYLOGIX TECHNOLOGIES is now providing LIVE PROJECTS for M.TECH/MCA/ BCA/B.Sc/M.Sc/B.E (CSE/ISE/ECE)final year candidates.Interested candidates can directly come to the company. WE GOT MORE THEN 30�� LIVE PROJECTS ON JAVA/J2EE/STRUTS/EJB. WE GOT MORE THEN 30 LIVE�� PROJECTS ON EMBEDED FOR ECE CANDIDATES. WE GOT MORE THEN 20 LIVE�� PROJECTS ON ASP.NET �� ALONG WITH PLACEMENT GUIDANCE FOR FINAL YEAR CANDIDATES. CONTACT: RAYLOGIX TECHNOLOGIES #737,2nd FLOOR DR. RAJ ROAD RAJAJINAGAR 6TH BLOCK BANGALORE-560010 Ravi.S.M: 9845311916 E-mail :- [EMAIL PROTECTED] OFFICE: (080)-41731643/44 WEBSITE: www.raylogix.com --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Friendly Graphs
Consider the following scenario. Let A be the vertex moved from Set 1 to Set 2. Which means that A had more edges within Set1 compared to those in Set 2. Now it is quite possible that there might be an edge B in Set 2 which now has more edges in Set2 than it had in Set 1. The increase for B might be more than increase in A. This means that |E| bound on the number of iterations is not accurate. if so, what is the criteria for exiting this algorithm. Thanks, Naveen On Oct 28, 9:46 pm, Gene [EMAIL PROTECTED] wrote: On Oct 28, 2:02 pm, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: I am trying to find the proof for the following problem from CLR. Prove that a undirected graph with no self edges can be divided into two groups such that for every node,atleast half of the nodes it is adjacent to, are in a different group than the node itself. Solutions/hints will be appreciated. One proof is to show the following algorithm must work: Put the vertices arbitrarily into two sets. As long as you can move a vertex from one set to the other and increase the number of edges between the two sets, do that. This criterion for moving a vertex is equivalent to saying that the vertex thas more neighbors in its own set than in the other. After moving, the situation is reversed: more neighbors are in the opposite set. Now the algorithm must terminate after moving vertices at most |E| times. This is because you are increasing the number of edges between sets by one with each move, and you can't do better than getting all the edges! --~--~-~--~~~---~--~~ 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] RAYLOGIX TECHNOLOGIES PROVIDES LIVE PROJECTS FOR THE FINAL YEAR STUDENTS(CSE ISE)
RAYLOGIX TECHNOLOGIES Software Development centre Offers through their Group of companies Live Projects for B.E,MCA, BCA,MSc,M.TECH (CS IT) Students Benefits to the students: - Excellent training from Industry Experienced Experts - Employable Soft-skills - Guaranteed Placement Support Contact us: Raylogix Technologies, No. 737, Dr Raj Road, Rajajinagar 6th Block, Bangalore - 560 010 Phone: 080-41731641/42 09845311916 (Service 24/7) [EMAIL PROTECTED] www.raylogix.com --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: coloring a graph of O(|V|) edges
In fact, we could use only 3 colors to do this, if this graph is connected. At first, I guess you know the famous 4-color theorem, so 4 colors is enough. In fact, if this graph can be disconnected, then we have to use 4 colors. But if it is connected, then it is a tree plus one extra edge, which makes it an almost tree, except for one cycle. If a connected graph has O(|V|-1) edges, then it is a tree. A tree could be colored in 2 colors: Suppose the root use color red, then the next level would use green, and the next next level would use red .. Two colors is OK. Then we add one edge into this tree, this would possiblly cause the two endpoints violate the coloring. So we could just add one color, then it is OK. So, 3 color is good. On Oct 21, 9:29 pm, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: Hi, Can some provide me hint or solution to the following problem. If a graph has O(|V|) edges , then show that it can be colored with (O|V| ^ 1/2) colors. Thanks --~--~-~--~~~---~--~~ 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] sort 2 d array
give algorithm for the following -: 1. sort a 2-d array 2. sort a 2-d array in snake order --~--~-~--~~~---~--~~ 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] combinations in lexographic order
Q) You are given a string in which the characters are sorted. Write a program to generate all the combinations of characters such that only the lexicographically lowest permutation of every combination is printed. (ie. If the string is abcd then ab is a valid combination, but ba is not). Further, the combinations generated must themselves be in dictionary order. Example: For the string ABC, the combinations are: A AB ABC AC B BC C You may write the output to standard output. --~--~-~--~~~---~--~~ 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] cups and saucers
Q) The array T represents the diameters of various teacups, and the
array S, the diameters of saucers, both the arrays sorted in non-
decreasing order. The 'i'th cup (whose diameter is T[i]) can be
paired with the 'j'th saucer (whose diameter is S[j]) if and only if
S[j] = T[i].
Given the sorted arrays 'S' and 'T', implement the 'C' function:
int getMaxNumberOfPairs(int* T, int* S, int no_cups, int no_saucers);
which would return the maximum number of cup and saucer pairings
possible for given arrays 'S' and 'T'.
For instance, given T = {15, 20, 20, 22, 30} and S = {10, 19, 26, 30},
the function should return '3' corresponding to any of the possible
maximal cup-saucer pairings, say, {[15,19], [20,26], [30,30]}, for
instance.
--~--~-~--~~~---~--~~
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] min height rootless tree
Q) You are given a root-less tree (which can also be thought of as an undirected acyclic connected graph). The problem is to choose one of the nodes from the tree as root such that the height of the resultant tree is minimum. Device an appropriate data-structure and write a program for the same. mum height possible is 2. So for this example the code should return the node '3'. Note: All nodes are numbered from 1 to n, where 'n' is the number of nodes. Incase there are more than one roots possible, then your program can return any one of them. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] count policemen
Q) A city has a number of roads that meet at various junctions (A junction is a point where two or more roads meet). The traffic police department is severely short of policemen and therefore wants to know the minimum number of policemen required to be placed at junctions so as to cover all the roads in the city. Assume that there isn't more than one path between any two junctions in the city. (A policeman can patrol all the roads connected to the junction where he is placed). Write a code in to return the minimum number of policemen required. It is not necessary to print the various combinations of the junctions at which each of the policemen would be placed. Input: adjacency matrix where if a[i][j] = 1, a road exists between i and j. Your prototype should be : int find_min_policemen_count(struct node* root); --~--~-~--~~~---~--~~ 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] coloring a graph of O(|V|) edges
Hi, Can some provide me hint or solution to the following problem. If a graph has O(|V|) edges , then show that it can be colored with (O|V| ^ 1/2) colors. Thanks --~--~-~--~~~---~--~~ 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] total number of one bits
Hi all: I met a problem in the programming pearls as follow: Q: Given a very long sequence(say, billions or trillions) of bytes, how would you efficiently count the total number of one bits? A: The first approach is to count the number of one bits in each input unit(perhaps an 8-bit character or perhaps a 32-bit integer), and sum them. To find the number of one bits in a 16-bit integer, one could look at each bit in order, or iterate through the bits that are on, or perform a lookup in a table of. What effect will the cache size have on your choice of unit? The second approach is to count the number of each input unit in th input, and then at the end take the sum of that number multiplied by the number of one bits in that unit. My question is, I am puzzled about the solution. What's the difference of the two approaches? In the second approach, what are multiplied? Thanks! --~--~-~--~~~---~--~~ 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 to optimize packing a box with different shaped profiles
dear adak gene, thanks for the interesting thoughts you provided. obviously i'm not an algorithm expert but i'm a very experienced C# developer. so i need this thing explained with simple terms. to further define near by, profiles of the same shape have to be either packed next or on top of each other. to try each possible layout and pick the one with the least amount of wasted space seems to be pretty straight forward. this works fine if we only pack 1 box, but what if we have to pack let's say 5 boxes of different profiles? then the layout combinations spread across all the boxes. reto On Oct 16, 7:34 am, adak [EMAIL PROTECTED] wrote: Obviously there is no need for the one line of code that deals with minimizing /maximizing player's moves, in this case. A/B would still prune, but it would only prune out the piece arrangements that left sub optimal piece arrangements, with more wasted space. You're right, Gene, this is indeed an interesting problem. Wish I had more time to study it. --~--~-~--~~~---~--~~ 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] How to optimize packing a box with different shaped profiles
Hi, I have a different number of different shaped profile bars which I need to fit into as few boxes as possible. The box has a fixed size. The profiles are always the same length, which means the problem only needs to be solved on 2 dimensions. The shape of the profiles are either rectangular or have an L-shape. During packing, the same type of profiles shall be packed together or near by. Here see a picture of an example: http://picasaweb.google.com/rlaemmler/ProfileBox/photo#5121155886125484770 I found a tool called Real Cut 2D which solves a similar problem but unfortunately only covers rectangular shaped figures. http://www.optimalprograms.com/RealCut2d.htm Has anybody a good algorithm or idea on how to solve this optimization problem? Thanks, Reto --~--~-~--~~~---~--~~ 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 numerical sequence problem
whoops, misunderstood the problem - I thought you meant the sum to the
end of the sequence minus the sum to the end. My bad. Please ignore
what I wrote above!
On 6 Sep, 01:21, [EMAIL PROTECTED] [EMAIL PROTECTED]
wrote:
I know you've solved the problem, but I'm bored. Would this work? I
was never good at analysing time constraints
Given an array
n_1
n_2
...
n_k
create another array called sums:
n_1
n_1 + n_2
n_1 + n_2 + n_3
n_1 + n_2 + n_3 + ... n_k
Take two indices min and max
min = 0 max = f;
while max L {
increment max until sums[max] - sums[min] = d
if (sums[max - 1] - sums[min]) f record max and min
increment min
}
This will give you longest possible sequences that match the
criteria. Since every subsequence would have match the d criterion,
you just need to list every subsequence where jf.
How does this look? Kinda new at this, so feedback is appreciated.
On 4 Sep, 03:33, Sticker [EMAIL PROTECTED] wrote:
I have a problem on sequences of numbers:
Given a sequence of integer numbers (could be quite long, let say, 10s
of thousands of numbers). Let us denote it as
{n_1,n_2,n_3,n_4,...,n_L}. The length of the sequence is L (meaning
that it contains L numbers)
From this sequence I want to find a segment of j consecutive numbers
S={n_i,n_(i+1),n_(i+2),...,n_(i+j)} such that the result of maximum
number of S minus the minimum number of S is smaller than user defined
d. The length of the segment j has to be larger than another user
defined f.
If there are more than one such segment, find them all.
I wonder whether there exists some linear algorithms to handle this
problem. The solution is better to be quick because it is only a
subproblem of the complete one and this operation is repeated several
times.
--~--~-~--~~~---~--~~
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] A dynamic problem
we define a multiplication on alpha table S={a,b,c} as follows:
| a b c
-
a | b b a
b | c b a
c | a c c
-
For any string S, we can add some parentheses into it.For example,
for
x=a, we add parentheses like this (b(bb))(ba), according to the
table, the result is a.Now, for any string S=x1x2x3x4...xn，calcuate
how many ways we can add parentheses into it, and the result is a
It is a question after dyanmic programming chapter in my algorithm
book, but I really don't know how to
solve it.I think first define a matrix M,so M[i][j] is the result for
how many ways to add parentheses to produce any character, fianlly
the M[1][n] is the result for the problem above,but it will be very
meomry cosumption, because M[i][j] has to record many kinds of
situation,
So are there other ways to solve 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 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 a single repeated element in an array
In your example, I noticed that all values are positive number and none of them are not out of array bounds. Which means that was really special case, not applicable for general cases. Pos Val 1 4 2 1 3 1 4 2 5 9 6 8 7 5 8 7 9 6 10 3 - 1 - 4 - 2 - 1 2 - 1 - 4 - 2 3 - 1 - 4 - 2 - 1 4 - 2 - 1 - 4 5 - 9 - 6 - 8 - 7 - 5 6 - 8 - 7 - 5 - 9 - 6 7 - 5 - 9 - 6 - 8 - 7 8 - 7 - 5 - 9 - 6 - 8 9 - 6 - 8 - 7 - 5 - 9 10 - 3 - 1 - 4 - 2 - 1 On Aug 16, 1:41 pm, dsha [EMAIL PROTECTED] wrote: Hi there, I'm interested in the following problem: there is an array of integers that contains each element only once except for one element that occurs exactly twice. Is there a way to find this element faster than O(n*log n) and with constant extra memory? If no, how can I prove it? Thanks in advance for ideas.- 따온 텍스트 숨기기 - - 따온 텍스트 보기 - --~--~-~--~~~---~--~~ 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: Longest Common Sequence
I am sorry I was not clear. My regexp is currently like: ^94530|93540|..list of zip codes that is 400 - 500 in size that ends like this..30329$ How do I go about making this concise.? Thank you. On Jul 31, 5:58 pm, dor [EMAIL PROTECTED] wrote: On Jul 23, 10:29 am, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: I have a list of zip codes (300) and I want to compress it so that my regexp is concise. Can someone give me some pointers please? TIA. What regular expression might that be? What's the connection between the title of your post and the problem you are trying to solve? Can you be a little more precise? --~--~-~--~~~---~--~~ 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: Longest Common Sequence
I basically want to find out the longest common sequence for a list of zip codes. My assumption is that I can use this in the regular expression to make my current regexp shorter. It is right now too long: ^94540|94530| .a huge list of zip codes ending in$ Thanks. On Jul 31, 5:58 pm, dor [EMAIL PROTECTED] wrote: On Jul 23, 10:29 am, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: I have a list of zip codes (300) and I want to compress it so that my regexp is concise. Can someone give me some pointers please? TIA. What regular expression might that be? What's the connection between the title of your post and the problem you are trying to solve? Can you be a little more precise? --~--~-~--~~~---~--~~ 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: Longest Common Sequence
I have a regexp which looks like: ^94530|94540|a very long list of zip codes separated by || 94397$ I want to reduce the regexp length. How can I do that? TIA. On Jul 31, 5:58 pm, dor [EMAIL PROTECTED] wrote: On Jul 23, 10:29 am, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: I have a list of zip codes (300) and I want to compress it so that my regexp is concise. Can someone give me some pointers please? TIA. What regular expression might that be? What's the connection between the title of your post and the problem you are trying to solve? Can you be a little more precise? --~--~-~--~~~---~--~~ 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] bmp图像数据处理算法
一个文件以16进制读取，统计其中每个word的个数。 如56 78 56 e6 78 56 其中56 78 1个 56 e6 1个 78 56 1个 其中78 56就不要算成2个. 我做这个程序的目的是： 有一个res文件里存储了许多bmp文件的位图数据，当然，按顺序储存。 我就是要利用图片像素与周围像素的过渡性，指出res文件里各个bmp文件的分割点，还有各个bmp文件的高和宽。 参考http://www.newsmth.net/bbstcon.php?board=Graphicsgid=47754 --~--~-~--~~~---~--~~ 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] Regexp question
I have a long regexp: ^94530|94540|..300 zip codes.|95030$ My question is how do I compress this sequence? TIA. P.S: I am starting this thread since I am not able to reply to my earlier thread. Sorry. --~--~-~--~~~---~--~~ 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] Longest Common Sequence
I have a list of zip codes (300) and I want to compress it so that my regexp is concise. Can someone give me some pointers please? TIA. --~--~-~--~~~---~--~~ 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: reversing strings using array
the reverse of hello world is dlrow olleh and not world hello Reversing chars is different from reversing words. In any case nobody is going to help you with your homework. So before asking for any concrete help post your trials... On Jun 16, 10:13 am, Misty [EMAIL PROTECTED] wrote: Hello friends, i want 2 know how to write a program to reverse strings for instance a string is hello world, i need to print it as world hello. please post your answers as soon as possible. --~--~-~--~~~---~--~~ 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: same perimeter triangles
the distance ap, bp and cp are the unknowns. we can get 3 simultaneous equations based on the condition that the permeters are same. ie, ab+ap= bc+pc ... and so on . 3 unknows and 3 equations = we can find the unknowns. once we find the distance ap and bp, finding the point 'p' is again solved by two simultaneous equations On Jun 1, 6:01 pm, Terry [EMAIL PROTECTED] wrote: Hi, This one's puzzling me since a while. Any thoughts In a triangle ABC, find a point P such that perimeter of the triangles formed by (A,B,P), (B,C,P) and (A,C,P) are same. how do we determine P and what is it called --~--~-~--~~~---~--~~ 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: Testing if 3 points form a triangle
In 3D, we can test |(p2-p1)*(p3-p1)|==0, where p1,p2 and p3 are vectors. On 5月27日, 上午7时22分, Feng [EMAIL PROTECTED] wrote: Hi all! Given 3 points in 3D, what is the fast and numerically stable way to test if they form a triangle? I am thinking computing the determinant of the square matrix formed by the 3 points and testing if the determinant is nonzero. But I am not sure. What about the case for high dimensions, i.e. 4D, 5D ... Thanks! --~--~-~--~~~---~--~~ 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: Testing if 3 points form a triangle
in 3D,we can test |(p2-p1)*(p3-p1)|==0,where p1,p2,p3 are 3D-vectors that represent the three points. in n-dimension,i think we can let A=(a1,a2,...,an)=p2-p1, and B=(b1,b2,...,bn)=p3-p1, and test every elements of the matrix (ATB- BTA). That is ai*bj-aj*bi. On 5月27日, 上午7时22分, Feng [EMAIL PROTECTED] wrote: Hi all! Given 3 points in 3D, what is the fast and numerically stable way to test if they form a triangle? I am thinking computing the determinant of the square matrix formed by the 3 points and testing if the determinant is nonzero. But I am not sure. What about the case for high dimensions, i.e. 4D, 5D ... Thanks! --~--~-~--~~~---~--~~ 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: random number generator
Monu Rathour wrote: i worked in *visual studio 8*,and there is a function *rand()* to generate random numbers. But now i have to work on *visual studio 6*, is there any such function? rand() is the function provided by the standard C library (stdlib), so as long as you're using an ANSI C confirmant compiler/library, the function should be present. --~--~-~--~~~---~--~~ 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: chessboard problem
I wrote the below code and tested with n =2 and n=3.
The idea is given a position (i,j) queen has three possibilities (i,j
+1),(i+1,,j+1) (i+1,,j) (Off Course not always since bounds needs to
be checked)
int numOfPath = 0;
int n = 3;
void FollowPath(int i,int j)
{
if (i = n || j =n)
{
if ( i == n j == n)
++numOfPath;
return;
}
FollowPath(i,,j+1);
FollowPath(i+1,j+1);
FollowPath(i,j+1);
}
main()
{
FollowPath(0,0);
coutnumOfPathendl;
}
For n=2 it give 3 and for n=3 it gave 13(which is correct)
--~--~-~--~~~---~--~~
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] Discussion on unique-elements-in-an-array
You can use a tweak of Merge Sort: Only change while merging of the two lists: Just while merging if two elements are equal you can make one of them equal to some predefined value. --~--~-~--~~~---~--~~ 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] Pirates of Silicon Valley Entire movie
Pirates of Silicon Valley Entire movie http://www.teenwag.com/playvideo/4294 --~--~-~--~~~---~--~~ 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] Pirates of Silicon Valley Entire movie
Pirates of Silicon Valley Entire movie http://www.teenwag.com/playvideo/4294 --~--~-~--~~~---~--~~ 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] JOB: Mathematician/contractor
and research philosophy may be helpful, but is not required. Please send plain text only. No attachments, hypertext, or active content. Please include the word Mathematician in e-mail subject line. Please send to: John F. McGowan, Ph.D. President, Research and Development Division GFT Group Inc. [EMAIL PROTECTED] --~--~-~--~~~---~--~~ 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] Block processing
Hi all,
I am writing an image processing algorithm that goes across an image
first row-wise and then column-wise. For illustration purposes,
imagine that for every pixels, the output is computed as the sum of
the input and its previous neighbourg. In the horizontal pass (i.e.
row-wise), the previous neighbourg is defined as the pixel on the
left. This is followed by a vertical pass, whereby the previous
neighbourg is defined as the pixel on top.
I quickly encountered a problem with the column-wise path, as
processing pixel in a vertical fashion was _very_ slow (0.31 vs. 0.009
for the horizontal). I since learned that it was due to cache misses.
Indeed, the image is stored row by row, so vertically-neighbouring
pixels are actually far away in memory, which entails all kind of
speed problems.
I was suggested to try a block processing approach, whereby the image
is stored by blocks rather than by rows. A block is typically 32x32,
so in memory, the first line of the block is followed by the second
line of the block, followed by the third, until we move on to the
next block, and the pattern is repeated. This has the advantage of
ensuring locality, i.e. both horizontal and vertical neighboring
pixels will be close, hence there should be less cache misses. Both
horizontal and vertical passes should be approximately as fast.
This is all well and good, but things are not that perfect in
practice. Accessing pixels is now significantly slower, even for
horizontal pass. For an image structured in blocks, an horizontal pass
is 0.030 sec. whereas with the original memory structure (row after
row, lets call it linear), the horizontal pass was only 0.009, 3 times
faster! This cannot be due to cache misses, as locality is pretty good
in both cases. The code to access a pixel is more costly in the case
of block processing. Compare the following, which is copied from my
implementation:
// linear access to pixel
// img: pointer to start of array in memory
#define PIXEL(img, width, row, col) ((img) + ((row) * width) +
(col))
// block access to pixel
#define PXL(img, width, col, row) \
((img) + (((row) (~BLOCK_Y_MASK)) * (width)) + (((col)
BLOCK_X_SHIFT) * BLOCK_SIZE) \
+ (((row) BLOCK_Y_MASK) BLOCK_X_SHIFT) + ((col)
BLOCK_X_MASK))
with enum
{
BLOCK_X_SHIFT = 5,
BLOCK_Y_SHIFT = 5,
BLOCK_X_MASK = (1 BLOCK_X_SHIFT) - 1,
BLOCK_Y_MASK = (1 BLOCK_Y_SHIFT) - 1,
BLOCK_WIDTH = (1 BLOCK_X_SHIFT),
BLOCK_HEIGHT = (1 BLOCK_Y_SHIFT),
BLOCK_SIZE = BLOCK_WIDTH * BLOCK_HEIGHT
};
Accessing a pixel is thus obviously much slower, and I was not able to
speed things up despite all my efforst. Does someone have any ideas or
suggestions that may help, or know of any good references discussing
the problem? Thanks in advance
Angus
--~--~-~--~~~---~--~~
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: RR*=R* ?
RR* = R* iff R containts epsilon (empty string). On Mar 27, 1:00 pm, Shashi Kant [EMAIL PROTECTED] wrote: which book ?? On 3/27/07, Dhruva Sagar [EMAIL PROTECTED] wrote: But it is used in books about automata...I am not agreeing to it being a valid assumption anyways. --~--~-~--~~~---~--~~ 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] DeQuba
http://www.ougo.com/setup.exe http://dequba.com/signup.php?REF=22264 http://neterminator.com/signup.php?REF=12405 --~--~-~--~~~---~--~~ 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] online $$$$
http://03mehmet.blogspot.com/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] counting subsets of S so that sum(S_n) = N
Hello!
I'd like to present my solution to the problem introduced in the
topic. First thing first, the detailed definition is in place :
Given the set of integers S = {e_1,e_2 , ... e_n } find (count) all
subsets S_n of S so, that sum(S_n) = N, for a given integer N.
After thinking a bit about the problem, I've came up with this
recursive version :
=
ways(N, S_n) :
if N == 0
if sort(S_n) not in OC # We consider solutions as {1,3}, {3,1}
only once.
append sorted(S_n) into OC
return 1
else
return 0
ret = 0
for e in S
if N - e 0
break
append e into S_n
ret += ways(N-e, S_n)
return ret
=
For all of you having a hard time reading this pseudocode, here it is
the Python version :
=
2 S = [1,6,4,3,5]
3 oc = []
4 def ways(m,l) :
5 if m == 0 :
6 l.sort()
7 if l not in oc :
8 oc.append(l)
9 return 1
10 else :
11 return 0
12 ret = 0
13 for c in S :
14 if m - c 0 :
15 break
16 l = [c] + l
17 x = ways(m - c, l)
18 ret += x
19 return ret
20
21 print ways(100,[])
=
Now, as far as I've tested the code, it works just fine, except for
performance. Converting the recursion to the iterative equivalent
sounds a bit ugly so I tought about using memonisation, but again, the
solution would be ugly as I'd have to use a set as the memonisation
index. I came to the conclusion, that another (better) algorithm
should exists and I'm asking you guys to give me some hints about some
other aproach, or, modification to the existing algorithm, in order to
increase it's performance.
Thanks!
--~--~-~--~~~---~--~~
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: reverse all the bits in a unsigned integer
On Mar 21, 7:40 am, hijkl [EMAIL PROTECTED] wrote:
. How to reverse all the bits in a unsigned integer? an signed
integer (you have to keep the sign of the integer)?
For an unsigned int, the following algorithm can be used (I believe
you can find in in the Hacker's Delight book by H.Warren) The idea
is to to swap bits with increasing distance each time:
uint bit_reverse (uint x)
{
x = ((x 0x) 1) | ((x 0x) 1);
x = ((x 0x) 2) | ((x 0x) 2);
x = ((x 0x0f0f0f0f) 4) | ((x 0xf0f0f0f0) 4);
x = ((x 0x00ff00ff) 8) | ((x 0xff00ff00) 8);
x = ((x 0x) 16) | ((x 0x) 16);
return x;
}
The function doesn't have if's and should work pretty fast. For 64-
bit numbers the solution is similar (masks are of double width and yet
another operation, shifting by 32 bits before return.
Regards,
Igor
--~--~-~--~~~---~--~~
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] E=mc2 and British Nobel Laureate Frederick Soddi
E=mc2 and British Nobel Laureate Frederick Soddi English Nobel Laureate (1921) Chemist F. Soddy stated that Material mass is converted to energy during the radioactive decay It is evident from book Radioactivity: An Elementary Treatise (The Electrician Printing and Publishing, London, 1904) in the chapter Anticipations published in 1904. In his 1905 paper Einstein also mentioned About radioactive Radium salts and energy emitted by them. And gave equation E=mc2 E= energy emitted , m = mass annihilated. Details at www.ajayonline.us Ajay Sharma --~--~-~--~~~---~--~~ 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] integers n1,n2 such that n1+n2 = x
Hello, There is a problem in the algorithm book I'm trying to digest, that I'd like to discuss a bit. So, first thing first, let me state the problem : == Describe a O( n*lg(n) ) algorithm that, given a set of integers S and another integer x, determines, weather or not, there exist two elements n1,n2 in S so that n1 + n2 = x. == OK, so now, regrading the questions - I've made an attempt to write an algorithm as follows : == find(A, x) sort(A) i = 1 while (A[i] x) n2 = x - A[i] if (binary_search(A, n2) == SUCCESS) return EXISTS i = i + 1 return not EXISTS == So, presuming the algorithm is correct, I get the following time complexity : sorting : n*lg(n) loop : n - 1 binary_search n*lg(n) * (n-1) summing these things up we have : n*lg(n) + n - 1 + n*lg(n)*(n-1) n*lg(n) + n - 1 + n*lg(n)*n - n*lg(n) cancelling out n*lg(n) and ignoring the linear terms, we have : n*lg(n)*n, which is : n^2*lg(n) So, either my algorithm sucks, or, my analysis skills suck, or, most probbably, both suck :-) Anyway, can someone check that algorithm and reasoning, correct any mistakes, or supply a better algorotihm for the task? Thanks. --~--~-~--~~~---~--~~ 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: MIPT Problem
Thanks! Solved it now. On Feb 12, 4:20 am, Lego Haryanto [EMAIL PROTECTED] wrote: Can be solved by dynamic programming. It can scale also even when we expand this and introduce the 5, 6, or more coefficients. Think of small stuff first. We know immediately the solution of x1 = n has only 1 solution. We also know that the solution of 2x2 + x1 = n will have floor(n/2) + 1 solution (basically, trying x2 = [0,1,...floor(n/2)] ... and whatever left of this can be solved in 1 way (see the x1 = n solution above). It's easy to have the solution for 2x2 + x1 = n available and let's assume that we have this in ways[0..n-1] array. For number of solution for 3x3 + 2x2 + x1 = n, start with trying x3 = 0, 1, ... floor(n/3). For x3 = 0, we have ways[n] solution, for x3 = 1, we have ways[n-3] solution ... etc. Same rule applies to 4x4. For this, I'd prefer top down with memoization method rather than bottom up as explained above. On 2/11/07, Jair Cazarin [EMAIL PROTECTED] wrote: I think that a simple backtracking approach could solve this problem. On 2/11/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: I`m trying to solvehttp://acm.mipt.ru/judge/problems.pl?problem=201. I`ve tried googling but couldn`t get any way to approach the problem. Brute force is ruled out, so how can we solve this problem? http://slipvayne.googlepages.com -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~-~--~~~---~--~~ 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] Permutation with a twist ??
Hey, I am looking for an algorithm to do as follows: my @array = qw (A B C); # This array may have several parameters, for ex. A B C D I will like to generate following (not sure if this will be called permutation): NULL C B A B C A C A B A B C Available permutation algorithms generate a different output, for example: b c a c b a c a b a c b b a c a b c Any suggestions! Thanks in advance. Manish --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: (need help) How to solve this random number generatioin problem?
ok, this is a lame attempt - can someone explain if it's correct, or
why not :
int limited_rand() {
return rand() % 8 + 1;
}
value = limited_rand() % 3 + limited_rand();
On Jan 31, 7:29 am, Ming \(Amos\) Zhang [EMAIL PROTECTED] wrote:
It's not uniformly distributed, suppose the given random generator is
uniformly distributed
-Original Message-
From: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] On
Behalf Of Sandesh
Sent: Tuesday, January 30, 2007 11:09 PM
To: Algorithm Geeks
Subject: [algogeeks] Re: (need help) How to solve this random number
generatioin problem?
suppose given function returns the random numbers between 1 -5 then
you can have
(given + given) % 7 +1
which will generate between 1 and 7 .
-Sandesh Hegde
On Jan 31, 6:57 am, Jialin [EMAIL PROTECTED] wrote:
Question:
Given a program which can generate one of {1, 2, 3, 4, 5} randomly.
How can we get another generator which can generate one of
{1,2,3,4,5,6,7} randomly?
Thank you!
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Kurukshetra Online Programming Contest
Kurukshetra OPC has been postponed. New date will be announced soon --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: how to implement doubly linked lists using only one pointer?
i mean: is it possible to get prev[x] with only x given and not knowing head? if not, then why should a double linked list be implemented?we do things exactly the same as with single linked list, i.e. using head and x to get prev[x]. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] how to implement doubly linked lists using only one pointer?
I'm reading MIT's book Introduction to Algorithms. The following is one of the excercises from it: 10.2-8 Explain how to implement doubly linked lists using only one pointer value np[x] per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as k-bit integers, and define np[x] to be np[x] = next[x] XOR prev[x], the k-bit exclusive-or of next[x] and prev[x]. (The value NIL is represented by 0.) Be sure to describe what information is needed to access the head of the list. Show how to implement the SEARCH, INSERT, and DELETE operations on such a list. Also show how to reverse such a list in O(1) time. / Could anybody tell me how to solve it? Thank you!!! --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: how to implement doubly linked lists using only one pointer?
Karthik Rathinavelu wrote: If A xor B = C, then C xor A = B and C xor B = A You can use these formulae to implement this ... That's the point! What a shame I don't know about 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 [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: NP complete Partition problem.
Found one explanation here http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK2/NODE45.HTM But one of the statements there is not acceptable to me. However, such heuristic methods are doomed to fail on certain inputs, because they do not systematically evaluate all possibilities. I just could not come up with any such sequence where the heuristic method would fail. Can anyone give me an example to that? Also, its said that the problem can be used in task scheduling by multiple processors. When the order of tasks is maintained, how will its use serve the purpose of parallel execution? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Minimal path sum - part #2
yes, this one was copy/pasted from :
http://groups.google.com/group/algogeeks/browse_thread/thread/8b9ed1060e275f29/a797db6ebd94035f?lnk=stq=minimal+path+sumrnum=1#a797db6ebd94035f
as i noticed noone seen it :)
Hello,
first of all, thanks to all for help!
as Lego Haryanto alredy guessed, this one was taken from some on-line
competition site. The next problem of this kind is a similar matrix of
size 80*80 except that you can start in any column and finish in any
other column on the other side of the matrix (i,0 = i,N-1). You can
move up down or right.
Now, as I'm doing all this problems to get more programming skills, I
tried the technique Karthik Krishnamurthy suggested - Dynamic
programming.
I reversed the path rules (I defined them as going from right to left)
and I got to the conclusion that each element (if we left out the
N-1'th row) can be accessed from N different locations , (eg. for
element 5) :
123
456
789
5+6
5+8+9
5+2+3
Knowing this, I coded a simple snippet which doesn't work :
=
int main() {
int i,j,k,c,min,res = INT_MAX;
for (j = N-2; j=0; j--) {
for (i = N-1;i= 0; i--) {
min = matrix[i][j+1];
c = 0;
for (k = i - 1; k = 0; k--) {
c += matrix[k][j];
if (c + matrix[k][j+1] min)
min = c + matrix[k][j+1];
}
c = 0;
for (k = i+1; k N; k++) {
c += matrix[k][j];
if (c + matrix[k][j+1] min)
min = c + matrix[k][j+1];
}
matrix[i][j] += min;
if (j == 0 res matrix[i][j]) {
res = matrix[i][j];
}
}
}
return printf(%d\n, res);
}
=
I tried a recursive method as in the previous post and the answer was
the same as with this code, so the problem is definitely in the
algortihm, but I'm really to stupid to get the reason - anyone can help
me?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Minimal path sum in a matrix (optimizing the algorithm)
Hello,
first of all, thanks to all for help!
as Lego Haryanto alredy guessed, this one was taken from some on-line
competition site. The next problem of this kind is a similar matrix of
size 80*80 except that you can start in any column and finish in any
other column on the other side of the matrix (i,0 = i,N-1). You can
move up down or right.
Now, as I'm doing all this problems to get more programming skills, I
tried the technique Karthik Krishnamurthy suggested - Dynamic
programming.
I reversed the path rules (I defined them as going from right to left)
and I got to the conclusion that each element (if we left out the
N-1'th row) can be accessed from N different locations , (eg. for
element 5) :
123
456
789
5+6
5+8+9
5+2+3
Knowing this, I coded a simple snippet which doesn't work :
=
int main() {
int i,j,k,c,min,res = INT_MAX;
for (j = N-2; j=0; j--) {
for (i = N-1;i= 0; i--) {
min = matrix[i][j+1];
c = 0;
for (k = i - 1; k = 0; k--) {
c += matrix[k][j];
if (c + matrix[k][j+1] min)
min = c + matrix[k][j+1];
}
c = 0;
for (k = i+1; k N; k++) {
c += matrix[k][j];
if (c + matrix[k][j+1] min)
min = c + matrix[k][j+1];
}
matrix[i][j] += min;
if (j == 0 res matrix[i][j]) {
res = matrix[i][j];
}
}
}
return printf(%d\n, res);
}
=
I tried a recursive method as in the previous post and the answer was
the same as with this code, so the problem is definitely in the
algortihm, but I'm really to stupid to get the reason - anyone can help
me?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] NP complete Partition problem.
Can someone please give me a algorithm/pseudo code for the following
problem?
Given an arrangement S of non-negative numbers {s1,s2,s3sn} and an
integer k.
Partition S into k ranges, so as to minimize the maximum sum over all
the ranges.
e.g Optimally S={1,2,3,4,5,6,7,8,9} partitioned into k=3 ranges will be
{1,2,3,4,5}, {6,7}, {8,9}
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Minimal path sum in a matrix (optimizing the algorithm)
Hello!
Let's say we have a matrix of size N*N filled with arbitrary positive
integers. Now, let's say we would like to move from the upper left
point ([0,0]) to the lower right point [N-1,N-1] moving only down OR
right, so that a path with the minimum sum of elements is created. Ex .
When n= 3
123
456
789
the minimal path sum is 1 + 2 +3 + 6 + 9 = 21
Now I wrote a recursive function, that calculates the minimal path sum
for a matrix N=80 :
=
unsigned long long sum(int i, int j) {
unsigned long long left,right;
if (i == 79 j == 79) {
return matrix[i][j];
} else if (j == 79 i != 79) {
return matrix[i][j] + sum(i+1,j);
} else if (i == 79 j != 79) {
return matrix[i][j] + sum(i, j+1);
}
left = sum(i, j+1);
right = sum(i+1, j);
if (left right)
return matrix[i][j] + right;
else
return matrix[i][j] + left;
}
=
Now, the code works pretty fast for small matrices, but it's running
since last night on the mentioned matrix of size 80*80.The number of
paths it has to check is :
92045125813734238026462263037378063990076729140
so there should be a faster method to determine which path to take. The
only optimisation I can think of is to calculate a middle bound and
return a sentinel value as soon as the sum exceeds this value to
indicate that the chosen path isn't optimal. I'm not really sure how to
implement that option (or, if it' possible) so I'm referring to the
list for _any_ code/algorithm optimisation hints.
Thanks.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Minimal path sum in a matrix (optimizing the algorithm)
Thanks for the reply :-) I've never worked with graphs or something, and I'm very interested in a non-graph solution. (working only on the integer array) --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Minimal path sum in a matrix (optimizing the algorithm)
Nice hint indeed! The code finish in 0.02s taking in account that some
sums repeats! Thanks for the hint really! I feel so dumb to not think
about that before :-(
Anyway, the renewed function looks like :
=
unsigned cache[80][80] = {0};
#define CACHED(i,j)\
if (!cache[i][j])\
cache[i][j] = sum(i,j);
unsigned sum(int i, int j) {
if (i == 79 j == 79) {
return matrix[i][j];
} else if (j == 79 i != 79) {
CACHED(i+1,j);
return matrix[i][j] + cache[i+1][j];
} else if (i == 79 j != 79) {
CACHED(i, j+1);
return matrix[i][j] + cache[i][j+1];
}
CACHED(i,j+1);
CACHED(i+1,j);
if (cache[i+1][j] cache[i][j+1])
return matrix[i][j] + cache[i][j+1];
else
return matrix[i][j] + cache[i+1][j];
}
=
thank you very much!
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: whether 2 lists produce identical BST's or not?
:).
Apparently, Ravi has an assumption that each BST should be constructed
with same method. And the first one is choosen as a root.
In fact, if two lists have identical elements, they have identical BST
sets.
At least, if we focus on Ravi's problem, this problem will be reduced
to order comparison between two strings.
And it can be handled in O(N).
On Nov 1, 2:23 pm, Vijendra Singh [EMAIL PROTECTED] wrote:
Oh ok.. I got confused... lemme think about this one. I think it has a
recursive soltuion but will confirm it.
-Vijju
On 11/1/06, ravi [EMAIL PROTECTED] wrote:
I think u have misunderstood the question.
I am not asking about the two lists have identical elements or not?
If we have two lists then how will we check whther two lists produce
identical BSTs or not?
For example
L1 = { 10, 5, 15 }
L2 = { 5 , 10, 15 }
L3 = { 10, 15, 5 }
L1, L2, L3 all have identical elements.
But only L1, L3 will produce identical BSTs.
L1, L3 produce tree as10
515
L2 produce BST as 5
10
15
I think now the question is clear?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: whether 2 lists produce identical BST's or not?
A list can be transformed to serveral BSTs (If the number of elements
is n, then you can caculate the numbers of its BSTs). But, if we chose
a specified method or process (just as ravi supposed) to construct the
BST, then it will be unique. I have the same opinion with Vijendra
Singh. He said If the two lists have same elements, then these *can*
produce identical BSTs. as for any list, there are number of ways to
construct a BST,
And I believe the right solution should be the same way arun kumar
manickan provided. Its time complexity can be reduce to O(n) by
comparing the orders of each lists(String in former post is a type
error).
I will put my program tomorrow in my time, as now I am kinda busy.
On Nov 2, 5:17 pm, Arun [EMAIL PROTECTED] wrote:
In fact, if two lists have identical elements, they have identical BSTsets.
this is not correct. its order sensitive. if u see his example L1 and L3
cannot be simply compared like strings. There can be many ways to have the
same elements given in slightly different order yet produce the same BST. Im
not sure why Ravi doesnt want to construct the BST. That wud give O(n) time
easily. (but also O(n) memory)
For now, the only way I can think of, is by actually constructing the BST in
some form.
Another way (O(n^2) time ) without constructing the BST can be formed by
making this observation:
For an element L[i] in the list , see the next smaller element than L[i].
Call it L[j] .
If in both the lists for all i, order of L[i] and its corresponding L[j] are
same (that is either L[i] comes first then L[j] or otherwise) then the lists
give the same BST.
Sorry ,its hard for me to picturise it here. Correct me if this is wrong :)
On 11/2/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
:).
Apparently, Ravi has an assumption that each BST should be constructed
with same method. And the first one is choosen as a root.
In fact, if two lists have identical elements, they have identical BST
sets.
At least, if we focus on Ravi's problem, this problem will be reduced
to order comparison between two strings.
And it can be handled in O(N).
On Nov 1, 2:23 pm, Vijendra Singh [EMAIL PROTECTED] wrote:
Oh ok.. I got confused... lemme think about this one. I think it has a
recursive soltuion but will confirm it.
-Vijju
On 11/1/06, ravi [EMAIL PROTECTED] wrote:
I think u have misunderstood the question.
I am not asking about the two lists have identical elements or not?
If we have two lists then how will we check whther two lists produce
identical BSTs or not?
For example
L1 = { 10, 5, 15 }
L2 = { 5 , 10, 15 }
L3 = { 10, 15, 5 }
L1, L2, L3 all have identical elements.
But only L1, L3 will produce identical BSTs.
L1, L3 produce tree as10
515
L2 produce BST as 5
10
15
I think now the question is clear?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: majority element
It seems that you gotta use the median algrithm. Here's some idea without implementation, I wish it will help. if the array has an odd number of lements, then the array can be devided into 3 parts: Head, Median, Tail If an element occurs more than n/m times, then at least in Head or in Tail it will occurs more than n/2m times. So we can divide and conquer it recursively. And for even case, it will be similar. On Nov 2, 10:21 am, ericunfuk [EMAIL PROTECTED] wrote: Dear all, I have worked out the following algorithm for finding the majority element(the element occurs more than n/2 times) of an array of n elements : Suppose that I have a subroutine that could find the median of an array in theta(n) time, then: the algorithm will be: 1.find the median of the array 2.check to see if it's the majority element by a single pass through the array, and count its occurrence Now, what if I want to find the element that occurs more than n/m times in the array, where m is an arbitrary integer?How can I just modify the above to get this new algorithm?It could be very straightforward, but i got stuck on this, Any hints, help appreciated!! Thanks. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Give an Optimal Allocation Algorithm for the described problem.
Knap sack algorithm works well when 'M' is small. I think this a NP problem. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Finding median in theta(n^lg3) time
binary search will not work in case the array is unsorted..otherwise use it. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Finding all loops in a directed graph
maybe u can use Floyd-warshall by mark the edges negative weight --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: How to calculate the time complexity of an algorithm?
could you talk it in detail? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Can we get a general formula for Lexicographic Ordering?
i think a better algo...but can be used only in languages where there is provision of conversion of characters into ascii code... so algo is... set a variable counter to one 1.copy the string in a string variable 2.take its first second character from left to right 3.if the ascii code of second character is less then first , delete the string 4.else move to third character in the string. 5. repeat steps 3 4 till the end of string 6. if the string ends replace the string in file by counter 7. Increment counter. 8 if end of file then exit else move to step1 if anybody thinks i am wrong plzz let me know --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: algo to find common parts in strings?
This is what grammar-based compression algorithms do. You should be
able to find many by searching for those words.
Flo wrote:
I am searching an algorithm that can find common parts within a set of
given strings. For example given the four strings
MinXBla MinYBla MinPhiBla MinThetaBla
The algorithm should see that the strings start with Min, then comes a
variable string, and then they end with Bla. An extra would be if it
would also return the list of variable strings, here {X,Y,Phi,Theta}.
What if I add another level? For example given the 8 strings:
fMinXBla fMinYBla fMinPhiBla fMinThetaBla
nMinXBla nMinYBla nMinPhiBla nMinThetaBla
Where we have almost the same situation as before, however a variable
string is prepended to each string. The list of variables is now 2
dimensional {f,n}{X,Y,Phi,Theta}.
I am happy if somebody knows the name such an algorithm, if it exists,
so I can look up the details myself.
Greetings
Flo
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Nesting of comments in C
smilitude of solitude wrote:
Uhh...
Stadazi, I think you missed the point.
It depends on which compiler you use - /to strictly define main to
return int/. Once upon a time, I used TC and TC didnt have that problem.
If you rewrite the code into this
The compiler wasn't ANSI C compliant then ;-) By the C standard, main
has to be int, it's not a compiler/platform question.
#include cstdio
#include iostream
#include cstdlib
using namespace std;
int main() {
int allowed=1;
/* /* */ allowed=0; // */
printf( allowed ? yes\n : no\n );
system(pause);
return 0;
}
This code isn't C anyway.
I'm sorry for being pedantic, but that's just the way C coders are ;-}
--~--~-~--~~~---~--~~
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] Photos of Dead Celebrities
http://groups.yahoo.com/group/RxR111 Search for.. THIS is Out of This World Don't have to join to view --~--~-~--~~~---~--~~ 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: Nesting of comments in C
Atamyrat Hezretguliyew wrote:
#includestdio.h
void main() {
int allowed=1;
/* /* */ allowed=0; // */
printf( allowed ? yes : no );
}
please correct me if there's smth i missed.
you missed that main is strictly defined as a function returning int :-)
--~--~-~--~~~---~--~~
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: Euclidean embedding of a graph?
Ok, i've understood; you're problem is related to the one of drawing
planar graphs (is it correct?).
I can't tell you ('cause i don't know) a proper algorithm but you might
find it useful to look at this:
http://www.graphviz.org/Theory.php
at least to have an idea of what the problem is then try
scholar.google.com.
When you've done post the solution here, i'm intrested :)
Giacomo
--~--~-~--~~~---~--~~
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: Quicksort duplicates
3-way quicksort - never heard of that before. I must do some independent learning. Thank you both for your comments/experiences. I appreciate your feedback. Al. --~--~-~--~~~---~--~~ 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: Need an algorithm to find the missing numbers.
This is a very old problem in this group.
The solution is simple. Here is an example
{1,3} missing 2
1 XOR 3 XOR 1 XOR 2 XOR 3 = 2
-Original Message-
From: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] On
Behalf Of Joe
Sent: Thursday, August 24, 2006 7:56 PM
To: Algorithm Geeks
Subject: [algogeeks] Need an algorithm to find the missing numbers.
Hi,
In a sequence o,f from 1 to n (1,2,3,...n) numbers, we need to find the
missing numbers. There will not be duplicates.
Can you please suggest an algorithm.
Thanks,
Joe.
--~--~-~--~~~---~--~~
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] Quicksort duplicates
Hi, Hope that you can help me with this one. Relative to what I have read Quicksort it is a very good sorting algorithm. However, there can be trouble if there is a high level of duplicates. I have 2 questions based upon this Q1: Can anyone recommend a good sorting algorithm that works well with a high level of duplicates are present? Q2: At what point should one considered moving from quicksort - other algorithm that works well with duplicates? Are there any useful metrics in determining the level of duplicates e.g. Duplicate Level = Total # of Duplicates / Total quantity of Elements At what point should you consider crossing over? Thanks for any comments/suggestions/user-experiences offered. Al. --~--~-~--~~~---~--~~ 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: Euclidean embedding of a graph?
Hi, could you please explain your problem more in detail? What is your problem, optimization? It is related with the embedding of finite metrics over finite graph? That is, what do you mean with euclidean separation of nodes? Something like w(i, j) is the distance between Rome and Venice or w(i, j) can be any real non negative value that defines a distance? If the latter is the case and you're problem is optimization you're looking to an optimization over the metric polytope; on the other hand if the former is the case and you're problem may be optimization over a network graph (possibly a network flow problem). If you specify deeper your problem maybe i can be a bit more helpful. Giacomo. --~--~-~--~~~---~--~~ 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: fwd : google code jam 2006
Heya! A bit offtopic. I was looking for the previous asigments/solutions on the CodeJam site but couldn't find none.. Can someone provide a link? --~--~-~--~~~---~--~~ 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: fwd : google code jam 2006
Goto www.topcoder.com -Original Message- From: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] On Behalf Of [EMAIL PROTECTED] Sent: Monday, August 21, 2006 7:38 PM To: Algorithm Geeks Subject: [algogeeks] Re: fwd : google code jam 2006 Heya! A bit offtopic. I was looking for the previous asigments/solutions on the CodeJam site but couldn't find none.. Can someone provide a link? --~--~-~--~~~---~--~~ 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: Nonrecursive algorithms for printing out BST keys
Just use a stack to stimulate the recursive method -Original Message- From: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] On Behalf Of martin-g Sent: Monday, August 14, 2006 11:58 AM To: Algorithm Geeks Subject: [algogeeks] Nonrecursive algorithms for printing out BST keys Hi. Would you help me in composing a nonrecursive algorithm to print out the keys of BST nodes in ascending order. Any approach will do whether it uses stack or not. Thanks in advance Martin --~--~-~--~~~---~--~~ 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] k-means clustering
Can anyone link me to a k-means clustering program? If not, then an algorithm would be helpful also. I have tried searching for one, but I get no results worth using. So I am wondering if there are any people experienced, that could be of more help. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] interval intersection
Given a set of intervals, (a,b)s some of which could have overlap, what is the best way to find the common sub-interval which overlaps most number of intervals (a,b) ? There could be more than one such sub-interval and algo should return all such sub-intervals. For example, (1, 5), (2, 6), (3, 8) have (3,5) as the answer. thanks dhiman --~--~-~--~~~---~--~~ 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: where to find problems?
Hello, http://mathschallenge.net Check for project euler --~--~-~--~~~---~--~~ 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: Is there any better solution than 0(nlgn) ?
1 #include stdio.h
2
3 int main() {
4
5 int A[] = {8,5,4,2,9}, B[] = {1,2,3,4,6};
6 static int fo[10] ,i,ret = 0 ; /* max value is stored in A
which is 9
7if we wouldn't know this, we'd
nee to rely
8on INT_MAX or some other shit */
9
10 for (i = 0; i 5; i++)
11 fo[A[i]] = 1;
12
13 for (i = 0; i 5; i++)
14 if (fo[B[i]])
15 ++ret;
16
17 return printf(%d\n , ret);
18 }
Just out of couriostiy... What's the complexity of the above code?
O(2n) ?
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
