Algorithms, Java You are given an n-by-n grid of distinct numbers. A number is a

Question

Algorithms, Java

You are given an n-by-n grid of distinct numbers. A number is a local minimum if it is smaller than all its neighbors. (A neighbor of a number is one immediately above, below, to the left, or to the right. Most numbers have four neighbors; numbers on the side have three; the four corners have two.) Use the divide-and-conquer algorithm design paradigm to compute a local minimum with only O(n) comparisons between pairs of numbers. (Note: since there are n^2 numbers in the input, you cannot afford to look at all of them.)

[Hint: Figure out how to recurse on an (n/2)-by-(n/2) grid after doing only O(n) work.]

Explanation / Answer

According to the above provided problem.I have developed an algorithm which fairly simple and follows recursion as listed above.Here we go,

Algorithm:

x=0 , where x is row index of the element obtained above
y=0 , where y is column index of the element obtained above
localMinimum(x,y)
minimum{ A[x][y], A[i-1][j-1], A[i][j+1], A[i+1][j] }
localMinimum(x,y)

Hence, the above algorithm can be used to develop an solution for the problem.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.