[algogeeks] Re: Counting number of rectangles
Write here again: I find an easier non-recursive solution to compute the rectangle number (represented as RN) of an h x w rectangle (which has a height of h units and a width of w units): Situation 1: If (h and w are coprime) or (h = 1) or (w = 1) then RN = h + w - 1. Situation 2: If h and w are not relatively prime, we can find the greatest common divisor (represented as gcd) that makes (1) h = h' x gcd, w = w' x gcd and (2) (h' and w' are coprime) or (h' = 1) or (w' = 1), then we finally get the result RN = (h' + w' - 1) x gcd. This computation method will obviously help you find all the rectangles with a given pair of height and width. It's pretty much like a reverse problem. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Counting number of rectangles
Write here again: I find an easier non-recursive solution to compute the rectangle number (represented as RN) of an h x w rectangle (which has a height of h units and a width of w units): Situation 1: If (h and w are coprime) or (h = 1) or (w = 1) then RN = h + w - 1. Situation 2: if h and w are not relatively prime, we can find the greatest common divisor (represented as gcd) that makes (1) h = h' x gcd, w = w' x gcd and (2) (h' and w' are coprime) or (h' = 1) or (w' = 1), then we finally get the result RN = (h' + w' - 1) x gcd. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Counting number of rectangles
I find an easier non-recursive solution to compute the rectangle number (represented as RN) of an h x w rectangle (which has a height of h units and a width of w units): Situation 1. if (h and w are coprime) or (h = 1) or (w = 1), then RN = h + w - 1 Situation 2. if h and w are not relatively prime, we can find the greatest common divisor (represented as gcd) that makes (1) h = h' x gcd, w = w' x gcd. and (2) (h' and w' are coprime) or (h' = 1) or (w' = 1). then RN = (h' + w' - 1) x gcd On Aug 23, 8:37 am, Nikhil Jindal wrote: > Here's my try: > > The following function returns the rectangle number given the dimensions of > the rectangle. > > int FindRectangleNumber(int row, int colm) > { > if (row == colm) > return row; > if (row == 1) > return colm; > if (row%2 == 0 && colm%2 == 0) > return 2*FindRectangleNumber(row/2, colm/2); > if (row%2 == 1 && colm%2 == 0) > return FindRectangleNumber(row - 1, colm) + 2; > if (row%2 == 0 && colm%2 == 1) > return FindRectangleNumber(row, colm - 1) + 2; > if (row%2 == 1 && colm%2 == 1) > return FindRectangleNumber(row - 1, colm-1) + 1; > > } > > This function can be used to solve the given problem. > > On Sun, Aug 22, 2010 at 3:29 PM, Saikat Debnath wrote: > > > > > Can anyone help in finding number of rectangles having a given > > recatngle number. A rectangle number is defined as the number of unit > > sided square formed inside the given rectangle having a common point > > with a diagonal of rectangle. The sides of rectangle have integer > > length. E.g. number of rectangle with rectangle number 4 is 4, i.e. > > 1X4, 2X4, 2X3 and 4X4. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > Please access the attached hyperlink for an important electronic > communications > disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: linked list as tree
What do you exactly mean? You want to represent a linear structure by using a tree structure? You can imagine a linked list as a tree with all its root and inner nodes only having one descendent/child node. On Aug 23, 10:50 am, Raj N wrote: > What will be the representation. How do you define left and right pointers > of the tree for a linked list. > > On Mon, Aug 23, 2010 at 10:35 PM, Yan Wang wrote: > > > Actually, a linear data structure like a linked list is also a > > specific kind of tree structure. > > > 2010/8/23 Raj N : > > > Hi, > > > Could anyone help me representing linked list in the form a binary > > > tree ? > > > > Thanks !! > > > > -- > > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > > To post to this group, send email to algoge...@googlegroups.com. > > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com > > . > > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sorting algorithm
Dat's Inplace count sort -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] linked list as tree
What will be the representation. How do you define left and right pointers of the tree for a linked list. On Mon, Aug 23, 2010 at 10:35 PM, Yan Wang wrote: > Actually, a linear data structure like a linked list is also a > specific kind of tree structure. > > 2010/8/23 Raj N : > > Hi, > > Could anyone help me representing linked list in the form a binary > > tree ? > > > > Thanks !! > > > > -- > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Counting number of rectangles
Here's my try: The following function returns the rectangle number given the dimensions of the rectangle. int FindRectangleNumber(int row, int colm) { if (row == colm) return row; if (row == 1) return colm; if (row%2 == 0 && colm%2 == 0) return 2*FindRectangleNumber(row/2, colm/2); if (row%2 == 1 && colm%2 == 0) return FindRectangleNumber(row - 1, colm) + 2; if (row%2 == 0 && colm%2 == 1) return FindRectangleNumber(row, colm - 1) + 2; if (row%2 == 1 && colm%2 == 1) return FindRectangleNumber(row - 1, colm-1) + 1; } This function can be used to solve the given problem. On Sun, Aug 22, 2010 at 3:29 PM, Saikat Debnath wrote: > Can anyone help in finding number of rectangles having a given > recatngle number. A rectangle number is defined as the number of unit > sided square formed inside the given rectangle having a common point > with a diagonal of rectangle. The sides of rectangle have integer > length. E.g. number of rectangle with rectangle number 4 is 4, i.e. > 1X4, 2X4, 2X3 and 4X4. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Sorting algorithm
@Tanveer: Count sort is not in place. uses extra memory On Mon, Aug 23, 2010 at 4:32 PM, varun bhatia wrote: > Who said count sort does not uses extra space??? > > As faras I know, it does need extra space to need thr frequency of each and > every element within a given range.. > > Regards, > > Varun Bhatia > > > > On Mon, Aug 23, 2010 at 4:20 PM, Tanveer Asif wrote: > >> Count sort.. >> >> >> -- >> *From:* Subhranil Banerjee >> *To:* algogeeks@googlegroups.com >> *Sent:* Mon, August 23, 2010 3:36:12 AM >> *Subject:* [algogeeks] Sorting algorithm >> >> Can anyone suggest a sorting algorithm that sorts in linear time without >> using extra space. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sorting algorithm
Right. If there is a O(n) sort that uses only constant space, I'd love to hear about it. Radix sort, bucket sort, counting sort all need O(n) space. On Aug 23, 7:02 am, varun bhatia wrote: > Who said count sort does not uses extra space??? > > As faras I know, it does need extra space to need thr frequency of each and > every element within a given range.. > > Regards, > > Varun Bhatia > > On Mon, Aug 23, 2010 at 4:20 PM, Tanveer Asif wrote: > > > > > Count sort.. > > > -- > > *From:* Subhranil Banerjee > > *To:* algogeeks@googlegroups.com > > *Sent:* Mon, August 23, 2010 3:36:12 AM > > *Subject:* [algogeeks] Sorting algorithm > > > Can anyone suggest a sorting algorithm that sorts in linear time without > > using extra space. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] linked list as tree
Actually, a linear data structure like a linked list is also a specific kind of tree structure. 2010/8/23 Raj N : > Hi, > Could anyone help me representing linked list in the form a binary > tree ? > > Thanks !! > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: 5 pirate problem
This is not a computer problem. Think about it backwards. If there are only 2 pirates left, then the elder can claim all 100 coins, at worst the vote will be tied, and so he survives and takes 100 coins. If there are 3 pirates left, then the oldest can claim 99 coins and give the youngest 1 coin, with the second oldest pirate getting nothing. Since the youngest gets more than he would if he voted no, he will vote yes with the oldest, so the oldest survives and takes 99 coins. If there are 4 pirates left, then the oldest can claim 99 coins and give the third oldest 1 coin, with the second oldest and youngest getting nothing. The third oldest vote yes because he gets more than if he voted no, so the vote is at least tied, so the oldest survives and takes 99 coins. At the beginning, with all 5 pirates, the oldest can claim 98 coins and give the third oldest and the youngest 1 coin each. They will vote with him because they will get more than if they voted no, so the oldest pirate survives and takes 98 coins. Dave On Aug 22, 10:36 pm, hari wrote: > Five pirates (of different ages) have 100 gold coins to divide > amongst themselves. They decide on the following approach to determine > how much each pirate receives: > > The eldest pirate proposes an allocation. All pirates (including the > eldest) then vote on the proposal. If the majority accept the proposal > then the coins are divided in the way suggested. If not, then the > eldest pirate is executed and the new eldest amongst the remaining > pirates proposes a new allocation. If the votes are tied then this is > enough for the proposal to be accepted. > > Assuming that the pirates are motivated primarily by survival, then to > a lesser extent by greed and finally to the least extent by sadism > (i.e. they'd prefer to receive a gold coin and see someone get > executed than just receive one coin earlier, but would prefer one coin > to none and an execution; and obviously would prefer 0 coins and > surviving to 100 coins and being executed), and act in a logical way, > what is the maximum number of coins the eldest pirate can get? > > please provide a source code > > thanks in advance -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: To sort an array of 0,1,2
@sathiah..i can get u ..but dont seem to understand the part where in we must keep track of the 1's...can u pls post the code.. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: To sort an array of 0,1,2
You can refer to this sample code i had tried to sort in a single pass: #include #include using namespace std; int main() { int a = 0, b=1, c=9; int s[10]= { 2,1,0,1,1,0,2,1,0,1}; while(ab) c--; if(!(a>=b) && !(b>=c)) { if(s[b]==0) { s[b]=s[a]; s[a]=0; } if(s[b]==2) { s[b]=s[c]; s[c]=2; } } for(int i = 0; i<10; i++) { cout
Re: [algogeeks] Re: BST Problem
I am not sure if I am repeating the answer: The problem will reduce to find the pair of elements which will sum up to a particular number. Then read the below article, http://www.rawkam.com/?p=345 On Mon, Aug 23, 2010 at 9:29 AM, R.ARAVINDH wrote: > @giri: > > can u post d correct answer?? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Sorting algorithm
Comparison Sort Algorithms cannot sort in linear time( http://www.rawkam.com/?p=886) so we have to use some non-comparison sorting algorithm like Counting Sort,Bucket Sort, Radix Sort etc. But all the non-comparison sort algorithms requires the input to be in a particular order. (For example: Counting Sort will not be a good option if range of numbers is high. On Mon, Aug 23, 2010 at 4:20 PM, Tanveer Asif wrote: > Count sort.. > > > -- > *From:* Subhranil Banerjee > *To:* algogeeks@googlegroups.com > *Sent:* Mon, August 23, 2010 3:36:12 AM > *Subject:* [algogeeks] Sorting algorithm > > Can anyone suggest a sorting algorithm that sorts in linear time without > using extra space. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: To sort an array of 0,1,2
Yes, it is possible in one pass without extra memory, I think this is a CLRS exercise problem. It is possible in one pass without using extra memory. Keep the 0's at left and 2's at right and scan the middle portion from left to right and if you see 0 keep at left side and if you see 2 keep it right side, what is left in the middle is the 1's. Keep track of 1's the tricky part and have a index at start of 1's. I think it is possible, I have a tested code, I will post, but you can try once. Thanks, Sathaiah Dontula On Mon, Aug 23, 2010 at 12:10 PM, Manjunath Manohar < manjunath.n...@gmail.com> wrote: > is it possible to do without any extra space... > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Sorting algorithm
Who said count sort does not uses extra space??? As faras I know, it does need extra space to need thr frequency of each and every element within a given range.. Regards, Varun Bhatia On Mon, Aug 23, 2010 at 4:20 PM, Tanveer Asif wrote: > Count sort.. > > > -- > *From:* Subhranil Banerjee > *To:* algogeeks@googlegroups.com > *Sent:* Mon, August 23, 2010 3:36:12 AM > *Subject:* [algogeeks] Sorting algorithm > > Can anyone suggest a sorting algorithm that sorts in linear time without > using extra space. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST Problem
Perform inorder traversal and store in an array. low = 0, high = size-1 while(low<=high) { if ( a[low] + a[high] < sum) low++; else if (a[low] + a[high] > sum) high--; else return a[high] and [low] } On Mon, Aug 23, 2010 at 9:29 AM, R.ARAVINDH wrote: > @giri: > > can u post d correct answer?? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: To sort an array of 0,1,2
Refer Dutch National Flag Algorithm On Mon, Aug 23, 2010 at 12:10 PM, Manjunath Manohar < manjunath.n...@gmail.com> wrote: > is it possible to do without any extra space... > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] linked list as tree
Hi, Could anyone help me representing linked list in the form a binary tree ? Thanks !! -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: To sort an array of 0,1,2
I think the first 3 methods of the total 4 specified at http://www.rawkam.com/?p=168 will be applicable for sorting arrays with 0,1 &2 On Mon, Aug 23, 2010 at 11:07 AM, Jameel Mohamed wrote: > Use counting sort. time complexity is O(n) > > On Aug 22, 1:11 pm, AlgoBoy wrote: > > An algorithm to sort an array of 0's,1's,2's in a single pass... > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: To sort an array of 0,1,2
yes we can a possible solution what i can think is treat 1&2 (same entity ) and 0 as other so in first pass we will short array which will have (all zeros first , then 1&2 in some random order ) take index number of zero then in second pass short for 1 & 2 still O(n) but takes 2 pass On Mon, Aug 23, 2010 at 12:10 PM, Manjunath Manohar < manjunath.n...@gmail.com> wrote: > is it possible to do without any extra space... > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Kumar Vishal StAy HunGrY , StAy fOOlisH Contact No:- 09560193839 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] 5 pirate problem
Five pirates (of different ages) have 100 gold coins to divide amongst themselves. They decide on the following approach to determine how much each pirate receives: The eldest pirate proposes an allocation. All pirates (including the eldest) then vote on the proposal. If the majority accept the proposal then the coins are divided in the way suggested. If not, then the eldest pirate is executed and the new eldest amongst the remaining pirates proposes a new allocation. If the votes are tied then this is enough for the proposal to be accepted. Assuming that the pirates are motivated primarily by survival, then to a lesser extent by greed and finally to the least extent by sadism (i.e. they'd prefer to receive a gold coin and see someone get executed than just receive one coin earlier, but would prefer one coin to none and an execution; and obviously would prefer 0 coins and surviving to 100 coins and being executed), and act in a logical way, what is the maximum number of coins the eldest pirate can get? please provide a source code thanks in advance -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sorting algorithm
Time is measured in O(n^2) where n is the size of the string. Quicksort can do in O(n * log(n)) but it uses extra spaces on the stack, as most sorting method using recursion. On Aug 23, 12:36 pm, Subhranil Banerjee wrote: > Can anyone suggest a sorting algorithm that sorts in linear time without > using extra space. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Sorting algorithm
Count sort.. From: Subhranil Banerjee To: algogeeks@googlegroups.com Sent: Mon, August 23, 2010 3:36:12 AM Subject: [algogeeks] Sorting algorithm Can anyone suggest a sorting algorithm that sorts in linear time without using extra space. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Sorting algorithm
Can anyone suggest a sorting algorithm that sorts in linear time without using extra space. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Longest Palindromic Substring
I don't think so, I've have wriiten a kart-trie: http://sourceforge.net/projects/kart-trie which is basically a patricia-tree or radix-tree. Such a tree has maximum 2 leafs at each branch whilst a suffix-tree can has more then 2 leafs at each branch (BTW. can you explain to me what does edge means when talking about trees?). This is my understanding of a suffix-tree so far. I'm awaiting your anwser! 2010/8/21 Chonku > You use a trie when you want to model a number of strings. Suffix Tree is > used only when you have one string in your model. Suffix Tree is a type of > trie, but the difference lies in the intent. > > > On Sat, Aug 21, 2010 at 7:22 PM, Chi wrote: > >> Isn't that by definition a compressed trie, i.e patricia-tree, crit- >> bit tree (suffix-tree)? Or what is the difference? >> >> On Aug 20, 5:17 pm, Nikhil Jindal wrote: >> > @chonku >> > As i understand, a trie is used when we have a lot of strings (such as a >> > dictionary). >> > Here we just have a single string. The resultant trie will be: >> > >> > a >> > \ >> > b >> >\ >> > c >> > \ >> > l >> >\ >> > e >> > \ >> > v >> >\ >> > e >> > \ >> > l >> >\ >> > a >> > \ >> > b >> >\ >> > c >> > >> > We get a similar trie for the reverse string. >> > >> > So why are you using a trie here? I cant see any advantage of it here. >> > >> > >> > >> > >> > >> > On Fri, Aug 20, 2010 at 8:36 AM, Chonku wrote: >> > > Can we use a trie here. >> > > Make first pass from left to right and construct the trie. >> > > Make second pass from right to left and look for the trie branch with >> > > maximum nodes that match the characters. >> > >> > > On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal < >> fundoon...@yahoo.co.in>wrote: >> > >> > >> Hi All, >> > >> > >> Givan a string, you have to find the longest palindromic substring. >> > >> For ex: Longest Palindromic substring for abclevelabc is level. >> > >> > >> What is the most optimised solution possible? >> > >> > >> Please access the attached hyperlink for an important electronic >> communications disclaimer: >> http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php >> > >> > >> -- >> > >> > >> You received this message because you are subscribed to the Google >> Groups "Algorithm Geeks" group. >> > >> > >> To post to this group, send email toalgoge...@googlegroups.com. >> > >> > >> To unsubscribe from this group, send email >> toalgogeeks+unsubscr...@googlegroups.com >> >> >. >> > >> > >> For more options, visit this group athttp:// >> groups.google.com/group/algogeeks?hl=en. >> > >> > > -- >> > > You received this message because you are subscribed to the Google >> Groups >> > > "Algorithm Geeks" group.> To post to this group, send email >> toalgoge...@googlegroups.com. >> > > To unsubscribe from this group, send email to> >> algogeeks+unsubscr...@googlegroups.com >> >> > > . >> > > For more options, visit this group at >> > >http://groups.google.com/group/algogeeks?hl=en. >> > >> > Please access the attached hyperlink for an important electronic >> communications disclaimer: >> http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- ...::: Chi Hoang :::... Freelancer/PHP/TYPO3/MySQL Tel: +49(0)221-9460023 Url1: http://www.chihoang.de Url2: http://nano-math.users.sourceforge.net e-Mail: info at chihoang.de Skype: tetramatrix -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Permutation of Array.
now its clear.. 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.