[algogeeks] Re: Testing if 3 points form a triangle
On Jun 5, 1:45 am, Feng [EMAIL PROTECTED] wrote: Hi BiGYaN, triangle is a 2D object which can be formed by any 3 non- collinear points. It can exist in 4D, just like a point existing in 3D. On May 31, 2:11 am, Victor Carvalho [EMAIL PROTECTED] wrote: Feng, how can form a triangle in four dimensions??? 2007/5/29, BiGYaN [EMAIL PROTECTED]: Just test whether they are collinear or not i.e. get the slopes, m1 from 1st and 2nd point m2 from 2nd and 3rd point if m1==m2 then they do not form a triangle else they do Computing the area of the triangle and testing for 0 might also work but I feel that the computation will be bigger -- Victor Carvalho Computação - UFC GELSoL - Grupo de Estudos de Linux e Software Livre E-Jr Empresa Júnior de Computação I never had a problem with a triangle in 4D !! You probably aimed it @ Victor. --~--~-~--~~~---~--~~ 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
Just test whether they are collinear or not i.e. get the slopes, m1 from 1st and 2nd point m2 from 2nd and 3rd point if m1==m2 then they do not form a triangle else they do Computing the area of the triangle and testing for 0 might also work but I feel that the computation will be bigger --~--~-~--~~~---~--~~ 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 me with finding the time complexcity
On May 28, 6:21 pm, sl7fat [EMAIL PROTECTED] wrote: hi i have an algorthim code and i have to find the time complixcity of the code so can you plz help me ASAP the code is written done ,, # include iostream.h void main() { int a[10][4]= {{ 16,17,19,13}, {18,14,15,19}, {18,20,20,19}, {13,14,15,10}, {20,17,19,19}, {18,13,18,19}, {18,10,15,12}, {12,14,15,11}, {12,16,17,18}, {18,11,15,10}} ; int i,j,max,min; float avg,sum; for(i=0;i10;i++) { for(j=0;j4;j++) { cout a[i][j] ; } cout \n; } for(i=0;i4;i++) { max= a[0][i]; min= a[0][i]; sum=0; for(j=1;j10;j++) { sum= sum+a[j][i]; if(a[j][i]max) max=a[j][i]; if(a[j][i]min) min=a[j][i]; } avg= sum/10; cout The average Grade for Exam i+1 is: avg\n; cout The minimum Grade for Exam i+1 is: min\n; cout The maximum Grade for Exam i+1 is: max\n\n; } for(i=0;i10;i++) { min= a[i][0]; sum=0; for(j=0;j4;j++) { sum= sum+a[i][j]; if ( mina[i][j]) min= a[i][j]; } sum= sum-min; cout The summation of the best 3 grades for student No i +1 is: sum\n; } } thanx alot :D O(n^2) there is no variable here so what exactly were u asking? --~--~-~--~~~---~--~~ 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: interesting collinear Points problem
As far as I get it, this may be the solution : Find out all the possible lines between those n points (total of nC2 lines). Here we define a line to be an ordered set of 2 points where the first point is 2nd point (ie. length of origin to first point is length of origin from 2nd point). Then we sort them by their slope value as primary key and starting point as secondary key. From the sorted list identify the longest sequence of the same slope and same starting point. Th length of this sequence is the required answer. Thus the complexity turns out to be : O(n^2) : for identifying nC2 lines. O(n^2*log_m) : for sorting those lines (where m is the different number of unique slope) O(n^2) : for identifying the longest sequence So the complexity comes to : O(n^2*log_m) What does everybody think on this? --~--~-~--~~~---~--~~ 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: Given Infinite array ,Find one number problem
@ Arun By, arr[i].val I meant the value stored in i-th position and not the valid/invalid bit. So I'm not making any assumption related to storing of valid numbers in contiguous positions. Guess I should have written arr[i].value as val is common to both value as well as valid. --~--~-~--~~~---~--~~ 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: Farmer John find location barn
You just want a solution or you want a DPP solution? A O(n^4) solution is trivial in nature and is quite easily achievable. --~--~-~--~~~---~--~~ 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: binary tree
The thing that you asked for is formally known as BFT (Breadth First Traversal). Here's the pseudo-code that'll give you the idea in general. #define MAX 100 void BFT ( node *root ) { node *p; ins_Q(root);// inserting the node into a queue do { p = del_Q(); // deleting an item from the queue visit(p); if ( p-left != NULL ) ins_Q(p-left); if ( p-right != NULL ) ins_Q(p-right); } while ( queue is not empty ); } This will cause the traversal from left to right in each level. --~--~-~--~~~---~--~~ 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: Height of a binary tree
Yup dudes I agree it was a wrong program I have put the proper indentation without proper braces and that makes the code incorrect. The correct program would be : int getheight ( node *p ) { if ( p==NULL ) return 0; else { rh = getheight ( p-right ); lh = getheight ( p-left ); return ( (lhrh ? lh : rh)+1 ); } } It's amazing to know that I can still make such silly mistakes after coding in C for 3+ yrs. Thanks to all those fellows who pointed out the error. I am really sorry for 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: Solution for Automata
I would also like to visit such a site. Its been quite frustrating trying out problems for hours only to find out that nowhere can you get the correct solution. --~--~-~--~~~---~--~~ 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: Heaps vs. B-Tree
There is no perfect hash function that will give an unique location every time it is called. So BTrees will be faster no doubt. Also note that with BTrees (or B+Trees) it is easier to retrieve data filtered on range(s) of keys. --~--~-~--~~~---~--~~ 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* only when R contains a null string. else, RR* = R+ --~--~-~--~~~---~--~~ 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: Algoritm needed
This looks like the classic Assignment problem to me do look up on this topic and I'm sure you'll come across a few good algos. Initially, it seems that it'll be an O(n^3) problem but maybe you can better 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: Sorting o(n) time
Yeah, after finding the k-th element there is no need for further partitioning. This is logically true indeed. But in this case, I guess you have to do it for determining who'll get the Samosas and who the Gulabjamuns !!. --~--~-~--~~~---~--~~ 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: 2D arrays
Please don't post homework questions here. This problem is too simple for a group calling themselves Algorithm Geeks. I hope most of you'll agree to this and put a stop to this practice. --~--~-~--~~~---~--~~ 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: C++
You could try : The C++ Programming Language (3rd or Special Ed) by, Bjarne Stroustrup This is the fellow who developed the C++ language and this is really an awesome book. However if you are a newbie to programming then you might find certain difficulties with 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: Sorting o(n) time
You could try the quick-sort algo with these further modifications : every time you partition the list (assuming ascending) you leave out the entire working for the right hand part iff the size of the left hand part is = m (m is the top m elements that you need). NB : Here left hand part indicates the part to the left of the pivot i.e. right from the beginning of the array. This on an average case should be able to accomplish the task in O(n) time. --~--~-~--~~~---~--~~ 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: Bitwise 2007
ThankZ a lot --~--~-~--~~~---~--~~ 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: C/C++ Programming
Trying to write an OS at 12 !! GR8. But unfortunately writing an OS is very difficult. I have written only a basic OS like DOS. It took me around a month and I am a Computer Science final year student. So dump the idea of writing an OS atleast for now. Better write some utility programs like Spellchecker - something which you need 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.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Finding the k largest/smallest elements in the array !
Deepu, are you sure that this Algo will have an O(n) complexity. None of my friends and for that matter most of my teachers disagree with it having a linear time bound. --~--~-~--~~~---~--~~ 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: check string A and B isPermutation ?
Assuming that you cannot have any letter repeated more than 15 times. Create a struct of 26, 4 bit bitfields. This is going to take 26x4 bits or 13 bytes of memory. Use this structure to store the character count of each character of the first string. Now proceed to the second string and for each character, decrease it's corresponding character count by 1 if it is greater than 0. If it is 0 then the second string is not a permutation of the first string. At the end of processin the second string check whether each caracter count is 0. If they all are 0 then the strings are permutations of one another. Of course you can modify the algo to accomodate higher maximum character counts. In any case the time required is O(n) and space required is 26 x ceiling ( log ( maximum_individual_character_count, base=2) ) bits. --~--~-~--~~~---~--~~ 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: Subset with largest sum
It is simple. Here are the steps, tot = sum of the entire array max = tot start = 0 end = n-1 sub_start = start sub_end = end while ( start end ) { if ( array[start] array[end] ) { tot=tot-array[start] start++ } else { tot=tot-array[start] end-- } if ( tot = max ) { max = tot sub_start = start sub_end = end } } At the completion of the above code, you will get sub_start = starting loaction of the subarray sub_end = ending loaction of the subarray --~--~-~--~~~---~--~~ 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: Program This!
Hey Admin, Please ban this fellow. He's just using the group for his own well being and spamming the group !! --~--~-~--~~~---~--~~ 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: Inscription test run problems
With regards to the first problem, it is pretty easy if you can have all the primes precomputed. As a matter of fact, if you search the net, you'll find the list of all prime no.s that can be stored as a 4 byte unsigned integer !!. Just use that list of primes to find out the nearest with the help of binary search. Else, you may also try the sieve of eratosthenes to compute prime numbers at run time, but I guess in the long run, the above method is better due to rduced computation. --~--~-~--~~~---~--~~ 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: Balanced tree building
If we can have the total no. of nodes in tree as an input (say N), this problem is pretty easy. We construct a full BST of level = ceiling ( log (base 2) N ) - 1 conatining only dummy nodes. Now we travel the BST in the same fashion as a linked list starting from the root node. The root must have the highest number, so it becomes the right-most daughter of the right-most node of the last level of the full BST. This tree is then filled (filled in reverse inorder mode) with the numbers obtained from the list-list traversal of the original BST. While doing the traversal in the original tree, we can delete each node as we have passed through it. At the exhaution of the original tree this new tree will obviously be balanced as the original tree with dummy values was balanced and in the worst case there will be only one level more in the RHS of the root of the BST. This algorithm can be accomplished in O(N) time O(N/2) space. The only hitch is that we have to know the total no. of nodes at the beginning. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: A challenging multiplication problem
Was that a test-your-knowledge question ? or are u really interested ? If latter then look up Knuth. If u are looking for a solution in a particular domain, this can be solved far easily. Please mention the data structure used for storing the number and the result and upto what accuracy ?? --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---