CODEWITHSUNDEEP
c++recursionmatrixdivide-and-conquer
user3461126
user3461126

Reputation: 25

Divide and conquer algorithm: find the minimum of a matrix

I'm starting to learn how to implement divide and conquer algorithms, but I'm having some serious trouble with this exercise. I have written an algorithm which finds the minimum value in a given vector using the divide and conquer method:

int minimum (int v[], int inf, int sup)
{
int med, m1, m2;
if (inf == sup)
return v[inf];
med = (inf+sup)/2;
m1 = minimum (v, inf, med);
m2 = minimum (v, med+1, sup);
if (m1 < m2)
return m1;
else
return m2;
}

And it works. Now, I have to do the same exercise on a matrix, but I'm getting lost. Specifically, I have been told to do the following: Let n = 2^k. Consider a nxn square matrix. Calculate its minimum value using a recursive function

double (minmatrix(Matrix M))
return minmatrix2(M, 0, 0, M.row);

(the Matrix type is given, and as you can imagine M.row gives the number of rows and columns of the matrix). Use an auxiliary function

double  minmatrix2(Matrix M, int i, int j, int m)

This has to be done use a recursive divide and conquer algorithm. So.. I can't figure out a way of doing it. I have been given the suggestion of splitting the matrix in 4 parts each time (from (i,j) to (i+m/2, j+m/2), from (i+m/2,j) to (i+m,j+m/2), from (i,j+m/2) to (i+m/2,j+m), from (i+m/2,j+m/2) to (i+m,j+m)) and try to implement a code working in a similar way to the one I have written for the array.. but I just seem to be unable to do it. Any suggestions? Even if you don't want to post a complete answer, just give me some indications. I really want to understand this.

EDIT: All right, I've done this. I'm posting the code I have used just in case someone else has the same doubt. 

double minmatrix2(Matrix M, int i, int j, int m)
{   
    int a1, a2, a3, a4;
    if (m == 1)
    return M[i][j];
    else
    a1 = minmatrix2(M, i, j, m/2);
    a2 = minmatrix2(M, i+(m/2), j, m/2);
    a3 = minmatrix2(M, i, j+(m/2), m/2);
    a4 = minmatrix2(M, i+(m/2), j+(m/2), m/2);
    if (min (a1, a2) < min (a3, a4))
    return min (a1, a2);
    else
    return min (a3, a4);
}

(function min defined elsewhere)

Upvotes: 2

Views: 1962

Answers (1)

John Zwinck
John Zwinck

Reputation: 249502

Consider that a 2D matrix in C or C++ is often implemented as accessor functions on top of a 1D array. You already know how to do this for a 1D array, so the only difference is how you address the cells. If you do this, your performance will intrinsically be optimal because you will address neighboring cells together.

Alternatively, consider that a 2D matrix has two dimensions N and M. Just break it in half along the larger dimension repeatedly until the larger dimension is less than X, some reasonable value to stop and do the actual computation sequentially. This is not entirely optimal because you will have to "skip" over parts of the matrix as you address memory.

A final idea is to divide by the major dimension first, then the minor one. In C this means divide by rows until you have single rows, then run your 1D array algorithm on each row. This produces roughly optimal performance.

Upvotes: 2

Related Questions