can we apply lcs on 2-d array and 1-d array ........ correct me ig i am
right complexity is high too
On Tue, Nov 8, 2011 at 4:21 AM, vikas <vikas.rastogi2...@gmail.com> wrote:
> probably you are mistaken about the complexity calculations,
> the above algo will search for the first element in the 2D matrix,
> and if you look carefully , at max n-1 match for each unsuccessful 1D
> combination is done
> hence complexity goes to n(n-1) or O(n^2) at max with space complexity
> O(n).
> BTW, I did not get your idea of reducing complexity , can you describe
> it in detail ?
>
> On Nov 4, 8:41 am, surender sanke <surend...@gmail.com> wrote:
> > @vikas
> >
> > ur algo will search for 1st element of 1d in whole 2d array,
> > on worst case u'll search it in n^2, then search for all 1d elements
> > in 2d in O(n)
> > so whole complexity goes to O(n^2 +n)
> > it can be reduced if we use hashing of 1d array, and count_found
> > and while searching for 1st element of 1d in 2d array, if it's found
> > make temp[i][j] as true(even though its not first element) and false
> > if its not in 1d hash, and increase count_found
> > this will reduce to O(n^2)
> >
> > surender
> >
> > On 11/1/11, vikas <vikas.rastogi2...@gmail.com> wrote:
> >
> > > ok,
> > > so do it like this;
> > > 1. create boolean array
> > > boolean temp[][] = new boolean[row][column];
> > > init(temp, true);
> >
> > > 2. traverse the array for the 1d array of 0th index and then a
> > > recursive search
> > > if search fails, or position already contains false, return and search
> > > again
> >
> > > boolean search(int searchArray[][], int givenArray[], int rpos, int
> > > cpos, int gpos){
> > > if(gpos > givenArray.len) return false;
> > > if(temp[rpos][cpos] == false) return false;
> > > if(searchArray[rpos][cpos] == givenArray[gpos])
> > > {
> > > temp[rpos][cpos] = search(searchArray, givenArray, rpos
> > > +1, cpos, gpos+1)|
> > > search(searchArray,
> > > givenArray, rpos-1, cpos, gpos+1) |
> > > search(searchArray,
> > > givenArray, rpos, cpos+1, gpos+1)|
> > > search(searchArray,
> > > givenArray, rpos+1, cpos-1, gpos+1)
> > > }
> > > if(temp[rpos][cpos]) return true;
> > > if(cpos < searchArray.len)
> > > search(searchArray, givenArray, rpos, cpos+1, 0);
> > > else
> > > search(searchArray, givenArray, rpos+1, 0, 0);
> >
> > > }
> >
> > > On Nov 1, 4:25 pm, SAMM <somnath.nit...@gmail.com> wrote:
> > >> For example :-
> >
> > >> 2d array ::
> >
> > >> 1 2 3 4 5 6
> > >> 7 8 9 10 11 12
> > >> 13 14 15 16 17 18
> > >> 19 20 21 22 23 24
> >
> > >> we hav 1d array as :-- 13 2 21 10 23 12
> >
> > >> So the 1d array is a subset of 2d array ...
> >
> > >> On 11/1/11, vikas <vikas.rastogi2...@gmail.com> wrote:
> >
> > >> > what do you mean by subset of 1D present in the 2D array? is it
> > >> > something like 3245 , the search may be 3245/ 24/ 45/ .... all 16
> > >> > subsets need to be searched?
> >
> > >> > On Oct 28, 12:02 pm, SAMMM <somnath.nit...@gmail.com> wrote:
> > >> >> How do u plan to implement it ???
> >
> > >> > --
> > >> > 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.
> >
> > >> --
> > >> 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.
>
> --
> 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.
>
>
--
*UTKARSH SRIVASTAV
CSE-3
B-Tech 3rd Year
@MNNIT ALLAHABAD*
--
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.
