Recursive Matrix Multiplication algorithm failing to calculate

Question

We were given an assignment to use dynamic programming to code a program in C++ for matrix multiplication. He told us to use recursion and gave us a custom written matrix class. I wrote the following recursive algorithm, however I am getting an error when I run that says

Object& Matrix<Object>::at(uint, uint) [with Object = unsigned int, uint = unsigned int]: Assertions 'row < rows && col < cols' failed.

Any ideas as to why this is happening? I included his matrix class and my recursive matrix multiplication method below.

#ifndef MATRIX_H
#define MATRIX_H

#include <cassert>
typedef unsigned int uint;

template <class Object>
class Matrix
{
public:
    Matrix( uint rows, uint cols );
    Object & at( uint row, uint col );
    const Object & at( uint row, uint col ) const;
    ~Matrix();
    Matrix( const Matrix<Object> & m ); // Copy constructor
    Matrix & operator= ( const Matrix<Object> & m );   // Assignment operator
    uint numrows() const;
    uint numcols() const;

private:
    uint rows;
    uint cols;
    Object* data;
};

template <class Object>
Matrix<Object>::Matrix( uint rows, uint cols )
: rows( rows ), cols( cols )
{
    assert( rows > 0 && cols > 0 );
    data = new Object[ rows * cols ];
}

template <class Object>
Matrix<Object>::~Matrix()
{
    delete[] data;
}

template <class Object>
Object & Matrix<Object>::at( uint row, uint col )
{
    assert( row < rows && col < cols );
    return data[ cols * row + col ];
}

template <class Object>
const Object & Matrix<Object>::at( uint row, uint col ) const
{
    assert( row < rows && col < cols );
    return data[ cols * row + col ];
}

template <class Object>
uint Matrix<Object>::numrows() const
{
    return rows;
}

template <class Object>
uint Matrix<Object>::numcols() const
{
    return cols;
}

int minmult( Matrix<uint> & P,
         Matrix<uint> & M,
         const vector<uint> & d,
         uint i,
         uint j )
{


if( M.at(i,j) != INF )
{
    return M.at(i,j);               //already has been defined
}
else if( i == j )
{
    M.at(i,j) = 0;                  //base case
}
else
{
    //M.at(i,j) = UINT_MAX;         //initialize to infinity
    for( uint k = i; k <= j-1; k++)
    {
        uint ops = minmult(P, M, d, i, k)
            + minmult(P, M, d, k+1, j)
            + d.at(i-1)*d.at(k)*d.at(j);
        if( ops < M.at(i,j))
        {
            M.at(i,j) = ops;        
            P.at(i,j) = k;          
        }
    }
}
return M.at(i,j);                  //returns the final cost
}

Answer 1

The error seems to be quite clear, you are calling the at method and passing values for row and col that are not smaller than the number of rows and columns... which is evident in the code:

uint i = M.numcols();
uint j = M.numrows();
if(i == j) {
    M.at(i,j) = 0;    // i == numcols() thus !(i<numcols()) 
                      // j == numrows() thus !(j<numrows())

Assuming that you intended on calling M.at(j,i), that is, since the arguments to at are rows and cols and not the other way around...

Other than that, your recursion step is wrong, since the next step in the recursion does not have a smaller problem than the original (it is actually of exactly the same size, since minmult(M,P,d) calls minmult(M,P,d). Once you fix the assert, this will kick you in the form of a Stack Overflow.

Finally, it is not clear what the intention of the code is, you should take the time to solve the problem with pen and paper, and then map the solution to your programming language of choice.