subject:"Re\: \[algogeeks\] Maximum size square sub\-matrix with all 1s"

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-15 Thread Sourabh Singh

@ atul and saurabh

Here is my code of what m trying to implement .

here starting at bottom right corner we try to come up moving row by row .
in end  b matrix contain's dimention of rectangle which can be formed
from Aij in Bij (width,height)

plz.. post what u make of it...  can it be improved to work for all case's
??

#includeiostream
#includeconio.h

using namespace std;
main()
{ int width=0,height=1;
  int a[6][6]={0,1,1,1,1,0,
   0,0,0,1,1,0,
   0,1,1,1,1,0,
   0,1,1,0,0,0,
   0,1,1,0,0,0,
   0,0,0,0,0,0 };

  int b[6][6][2]={0};

  int i,j;
  for(i=0;i6;i++)
  {   b[5][i][width]=1;
  b[i][5][width]=1;

  b[5][i][height]=1;
  b[i][5][height]=1;
  }
  for(i=4;i=0;i--)
  {
  for(j=4;j=0;j--)
  {

   if(a[i][j]!=a[i+1][j]  a[i][j]!=a[i][j+1])
   {
 b[i][j][width]=1;
 b[i][j][height]=1;
   }
   else if(a[i][j]==a[i][j+1] 
a[i][j]!=a[i+1][j])
{
 b[i][j][width]=b[i][j+1][width]+1;
 b[i][j][height]=1;

//printf(widht\n);
}
else if(a[i][j]==a[i+1][j] 
a[i][j]!=a[i][j+1])
 {
 b[i][j][width]=1;

b[i][j][height]=b[i+1][j][height]+1;
// printf(height\n);
 }
 else
 {

b[i][j][width]=min(b[i+1][j][width],b[i][j+1][width]+1);

b[i][j][height]=min(b[i+1][j][height]+1,b[i][j+1][height]);
 }
  }
  }

  for(i=0;i6;i++)
  {
  for(j=0;j6;j++)
  {
 printf(%d,%d ,b[i][j][width],b[i][j][height]);
  }
  printf(\n);
  }
  getch();
}



On Wed, Mar 14, 2012 at 8:59 PM, atul anand atul.87fri...@gmail.com wrote:

 @Sourabh : here we are talking abt 2 different problems in this
 post..which are little bit similar.

 1) original question says find max subset of matix contaning '1' and '0'

 we knw recurrence to solve this problem , as posted above.

 2) now your question is to find max subset of matrix which contain +ve or
 -ve numbers , not necessarily only '1' or '0'

 so in my solution , you need to give some input to solve this problem 
 and that input is say matrix m[][].
 if you check my solution then in just modifies input matrix to find
 solution , its space complexity is O(1).



 On Thu, Mar 15, 2012 at 12:26 AM, Sourabh Singh 
 singhsourab...@gmail.comwrote:

 @atul

 1) it won't work for large dimention's coz their is a limit to size of
 array we can declare on stack.
( which is typically 10^6 as far as i know :-)  ).

 2) the algo i m trying to find would work in linear time. while this one
 is more then O(n^2)
 fo rvery very large input this algo would be very very slow.. making
 it impractial..

 ( it's like if u can find substring's in linear time then why use an
 O(n^2) algo ;-) )

 NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit
 short on time to check implemention of  your algo right now )



 On Wed, Mar 14, 2012 at 9:07 AM, atul anand atul.87fri...@gmail.comwrote:

 @rahul: i have alreday explained it in the provided link.
 @sourbh : why it would not work for large dimension
 On 14 Mar 2012 19:39, rahul sharma rahul23111...@gmail.com wrote:

 @atul..plz tell me an example for square matrix...actually i faced it
 first tym...it executes...but explain plz..

 On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh 
 singhsourab...@gmail.com wrote:

 @atul

 Also the histogram algo and algo given by you can't work on very very
 big dimentions. say 10^5 x 10^5 matrix.
  but if we can find a DP then  we just need to keep 2 row's at a time.
 :-)



 On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh 
 singhsourab...@gmail.com wrote:

 @atul

 read it ..

 it's good but more or less like the histogram algo.. i wanted a DP.
 approach..

 here is some of wat i heard from a senior in colg..

 1. at every index we can keep 4 variable

 ht: height of max rectangle possible at index above current
  wt width  

  hl:height of max rectangle possible at index left of  current
 wl:   
 


 now problem is which one to take for current... index



 On Tue, Mar 13, 2012 at 10:52 AM, atul anand

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-14 Thread Sourabh Singh

@atul

Also the histogram algo and algo given by you can't work on very very big
dimentions. say 10^5 x 10^5 matrix.
but if we can find a DP then we just need to keep 2 row's at a time. :-)

On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh singhsourab...@gmail.comwrote:

@atul

read it ..

it's good but more or less like the histogram algo.. i wanted a DP.
approach..

here is some of wat i heard from a senior in colg..

1. at every index we can keep 4 variable

ht: height of max rectangle possible at index above current
wt width

hl:height of max rectangle possible at index left of current
wl:

now problem is which one to take for current... index

On Tue, Mar 13, 2012 at 10:52 AM, atul anand atul.87fri...@gmail.comwrote:

@ Sourabh: check solution i have posted in below link

http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0

On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh singhsourab...@gmail.com
wrote:

@ ALL

finding square matrix is quite a standard question and nw an easy one
as everyone knows the reccussence atul has given.
but i wanted to find max rectangle..

i know there is a DP for it. in O(n^2). for nxn matrix..don't know the
whole approach .but here is what i remember..

1. aproach is simple to keep track of max rectangle which can be formed
from any point taking that point as top left corner of max rectangle and
proceed further down .

can someone suggest how can be proceed further..

[ NOTE: problem occurs mainly when their are more than one rectangles
which can be formed from same point ]

plz.. don't suggest the histogram method it's just a dirty way of
avoiding to work on getting this DP right. :-)

On Mon, Mar 12, 2012 at 11:29 PM, atul anand atul.87fri...@gmail.comwrote:

here is the recurrence for solving this

R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1], R[i,,j-1]
) );

On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma rahul23111...@gmail.com
wrote:

April 4, 2010

Given a binary matrix, find out the maximum size square sub-matrix
with all 1s.

For example, consider the below binary matrix.

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

The maximum square sub-matrix with all set bits is

1 1 1
1 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.

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-14 Thread rahul sharma

@atul..plz tell me an example for square matrix...actually i faced it first
tym...it executes...but explain plz..

On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh singhsourab...@gmail.comwrote:

@atul

Also the histogram algo and algo given by you can't work on very very big
dimentions. say 10^5 x 10^5 matrix.
but if we can find a DP then we just need to keep 2 row's at a time. :-)

On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh
singhsourab...@gmail.comwrote:

@atul

read it ..

it's good but more or less like the histogram algo.. i wanted a DP.
approach..

here is some of wat i heard from a senior in colg..

1. at every index we can keep 4 variable

ht: height of max rectangle possible at index above current
wt width

hl:height of max rectangle possible at index left of current
wl:

now problem is which one to take for current... index

On Tue, Mar 13, 2012 at 10:52 AM, atul anand atul.87fri...@gmail.comwrote:

@ Sourabh: check solution i have posted in below link

http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0

On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh
singhsourab...@gmail.com wrote:

@ ALL

finding square matrix is quite a standard question and nw an easy one
as everyone knows the reccussence atul has given.
but i wanted to find max rectangle..

i know there is a DP for it. in O(n^2). for nxn matrix..don't know the
whole approach .but here is what i remember..

1. aproach is simple to keep track of max rectangle which can be formed
from any point taking that point as top left corner of max rectangle and
proceed further down .

can someone suggest how can be proceed further..

[ NOTE: problem occurs mainly when their are more than one rectangles
which can be formed from same point ]

plz.. don't suggest the histogram method it's just a dirty way of
avoiding to work on getting this DP right. :-)

On Mon, Mar 12, 2012 at 11:29 PM, atul anand
atul.87fri...@gmail.comwrote:

here is the recurrence for solving this

R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1],
R[i,,j-1] ) );

On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma
rahul23111...@gmail.com wrote:

April 4, 2010

Given a binary matrix, find out the maximum size square sub-matrix
with all 1s.

For example, consider the below binary matrix.

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

The maximum square sub-matrix with all set bits is

1 1 1
1 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.

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-14 Thread atul anand

@rahul: i have alreday explained it in the provided link.
@sourbh : why it would not work for large dimension
On 14 Mar 2012 19:39, rahul sharma rahul23111...@gmail.com wrote:

@atul..plz tell me an example for square matrix...actually i faced it
first tym...it executes...but explain plz..

On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh
singhsourab...@gmail.comwrote:

@atul

Also the histogram algo and algo given by you can't work on very very big
dimentions. say 10^5 x 10^5 matrix.
but if we can find a DP then we just need to keep 2 row's at a time. :-)

On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh
singhsourab...@gmail.comwrote:

@atul

read it ..

it's good but more or less like the histogram algo.. i wanted a DP.
approach..

here is some of wat i heard from a senior in colg..

1. at every index we can keep 4 variable

ht: height of max rectangle possible at index above current
wt width

hl:height of max rectangle possible at index left of current
wl:

now problem is which one to take for current... index

On Tue, Mar 13, 2012 at 10:52 AM, atul anand atul.87fri...@gmail.comwrote:

@ Sourabh: check solution i have posted in below link

http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0

On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh
singhsourab...@gmail.com wrote:

@ ALL

finding square matrix is quite a standard question and nw an easy one
as everyone knows the reccussence atul has given.
but i wanted to find max rectangle..

i know there is a DP for it. in O(n^2). for nxn matrix..don't know the
whole approach .but here is what i remember..

1. aproach is simple to keep track of max rectangle which can be
formed from any point taking that point as top left corner of max
rectangle and
proceed further down .

can someone suggest how can be proceed further..

[ NOTE: problem occurs mainly when their are more than one rectangles
which can be formed from same point ]

plz.. don't suggest the histogram method it's just a dirty way of
avoiding to work on getting this DP right. :-)

On Mon, Mar 12, 2012 at 11:29 PM, atul anand
atul.87fri...@gmail.comwrote:

here is the recurrence for solving this

R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1],
R[i,,j-1] ) );

On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma
rahul23111...@gmail.com wrote:

April 4, 2010

Given a binary matrix, find out the maximum size square sub-matrix
with all 1s.

For example, consider the below binary matrix.

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

The maximum square sub-matrix with all set bits is

1 1 1
1 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

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-14 Thread Sourabh Singh

@atul

1) it won't work for large dimention's coz their is a limit to size of
array we can declare on stack.
( which is typically 10^6 as far as i know :-) ).

2) the algo i m trying to find would work in linear time. while this one is
more then O(n^2)
fo rvery very large input this algo would be very very slow.. making it
impractial..

( it's like if u can find substring's in linear time then why use an O(n^2)
algo ;-) )

NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit short
on time to check implemention of your algo right now )

On Wed, Mar 14, 2012 at 9:07 AM, atul anand atul.87fri...@gmail.com wrote:

@rahul: i have alreday explained it in the provided link.
@sourbh : why it would not work for large dimension
On 14 Mar 2012 19:39, rahul sharma rahul23111...@gmail.com wrote:

@atul..plz tell me an example for square matrix...actually i faced it
first tym...it executes...but explain plz..

On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh
singhsourab...@gmail.comwrote:

@atul

Also the histogram algo and algo given by you can't work on very very
big dimentions. say 10^5 x 10^5 matrix.
but if we can find a DP then we just need to keep 2 row's at a time.
:-)

On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh singhsourab...@gmail.com
wrote:

@atul

read it ..

it's good but more or less like the histogram algo.. i wanted a DP.
approach..

here is some of wat i heard from a senior in colg..

1. at every index we can keep 4 variable

ht: height of max rectangle possible at index above current
wt width

hl:height of max rectangle possible at index left of current
wl:

now problem is which one to take for current... index

On Tue, Mar 13, 2012 at 10:52 AM, atul anand
atul.87fri...@gmail.comwrote:

@ Sourabh: check solution i have posted in below link

http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0

On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh
singhsourab...@gmail.com wrote:

@ ALL

finding square matrix is quite a standard question and nw an easy
one as everyone knows the reccussence atul has given.
but i wanted to find max rectangle..

i know there is a DP for it. in O(n^2). for nxn matrix..don't know
the whole approach .but here is what i remember..

1. aproach is simple to keep track of max rectangle which can be
formed from any point taking that point as top left corner of max
rectangle and
proceed further down .

can someone suggest how can be proceed further..

[ NOTE: problem occurs mainly when their are more than one rectangles
which can be formed from same point ]

plz.. don't suggest the histogram method it's just a dirty way of
avoiding to work on getting this DP right. :-)

On Mon, Mar 12, 2012 at 11:29 PM, atul anand atul.87fri...@gmail.com
wrote:

here is the recurrence for solving this

R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1],
R[i,,j-1] ) );

On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma
rahul23111...@gmail.com wrote:

April 4, 2010

Given a binary matrix, find out the maximum size square sub-matrix
with all 1s.

For example, consider the below binary matrix.

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

The maximum square sub-matrix with all set bits is

1 1 1
1 1 1
1 1 1

--
You

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-14 Thread Sourabh Singh

@rahul

may be this will help you..

/* Given a binary matrix, find out the maximum size square sub-matrix with
all 1s.
   1. O(n^3) sol is very obvious
   2. O(n^2) sol [ this file]
   3. O(n)   sol [ possible but we need to know tucker matrix, etc advanced
set theory's]
*/


#includeiostream
#includeconio.h

int b[6][6];
using namespace std;
main()
{ int i,j,t;
  int a[6][6]=
  { 0,0,0,1,0,1,
0,1,1,1,0,0,
1,1,1,1,0,1,
0,1,1,1,1,0,
1,0,0,1,0,0,
0,1,0,1,1,0,};
  for(i=0;i6;i++)
  for(j=0;j6;j++)
  {   if(a[i][j]==1)
  {

b[i][j]=min(min(b[i-1][j],b[i][j-1]),b[j-1][i-1])+1;
  }
  else
b[i][j]=0;
  }
  for(i=0;i6;i++)
  {   for(j=0;j6;j++)
  {printf( %d,a[i][j]);
  }
  printf(\n);
  }
  printf(\n\n\n\n\n);
  for(i=0;i6;i++)
  {   for(j=0;j6;j++)
  {printf( %d,b[i][j]);
  }
  printf(\n);
  }
  getch();
  return 0;
}


On Wed, Mar 14, 2012 at 11:56 AM, Sourabh Singh singhsourab...@gmail.comwrote:

 @atul

 1) it won't work for large dimention's coz their is a limit to size of
 array we can declare on stack.
( which is typically 10^6 as far as i know :-)  ).

 2) the algo i m trying to find would work in linear time. while this one
 is more then O(n^2)
 fo rvery very large input this algo would be very very slow.. making
 it impractial..

 ( it's like if u can find substring's in linear time then why use an
 O(n^2) algo ;-) )

 NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit short
 on time to check implemention of  your algo right now )



 On Wed, Mar 14, 2012 at 9:07 AM, atul anand atul.87fri...@gmail.comwrote:

 @rahul: i have alreday explained it in the provided link.
 @sourbh : why it would not work for large dimension
 On 14 Mar 2012 19:39, rahul sharma rahul23111...@gmail.com wrote:

 @atul..plz tell me an example for square matrix...actually i faced it
 first tym...it executes...but explain plz..

 On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh singhsourab...@gmail.com
  wrote:

 @atul

 Also the histogram algo and algo given by you can't work on very very
 big dimentions. say 10^5 x 10^5 matrix.
  but if we can find a DP then  we just need to keep 2 row's at a time.
 :-)



 On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh 
 singhsourab...@gmail.com wrote:

 @atul

 read it ..

 it's good but more or less like the histogram algo.. i wanted a DP.
 approach..

 here is some of wat i heard from a senior in colg..

 1. at every index we can keep 4 variable

 ht: height of max rectangle possible at index above current
  wt width  

  hl:height of max rectangle possible at index left of  current
 wl:   
 


 now problem is which one to take for current... index



 On Tue, Mar 13, 2012 at 10:52 AM, atul anand 
 atul.87fri...@gmail.comwrote:

 @ Sourabh: check solution i have posted in below link


 http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0



 On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh 
 singhsourab...@gmail.com wrote:

 @ ALL

  finding square matrix is quite a standard question and nw an easy
 one as everyone knows the reccussence atul has given.
  but  i wanted to find max rectangle..

 i know there is a DP for it. in O(n^2). for nxn matrix..don't know
 the whole approach .but  here is what i remember..

 1. aproach is simple to keep track of max rectangle which can be
 formed from any point taking that point as top  left corner of max
 rectangle and
 proceed further down .

 can someone suggest how can be proceed further..


 [ NOTE: problem occurs mainly when their are more than one
 rectangles which can be formed from same point ]

 plz.. don't suggest the histogram method it's just a dirty way of
 avoiding to work on getting this DP right. :-)


 On Mon, Mar 12, 2012 at 11:29 PM, atul anand 
 atul.87fri...@gmail.com wrote:

 here is the recurrence for solving this

 R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1],
 R[i,,j-1] ) );


 On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma 
 rahul23111...@gmail.com wrote:


  April 4, 2010

 Given a binary matrix, find out the maximum size square sub-matrix
 with all 1s.

 For example, consider the below binary matrix.

0  1  1  0  1
1  1  0  1  0
0  1  1  1  0
1  1  1  1  0
1  1  1  1  1
0  0  0  0  0

 The maximum square sub-matrix with all set bits is

 1  1  1
 1  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.

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-14 Thread saurabh singh

On 3/15/12, Sourabh Singh singhsourab...@gmail.com wrote:
 @rahul

 may be this will help you..

 /* Given a binary matrix, find out the maximum size square sub-matrix with
 all 1s.
1. O(n^3) sol is very obvious
2. O(n^2) sol [ this file]
3. O(n)   sol [ possible but we need to know tucker matrix, etc advanced
 set theory's]
 */


 #includeiostream
 #includeconio.h

 int b[6][6];
 using namespace std;
 main()
 { int i,j,t;
   int a[6][6]=
   { 0,0,0,1,0,1,
 0,1,1,1,0,0,
 1,1,1,1,0,1,
 0,1,1,1,1,0,
 1,0,0,1,0,0,
 0,1,0,1,1,0,};
   for(i=0;i6;i++)
   for(j=0;j6;j++)
   {   if(a[i][j]==1)
   {

 b[i][j]=min(min(b[i-1][j],b[i][j-1]),b[j-1][i-1])+1;
   }
   else
 b[i][j]=0;
   }
   for(i=0;i6;i++)
   {   for(j=0;j6;j++)
   {printf( %d,a[i][j]);
   }
   printf(\n);
   }
   printf(\n\n\n\n\n);
   for(i=0;i6;i++)
   {   for(j=0;j6;j++)
   {printf( %d,b[i][j]);
   }
   printf(\n);
   }
   getch();
   return 0;
 }


 On Wed, Mar 14, 2012 at 11:56 AM, Sourabh Singh
 singhsourab...@gmail.comwrote:

 @atul

 1) it won't work for large dimention's coz their is a limit to size of
 array we can declare on stack.
( which is typically 10^6 as far as i know :-)  ).

 2) the algo i m trying to find would work in linear time. while this one
 is more then O(n^2)
 fo rvery very large input this algo would be very very slow.. making
 it impractial..

 ( it's like if u can find substring's in linear time then why use an
 O(n^2) algo ;-) )

 NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit short
 on time to check implemention of  your algo right now )



 On Wed, Mar 14, 2012 at 9:07 AM, atul anand
 atul.87fri...@gmail.comwrote:

 @rahul: i have alreday explained it in the provided link.
 @sourbh : why it would not work for large dimension
 On 14 Mar 2012 19:39, rahul sharma rahul23111...@gmail.com wrote:

 @atul..plz tell me an example for square matrix...actually i faced it
 first tym...it executes...but explain plz..

 On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh singhsourab...@gmail.com
  wrote:

 @atul

 Also the histogram algo and algo given by you can't work on very very
 big dimentions. say 10^5 x 10^5 matrix.
  but if we can find a DP then  we just need to keep 2 row's at a time.
 :-)



 On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh 
 singhsourab...@gmail.com wrote:

 @atul

 read it ..

 it's good but more or less like the histogram algo.. i wanted a DP.
 approach..

 here is some of wat i heard from a senior in colg..

 1. at every index we can keep 4 variable

 ht: height of max rectangle possible at index above current
  wt width  

  hl:height of max rectangle possible at index left of  current
 wl:   
 


 now problem is which one to take for current... index



 On Tue, Mar 13, 2012 at 10:52 AM, atul anand
 atul.87fri...@gmail.comwrote:

 @ Sourabh: check solution i have posted in below link


 http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0



 On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh 
 singhsourab...@gmail.com wrote:

 @ ALL

  finding square matrix is quite a standard question and nw an easy
 one as everyone knows the reccussence atul has given.
  but  i wanted to find max rectangle..

 i know there is a DP for it. in O(n^2). for nxn matrix..don't know
 the whole approach .but  here is what i remember..

 1. aproach is simple to keep track of max rectangle which can be
 formed from any point taking that point as top  left corner of max
 rectangle and
 proceed further down .

 can someone suggest how can be proceed further..


 [ NOTE: problem occurs mainly when their are more than one
 rectangles which can be formed from same point ]

 plz.. don't suggest the histogram method it's just a dirty way of
 avoiding to work on getting this DP right. :-)


 On Mon, Mar 12, 2012 at 11:29 PM, atul anand 
 atul.87fri...@gmail.com wrote:

 here is the recurrence for solving this

 R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1],
 R[i,,j-1] ) );


 On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma 
 rahul23111...@gmail.com wrote:


  April 4, 2010

 Given a binary matrix, find out the maximum size square sub-matrix
 with all 1s.

 For example, consider the below binary matrix.

0  1  1  0  1
1  1  0  1  0
0  1  1  1  0
1  1  1  1  0
1  1  1  1  1
0  0  0  0  0

 The maximum square sub-matrix with all set bits is

 1  1  1
 1  1  1
 1  1  1

  --
 You received this message because you are subscribed to

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-14 Thread saurabh singh

@sourabhThere are O(n^2) elements in the matrix of size nXn. Yes
we can find patterns in a substring with n elements in O(n) but can
you do that in O(sqrt(n)) (To complete your analogy),
Beside's can you allocate a 10^6X10^6 matrix in an array?


On 3/15/12, saurabh singh saurab...@gmail.com wrote:
 On 3/15/12, Sourabh Singh singhsourab...@gmail.com wrote:
 @rahul

 may be this will help you..

 /* Given a binary matrix, find out the maximum size square sub-matrix
 with
 all 1s.
1. O(n^3) sol is very obvious
2. O(n^2) sol [ this file]
3. O(n)   sol [ possible but we need to know tucker matrix, etc
 advanced
 set theory's]
 */


 #includeiostream
 #includeconio.h

 int b[6][6];
 using namespace std;
 main()
 { int i,j,t;
   int a[6][6]=
   { 0,0,0,1,0,1,
 0,1,1,1,0,0,
 1,1,1,1,0,1,
 0,1,1,1,1,0,
 1,0,0,1,0,0,
 0,1,0,1,1,0,};
   for(i=0;i6;i++)
   for(j=0;j6;j++)
   {   if(a[i][j]==1)
   {

 b[i][j]=min(min(b[i-1][j],b[i][j-1]),b[j-1][i-1])+1;
   }
   else
 b[i][j]=0;
   }
   for(i=0;i6;i++)
   {   for(j=0;j6;j++)
   {printf( %d,a[i][j]);
   }
   printf(\n);
   }
   printf(\n\n\n\n\n);
   for(i=0;i6;i++)
   {   for(j=0;j6;j++)
   {printf( %d,b[i][j]);
   }
   printf(\n);
   }
   getch();
   return 0;
 }


 On Wed, Mar 14, 2012 at 11:56 AM, Sourabh Singh
 singhsourab...@gmail.comwrote:

 @atul

 1) it won't work for large dimention's coz their is a limit to size of
 array we can declare on stack.
( which is typically 10^6 as far as i know :-)  ).

 2) the algo i m trying to find would work in linear time. while this one
 is more then O(n^2)
 fo rvery very large input this algo would be very very slow.. making
 it impractial..

 ( it's like if u can find substring's in linear time then why use an
 O(n^2) algo ;-) )

 NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit
 short
 on time to check implemention of  your algo right now )



 On Wed, Mar 14, 2012 at 9:07 AM, atul anand
 atul.87fri...@gmail.comwrote:

 @rahul: i have alreday explained it in the provided link.
 @sourbh : why it would not work for large dimension
 On 14 Mar 2012 19:39, rahul sharma rahul23111...@gmail.com wrote:

 @atul..plz tell me an example for square matrix...actually i faced it
 first tym...it executes...but explain plz..

 On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh
 singhsourab...@gmail.com
  wrote:

 @atul

 Also the histogram algo and algo given by you can't work on very very
 big dimentions. say 10^5 x 10^5 matrix.
  but if we can find a DP then  we just need to keep 2 row's at a
 time.
 :-)



 On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh 
 singhsourab...@gmail.com wrote:

 @atul

 read it ..

 it's good but more or less like the histogram algo.. i wanted a DP.
 approach..

 here is some of wat i heard from a senior in colg..

 1. at every index we can keep 4 variable

 ht: height of max rectangle possible at index above current
  wt width  

  hl:height of max rectangle possible at index left of  current
 wl:   
 


 now problem is which one to take for current... index



 On Tue, Mar 13, 2012 at 10:52 AM, atul anand
 atul.87fri...@gmail.comwrote:

 @ Sourabh: check solution i have posted in below link


 http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0



 On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh 
 singhsourab...@gmail.com wrote:

 @ ALL

  finding square matrix is quite a standard question and nw an easy
 one as everyone knows the reccussence atul has given.
  but  i wanted to find max rectangle..

 i know there is a DP for it. in O(n^2). for nxn matrix..don't know
 the whole approach .but  here is what i remember..

 1. aproach is simple to keep track of max rectangle which can be
 formed from any point taking that point as top  left corner of max
 rectangle and
 proceed further down .

 can someone suggest how can be proceed further..


 [ NOTE: problem occurs mainly when their are more than one
 rectangles which can be formed from same point ]

 plz.. don't suggest the histogram method it's just a dirty way of
 avoiding to work on getting this DP right. :-)


 On Mon, Mar 12, 2012 at 11:29 PM, atul anand 
 atul.87fri...@gmail.com wrote:

 here is the recurrence for solving this

 R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1],
 R[i,,j-1] ) );


 On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma 
 rahul23111...@gmail.com wrote:


  April 4, 2010

 Given a binary matrix, find out the maximum size square
 sub-matrix
 with all 1s.

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-14 Thread atul anand

@Sourabh : here we are talking abt 2 different problems in this post..which
are little bit similar.

1) original question says find max subset of matix contaning '1' and '0'

we knw recurrence to solve this problem , as posted above.

2) now your question is to find max subset of matrix which contain +ve or
-ve numbers , not necessarily only '1' or '0'

so in my solution , you need to give some input to solve this problem
and that input is say matrix m[][].
if you check my solution then in just modifies input matrix to find
solution , its space complexity is O(1).

On Thu, Mar 15, 2012 at 12:26 AM, Sourabh Singh singhsourab...@gmail.comwrote:

@atul

1) it won't work for large dimention's coz their is a limit to size of
array we can declare on stack.
( which is typically 10^6 as far as i know :-) ).

2) the algo i m trying to find would work in linear time. while this one
is more then O(n^2)
fo rvery very large input this algo would be very very slow.. making
it impractial..

( it's like if u can find substring's in linear time then why use an
O(n^2) algo ;-) )

NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit short
on time to check implemention of your algo right now )

On Wed, Mar 14, 2012 at 9:07 AM, atul anand atul.87fri...@gmail.comwrote:

@rahul: i have alreday explained it in the provided link.
@sourbh : why it would not work for large dimension
On 14 Mar 2012 19:39, rahul sharma rahul23111...@gmail.com wrote:

@atul..plz tell me an example for square matrix...actually i faced it
first tym...it executes...but explain plz..

On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh singhsourab...@gmail.com
wrote:

@atul

Also the histogram algo and algo given by you can't work on very very
big dimentions. say 10^5 x 10^5 matrix.
but if we can find a DP then we just need to keep 2 row's at a time.
:-)

On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh
singhsourab...@gmail.com wrote:

@atul

read it ..

it's good but more or less like the histogram algo.. i wanted a DP.
approach..

here is some of wat i heard from a senior in colg..

1. at every index we can keep 4 variable

ht: height of max rectangle possible at index above current
wt width

hl:height of max rectangle possible at index left of current
wl:

now problem is which one to take for current... index

On Tue, Mar 13, 2012 at 10:52 AM, atul anand
atul.87fri...@gmail.comwrote:

@ Sourabh: check solution i have posted in below link

http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0

On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh
singhsourab...@gmail.com wrote:

@ ALL

finding square matrix is quite a standard question and nw an easy
one as everyone knows the reccussence atul has given.
but i wanted to find max rectangle..

i know there is a DP for it. in O(n^2). for nxn matrix..don't know
the whole approach .but here is what i remember..

1. aproach is simple to keep track of max rectangle which can be
formed from any point taking that point as top left corner of max
rectangle and
proceed further down .

can someone suggest how can be proceed further..

[ NOTE: problem occurs mainly when their are more than one
rectangles which can be formed from same point ]

plz.. don't suggest the histogram method it's just a dirty way of
avoiding to work on getting this DP right. :-)

On Mon, Mar 12, 2012 at 11:29 PM, atul anand
atul.87fri...@gmail.com wrote:

here is the recurrence for solving this

R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1],
R[i,,j-1] ) );

On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma
rahul23111...@gmail.com wrote:

April 4, 2010

Given a binary matrix, find out the maximum size square sub-matrix
with all 1s.

For example, consider the below binary matrix.

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

The maximum square sub-matrix with all set bits is

1 1 1
1 1 1
1 1 1

--
You received this message

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-13 Thread atul anand

here is the recurrence for solving this

R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1], R[i,,j-1] ) );

On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma rahul23111...@gmail.comwrote:


  April 4, 2010

 Given a binary matrix, find out the maximum size square sub-matrix with
 all 1s.

 For example, consider the below binary matrix.

0  1  1  0  1
1  1  0  1  0
0  1  1  1  0
1  1  1  1  0
1  1  1  1  1
0  0  0  0  0

 The maximum square sub-matrix with all set bits is

 1  1  1
 1  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.

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-13 Thread rahul sharma

wats d logic behind this???

On Tue, Mar 13, 2012 at 11:59 AM, atul anand atul.87fri...@gmail.comwrote:

 here is the recurrence for solving this

 R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1], R[i,,j-1] )
 );

 On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma rahul23111...@gmail.comwrote:


  April 4, 2010

 Given a binary matrix, find out the maximum size square sub-matrix with
 all 1s.

 For example, consider the below binary matrix.

0  1  1  0  1
1  1  0  1  0
0  1  1  1  0
1  1  1  1  0
1  1  1  1  1
0  0  0  0  0

 The maximum square sub-matrix with all set bits is

 1  1  1
 1  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] Maximum size square sub-matrix with all 1s

2012-03-13 Thread Sourabh Singh

@ ALL

 finding square matrix is quite a standard question and nw an easy one as
everyone knows the reccussence atul has given.
 but  i wanted to find max rectangle..

i know there is a DP for it. in O(n^2). for nxn matrix..don't know the
whole approach .but  here is what i remember..

1. aproach is simple to keep track of max rectangle which can be formed
from any point taking that point as top  left corner of max rectangle and
proceed further down .

can someone suggest how can be proceed further..


[ NOTE: problem occurs mainly when their are more than one rectangles which
can be formed from same point ]

plz.. don't suggest the histogram method it's just a dirty way of avoiding
to work on getting this DP right. :-)


On Mon, Mar 12, 2012 at 11:29 PM, atul anand atul.87fri...@gmail.comwrote:

 here is the recurrence for solving this

 R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1], R[i,,j-1] )
 );


 On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma rahul23111...@gmail.comwrote:


  April 4, 2010

 Given a binary matrix, find out the maximum size square sub-matrix with
 all 1s.

 For example, consider the below binary matrix.

0  1  1  0  1
1  1  0  1  0
0  1  1  1  0
1  1  1  1  0
1  1  1  1  1
0  0  0  0  0

 The maximum square sub-matrix with all set bits is

 1  1  1
 1  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] Maximum size square sub-matrix with all 1s

2012-03-13 Thread atul anand

@ Sourabh: check solution i have posted in below link

http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0

On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh singhsourab...@gmail.comwrote:

@ ALL

finding square matrix is quite a standard question and nw an easy one as
everyone knows the reccussence atul has given.
but i wanted to find max rectangle..

i know there is a DP for it. in O(n^2). for nxn matrix..don't know the
whole approach .but here is what i remember..

1. aproach is simple to keep track of max rectangle which can be formed
from any point taking that point as top left corner of max rectangle and
proceed further down .

can someone suggest how can be proceed further..

[ NOTE: problem occurs mainly when their are more than one rectangles
which can be formed from same point ]

plz.. don't suggest the histogram method it's just a dirty way of avoiding
to work on getting this DP right. :-)

On Mon, Mar 12, 2012 at 11:29 PM, atul anand atul.87fri...@gmail.comwrote:

here is the recurrence for solving this

R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1], R[i,,j-1] )
);

On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma
rahul23111...@gmail.comwrote:

April 4, 2010

Given a binary matrix, find out the maximum size square sub-matrix with
all 1s.

For example, consider the below binary matrix.

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

The maximum square sub-matrix with all set bits is

1 1 1
1 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.

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-03-13 Thread Sourabh Singh

@atul

read it ..

it's good but more or less like the histogram algo.. i wanted a DP.
approach..

here is some of wat i heard from a senior in colg..

1. at every index we can keep 4 variable

ht: height of max rectangle possible at index above current
wt width

hl:height of max rectangle possible at index left of current
wl:

now problem is which one to take for current... index

On Tue, Mar 13, 2012 at 10:52 AM, atul anand atul.87fri...@gmail.comwrote:

@ Sourabh: check solution i have posted in below link

http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=enlnk=gstq=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0

On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh
singhsourab...@gmail.comwrote:

@ ALL

finding square matrix is quite a standard question and nw an easy one as
everyone knows the reccussence atul has given.
but i wanted to find max rectangle..

i know there is a DP for it. in O(n^2). for nxn matrix..don't know the
whole approach .but here is what i remember..

1. aproach is simple to keep track of max rectangle which can be formed
from any point taking that point as top left corner of max rectangle and
proceed further down .

can someone suggest how can be proceed further..

[ NOTE: problem occurs mainly when their are more than one rectangles
which can be formed from same point ]

plz.. don't suggest the histogram method it's just a dirty way of
avoiding to work on getting this DP right. :-)

On Mon, Mar 12, 2012 at 11:29 PM, atul anand atul.87fri...@gmail.comwrote:

here is the recurrence for solving this

R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1], R[i,,j-1]
) );

On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma
rahul23111...@gmail.comwrote:

April 4, 2010

Given a binary matrix, find out the maximum size square sub-matrix with
all 1s.

For example, consider the below binary matrix.

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

The maximum square sub-matrix with all set bits is

1 1 1
1 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.

Re: [algogeeks] Maximum size square sub-matrix with all 1s

2012-01-10 Thread atul anand

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

2012-01-10 Thread Sanjay Rajpal

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] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

Re: [algogeeks] Maximum size square sub-matrix with all 1s

16 matches

Site Navigation

Mail list logo

Footer information