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]
> */
>
>
> #include<iostream>
> #include<conio.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;i<6;i++)
> for(j=0;j<6;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;i<6;i++)
> { for(j=0;j<6;j++)
> { printf(" %d",a[i][j]);
> }
> printf("\n");
> }
> printf("\n\n\n\n\n");
> for(i=0;i<6;i++)
> { for(j=0;j<6;j++)
> { printf(" %d",b[i][j]);
> }
> printf("\n");
> }
> getch();
> return 0;
> }
>
>
> On Wed, Mar 14, 2012 at 11:56 AM, Sourabh Singh
> <singhsourab...@gmail.com>wrote:
>
>> @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.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.com>wrote:
>>>>>>
>>>>>>> @ Sourabh: check solution i have posted in below link
>>>>>>>
>>>>>>>
>>>>>>> http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=en&lnk=gst&q=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.
>>>>>>>>>> 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.
>>>>>>>
>>>>>>
>>>>>>
>>>>> --
>>>>> 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.
>
>
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
