a Problem 3. (2 points) In this problem we will consider the problem of finding a "hill” in a 2D array A. This is define

[answerhappygod]

A Problem 3 2 Points In This Problem We Will Consider The Problem Of Finding A Hill In A 2d Array A This Is Define 1 (67.53 KiB) Viewed 41 times

a Problem 3. (2 points) In this problem we will consider the problem of finding a "hill” in a 2D array A. This is defined to be an entry A[i, j], such that A[i, j] > A[i, j - 1], A[i, j] > A[i, j + 1], A[i, j] > A[i – 1,j], A[i, j] > A[i+1, j]. That is, A[i, j] has to be larger than all of its neighbors, ignoring the diagonal neighbors. Assume for simplicity that all of the entries of A are unique. = 3.1 (1 point) Give a proof of correctness for the following algorithm and prove that it runs in time O(n log n). hill2D(A, i, j) 1. Find the maximum element of column m= [(i+1)/2]. Assume it's Aſk, m]. 2. If A[k, m] > A[k, m + 1) and Aſk, m] > A[k, m – 1), return Aſk, m]. 3. Else if A[k, m] <A[k, m +1], return hill2D(A, m+1,j) 4. Else return hill2D(A, i, m - 1)