[algogeeks] Partition of flow graph
Hello For the data flow graph G= (V,E),I have to determine a partition - in such a way that sub graphs created could be computed in parallel and the sub graphs are approximately of the same size (sqrt(|V|)) For example as in graph attached ( http://i55.tinypic.com/35lvu6x.png - the graph should be directed upwards) - B0,B1,B2 - describe partially the partition. Do you have idea for algorithm? 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 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] Partition of flow graph
Hello For the data flow graph G= (V,E),I have to determine a partition - in such a way that sub graphs created could be computed in parallel and the sub graphs are approximately of the same size (sqrt(|V|)) For example as in graph attached ( http://i55.tinypic.com/35lvu6x.png - the graph should be directed upwards) - B0,B1,B2 - describe partially the partition. Do you have idea for algorithm? 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 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] search a 2d sorted array in less than O(n)
Trivial algorithm : (Assuming it is in ascending order in both columns and rows) logarithmic time in max(n,m) Divide the 2-d table to 4 parts, the -right-bottom-most and the left-bottom-most are the smallest and largest values in the subtable. It should be clear that atleast two subtables can be rejected straightforward from just this info. Hence the complexity T(m,n) = 2 * T(m/4,n/4) + c Rohit Saraf Third Year Undergraduate Compter Science Engineering IIT Bombay -- 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: Partition of flow graph
http://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/ On Sep 28, 2:52 pm, yako...@gmail.com yako...@gmail.com wrote: Hello For the data flow graph G= (V,E),I have to determine a partition - in such a way that sub graphs created could be computed in parallel and the sub graphs are approximately of the same size (sqrt(|V|)) For example as in graph attached (http://i55.tinypic.com/35lvu6x.png- the graph should be directed upwards) - B0,B1,B2 - describe partially the partition. Do you have idea for algorithm? 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 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: arrays
#includestdio.h
#includestdlib.h
int main()
{
int a[20],i,n,max,t,j,k;
printf(Enter the no. of elements\n);
scanf(%d,n);
for(i=0;in;i++)
scanf(%d,a[i]);
for(i=0;in-1;i++)
{
j=n-1;
max=0;
k=i;
while(ij)
{
if(a[j]a[i]a[j]=max)
{
max=a[j];
k=j;
j--;
}
else
j--;
}
t=a[i];
a[i]=a[k];
a[k]=t;
}
for(i=0;in;i++)
printf(%d\t,a[i]);
return 0;
}
On Tue, Sep 28, 2010 at 3:43 AM, Chi c...@linuxdna.com wrote:
Move-To-The-Front.
On Sep 27, 11:58 pm, Anand anandut2...@gmail.com wrote:
Given an array of integers, for each index i, you have to swap the value
at
i with the first value smaller than A[ i ] that comes after index i
--
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.comalgogeeks%2bunsubscr...@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 in BT
Maximum Sized Binary Search Tree in a Binary Tree: http://www.rawkam.com/?p=822 On Mon, Sep 27, 2010 at 10:34 AM, Chonku cho...@gmail.com wrote: @Prodigy As per your example, 8 15 20 25 which is the is indeed the maximum binary search tree in this binary tree is only a solution to smaller problem used to solve a bigger problem. The solution to smaller problem can be translated directly to the solution of the bigger problem. On Mon, Sep 27, 2010 at 8:28 AM, prodigy 1abhishekshu...@gmail.comwrote: 15 /\ 8 25 /\ 20 22 On Sep 26, 10:45 am, Chonku cho...@gmail.com wrote: This can also be done if we do an inorder traversal of the binary tree and look for the longest continuous sequence of numbers in ascending order. Your idea will fail for above case. In Order = 8 15 20 25 22 longest continuous sequence of numbers in ascending order = 8 15 20 25 But that's not the answer (I hope you realize what correct output would be ) -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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: do this: two numbers with min diff
Hi Friends
This is an interesting problem and request you all to give a brief
intro to your code before putting the code. Or you may just mention
the under lying concept in the code. This will be of great help and
others will find it more ready to improve by adding there approach.
Coming back to the problem an O(n) solution can exist by following the
approach of building a min heap (or max heap) from an array of
elements. A mean heap from an array of elements can be built by
starting from middle element (all elements from mid +1 to end are them
selves single element min heaps) (references available in Cormen or
other books).
During constructing the mean heap always track the min difference
between any two elements in the so far constructed heap. At any
instant if you are handling root 'a' which has left child l and right
child r and aiming to build a min heap rooted at a, then the following
cases arise
1. a is less than both l and r. In this case no movement of a is
required. Now find |a-l| = x and |a-r| = y. 'a' cannot have a
difference z with any element under tree rooted at l such that z x
becuase l is the least element in the tree rooted at l. Similarly 'a'
cannot have a difference z' with any element under tree rooted at r
such that z' r. So least of x and y is the min diff between any
elements in the so far constructed min heap rooted at 'a'.
2. a is less than l but greater than r. In this case r will replace a
and a need to be pushed down the its right child. While pushing 'a'
down keep calculating the differences between 'a' and 'r' as long as
'a' is not pushed down to a node where it is the min element. While
you keep calculating also keep track of the min diff calculated so far
(say 'p'). Compare this 'p' with |a-l| and min diff between any two
elements for the tree rooted at l. Least of these three will be the
min diff between any 2 elements for the min head rooted at 'r' (which
replaced 'a''s position.
3. Both 'l' and 'r' are less than 'a'. Take the lesser or 'l' and 'r'
and replace that with 'a' and push 'a' down as in case 2 (normal min
heap construction algo).
Thus we can continue building the min heap and at the end have the min
diff between any 2 elements in the array. Just we keep tracking the
min diff, we can also keep note of the 2 elements than are
contributing to this min diff my adding some more steps.
This idea is all based on the fact that min heap can be constructed
from an array in linear time.
Thanks,
Sourav
On Sep 27, 1:32 pm, rahul rahulr...@gmail.com wrote:
If their is no constrain on assumptions.
1.Sort the array.
2. check the dif between 2 elements.
{ 99,35,45,33,88,9098,112,33455,678,3}
sorted arrary : { } would be something.
now update the min_diff.
another example : { 7,8,1,3,5,4}
sorted arrary : { 1,3,4,5,7,8}
min diff is 1.
Please correct me if i missed something.
On Mon, Sep 27, 2010 at 1:13 PM, satish satish@gmail.com wrote:
step1construct heap using siftdown. // time complexity wil be O(n) and
space complexity O(1).
step2take mindifference=a[1].
step3for i=1 ,i=n/2 do
{ find the difference of (root,root-left),(root,root-right)and
(root-left,root-right).and maintain mindifference is the smallest
difference of among
three differences.
}
step4return mindifference.
plz correct me if im wrong
--
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.comalgogeeks%2bunsubscr...@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: ALgo help pls
In my opinion also, this is a Majority vote algorithm as mentioned by Navin and as coded by Dave. Only point I would add to @Dave's code is that it wont be possible to find if the majority element has 2n/3 occurance as majority element keeps changing during the run and as the majority algorithm tells you a number which has greater than n/2 occurrence. So all you need to do is another liner scan after the majority element is found to check if its count is 2n/3. @Narsimha Raju: your failure to find 2n/3 occurrence by adding a for loop is expected. Please reply if we are able to add a for loop into code above (given by @Dave) to find if majority element has 2n/3 occurance. Thanks, Sourav On Sep 22, 9:02 am, Navin Naidu navinmna...@gmail.com wrote: Use majority vote algorithm: http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html On Wed, Sep 22, 2010 at 9:12 AM, pre pre.la...@gmail.com wrote: Hi all, pls help me solve this problem.. Design an algorithm to find the majority element of an array.. majority element must be an element tht has the cardinality greater than 2n/3 where n is the number of elements in the array and the time complexity must be a linear time.. ie o(n).. hint : use mode or median to solve .. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, - NMN -- 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: power set
Power set : http://www.rawkam.com/?p=330 On Sun, Sep 19, 2010 at 2:45 AM, Gene gene.ress...@gmail.com wrote: The power set of a set with N elements has size O(2^N). You can't do anything with it in polynomial time. On Sep 18, 5:03 pm, bittu shashank7andr...@gmail.com wrote: can we solve power set in O(n) or O(nlogn)..is it posible... Regards Shashank -- 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.comalgogeeks%2bunsubscr...@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] finding largest and second largest elements
see a nice solution and related puzzle at http://www.rawkam.com/?p=1034 On Tue, Sep 28, 2010 at 6:31 AM, sharad kumar aryansmit3...@gmail.comwrote: hey isn't it suppposed to be tournament problem.. On Fri, Sep 24, 2010 at 12:06 AM, Divesh Dixit dixit.coolfrog.div...@gmail.com wrote: finding largest and second largest elements from a set of n elements by means of Minimum comparison of n+celling(log n) +2 -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- 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.comalgogeeks%2bunsubscr...@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: Amazon Interview
still there is some problem related to numbers encoding like.. 22333101 here how will u going to encode it??? On Tue, Sep 28, 2010 at 1:38 AM, ligerdave david.c...@gmail.com wrote: it's a compression problem. using hex instead of oct saves more space 00aaa0ss yyy = 50 2a 0 1s 3f 1\s ay On Sep 15, 8:21 am, bittu shashank7andr...@gmail.com wrote: A file is given with many 0s stored in continuous way , store it in another file such that when you store try saving the space by using minimum amount of space. When you want to create the original file , you should be able to do so with the new file created -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Umesh kewat -- 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] find out the mid point of a single linked list
Given a singly-linked, find out (just give the basic logic) the mid point of a single linked list in a single parse of the list. Assume the program would be loaded in read-only memory so no manipulation of the list is allowed. -- 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: do this: two numbers with min diff
@ sorurav
yes , the basic logic is required so that the code can be understood in
single Run..
i also request the same to all dear friends.
Regards..
On Tue, Sep 28, 2010 at 8:11 PM, sourav souravs...@gmail.com wrote:
Hi Friends
This is an interesting problem and request you all to give a brief
intro to your code before putting the code. Or you may just mention
the under lying concept in the code. This will be of great help and
others will find it more ready to improve by adding there approach.
Coming back to the problem an O(n) solution can exist by following the
approach of building a min heap (or max heap) from an array of
elements. A mean heap from an array of elements can be built by
starting from middle element (all elements from mid +1 to end are them
selves single element min heaps) (references available in Cormen or
other books).
During constructing the mean heap always track the min difference
between any two elements in the so far constructed heap. At any
instant if you are handling root 'a' which has left child l and right
child r and aiming to build a min heap rooted at a, then the following
cases arise
1. a is less than both l and r. In this case no movement of a is
required. Now find |a-l| = x and |a-r| = y. 'a' cannot have a
difference z with any element under tree rooted at l such that z x
becuase l is the least element in the tree rooted at l. Similarly 'a'
cannot have a difference z' with any element under tree rooted at r
such that z' r. So least of x and y is the min diff between any
elements in the so far constructed min heap rooted at 'a'.
2. a is less than l but greater than r. In this case r will replace a
and a need to be pushed down the its right child. While pushing 'a'
down keep calculating the differences between 'a' and 'r' as long as
'a' is not pushed down to a node where it is the min element. While
you keep calculating also keep track of the min diff calculated so far
(say 'p'). Compare this 'p' with |a-l| and min diff between any two
elements for the tree rooted at l. Least of these three will be the
min diff between any 2 elements for the min head rooted at 'r' (which
replaced 'a''s position.
3. Both 'l' and 'r' are less than 'a'. Take the lesser or 'l' and 'r'
and replace that with 'a' and push 'a' down as in case 2 (normal min
heap construction algo).
Thus we can continue building the min heap and at the end have the min
diff between any 2 elements in the array. Just we keep tracking the
min diff, we can also keep note of the 2 elements than are
contributing to this min diff my adding some more steps.
This idea is all based on the fact that min heap can be constructed
from an array in linear time.
Thanks,
Sourav
On Sep 27, 1:32 pm, rahul rahulr...@gmail.com wrote:
If their is no constrain on assumptions.
1.Sort the array.
2. check the dif between 2 elements.
{ 99,35,45,33,88,9098,112,33455,678,3}
sorted arrary : { } would be something.
now update the min_diff.
another example : { 7,8,1,3,5,4}
sorted arrary : { 1,3,4,5,7,8}
min diff is 1.
Please correct me if i missed something.
On Mon, Sep 27, 2010 at 1:13 PM, satish satish@gmail.com wrote:
step1construct heap using siftdown. // time complexity wil be O(n)
and
space complexity O(1).
step2take mindifference=a[1].
step3for i=1 ,i=n/2 do
{ find the difference of
(root,root-left),(root,root-right)and
(root-left,root-right).and maintain mindifference is the smallest
difference of among
three differences.
}
step4return mindifference.
plz correct me if im wrong
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Divesh*
(¨`·.·´¨) Always
`·.¸(¨`·.·´¨ ) Keep
(¨`·.·´¨)¸.·´Smiling!
`·.¸.·´ Life can give u 100's of reason 2cry,but u can give life 1000's
of reasons 2Smile
--
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] Algorithm to determine the largest number of envelopes that can be nested inside one another.
You are given an unlimited number of each of n different types of envelopes. The dimensions of envelope type i are xi × yi.(i is in sub script) In nesting envelopes inside one another, you can place envelope A inside envelope B if and only if the dimensions A are strictly smaller than the dimensions of B. Algorithm to determine the largest number of envelopes that can be nested inside one another. -- 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: Amazon Interview
that will be 12 23 34 1 0 1c1 what's the some related problem? only last char in the group represent the char, leading chars represent the number of the repeated char. space(or whatever you like it to be) is the separator of groups. when you see space, replace w/ '\t'. On Sep 28, 2:58 am, umesh kewat umesh1...@gmail.com wrote: still there is some problem related to numbers encoding like.. 22333101 here how will u going to encode it??? On Tue, Sep 28, 2010 at 1:38 AM, ligerdave david.c...@gmail.com wrote: it's a compression problem. using hex instead of oct saves more space 00aaa0ss yyy = 50 2a 0 1s 3f 1\s ay On Sep 15, 8:21 am, bittu shashank7andr...@gmail.com wrote: A file is given with many 0s stored in continuous way , store it in another file such that when you store try saving the space by using minimum amount of space. When you want to create the original file , you should be able to do so with the new file created -- 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.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Umesh kewat -- 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] Algorithm to determine the largest number of envelopes that can be nested inside one another.
A possible solution i can think is create a directed graph where each vertex is a envelope and edges are from a bigger envelope to smaller envelope ( one which can fit in bigger envelope ) . Now the problem is reduce to finding longest path in the graph . Regards Rahul -- 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: Finding hash collisions without storage
Can u elaborate more? On Sep 28, 5:41 am, saurabh singh saurabh.n...@gmail.com wrote: u can use log(n)+1 space to do that by using bit string On Mon, Sep 27, 2010 at 10:37 PM, AdrianW atw...@gmail.com wrote: Suppose you have N strings that can be generated on-the-fly, and you wanted to discover if a hash function generates any collisions. Is there a way to do this without O(N) storage? -- 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.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, Saurabh -- 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: do this: two numbers with min diff
May be this helps
http://ds-gyan.blogspot.com/2009/12/two-numbers-with-minimum-difference.html
On Sep 28, 10:28 am, coolfrog$ dixit.coolfrog.div...@gmail.com
wrote:
@ sorurav
yes , the basic logic is required so that the code can be understood in
single Run..
i also request the same to all dear friends.
Regards..
On Tue, Sep 28, 2010 at 8:11 PM, sourav souravs...@gmail.com wrote:
Hi Friends
This is an interesting problem and request you all to give a brief
intro to your code before putting the code. Or you may just mention
the under lying concept in the code. This will be of great help and
others will find it more ready to improve by adding there approach.
Coming back to the problem an O(n) solution can exist by following the
approach of building a min heap (or max heap) from an array of
elements. A mean heap from an array of elements can be built by
starting from middle element (all elements from mid +1 to end are them
selves single element min heaps) (references available in Cormen or
other books).
During constructing the mean heap always track the min difference
between any two elements in the so far constructed heap. At any
instant if you are handling root 'a' which has left child l and right
child r and aiming to build a min heap rooted at a, then the following
cases arise
1. a is less than both l and r. In this case no movement of a is
required. Now find |a-l| = x and |a-r| = y. 'a' cannot have a
difference z with any element under tree rooted at l such that z x
becuase l is the least element in the tree rooted at l. Similarly 'a'
cannot have a difference z' with any element under tree rooted at r
such that z' r. So least of x and y is the min diff between any
elements in the so far constructed min heap rooted at 'a'.
2. a is less than l but greater than r. In this case r will replace a
and a need to be pushed down the its right child. While pushing 'a'
down keep calculating the differences between 'a' and 'r' as long as
'a' is not pushed down to a node where it is the min element. While
you keep calculating also keep track of the min diff calculated so far
(say 'p'). Compare this 'p' with |a-l| and min diff between any two
elements for the tree rooted at l. Least of these three will be the
min diff between any 2 elements for the min head rooted at 'r' (which
replaced 'a''s position.
3. Both 'l' and 'r' are less than 'a'. Take the lesser or 'l' and 'r'
and replace that with 'a' and push 'a' down as in case 2 (normal min
heap construction algo).
Thus we can continue building the min heap and at the end have the min
diff between any 2 elements in the array. Just we keep tracking the
min diff, we can also keep note of the 2 elements than are
contributing to this min diff my adding some more steps.
This idea is all based on the fact that min heap can be constructed
from an array in linear time.
Thanks,
Sourav
On Sep 27, 1:32 pm, rahul rahulr...@gmail.com wrote:
If their is no constrain on assumptions.
1.Sort the array.
2. check the dif between 2 elements.
{ 99,35,45,33,88,9098,112,33455,678,3}
sorted arrary : { } would be something.
now update the min_diff.
another example : { 7,8,1,3,5,4}
sorted arrary : { 1,3,4,5,7,8}
min diff is 1.
Please correct me if i missed something.
On Mon, Sep 27, 2010 at 1:13 PM, satish satish@gmail.com wrote:
step1construct heap using siftdown. // time complexity wil be O(n)
and
space complexity O(1).
step2take mindifference=a[1].
step3for i=1 ,i=n/2 do
{ find the difference of
(root,root-left),(root,root-right)and
(root-left,root-right).and maintain mindifference is the smallest
difference of among
three differences.
}
step4return mindifference.
plz correct me if im wrong
--
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.comalgogeeks%2bunsubscr...@googlegroups
.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googleg
roups.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.comalgogeeks%2bunsubscr...@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Divesh*
(¨`·.·´¨) Always
`·.¸(¨`·.·´¨ ) Keep
(¨`·.·´¨)¸.·´Smiling!
`·.¸.·´ Life can give u 100's of reason 2cry,but u can give life
[algogeeks] please explain the pointer math on page 22 of this pdf
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-087-practical-programming-in-c-january-iap-2010/lecture-notes/MIT6_087IAP10_lec05.pdf Thanking In Advance -- Rahul K Rai And The Geek Shall Inherit The Earth -- 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] Algorithm to determine the largest number of envelopes that can be nested inside one another.
i think it is similar to finding max in a list O(n) or sorting algorithm O(n log n) -- Prashant Kulkarni On Tue, Sep 28, 2010 at 11:33 PM, Rahul Singal rahulsinga...@gmail.comwrote: A possible solution i can think is create a directed graph where each vertex is a envelope and edges are from a bigger envelope to smaller envelope ( one which can fit in bigger envelope ) . Now the problem is reduce to finding longest path in the graph . Regards Rahul -- 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.comalgogeeks%2bunsubscr...@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] find out the mid point of a single linked list
maintain two pointer 1) slow pointer : it will point to next node for each iteration (ie node=node-next) 2) fast pointer : it will point to two ahead node for each iteration ( ie node=node-next-next) when fast pointer reaches the end of linked list (NULL), slow pionter will point to middle of the linked list -- Prashant Kulkarni On Tue, Sep 28, 2010 at 10:54 PM, Divesh Dixit dixit.coolfrog.div...@gmail.com wrote: Given a singly-linked, find out (just give the basic logic) the mid point of a single linked list in a single parse of the list. Assume the program would be loaded in read-only memory so no manipulation of the list is allowed. -- 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.comalgogeeks%2bunsubscr...@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: please explain the pointer math on page 22 of this pdf
Hi Rahul, All it is saying is that you can do simple arithmetic on pointers directly which modified the address it is pointing to. Suppose you have an array of int type (int arr[10];)then you can access elements of the array in following ways: 1. arr[1], arr[4] etc. 2. arr+1, arr+4 etc. as arr is also address of first element and being int type will increment in int size. 3. int *p = arr; or int *p = arr[0] // here we created a pointer to integer and point it to first element of array p+1 will point to second element of arr and *(p+1) will be the content of arr[1] on the other hand if you declare your pointer as any other type than the array type itself, you can access each bytes within the element too so for above example arr which is of type int char *p = arr; or char *p = arr[0]; // this will create a pointer to character (1 byte) while arr is an integer array so now, p+1 will point to second byte of arr[0] let's say integer is 4 bytes then to go to start of each element of array using such p will be done as: p - points to first element's first byte (depends on big-endian/little- endianness of machine) p+4 - points to second element's first byte p+8 - points to third element's first byte and so on. Hope this helps. Kapil. On Sep 28, 11:04 pm, rahul rai raikra...@gmail.com wrote: http://ocw.mit.edu/courses/electrical-engineering-and-computer-scienc... Thanking In Advance -- Rahul K Rai And The Geek Shall Inherit The Earth -- 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.
