Question

(Can you answer my question by explaining, I mean that step by step. I don't want a short answer. Be sure to I like it if you write step by step

For Design and Analysis of the Algorithme lecture)

Peak Finding

Implement the 2-D peak finder mentioned and explain the asymptotic complexity of the algorithm.

Answer 1

An element is a peak element if it is greater than or equal to its four neighbors, left, right, top and bottom. For example neighbors for A[i][j] are A[i-1][j], A[i+1][j], A[i][j-1] and A[i][j+1]. For corner elements, missing neighbors are considered of negative infinite value.

Example:

Input : 10 20 15
21 30 14
7 16 32
Output : 30
30 is a peak element because all its neighbors are smaller or equal to it.
32 can also be picked as a peak.

Algorithm :

1)Consider mid column and find maximum element in it.

2)Let index of mid column be ‘mid’, value of maximum element in mid column be ‘max’ and maximum element be at ‘mat[max_index][mid]’.

3)If max >= A[index][mid-1] & max >= A[index][pick+1], max is a peak, return max.

4)If max < mat[max_index][mid-1], recur for left half of matrix.

5)If max < mat[max_index][mid+1], recur for right half of matrix.

Time Complexity : O(rows * log(columns)). We recur for half the number of columns. In every recursive call, we linearly search for the maximum in the current mid column.

Auxiliary Space: O(columns/2) for Recursion Call Stack.

Code:

// Finding peak element in a 2D Array.
#include <bits/stdc++.h>

using namespace std;

const int MAX = 100;

// Function to find the maximum in column 'mid'
// 'rows' is number of rows.

int findMax(int arr[][MAX], int rows, int mid, int& max)
{

int max_index = 0;

for (int i = 0; i < rows; i++) {

if (max < arr[i][mid]) {

// Saving global maximum and its index

// to check its neighbours

max = arr[i][mid];

max_index = i;

}

}

return max_index;
}

// Function to find a peak element

int findPeakRec(int arr[][MAX], int rows, int columns,

int mid)
{

// Evaluating maximum of mid column. Note max is

// passed by reference.

int max = 0;

int max_index = findMax(arr, rows, mid, max);

// If we are on the first or last column,

// max is a peak

if (mid == 0 || mid == columns - 1)

return max;

// If mid column maximum is also peak

if (max >= arr[max_index][mid - 1] && max >= arr[max_index][mid + 1])

return max;

// If max is less than its left

if (max < arr[max_index][mid - 1])

return findPeakRec(arr, rows, columns, mid - ceil((double)mid / 2));

// If max is less than its left

// if (max < arr[max_index][mid+1])

return findPeakRec(arr, rows, columns, mid + ceil((double)mid / 2));
}

// A wrapper over findPeakRec()

int findPeak(int arr[][MAX], int rows, int columns)
{

return findPeakRec(arr, rows, columns, columns / 2);
}

int main()
{

int arr[][MAX] = { { 10, 8, 10, 10 },

{ 14, 13, 12, 11 },

{ 15, 9, 11, 21 },

{ 16, 17, 19, 20 } };

// Number of Columns

int rows = 4, columns = 4;

cout << findPeak(arr, rows, columns);

return 0;
}

Output :

21.

Please do upvote thank you.