data stracture 9

CSC 240

Extra Credit (+5 points)

Peak Min/Peak Max

Use recursion to find all of the peak min/peak max elements of an 𝑀 ×𝑁 matrix.

Modify the CSC240_PeakMinMaxRecursion.cpp file provided in Extra Files under Content in D2L.

Here are the contents of that file:

#include <iostream> using namespace std; #define M 4 #define N 3 int arr[M][N] = { {10, 8, 10, 10}, {14, 13, 12, 11}, {15, 9, 11, 21}, {16, 17, 19, 20} }; int findMaxMid(int rows, int mid, int& max) { int maxIndex = 0; //find max element in the mid column for (int i = 0; i < rows; i++) { if (max <arr[i][mid]) { max = arr[i][mid]; maxIndex = i; } } return maxIndex; } int findPeakElement(int rows, int columns, int mid) { int maxMid = 0; int maxMidIndex = findMaxMid(rows, mid, maxMid); //for first and last column, the maxMid is maximum if (mid == 0 || mid == columns-1) return maxMid; // If maxMid is also peak if (maxMid>= arr[maxMidIndex][mid-1] && maxMid>= arr[maxMidIndex][mid+1]) return maxMid; // If maxMid is less than its left element if (maxMid < arr[maxMidIndex][mid-1]) return findPeakElement(rows, columns, mid - mid/2); return findPeakElement(rows, columns, mid+mid/2); } int main() { int row = 4, col = 4; cout << "The peak element is: " << findPeakElement(row, col, col/2); }

Your updated implementation of the peak min/peak max algorithm is to print all peak min and peak max

elements found within the matrix. Therefore, the return type of findPeakElement should be void.

Solve the peak min/peak max problem recursively, such that diagonal elements are considered neighbors and all peak min and peak max elements are found. Also, these peak min/max elements are strictly greater than or strictly less than their neighbors. This can be solved using the 2D array or an extended 1D array. The solution provided above solves a peak min/peak max problem that only considers a single peak value, non-diagonal neighbors are considered, and a peak element is allowed to be equal to a neighbor. The implementation provided above can be used as a starting point, but is not to be considered the solution.

Consider the following matrix:

10 8 10 10

14 13 12 11

15 9 11 21

18 17 19 20

The peak min elements are: 8 and 9

The peak max elements are: 18 and 21