Re: [algogeeks] c output ??
@amol this is not the behaviour of printf, its totally about the typecasting -- 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/-/GPVlt15S3V0J. 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] Re: Maximal possible subsets Algorithm
@Piyush:.. nope is not correct ...
this is right
0 1 2 3
0 1 0 0 0
1 1 0 1 0
2 1 0 1 0
3 1 0 1 0
4 1 0 1 0
use this code to precompute..
A[i,j] = A[i-1, j];
if ( A[i, j] == 0 and j - W[i] =0)
A[i, j] = A[i -1, j - W[i]];
On Tue, Jan 10, 2012 at 1:05 PM, Piyush Grover piyush4u.iit...@gmail.comwrote:
How to create the lookup table?
say if I have W = {2, 4, 6, 8} and Wmax = 3
0 1 2 3
0 1 0 0 0
1 1 1 1 0
2 1 1 1 1
3 1 1 1 1
4 1 1 1 1
Is this correct???
On Mon, Jan 9, 2012 at 2:55 PM, Lucifer sourabhd2...@gmail.com wrote:
@All
The same algo will work for both +ve and -ve nos.. no need for
modification..
For ex-
Say the sum is 4 and the set is { 1, 2, 3, -2 }
Now if u include -2 as part of ur solution then for the rest 3
elements the sum would be 4-(-2) = 6, which is correct...
On Jan 9, 2:20 pm, Siddhartha thefourrup...@gmail.com wrote:
yup...that was what i was thinking... i guess for negative nos, we can
define Wmax= sum of modulus of weights,and then the same algo works...
--
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.
--
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] MS Q
@Ramakant : for which test case your code would fail?? On Tue, Jan 10, 2012 at 1:04 PM, Ramakant Sharma ramakant...@gmail.comwrote: @atul: no..my approach was wrongwe have to check recursively...as sravan said -- 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.
Re: [algogeeks] c output ??
It's painful to see printf being accused for the (un) expected output..The declaration of printf means that any data type can be passed to it as argument.Inherently what printf does is print the bytes in meaningful form according to the first argument which is a string.So its impossible for printf to typecast arguments once they are passed they appear the same way to printf...*A stream of bits from which it has to extract the valid info.*Its the responsibility of the programmer to pass the right data type with right format specifier...Just to complete my answer http://www.ideone.com/CNkCo . Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Tue, Jan 10, 2012 at 2:29 PM, Rahul Verma rahulverma@gmail.comwrote: @amol this is not the behaviour of printf, its totally about the typecasting -- 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/-/GPVlt15S3V0J. 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.
Re: [algogeeks] MS Q
@Ramakan: for j=0 to col arr[0][j]=0; for i=0 to rows arr[i][0]=0; assuming that given matrix is surrounded by 0 i.e indexs (i,j) for arr[][] will start from i=1 = row and j=1 = col. i guess your approach will work. -- 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] Re: finding subarray
sry for last post:
the code bye sravan reddy would not work for negative nos.
but slight modification in if conditions make it work for negative nos too.
by the way nice algo suggested
#includestdio.h
int main(int argc, char **argv){
int a[] = {-2,-3,-4,-19,10};
//int a[]={2,8,-6};
//int a[]={2,2,13,4,7,3,8,12,9,1,5};
int len = sizeof(a)/sizeof(a[0]);
for(int i=0;ilen;i++){
int left=0,right=0;
int p1 = i;
int p2 = i+1;
left = left + a[p1];
right = right + a[p2];
while(p1=0 p2 len){
if( left == right){
printf(Possible for \tLeft : %d, Right: %d, Center: %d
\n,p1,p2,i);
break;
//return 0;
}
else if(((left right p2 len-1
a[p2+1]0))|| ((a[p2+1]0))){
p2++;
right = right+ a[p2];
}
else if(((left right p1 0) a[p1-1]0)||
((a[p1-1]0))){
p1--;
left = left + a[p1];
}
else{
printf(Not Possible for \t Left : %d, Right: %d, Center:
%d \n,p1,p2,i);
break;
//return 0;
}
}
}
On Tue, Jan 10, 2012 at 10:42 AM, priyanka jaggi
priyankajag...@gmail.comwrote:
@ankur : in this question, the elements of the array are continuous
i think the solution of shravan reddy is correct and works for negative
nos too.
--
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] MS Q
0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 -- 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] Re: finding subarray
@priyanka..
I don't think it will work...
Say for ex- 1,-1,3,5,1,-3 ... the answer should be (3),(5,1,-3)..
Will the above fix give the correct answer for the given input ??
Also, i see a couple of flaws in the checks...
Say, Left right and p2 = len -1, then it will actually take A[len]
into consideration which is wrong..
Secondly, if (left right p2 len -1) passes then irrespective of
whether A[p2+1] is smaller or greater than 0, it will be added to
'right'...
-
The left/right logic will seamlessly work for positive nos... For it
to work for negative nos., the considered inputs need to sorted...
Basically what we are trying to do here is generate cumulative sums on
the fly starting at index 'i' towards left and right and see if there
is a matching value... if the generated cumulative values on either
side are not sorted then its difficult to ensure that we will be able
to catch a 'matched' value if we incremently work on 'left' and
'right' (pointers)..
---
If the left/right logic is correct, then the following problem should
be solvable in O(n) without extra space...
Say, given 2 arrays A[n] and B[n] (not sorted and contains both -ive
and +ive integers)...
1) Find the first pair (i,j) such that:
sum( A[0] .. till A[i]) = sum(B[0] ... B[i])
/*
this is exactly what we are trying to solve using left/right
logic, here left = A[0],right= B[0], p1 = 0, p2 =0, and we will
continue till p1 len and p2 len...
*/
2) A variation of the first part... find (i,j) such that (i+j) is
maximum...
Well looking at the above problem, i do see a nlogn solution, but not
sure if it can be solved in O(n)...
--
@All
Can the above problem be solved in O(n),, if yes, then we can do it in
O(n^2) using the previously presented algo.. otherwise the runtime
would be O(n^2 log n)...
Posting in a hurry. If i m wrong, plz do correct me...
--
On Jan 10, 1:27 pm, priyanka jaggi priyankajag...@gmail.com wrote:
sry for last post:
the code bye sravan reddy would not work for negative nos.
but slight modification in if conditions make it work for negative nos too.
by the way nice algo suggested
#includestdio.h
int main(int argc, char **argv){
int a[] = {-2,-3,-4,-19,10};
//int a[]={2,8,-6};
//int a[]={2,2,13,4,7,3,8,12,9,1,5};
int len = sizeof(a)/sizeof(a[0]);
for(int i=0;ilen;i++){
int left=0,right=0;
int p1 = i;
int p2 = i+1;
left = left + a[p1];
right = right + a[p2];
while(p1=0 p2 len){
if( left == right){
printf(Possible for \tLeft : %d, Right: %d, Center: %d
\n,p1,p2,i);
break;
//return 0;
}
else if(((left right p2 len-1
a[p2+1]0))|| ((a[p2+1]0))){
p2++;
right = right+ a[p2];
}
else if(((left right p1 0) a[p1-1]0)||
((a[p1-1]0))){
p1--;
left = left + a[p1];
}
else{
printf(Not Possible for \t Left : %d, Right: %d, Center:
%d \n,p1,p2,i);
break;
//return 0;
}
}
}
On Tue, Jan 10, 2012 at 10:42 AM, priyanka jaggi
priyankajag...@gmail.comwrote:
@ankur : in this question, the elements of the array are continuous
i think the solution of shravan reddy is correct and works for negative
nos too.
--
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] Re: finding subarray
@correction..
1) Find the first pair (i,j) such that:
/*
sum( A[0] .. till A[i]) = sum(B[0] ... B[j])
*/
On Jan 10, 6:13 pm, Lucifer sourabhd2...@gmail.com wrote:
@priyanka..
I don't think it will work...
Say for ex- 1,-1,3,5,1,-3 ... the answer should be (3),(5,1,-3)..
Will the above fix give the correct answer for the given input ??
Also, i see a couple of flaws in the checks...
Say, Left right and p2 = len -1, then it will actually take A[len]
into consideration which is wrong..
Secondly, if (left right p2 len -1) passes then irrespective of
whether A[p2+1] is smaller or greater than 0, it will be added to
'right'...
-
The left/right logic will seamlessly work for positive nos... For it
to work for negative nos., the considered inputs need to sorted...
Basically what we are trying to do here is generate cumulative sums on
the fly starting at index 'i' towards left and right and see if there
is a matching value... if the generated cumulative values on either
side are not sorted then its difficult to ensure that we will be able
to catch a 'matched' value if we incremently work on 'left' and
'right' (pointers)..
---
If the left/right logic is correct, then the following problem should
be solvable in O(n) without extra space...
Say, given 2 arrays A[n] and B[n] (not sorted and contains both -ive
and +ive integers)...
1) Find the first pair (i,j) such that:
sum( A[0] .. till A[i]) = sum(B[0] ... B[i])
/*
this is exactly what we are trying to solve using left/right
logic, here left = A[0],right= B[0], p1 = 0, p2 =0, and we will
continue till p1 len and p2 len...
*/
2) A variation of the first part... find (i,j) such that (i+j) is
maximum...
Well looking at the above problem, i do see a nlogn solution, but not
sure if it can be solved in O(n)...
--
@All
Can the above problem be solved in O(n),, if yes, then we can do it in
O(n^2) using the previously presented algo.. otherwise the runtime
would be O(n^2 log n)...
Posting in a hurry. If i m wrong, plz do correct me...
--
On Jan 10, 1:27 pm, priyanka jaggi priyankajag...@gmail.com wrote:
sry for last post:
the code bye sravan reddy would not work for negative nos.
but slight modification in if conditions make it work for negative nos too.
by the way nice algo suggested
#includestdio.h
int main(int argc, char **argv){
int a[] = {-2,-3,-4,-19,10};
//int a[]={2,8,-6};
//int a[]={2,2,13,4,7,3,8,12,9,1,5};
int len = sizeof(a)/sizeof(a[0]);
for(int i=0;ilen;i++){
int left=0,right=0;
int p1 = i;
int p2 = i+1;
left = left + a[p1];
right = right + a[p2];
while(p1=0 p2 len){
if( left == right){
printf(Possible for \tLeft : %d, Right: %d, Center: %d
\n,p1,p2,i);
break;
//return 0;
}
else if(((left right p2 len-1
a[p2+1]0))|| ((a[p2+1]0))){
p2++;
right = right+ a[p2];
}
else if(((left right p1 0) a[p1-1]0)||
((a[p1-1]0))){
p1--;
left = left + a[p1];
}
else{
printf(Not Possible for \t Left : %d, Right: %d, Center:
%d \n,p1,p2,i);
break;
//return 0;
}
}
}
On Tue, Jan 10, 2012 at 10:42 AM, priyanka jaggi
priyankajag...@gmail.comwrote:
@ankur : in this question, the elements of the array are continuous
i think the solution of shravan reddy is correct and works for negative
nos too.
--
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] MS Q
i liked the solution given by the reference i have provided. The thought process is similar to mazing problem given in horowitz sahani. nice question, however, how can this be an interview question? If you give this solution, the interviewer would understand that you knew the problem and hence would reject. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jan 10, 2012 at 4:06 PM, Ramakant Sharma ramakant...@gmail.comwrote: 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 -- 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.
[algogeeks] Re: SuperSum
@lucifier : Please tell how you reduce SuperSum ( k, n) into SuperSum(k,n) = SuperSum (k-1, n) * (n+k) / (k+1) -- 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/-/jWq_vujbiCkJ. 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] MS Q
@atul: 0 0 0 0 0 0 --0 1 0 0 1 0 count=2 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 --0 1 1 1 1 1 count=2 (will not change) but there is only one islandso it wouldnt work... am i right? -- 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] Re: extracting vector (digitization) from an ECG image
@SAMM i want to achieve the digitization as shown in the video http://www.youtube.com/watch?v=yCIeKc__LdM kindly have a look On Mon, Jan 9, 2012 at 12:40 AM, SAMM somnath.nit...@gmail.com wrote: 1 month back I wrote C++ code using Magick++ to zoom a image without distorting the Pixels . In that Code we can extact the Pixel attributes which are the Combination of Red , Blue and Green and Alpha attributes(Contributes to Picture Transparancy So , not present in Every Image ). But RBG combination is present in every image . Each attributes contribute to 1 byte (32 bits ) . Every 4bytes/3 bytes Constitute a single pixel depending alpha attribute is present or not in the pic . If u want to get Quantize the image then u have to read the Pixel's Property starting from (0,0) to (M,N) , where MxN is the dimension of the image . This Attibutes are representated in 2D array and is sufficient to serve ur purpose . And I this is Offcourse Supported for Java except for TIFF and JPEG 2000(plugin required separately) . There are many plugins also available for extracting this attributes . Some plug in enables you to read the Image and and and it will return you the starting address of the index (0,0) Corner left of the Image . And from there u can read the Bytes to get the attributes depending the picture support the Tranparency Property(alpha attribute). On 1/8/12, sravanreddy001 sravanreddy...@gmail.com wrote: @Deepak: Digitization of the image doesn't have a algorithmic approach, (unless you need to compress it) But, i see that you are asking for a way to convert the image (jpg) into a memory representation. I am not sure of matlab, but, using java (images API) you have to read the data into digital form (format needed for the neutal network) -- 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/-/OdrIp1J5tbsJ. 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. -- Somnath Singh -- 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. -- U.D.I.T Sent by Nokia OVI (c) -- 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] Re: SuperSum
@Lucifier : your reduced form is not generating right output... remove modulo and calculate for SuperSum(2,3) On Tue, Jan 10, 2012 at 6:12 PM, priyanka priyankajag...@gmail.com wrote: @lucifier : Please tell how you reduce SuperSum ( k, n) into SuperSum(k,n) = SuperSum (k-1, n) * (n+k) / (k+1) -- 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/-/jWq_vujbiCkJ. 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.
Re: [algogeeks] MS Q
@ Ramakant : yupwont work. On Tue, Jan 10, 2012 at 7:28 PM, Ramakant Sharma ramakant...@gmail.comwrote: @atul: 0 0 0 0 0 0 --0 1 0 0 1 0 count=2 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 --0 1 1 1 1 1 count=2 (will not change) but there is only one islandso it wouldnt work... am i right? -- 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.
[algogeeks] Re: SuperSum
@atul First of all, i must say you are really good at catching my editing mistakes :).. Correction: superSum = ( superSum * ( ( n + i )%17 ) ) / (i+1); On Jan 10, 8:29 pm, atul anand atul.87fri...@gmail.com wrote: @Lucifier : your reduced form is not generating right output... remove modulo and calculate for SuperSum(2,3) On Tue, Jan 10, 2012 at 6:12 PM, priyanka priyankajag...@gmail.com wrote: @lucifier : Please tell how you reduce SuperSum ( k, n) into SuperSum(k,n) = SuperSum (k-1, n) * (n+k) / (k+1) -- 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/-/jWq_vujbiCkJ. 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.
Re: [algogeeks] MS Q
@ Ashish : abt the solution given by reference. well sometimes it depends , interviewer may take it +vely as he can see you are keen to learn abt different algorithm dats why you knw it... On Tue, Jan 10, 2012 at 7:28 PM, Ashish Goel ashg...@gmail.com wrote: i liked the solution given by the reference i have provided. The thought process is similar to mazing problem given in horowitz sahani. nice question, however, how can this be an interview question? If you give this solution, the interviewer would understand that you knew the problem and hence would reject. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jan 10, 2012 at 4:06 PM, Ramakant Sharma ramakant...@gmail.comwrote: 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 -- 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. -- 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] Re: SuperSum
@Lucifier : hehehe...i dont accept solution blindly..may be dats why :D :D yeah got your editing mistake after i posted it bcoz you where not using i in the loop so same calculation were goin on. On Tue, Jan 10, 2012 at 9:05 PM, Lucifer sourabhd2...@gmail.com wrote: @atul First of all, i must say you are really good at catching my editing mistakes :).. Correction: superSum = ( superSum * ( ( n + i )%17 ) ) / (i+1); On Jan 10, 8:29 pm, atul anand atul.87fri...@gmail.com wrote: @Lucifier : your reduced form is not generating right output... remove modulo and calculate for SuperSum(2,3) On Tue, Jan 10, 2012 at 6:12 PM, priyanka priyankajag...@gmail.com wrote: @lucifier : Please tell how you reduce SuperSum ( k, n) into SuperSum(k,n) = SuperSum (k-1, n) * (n+k) / (k+1) -- 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/-/jWq_vujbiCkJ. 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. -- 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] Maximum size square sub-matrix with all 1s
Suggest an algorithm guyzzz. * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * -- 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] Maximum size square sub-matrix with all 1s
i dint get...you should provide more details , if it is all 1 then whole matrix is a max square.. anyways equation to find max sub square is this. M[i,j]=R[i,j]==0 ? 0 : 1+min(M[i-1][,j] , M[i][j-1], M[i-1][j-1] ) On Tue, Jan 10, 2012 at 10:00 PM, Sanjay Rajpal sanjay.raj...@live.inwrote: Suggest an algorithm guyzzz. * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * -- 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.
Re: [algogeeks] Maximum size square sub-matrix with all 1s
Its a square matrix containing 0s and 1s. Will u plz elaborate about this equation ? * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * On Tue, Jan 10, 2012 at 8:36 AM, atul anand atul.87fri...@gmail.com wrote: i dint get...you should provide more details , if it is all 1 then whole matrix is a max square.. anyways equation to find max sub square is this. M[i,j]=R[i,j]==0 ? 0 : 1+min(M[i-1][,j] , M[i][j-1], M[i-1][j-1] ) On Tue, Jan 10, 2012 at 10:00 PM, Sanjay Rajpal sanjay.raj...@live.inwrote: Suggest an algorithm guyzzz. * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * -- 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. -- 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] Re: SuperSum
@priyanka..
SuperSum(k, n) :
For any given base X representation there will be X digits..
Now say, the digits are named as A(i) ... such that,
A1 A2 A3 A(X)...
[ all digits being significant ]
Then SuperSum basically says that what are the no. of (k+1) sized
integers that can formed such that the digits in the integers are in
non-decreasing order from left to right and ends with A(n) where n =
X...
For ex - for Base 5, the digits are 1,2,3, 4, 5
Now SuperSum(1,4) = No. of 2-sized integers that can be formed for
base-5, where the integer ends with at A(4) [ i.e. '4' for base-5]..
--
For simplicity, lets define P(i, j) = SuperSum(i - 1, j)..
Therefore,
P(k, n) :
the no. of (k) sized integers that can formed such that the digits in
the integers are in non-decreasing order from left to right and ends
with A(n) where n = X
Hence,
P(1, i) = 1
P( k, n ) = P(k-1, 1) + P(k-1, 2) + + P(k-1,n)
i.e.
No. of 'k' sized non-decreasing integers = sum over all i { no. of
'k-1' sized integers that end at A(i) such that A(i)= A(n) }
Now, the P(k, n) equation is nothing but a recurrence equation which
should be obvious based on the above explanation..
But, P(k, n) is nothing but (n+k-1) C (k)..
i.e
SuperSum(k, n) = (n+k) C (k+1)...
= SuperSum(k-1, n) * (n+k) / (k+1)..
---
Probably the next question would be :
P(k, n) = (n+k-1) C (k) ??
Well i will explain it with a short example...
Base-3 : {1, 2 ,3 }
Size : 1
Integers endingNo. of integers
at 'i' th digit
1 1
2 1
3 1
Size-2
Integers endingNo. of integers
at 'i' th digit
(1)1 1
(1)2, (2)2 2
(1)3, (2)3, (3)3 3
// the brackets above indicate that the integers within the bracket
have been used from table 'Size-1'
// Basically we are building table 'Size-n' based on table 'Size-
(n-1)'...
Also you must observe that the 'no. of digits' column of table
'Size-2' is nothing
but the cumulative sum of 'no. of digits' column of table 'Size-1'
The 'no. of digits' column of table 'Size-3' would be
1
3
6
The 'no. of digits' column of table 'Size-4' would be
1
4
10..
Do you observe something ???
[Remember pascal's triangle...]
-
A naive approach would be prove:
SuperSum(k-1, n) = SuperSum(k-1, n) * (n+k) / (k+1) using induction..
Calculate for SuperSum(1, 1), SuperSum(1, 2),.. SuperSum(1, n) and so
on.. and see how it goes...
Observe the pattern...
--
On Jan 10, 8:35 pm, Lucifer sourabhd2...@gmail.com wrote:
@atul
First of all, i must say you are really good at catching my editing
mistakes :)..
Correction:
superSum = ( superSum * ( ( n + i )%17 ) ) / (i+1);
On Jan 10, 8:29 pm, atul anand atul.87fri...@gmail.com wrote:
@Lucifier : your reduced form is not generating right output...
remove modulo and calculate for SuperSum(2,3)
On Tue, Jan 10, 2012 at 6:12 PM, priyanka priyankajag...@gmail.com wrote:
@lucifier :
Please tell how you reduce SuperSum ( k, n) into
SuperSum(k,n) = SuperSum (k-1, n) * (n+k) / (k+1)
--
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/-/jWq_vujbiCkJ.
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.
[algogeeks] Re: SuperSum
@priyanka..
If you are looking for some problem where the same concept has been
applied, then go thru the following link...
http://groups.google.com/group/algogeeks/browse_thread/thread/0751e67f32266e53#
and look for the explanation and code that has been posted for the
following problem:
http://www.spoj.pl/problems/NY10E/
[@ Non-Decreasing Digits]
On Jan 10, 11:14 pm, Lucifer sourabhd2...@gmail.com wrote:
@priyanka..
SuperSum(k, n) :
For any given base X representation there will be X digits..
Now say, the digits are named as A(i) ... such that,
A1 A2 A3 A(X)...
[ all digits being significant ]
Then SuperSum basically says that what are the no. of (k+1) sized
integers that can formed such that the digits in the integers are in
non-decreasing order from left to right and ends with A(n) where n =
X...
For ex - for Base 5, the digits are 1,2,3, 4, 5
Now SuperSum(1,4) = No. of 2-sized integers that can be formed for
base-5, where the integer ends with at A(4) [ i.e. '4' for base-5]..
--
For simplicity, lets define P(i, j) = SuperSum(i - 1, j)..
Therefore,
P(k, n) :
the no. of (k) sized integers that can formed such that the digits in
the integers are in non-decreasing order from left to right and ends
with A(n) where n = X
Hence,
P(1, i) = 1
P( k, n ) = P(k-1, 1) + P(k-1, 2) + + P(k-1,n)
i.e.
No. of 'k' sized non-decreasing integers = sum over all i { no. of
'k-1' sized integers that end at A(i) such that A(i)= A(n) }
Now, the P(k, n) equation is nothing but a recurrence equation which
should be obvious based on the above explanation..
But, P(k, n) is nothing but (n+k-1) C (k)..
i.e
SuperSum(k, n) = (n+k) C (k+1)...
= SuperSum(k-1, n) * (n+k) / (k+1)..
---
Probably the next question would be :
P(k, n) = (n+k-1) C (k) ??
Well i will explain it with a short example...
Base-3 : {1, 2 ,3 }
Size : 1
Integers ending No. of integers
at 'i' th digit
1 1
2 1
3 1
Size-2
Integers ending No. of integers
at 'i' th digit
(1)1 1
(1)2, (2)2 2
(1)3, (2)3, (3)3 3
// the brackets above indicate that the integers within the bracket
have been used from table 'Size-1'
// Basically we are building table 'Size-n' based on table 'Size-
(n-1)'...
Also you must observe that the 'no. of digits' column of table
'Size-2' is nothing
but the cumulative sum of 'no. of digits' column of table 'Size-1'
The 'no. of digits' column of table 'Size-3' would be
1
3
6
The 'no. of digits' column of table 'Size-4' would be
1
4
10..
Do you observe something ???
[Remember pascal's triangle...]
-
A naive approach would be prove:
SuperSum(k-1, n) = SuperSum(k-1, n) * (n+k) / (k+1) using induction..
Calculate for SuperSum(1, 1), SuperSum(1, 2),.. SuperSum(1, n) and so
on.. and see how it goes...
Observe the pattern...
--
On Jan 10, 8:35 pm, Lucifer sourabhd2...@gmail.com wrote:
@atul
First of all, i must say you are really good at catching my editing
mistakes :)..
Correction:
superSum = ( superSum * ( ( n + i )%17 ) ) / (i+1);
On Jan 10, 8:29 pm, atul anand atul.87fri...@gmail.com wrote:
@Lucifier : your reduced form is not generating right output...
remove modulo and calculate for SuperSum(2,3)
On Tue, Jan 10, 2012 at 6:12 PM, priyanka priyankajag...@gmail.com
wrote:
@lucifier :
Please tell how you reduce SuperSum ( k, n) into
SuperSum(k,n) = SuperSum (k-1, n) * (n+k) / (k+1)
--
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/-/jWq_vujbiCkJ.
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.
[algogeeks] Re: extracting vector (digitization) from an ECG image
This is pretty funny because modern ECG machines generate digital output. You might first look into whether you can get the digits directly from the machine rather than scans of paper. But suppose you can't. I assume you asking how to find numerical coordinates for the curve by scanning and then analysing the scan. The process of converting a pixmap or bitmap--a big 2d array of pixel data--to polyline coordinates is called vectorzation. I did a quick Google search and came up with this page, which mentions several open source vectorizers: http://wiki.inkscape.org/wiki/index.php/Tools Most of these tools are going to produce SVG files. You'll probably need to look up the SVG file format to determine how to extract the coordinates you need. Since you are training neural nets, you are going to have to clean the results: put them all on the same vertical and horizontal scale, ensure the grid in the background isn't interpreted as data, etc. If you are required to implement the vectorizer yourself, write back. I have done that and can give you pointers. Once you have numerical descriptions of the code, I'd stay in MATLAB. Just so you know, professional ECG analyzers usually work in the _frequency_ domain. I.e. they work on the DFT of the ECG signal, not the signal itself. Or they use both, but the DFT is primary. With MATLAB, taking the DFT is one line of code. And MATLAB has a neural net toolkit. On Jan 8, 1:08 am, Deepak Garg deepakgarg...@gmail.com wrote: my question is about how to achieve digitization of an image/graph image. for example i have the following ECG image( taken from a normal camera ):- http://i.stack.imgur.com/QAMfk.png so what algorithm should i follow to get the digitized image, my final aim is to feed this information to a neural network that can classify the given ECG image into a disease class. please suggest me which platform is more feasible MATLAB or JAVA? please help me guys!! -- 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] Re: MS Q
Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and adjacent 1's are connected by undirected edges.
You must count components in the graph. So the algorithm is easy:
Find a component, erase it, repeat. Count components as you go.
What's an efficient way to do this with this special kind of graph we
have? Just erase components by erasing 1's.
So we get:
#include stdio.h
int a[100][100] = {
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 1, 1},
};
int m = 3, n = 4;
// Erase the undirected component rooted at i,j.
void erase(int i, int j)
{
// If we're off the graph or already erased,
// there's nothing to do.
if (i 0 || j 0 || i = m || j = n || !a[i][j])
return;
// Erase!
a[i][j] = 0;
// Recursively erase the 4 neighbors.
erase(i+1, j); erase(i-1, j);
erase(i, j+1); erase(i, j-1);
}
void count_islands()
{
int i, j, n_islands = 0;
// Search for a component.
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
if (a[i][j] == 1) {
// Found one! Count and erase.
n_islands++;
erase(i, j);
}
}
}
printf(found %d islands\n, n_islands);
}
int main(void)
{
count_islands();
return 0;
}
On Jan 9, 9:06 pm, Ashish Goel ashg...@gmail.com wrote:
row, col, diag all
1-1-1 is a single island :)
1 1 0 0
1 1 0 0
0 0 1 1
this has only 2 islands
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 10, 2012 at 7:29 AM, Ankur Garg ankurga...@gmail.com wrote:
Can you give an example
Say matrix is
1 1 0 0
1 1 0 0
0 0 1 1
Has it got 3 islands i.e 1-1 be in same row or they can be column wise
also i.e. 5
On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel ashg...@gmail.com wrote:
there is a matrix of 1 and 0
1 is a island and 0 is water
1-1 together makes one island
calculate total no of islands
--
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] Re: MS Q
@gene
in that case ur erase() should even consider diagonal elements as well,
else there would be 2 islands in example
surender
On Wed, Jan 11, 2012 at 7:19 AM, Gene gene.ress...@gmail.com wrote:
Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and adjacent 1's are connected by undirected edges.
You must count components in the graph. So the algorithm is easy:
Find a component, erase it, repeat. Count components as you go.
What's an efficient way to do this with this special kind of graph we
have? Just erase components by erasing 1's.
So we get:
#include stdio.h
int a[100][100] = {
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 1, 1},
};
int m = 3, n = 4;
// Erase the undirected component rooted at i,j.
void erase(int i, int j)
{
// If we're off the graph or already erased,
// there's nothing to do.
if (i 0 || j 0 || i = m || j = n || !a[i][j])
return;
// Erase!
a[i][j] = 0;
// Recursively erase the 4 neighbors.
erase(i+1, j); erase(i-1, j);
erase(i, j+1); erase(i, j-1);
}
void count_islands()
{
int i, j, n_islands = 0;
// Search for a component.
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
if (a[i][j] == 1) {
// Found one! Count and erase.
n_islands++;
erase(i, j);
}
}
}
printf(found %d islands\n, n_islands);
}
int main(void)
{
count_islands();
return 0;
}
On Jan 9, 9:06 pm, Ashish Goel ashg...@gmail.com wrote:
row, col, diag all
1-1-1 is a single island :)
1 1 0 0
1 1 0 0
0 0 1 1
this has only 2 islands
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 10, 2012 at 7:29 AM, Ankur Garg ankurga...@gmail.com
wrote:
Can you give an example
Say matrix is
1 1 0 0
1 1 0 0
0 0 1 1
Has it got 3 islands i.e 1-1 be in same row or they can be column wise
also i.e. 5
On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel ashg...@gmail.com
wrote:
there is a matrix of 1 and 0
1 is a island and 0 is water
1-1 together makes one island
calculate total no of islands
--
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.
[algogeeks] Re: Maximum size square sub-matrix with all 1s
The 1's and 0's are in matrix R. We want to compute an integer matrix M of the same dimensions as R such that Mij is the size of the largest square of 1's of which Rij is the bottom right corner. As we go we can keep track of max(Mij), and this will be the answer. So how to compute Mij? The values north, west, and northwest of Mij tells us about the sizes of squares of 1's in those directions. If we take the min; call it M, then we can be sure all the elements of the square with diagonal (i,j)-(i-M,j-M) are all 1's and moreover that if we tried a bigger square we'd either run off the edge of the matrix or hit a zero. So the size of this new square is M+1. Atul anand's algorithm is almost the story. He left out the base cases. The left and top edges of M are just the same as R. So to write a program, for (i = 0; i m; i++) for (j = 0; j n; j++) M[i][j] = (i == 0 || j == 0 || R[i][j] == 0) ? R[i][j] : 1 + min3(M[i-1][j], M[i-1,j-1], M[i][j-1]); If you recode this carefully, you don't need a 2d matrix for M. You can get away with a single row plus one integer variable. On Jan 10, 11:37 am, Sanjay Rajpal sanjay.raj...@live.in wrote: Its a square matrix containing 0s and 1s. Will u plz elaborate about this equation ? * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * On Tue, Jan 10, 2012 at 8:36 AM, atul anand atul.87fri...@gmail.com wrote: i dint get...you should provide more details , if it is all 1 then whole matrix is a max square.. anyways equation to find max sub square is this. M[i,j]=R[i,j]==0 ? 0 : 1+min(M[i-1][,j] , M[i][j-1], M[i-1][j-1] ) On Tue, Jan 10, 2012 at 10:00 PM, Sanjay Rajpal sanjay.raj...@live.inwrote: Suggest an algorithm guyzzz. * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * -- 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. -- 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] Re: Maximum size square sub-matrix with all 1s
g[][]- given matrix r[][]- result matrix copy first row n column from g[][] to r[][] rest for i=1 to n-1 for =1 to n-1j if(g[][]) r[][]=min(r[i][j-1],r[i-1][j],r[i-1][j-1])+1; else r[][]=0; On Wed, Jan 11, 2012 at 10:00 AM, Gene gene.ress...@gmail.com wrote: The 1's and 0's are in matrix R. We want to compute an integer matrix M of the same dimensions as R such that Mij is the size of the largest square of 1's of which Rij is the bottom right corner. As we go we can keep track of max(Mij), and this will be the answer. So how to compute Mij? The values north, west, and northwest of Mij tells us about the sizes of squares of 1's in those directions. If we take the min; call it M, then we can be sure all the elements of the square with diagonal (i,j)-(i-M,j-M) are all 1's and moreover that if we tried a bigger square we'd either run off the edge of the matrix or hit a zero. So the size of this new square is M+1. Atul anand's algorithm is almost the story. He left out the base cases. The left and top edges of M are just the same as R. So to write a program, for (i = 0; i m; i++) for (j = 0; j n; j++) M[i][j] = (i == 0 || j == 0 || R[i][j] == 0) ? R[i][j] : 1 + min3(M[i-1][j], M[i-1,j-1], M[i][j-1]); If you recode this carefully, you don't need a 2d matrix for M. You can get away with a single row plus one integer variable. On Jan 10, 11:37 am, Sanjay Rajpal sanjay.raj...@live.in wrote: Its a square matrix containing 0s and 1s. Will u plz elaborate about this equation ? * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * On Tue, Jan 10, 2012 at 8:36 AM, atul anand atul.87fri...@gmail.com wrote: i dint get...you should provide more details , if it is all 1 then whole matrix is a max square.. anyways equation to find max sub square is this. M[i,j]=R[i,j]==0 ? 0 : 1+min(M[i-1][,j] , M[i][j-1], M[i-1][j-1] ) On Tue, Jan 10, 2012 at 10:00 PM, Sanjay Rajpal sanjay.raj...@live.in wrote: Suggest an algorithm guyzzz. * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * -- 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. -- 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.
Re: [algogeeks] Re: MS Q
I think atul/Ramakanth's approach will work fine, if we include one more
condition
for each arr[i][j]
if(arr[i][j]==1)
{
if (arr[i-1][j]==0 arr[i][j-1]==0 arr[i-1][j-1]==0)
count++;
else if (arr[i-1][j]==1 arr[i][j-1]==1 arr[i-1][j-1]==0)
count--;
}
On Wed, Jan 11, 2012 at 8:10 AM, surender sanke surend...@gmail.com wrote:
@gene
in that case ur erase() should even consider diagonal elements as well,
else there would be 2 islands in example
surender
On Wed, Jan 11, 2012 at 7:19 AM, Gene gene.ress...@gmail.com wrote:
Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and adjacent 1's are connected by undirected edges.
You must count components in the graph. So the algorithm is easy:
Find a component, erase it, repeat. Count components as you go.
What's an efficient way to do this with this special kind of graph we
have? Just erase components by erasing 1's.
So we get:
#include stdio.h
int a[100][100] = {
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 1, 1},
};
int m = 3, n = 4;
// Erase the undirected component rooted at i,j.
void erase(int i, int j)
{
// If we're off the graph or already erased,
// there's nothing to do.
if (i 0 || j 0 || i = m || j = n || !a[i][j])
return;
// Erase!
a[i][j] = 0;
// Recursively erase the 4 neighbors.
erase(i+1, j); erase(i-1, j);
erase(i, j+1); erase(i, j-1);
}
void count_islands()
{
int i, j, n_islands = 0;
// Search for a component.
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
if (a[i][j] == 1) {
// Found one! Count and erase.
n_islands++;
erase(i, j);
}
}
}
printf(found %d islands\n, n_islands);
}
int main(void)
{
count_islands();
return 0;
}
On Jan 9, 9:06 pm, Ashish Goel ashg...@gmail.com wrote:
row, col, diag all
1-1-1 is a single island :)
1 1 0 0
1 1 0 0
0 0 1 1
this has only 2 islands
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 10, 2012 at 7:29 AM, Ankur Garg ankurga...@gmail.com
wrote:
Can you give an example
Say matrix is
1 1 0 0
1 1 0 0
0 0 1 1
Has it got 3 islands i.e 1-1 be in same row or they can be column wise
also i.e. 5
On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel ashg...@gmail.com
wrote:
there is a matrix of 1 and 0
1 is a island and 0 is water
1-1 together makes one island
calculate total no of islands
--
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.
--
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] Re: MS Q
@Umer : it has 1 island ashish made editing mistake before.
On Wed, Jan 11, 2012 at 11:58 AM, Umer Farooq the.um...@gmail.com wrote:
I still don't get how are they two islands. As long as I have understood,
diagonals abridge the two islands into one. In this case, these two islands
are connected so they form one single island?
1 1 0 0
1 1 0 0
0 0 1 1
This can be either one single island. Or they are three island if a change
in direction makes a whole new island.
Can anyone please clear me the problem?
On Wed, Jan 11, 2012 at 10:24 AM, prakash y yprakash@gmail.comwrote:
I think atul/Ramakanth's approach will work fine, if we include one more
condition
for each arr[i][j]
if(arr[i][j]==1)
{
if (arr[i-1][j]==0 arr[i][j-1]==0 arr[i-1][j-1]==0)
count++;
else if (arr[i-1][j]==1 arr[i][j-1]==1 arr[i-1][j-1]==0)
count--;
}
On Wed, Jan 11, 2012 at 8:10 AM, surender sanke surend...@gmail.comwrote:
@gene
in that case ur erase() should even consider diagonal elements as well,
else there would be 2 islands in example
surender
On Wed, Jan 11, 2012 at 7:19 AM, Gene gene.ress...@gmail.com wrote:
Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and adjacent 1's are connected by undirected edges.
You must count components in the graph. So the algorithm is easy:
Find a component, erase it, repeat. Count components as you go.
What's an efficient way to do this with this special kind of graph we
have? Just erase components by erasing 1's.
So we get:
#include stdio.h
int a[100][100] = {
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 1, 1},
};
int m = 3, n = 4;
// Erase the undirected component rooted at i,j.
void erase(int i, int j)
{
// If we're off the graph or already erased,
// there's nothing to do.
if (i 0 || j 0 || i = m || j = n || !a[i][j])
return;
// Erase!
a[i][j] = 0;
// Recursively erase the 4 neighbors.
erase(i+1, j); erase(i-1, j);
erase(i, j+1); erase(i, j-1);
}
void count_islands()
{
int i, j, n_islands = 0;
// Search for a component.
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
if (a[i][j] == 1) {
// Found one! Count and erase.
n_islands++;
erase(i, j);
}
}
}
printf(found %d islands\n, n_islands);
}
int main(void)
{
count_islands();
return 0;
}
On Jan 9, 9:06 pm, Ashish Goel ashg...@gmail.com wrote:
row, col, diag all
1-1-1 is a single island :)
1 1 0 0
1 1 0 0
0 0 1 1
this has only 2 islands
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 10, 2012 at 7:29 AM, Ankur Garg ankurga...@gmail.com
wrote:
Can you give an example
Say matrix is
1 1 0 0
1 1 0 0
0 0 1 1
Has it got 3 islands i.e 1-1 be in same row or they can be column
wise
also i.e. 5
On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel ashg...@gmail.com
wrote:
there is a matrix of 1 and 0
1 is a island and 0 is water
1-1 together makes one island
calculate total no of islands
--
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.
--
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.
--
Umer
--
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.
[algogeeks] sort 2D array
Given 2D array. The rows are sorted in ascending order and the colums are sorted in ascending order. We have to sort the whole matrix in ascending array. We cannot use 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?hl=en.
Re: [algogeeks] sort 2D array
sort the whole matrix in ascending array means? can you please explain ? On Wed, Jan 11, 2012 at 12:53 PM, atul anand atul.87fri...@gmail.comwrote: Given 2D array. The rows are sorted in ascending order and the colums are sorted in ascending order. We have to sort the whole matrix in ascending array. We cannot use 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?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.
Re: [algogeeks] sort 2D array
I guess sort the array such that elements are sorted finally in such a way that if we print them row by row, the result is a sorted array. K-way merge can be useful. * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * On Tue, Jan 10, 2012 at 11:28 PM, prakash y yprakash@gmail.com wrote: sort the whole matrix in ascending array means? can you please explain ? On Wed, Jan 11, 2012 at 12:53 PM, atul anand atul.87fri...@gmail.comwrote: Given 2D array. The rows are sorted in ascending order and the colums are sorted in ascending order. We have to sort the whole matrix in ascending array. We cannot use 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?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. -- 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.
