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 wrote: > "sort the whole matrix in ascending array" means? > can you please explain ? > > > On Wed, Jan 11, 2012 at 12:53 PM, atul anand wrote: > >> 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.
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 wrote: > 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.
[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] Re: MS Q
@Umer : it has 1 island ashish made editing mistake before. On Wed, Jan 11, 2012 at 11:58 AM, Umer Farooq 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 wrote: > >> 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 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 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 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 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 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 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://gro
Re: [algogeeks] Re: MS Q
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 wrote: > 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 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 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 >>> >>> 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 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 >>> 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 >>> 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.
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 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 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 >> >> 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 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 >> 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 >> 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: 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 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 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 > 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 >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.
[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 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 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 > > 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.
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 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 > > 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 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 > 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 > 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: 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 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 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 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 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.
[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 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: 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 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 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 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 > > > 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.. 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 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 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 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] 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 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 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.
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 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.
[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] 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 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 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 > 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.
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 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 wrote: > >> 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.
[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 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 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 wrote: > > @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.
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 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] 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 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 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] 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.
[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
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 wrote: > 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: 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 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 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 > > > #include > > > 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;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 > > wrote: > > > > @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
@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 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 > > #include > > 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;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 > wrote: > > > > > > > > > @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] 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 #include 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;i=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 wrote: > @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.
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] C QUESTION???
thanks for the info -- 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/-/E1c87OjP6LAJ. 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 wrote: > @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
@Ramakant : for which test case your code would fail?? On Tue, Jan 10, 2012 at 1:04 PM, Ramakant Sharma wrote: > @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] 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 wrote: > 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 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 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] 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.