Re: [algogeeks] binary search tree over btree
In BST the height can be made as bad as u can but in case of btree the height can not be more than log n base 2 because for each internal node it is necessary to have at least 2 child and here all the leaf nodes must be at the same label. On Sun, Apr 1, 2012 at 8:34 PM, arun kumar kumar0...@gmail.com wrote: hi i just like to know when you will go for binary search tree over btree. advantage and disadvantage, application of both of them. thank you in advance Regards, Arun kumar -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Sanjiv Yadav MobNo.- 8050142693 Email Id- sanjiv2009...@gmail.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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Grid Points in Irregular polygon
Suppose you are given some convex polygon . Now suppose you want to divide the polygon area into a number of grids . And I want to find the points after we have divided the polygon . For simplicity u can consider convex polygon , don't take into account concave or self intersecting polygon . For example :- This is a Grid :- The points are the one where the Vertical and horizontal lines cross each other . | | | | | | -|--|-|--|-|-|-- | | | | | | -|--|-|--|-|-|-- | | | | | | -|--|-|--|-|-|-- | | | | | | -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: 答复: [algogeeks] Given an array A[1..n] of log n
in-place is O(1) auxiliary space. Could you please of something else? On Thursday, 5 April 2012 10:24:09 UTC+5:30, Rujin Cao wrote: =?utf-8?Q?_bit_integers,_sort_them_in-place_in_O(n)_time?= MIME-Version: 1.0 Content-Type: multipart/alternative; boundary==_Part_1591_7508851.1333541114758 --=_Part_1591_7508851.1333541114758 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable using counting sort with an extra O(log n) space to store the appearance count of each number in the range[0,log n]. And then iterate from begin to end to set each number with its count times. I'm not sure whether it is appropriate to call it in-place, but at least it doesn't use O(n) space. Sent from my Windows Phone =E5=8F=91=E4=BB=B6=E4=BA=BA: Doom =E5=8F=91=E9=80=81=E6=97=B6=E9=97=B4: 2012/4/4 20:05 =E6=94=B6=E4=BB=B6=E4=BA=BA: algogeeks@googlegroups.com =E4=B8=BB=E9=A2=98: Re: [algogeeks] Given an array A[1..n] of log n bit int= egers, sort them in-place in O(n) time how are you going to do it in-place? On Wednesday, 4 April 2012 13:24:01 UTC+5:30, Siddhartha wrote: if the length of the binary representation of elements is logn, then the= =20 elements themselves are of size less than 2^log(n)=3Dn. as all the elements are less than n, use counting sort!!! --=20 You received this message because you are subscribed to the Google Groups = Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/al= gogeeks/-/glXPUeyoh8IJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@googleg= roups.com. For more options, visit this group at http://groups.google.com/group/algoge= eks?hl=3Den. --=_Part_1591_7508851.1333541114758 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: quoted-printable htmlheadmeta content=3Dtext/html; charset=3Dutf-8 http-equiv=3DCont= ent-Type/headbodydivdiv style=3Dfont-family: Calibri,sans-serif; = font-size: 11pt;using counting sort with an extra O(log n) space to store= the appearance count of each number in the range[0,log n].brAnd then ite= rate from begin to end to set each number with its count times.brI'm not = sure whether it is appropriate to call it in-place, but at least it doesn= 't use O(n) space.brbrSent from my Windows Phonebr/div/divhrsp= an style=3Dfont-family: Tahoma,sans-serif; font-size: 10pt; font-weight: b= old;=E5=8F=91=E4=BB=B6=E4=BA=BA: /spanspan style=3Dfont-family: Tahom= a,sans-serif; font-size: 10pt;Doom/spanbrspan style=3Dfont-family: = Tahoma,sans-serif; font-size: 10pt; font-weight: bold;=E5=8F=91=E9=80=81= =E6=97=B6=E9=97=B4: /spanspan style=3Dfont-family: Tahoma,sans-serif; f= ont-size: 10pt;2012/4/4 20:05/spanbrspan style=3Dfont-family: Tahom= a,sans-serif; font-size: 10pt; font-weight: bold;=E6=94=B6=E4=BB=B6=E4=BA= =BA: /spanspan style=3Dfont-family: Tahoma,sans-serif; font-size: 10pt;= algogeeks@googlegroups.com/spanbrspan style=3Dfont-family: Tahoma,s= ans-serif; font-size: 10pt; font-weight: bold;=E4=B8=BB=E9=A2=98: /span= span style=3Dfont-family: Tahoma,sans-serif; font-size: 10pt;Re: [algog= eeks] Given an array A[1..n] of log n bit integers, sort them in-place in O= (n) time/spanbrbr/body/htmlhow are you going to do it in-place?= brbrOn Wednesday, 4 April 2012 13:24:01 UTC+5:30, Siddhartha wrote:bl= ockquote class=3Dgmail_quote style=3Dmargin: 0;margin-left: 0.8ex;border= -left: 1px #ccc solid;padding-left: 1ex;if the length of the binary repre= sentation of elements is logn, then the elements themselves are of size les= s than 2^log(n)=3Dn.divas all the elements are less than n, use counting = sort!!!/div /blockquote p/p -- br / You received this message because you are subscribed to the Google Groups = Algorithm Geeks group.br / To view this discussion on the web visit a href=3D https://groups.google.c= om/d/msg/algogeeks/-/glXPUeyoh8IJ https://groups.google.com/d/msg/algogeek= s/-/glXPUeyoh8IJ/a.br /=20 To post to this group, send email to algogeeks@googlegroups.com.br / To unsubscribe from this group, send email to algogeeks+unsubscribe@googleg= roups.com.br / For more options, visit this group at http://groups.google.com/group/algoge= eks?hl=3Den.br / --=_Part_1591_7508851.1333541114758-- -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/LGcbPhxQFrsJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find the maximum boxes which can fit each other?
@Don: Any ideas which oppose the above proposed solution? On Saturday, 24 March 2012 21:52:49 UTC+5:30, Don wrote: Build a graph in which each box is a vertex and there is an edge from A to B if B can fit inside A. Then use the longest path algorithm to find the solution. Don On Mar 24, 1:55 am, Ratan success.rata...@gmail.com wrote: You are given a lot of cuboid boxes with different length, breadth and height. You need to find the maximum subset which can fit into each other. For example: If Box A has LBH as 7 8 9 If Box B has LBH as 5 6 8 If Box C has LBH as 5 8 7 If Box D has LBH as 4 4 4 then answer is A,B,D A box can fit into another only and only if all dimensions of that is less than the bigger box. Also Rotation of boxes is not possible... can ny1 suggest a good algo for this? -- -- Ratan | 3rd Year | Information Technology | NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/C1yQ1v_QAboJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: water-jug problem
@Don: Could you please explain ur tree approach with an example? Thanks Doom On Tuesday, 3 April 2012 02:52:17 UTC+5:30, Don wrote: I did that by building a tree in which each node stores the configuration, including number of steps to that point, amount of water in each bucket, and a pointer to the parent, sibling, and leftmost child. Start out with one node with stepCount set to zero and all the buckets empty. You want the solution with the least number of steps, so use a breadth-first search. For each node, create a list of children based on the following: 1. For each bucket which is not full, fill it 2. For each bucket which is not empty, empty it 3. For each pair of buckets A and B where A is not empty and B is not full, pour A into B When you find a bucket with the desired amount of water, you can trace back through the parent pointers to get the series of moves required to get there. If you just need the minimum number of steps, the problem is much easier. Just use a 99x99x99 table D[99][99][99]. If the bucket capacities are a,b,c, start with all table values set to a large value except D[a][0][0] = D[0][b][0] = D[0][0][c] = 1 Then iteratively start with all states with depth d and set all states which can be reached from that state by a single step to d+1 if their current depth is greater than d+1. You'll end up with a table of all states reachable with the set of buckets, and the minimum number of steps to reach each state. Don On Apr 1, 12:57 pm, bharat b bagana.bharatku...@gmail.com wrote: A common puzzle asked during interviews is how to measure 4 liters of water with just two uneven shaped buckets, one of 3 liter another of 5 liter, in minimum number of steps. To extend and generalize this, write a program to evaluate the minimum number of steps to measure “X” liters of water, with “Y” buckets each having a separate denomination. The assumptions and sample input/output as given below: *Assumptions:* * * 1. Each bucket used for measuring water should be unique in denomination and the number of buckets will be = 3 2. The target amount to be reached has to finally reside in a single bucket (at the end of the measuring activity). 3. The bucket capacities and target amount will be = 99 4. If there are multiple ways to measure the same amount, only one way, having the minimum number of steps, has to be shown in the output. If there are multiple minimum steps solutions present, displaying one solution should be enough. 5. The console input as well as the output should be in single line and in the format shown below. 6. You can assume (not mandatory) minimum 2 steps will be required. You can ignore the cases where solution can be achieved in single step. 7. You can assume that maximum 10 steps will be required to reach the target amount. If any solution requires more than 10 steps to reach the target amount, you can stop the calculation and ignore that test case. *Input Format:* The input will be of the following comma separated format – No. of buckets, capacity of bucket 1, capacity of bucket 2, …, Target amount desired. The following examples will provide more clarity *Sl. No.* *Input string* *Explanation* 1 2,3,5,4 Implies that there are 2 buckets of capacity 3 and 5 lts each and the target amount desired is 4 lts. 2 3,4,6,9,7 Implies that there are 3 buckets of capacity 4, 6 and 9 lts each and the target amount desired is 7 lts. . *Output Format:* Each step should be a 11 bytes field left aligned right padded with spaces along with the right boundary as “|”. Together “|” character the length should be 12 characters. The following examples will provide more clarity *Sl. No.* *Input string* *Expected Output String* 1 2,3,5,4 Fill 2 |Move 2 to 1|Empty 1|Move 2 to 1|Fill 2 |Move 2 to 1| 2 3,4,6,9,7 Fill 1 |Move 1 to 2|Fill 3 |Move 3 to 2| * * *Let’s explain 1**st** output sample in more detail*: As explained earlier, effectively the input 2,3,5,4 means there are 2 buckets of capacity 3 liter and 5 liter and using these two buckets we have to measure 4 liter (which is the target). The answer is: Fill 2 |Move 2 to 1|Empty 1|Move 2 to 1|Fill 2 |Move 2 to 1| Let’s explain the answer also for test case 1: *Step #* *Step Description* *Status of 3 liter bucket (Bucket 1)* *Status of 5 liter bucket (Bucket 2)* *Explanation* Step 1 Fill
[algogeeks] Re: Grid Points in Irregular polygon
If you just want to know the integer points which are inside the polygon, you can do this: Find the min and max y values for the segments making up the polygon. Call them minY and maxY. For y = minY to maxY Find points where polygon segments intersect y. Call them minX and maxX. For x = minX to maxX Output (x,y) Don On Apr 5, 3:08 am, SAMMM somnath.nit...@gmail.com wrote: Suppose you are given some convex polygon . Now suppose you want to divide the polygon area into a number of grids . And I want to find the points after we have divided the polygon . For simplicity u can consider convex polygon , don't take into account concave or self intersecting polygon . For example :- This is a Grid :- The points are the one where the Vertical and horizontal lines cross each other . | | | | | | -|--|-|--|-|-|-- | | | | | | -|--|-|--|-|-|-- | | | | | | -|--|-|--|-|-|-- | | | | | | -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Modified binary search
code needed… not ble to visualize what to do if there are too many spikes and valleys in the multiple times rotated array, is that possible?? On Sep 28, 2011, at 1:36 AM, Gene wrote: Indeed you must be given that all the array elements are unique or at least that there are no more than floor(n/2) repeats). Otherwise this is impossible. The simplest way to think about it is first to search for i such that a[i] a[i+1]. At that point you know there are two sorted ranges a[0]..a[i] and a[i+1] to a[n-1], so you can use regular binary search on each of these pieces. So how to find i? This is itself a binary search. At each stage, check whether a[0] a[mid] and a[mid] a[n-1]. The half that passes this test contains i. So throw away the other. On Sep 27, 10:01 am, Decipher ankurseth...@gmail.com wrote: A given sorted array is rotated unknown number of times , write a C/C++ code to find an element in the sorted array in O(log n) time . I know the solution to this problem is through binary search , but don't know the exact solution . Please 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 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
