[algogeeks] Re: coloring (Marking)
Find the minimum spanning tree. Find the nodes with indegree of 1 and mark the node which connects to that node with indgree 1. On Wed, Oct 7, 2009 at 11:08 PM, Ramaswamy R ramaswam...@gmail.com wrote: We have to find the minimum cardinality out of all possible bi-partite sets of the graph. (provided the graph is 2 colourable.) Brute force method would be to choose N nodes from V and check for its connectivity with the rest. First we'd have vC1 sets, then vC2 and so on. Am unaware of a better algorithm. On Wed, Oct 7, 2009 at 1:07 AM, ankur aggarwal ankur.mast@gmail.comwrote: Given a graph.. Find the minimum number of coloring (Marking) required to node such that every node in the final graph is connected by at least one of the colored(marked) node. ex: AB AC BD BE CF sol: 2 nodes to be colored. i.e. Colouring C and B would suffice.. -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: coloring (Marking)
LOL search for dominance in graph. 2009/10/7 ankur aggarwal ankur.mast@gmail.com Given a graph.. Find the minimum number of coloring (Marking) required to node such that every node in the final graph is connected by at least one of the colored(marked) node. ex: AB AC BD BE CF sol: 2 nodes to be colored. i.e. Colouring C and B would suffice.. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] sum of subsequence.
2. Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. i) 3 2 7 10 should return 13 (sum of 3 and 10) ii) 3 2 5 10 7 should return 15 (sum of 3, 5 and 7) --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Y shaped linklist
How to find the intersection point in linked list with the following constraints 1) one traversal for each of the lists 2) should not find the LENGTH of the lists 3) can USE recursion It goes like 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 algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] infinite memory
How will you implement infinite memory(infinite strings) in finite space Propose some method... --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] search your friend
You are standing at a crossing from where there emerge four roads extending to infinity. Your friend is somewhere on one of the four roads. You do not know on which road he is and how far he is from you. You have to walk to your friend and the total distance traveled by you must be at most a constant times the actual distance of your friend from you. In terminology of algorithms, you should traverse O(d) distance, where d is the distance of your friend from you. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Y shaped linklist
hash one list and wen u traverse other check if prest in hash On Fri, Oct 9, 2009 at 10:02 AM, ankur aggarwal ankur.mast@gmail.comwrote: How to find the intersection point in linked list with the following constraints 1) one traversal for each of the lists 2) should not find the LENGTH of the lists 3) can USE recursion It goes like 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 algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: sum of subsequence.
This is a simple dp problem .
define for each i following 2 quantities :
best1[i] : best sum in similar constraint of first i elements only when last
( ith ) term is always included
best2[i] : best sum in similar constraint of the first i elements only when
last (ith ) term is NOT included
so we can define best1 and best2 in terms of smaller bests like this :
best1[i] : max{ (best2[i-1]+a[i]) , a[i] }
best2[i]: max{ (best1[i-1] + a[i] ) , (best2[i-1]+a[i] ) , a[i] }
best1[0]=a[0] ans best2[0]=0;
finally we are concerned in :
max { best1[last] , best2[last] }
so we can find the answer in O(n)
On Fri, Oct 9, 2009 at 9:26 AM, ankur aggarwal ankur.mast@gmail.comwrote:
2. Given an array all of whose elements are positive numbers, find the
maximum sum of a subsequence with the constraint that no 2 numbers in the
sequence should be adjacent in the array.
i) 3 2 7 10 should return 13 (sum of 3 and 10)
ii) 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)
--
nikhil-
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: sum of subsequence.
#includeiostream
using namespace std;
int maxsum(int a[], int n)
{
int prevmaxsum=0;
int currmaxsum=a[0];
int last=0,temp=0;
for(int i=1;in;i++)
{
if(last!=(i-1))
{
prevmaxsum=currmaxsum;
currmaxsum=a[i]+prevmaxsum;
last=i;
coutprevmaxsum\t\t\tcurrmaxsum\t\t\tlastendl;
continue;
}
if((a[i]+prevmaxsum)currmaxsum)
{
temp=a[i]+prevmaxsum;
prevmaxsum=currmaxsum;
currmaxsum=temp;
last=i;
coutprevmaxsum\t\t\tcurrmaxsum\t\t\tlastendl;
}
}
return currmaxsum;
}
int main()
{
int arr[6]={3, 2 ,5,7 ,10};
int num=5;
int sum=maxsum(arr,6);
coutsum;
getchar();
return 0;
}
On Fri, Oct 9, 2009 at 9:26 AM, ankur aggarwal ankur.mast@gmail.comwrote:
2. Given an array all of whose elements are positive numbers, find the
maximum sum of a subsequence with the constraint that no 2 numbers in the
sequence should be adjacent in the array.
i) 3 2 7 10 should return 13 (sum of 3 and 10)
ii) 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: sum of subsequence.
On Oct 9, 8:56 am, ankur aggarwal ankur.mast@gmail.com wrote:
2. Given an array all of whose elements are positive numbers, find the
maximum sum of a subsequence with the constraint that no 2 numbers in the
sequence should be adjacent in the array.
i) 3 2 7 10 should return 13 (sum of 3 and 10)
ii) 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)
Quite Simple:
void FindMaxSum(int buf[], size_t cnt)
{
int incl = 0; // max sequence including the previous item
int excl = 0; // max sequence excluding the previous item
int excl_new=0;
for (size_t i = 0; i cnt; i++)
{
// current max excluding i
if (incl excl) excl_new = incl;
else
excl_new = excl;
// current max including i
incl = excl + buf[i];
excl = excl_new;
}
cout \nmax sum = ((incl excl)? incl : excl) endl;
}
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: Y shaped linklist
@sharad wat about space ?? 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 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 -~--~~~~--~~--~--~---
[algogeeks] Re: coloring (Marking)
it is NP hard problem i suppose.. On Fri, Oct 9, 2009 at 4:20 PM, Miroslav Balaz gpsla...@googlemail.comwrote: LOL search for dominance in graph. 2009/10/7 ankur aggarwal ankur.mast@gmail.com Given a graph.. Find the minimum number of coloring (Marking) required to node such that every node in the final graph is connected by at least one of the colored(marked) node. ex: AB AC BD BE CF sol: 2 nodes to be colored. i.e. Colouring C and B would suffice.. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Y shaped linklist
space comp O(n) time o(2n) both in terms of worst case On Fri, Oct 9, 2009 at 8:46 PM, ankur aggarwal ankur.mast@gmail.comwrote: @sharad wat about space ?? 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 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 -~--~~~~--~~--~--~---
[algogeeks] Re: search your friend
Wouldn't it be better to replace step 5 with Travel 2^(n+1) distance on the fourth road. If you find your friend DONE else return back to the crossing ? After you have exhausted the first three roads to a distance 2^n, there is no point to going only 2^n on the fourth road and then returning to the crossing so that you go 2^(n+1) on the first road. You can save 2^(n+1) by continuing down the fourth road for an additional 2^n before turning around. Dave On Oct 9, 9:56 am, anilkumarmyla anilkumarm...@gmail.com wrote: This is a simple extension of finding a friend on a single road without knowing his position. 1) n=0 2) Travel 2^n distance on the first road. If you find your friend DONE else return back to the crossing 3) Travel 2^n distance on the second road. If you find your friend DONE else return back to the crossing 4) Travel 2^n distance on the third road. If you find your friend DONE else return back to the crossing 5) Travel 2^n distance on the fourth road. If you find your friend DONE else return back to the crossing 6) n = n+1 GOTO STEP 2 Lets analyze the algo Assume d can be written as 2^a for some a ( can be extended to cases when d is not the form of 2^a) Assume the worst case of your friend being in the fourth road. Then the total distance travelled by you till you find your friend is = 4 * 2 * ( 2^0 + 2^1 + 2^2 + ... + 2^a) // The factor of 2 at the beginning is for your returning back = 8 * (2^a+1 - 1) = 8 * (2d-1) which is O(d) --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: search your friend
Anyway the solution is O(d) [:)] which is asked to be proved. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Y shaped linklist
Here is one solution http://geeksforgeeks.org/?p=2405 On Fri, Oct 9, 2009 at 9:00 AM, sharad kumar aryansmit3...@gmail.comwrote: space comp O(n) time o(2n) both in terms of worst case On Fri, Oct 9, 2009 at 8:46 PM, ankur aggarwal ankur.mast@gmail.comwrote: @sharad wat about space ?? 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 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 -~--~~~~--~~--~--~---
[algogeeks] Re: search your friend
yes anil your approach is rite.. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] balls and lines
Given 13 balls, how would you arrange them in 9 lines, such that there are 4 balls in each line? You can assume that the lines are arranged in 2-D space and that a ball cannot be placed on top of another ball. Bonus: if you find that too easy, and have loads of time to kill, then how about arranging 22 balls in 21 lines of 4? --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] n balls and k different colors 1=k=n
u have to color n similar balls with k diff. colors , such that every color must be used atleast once find the no. of ways --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: n balls and k different colors 1=k=n
example: n=10,k=10 ans:1 n=30,k=7 ans: 475020 On Oct 10, 9:51 am, vicky mehta...@gmail.com wrote: u have to color n similar balls with k diff. colors , such that every color must be used atleast once find the no. of ways --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: n balls and k different colors 1=k=n
Sterling numbers of second kind. On Sat, Oct 10, 2009 at 10:41 AM, vicky mehta...@gmail.com wrote: example: n=10,k=10 ans:1 n=30,k=7 ans: 475020 On Oct 10, 9:51 am, vicky mehta...@gmail.com wrote: u have to color n similar balls with k diff. colors , such that every color must be used atleast once find the no. of ways --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
