In this lab, you will design and implement algorithms to solve the matrix search problemfinding the maxima of each row in the matrix. The problem is disguised as different problems in many applications. They include breaking paragraphs into lines, sequence alignment, RNA secondary structure prediction, and image thresholding.

1 The matrix search problem

The matrix search problem finds the maxima of each row in a matrix.

Input: an m n matrix

Output: the maximum element of each row, marked in red.

2 A bruteforce iterative solution

This algorithm searches for the maxima row by row. On each row, it linearly scans each element to find the maximum. The runtime is apparently O(mn). Implement this algorithm using a C++ program. Please define your function as follows:

template<typename T>

vector<T> find_row_maxima_itr(const matrix<T> & m)

{

// Your code here

}

//[[Rcpp::export]] vector<double> row_maxima_itr

(const vector<double> & v, size_t nrow, size_t ncol)

{ matrix<double> mat(v, nrow, ncol); return find_row_maxima_itr(mat);

}

The input matrix is represented in the vector v column by column (not row by row). This choice is made so that the R matrix class can be passed to the C++ vector class without any data type conversion, saving time. Internally in R, a matrix is already stored as a columnmajor vector.

This function uses a C++ template matrix class given in the skeleton code file MatrixSearch-Skeleton.cpp.

3 Divideandconquer monotonic matrices

Let j(i) define the smallest column index to the maximum element in row i. A matrix is monotone if for any i₁ < i₂, j(i₁) j(i₂). In the following example

we have the following column positions of the row maxima j(0) = 1 j(1) = 1 j(2) = 2 j(3) = 4 j(4) = 4 j(5) = 4

Please note that the column indices of the row maxima are nondecreasing (1, 1, 2, 4, 4, 4), but the row maximum values are not necessarily increasing. In this example, they are 4, 8, 1, 2.5, 3, 10the row maximum values can go up and down.

For a monotonic matrix, we can perform divideandconquer on the rows to solve the matrix search problem much faster than the bruteforce iterative solution. Please design a divideandconquer strategy to achieve a runtime of O(n lg m), using the following template

template<typename T>

vector<T> find_row_maxima(const matrix<T> & m)

{

// Your divide-and-conquer code here

}

//[[Rcpp::export]] vector<double> row_maxima

(const vector<double> & v, size_t nrow, size_t ncol)

{ matrix<double> mat(v, nrow, ncol); return find_row_maxima(mat);

}

4 Test the two functions

Develop a C/C++ test function to include five examples to check your functions. If a function passes the tests, minimal output should be displayed on the screen to indicate success otherwise, point out which example the function failed. This test function should take a function parameter so that it can test both of your functions, defined as follows:

bool test_row_maxima

(vector<double> (*rmfun) (const vector<double> & v, size_t nrow, size_t ncol))

{

// Example 1 bool passed = true;

/* Monotonic matrix example 1:

0, 4, -1, 2.5, -4,

-3, 8, -10, 2, 7,

-4, -3, -1, -100, -5.5,

0, 2, 0.3, -3, 2.5,

1, 0, 1, 2, 3,

-8, 9, 2, 5, 10};

*/

// x is column major vectorization of the matrix double x[] = { 0, -3, -4, 0, 1, -8, 4, 8, -3, 2, 0, 9,

-1, -10, -1, 0.3, 1, 2,

2.5, 2, -100, -3, 2, 5,

-4, 7, -5.5, 2.5, 3, 10};

vector<double> v(x, x+30); double rmax_truth[] = {4, 8, -1, 2.5, 3, 10};

if(rmfun(v, 6, 5) != vector<double>(rmax_truth, rmax_truth+6)) {

cout << ERROR: failed test 1! << endl; passed = false;

}

// Example 2

// Example 5 return passed;

}

//[[Rcpp::export]] bool testall()

{ bool passed = true; if(!test_row_maxima(row_maxima_itr)) {

cout << ERROR: row_maxima_itr() failed some test! << endl; passed = false;

} if(!test_row_maxima(row_maxima)) { cout << ERROR: row_maxima() failed some test! << endl; passed = false;

}

if(passed) {

cout << All tests passed. Congratulations! << endl;

}

return passed;

}

Your C++ program must include a main() function that calls the testall() function. When the program is compiled by a C++ compiler it generates a binary executable file that will run when invoked from the command line.

5 Visualize the runtime of the two methods

Develop R code inside your C++ source code file to generate runtime report on the two functions you developed.

You should use the following R function to generate any sized monotonic matrix: random.monotone.matrix(nrow, ncol)

which is already provided in the skeleton code. In the runtime evaluation you can focus on testing square matrices (m = n).

You will generate one plot containing four curves as shown in Figure 1. It shows both empirical runtime and estimated theoretical runtime. Your code will estimate the coefficients c₁ and c₂ so that you can plot the theoretical curves fitted to the runtime data.

You need to call the testall() function first. If the test failed, visualization should not proceed and you must fix the code first.