Question

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

For Design and Analysis of the Algorithme lecture

Answer 1

Peak finder in a 2D array means to find out the largest or equal values of an element when comparing with the neighboring elements lying in top,bottom,left and right in the matrix.For corner elements neighbour values are considered nil for the missing ones.

for eg: 20 40 4

2 9 6

4 11 9

here peak value is 40 and 11 because all its neigbours are smaller or equal to it.

Here goes the c++ code:

using namespace std;

const int ROWS=10; //initialise

const int COLS=10;

void init_array(int arr[][COLS]);

void print_array(int arr[][COLS]);

void find_peak(int arr[][COLS]);

int main()

{

int myArr[ROWS][COLS];

init_array(myArray);

print_array(myArray);

find_peak(myArray);

system("pause");

return 0;

}

void init_array(int arr[][COLS])

{

srand(time(0));

for(int i=0;i<ROWS;i++)

for(int j=0;i<COLS;j++)

arr[i][j]=rand();

}

void print_array(int arr[][COLS])

{

  for(int i=0;i<ROWS;i++)

{

for(int j=0;i<COLS;j++)

cout<<arr[i][j]<<"\t";

cout<<endl

}

}

void find_peak(int arr[][COLS]) //finding peakvalue function

{

int current=0;

int peakCounter=0;

int minPeakCounter=0;

for(int i=1;i<ROWS-1;i++)

for (j=1;j<COLS-1;j++)

{

current=arr[i][j];

for(int k=i-1;k<=i+1;k++)

{

for(int l=j-1;l<=j+1;l++)

{

if (arr[k][l]>current)

minPeakCounter++;

}

}

if (peak counter==8)

count<<"Peak at("<<i<<","<<j<<")"<<endl;

if(minPeak counter==8)

vcount<<"minPeak at("<<i<<","<<j<<")"<<endl;

peakCounter=0;

minpeakCounter=0;

}}

YOu can refer to the attached diagram to understand better.