3 Mountaneous terrains and local maxima You have acquired a map showing the ground elevation at each point of a region, and you want to find a local marimum: a point that is higher than all of the neighbouring points. For the sake of this problem, we will assume that the map is given as an n x n two-dimensional array M, where each element of the array contains a real number M[i][j] that is the ground elevation at point (i,j) in the region. The point (i,j) is higher than its neighbours if M[i, j] > M(i 1,j], M[i, j > M(i +1, j], M[i, j] > M[i, j - 1] and M[i, j] > M[i, j +1] (not all four neigbours may exist when (i,j) is on the boundary of the map). We will further assume that no two points have exactly the same ground elevation. There will always be at least one local maximum: because no two points have exactly the same ground elevation, the point with maximum M[i,j] is uniquely defined, and is a local maximum. It is however possible that many local maxima exist (there can be as many as N(na) of them). Dr. Isulo, an alien computer scientists, suggests the following algorithm: Start at an arbitrary point (i, j). While the current point is not a local maximum, move to its neighbour with the highest ground elevation. 2. [3 marks] Show how to construct a n x n map where Dr. Isulos algorithm will run in O(n) time. Hint: think of a shape that's a 6 letter word starting with 's'. 3. [6 marks] Design an O(n) time prune and search algorithm that takes the map M as input, and returns a point (i,j) that is a local maximum. Hint: use four subproblems and spend O(n) time determining which one to recurse on. 3 Mountaneous terrains and local maxima You have acquired a map showing the ground elevation at each point of a region, and you want to find a local marimum: a point that is higher than all of the neighbouring points. For the sake of this problem, we will assume that the map is given as an n x n two-dimensional array M, where each element of the array contains a real number M[i][j] that is the ground elevation at point (i,j) in the region. The point (i,j) is higher than its neighbours if M[i, j] > M(i 1,j], M[i, j > M(i +1, j], M[i, j] > M[i, j - 1] and M[i, j] > M[i, j +1] (not all four neigbours may exist when (i,j) is on the boundary of the map). We will further assume that no two points have exactly the same ground elevation. There will always be at least one local maximum: because no two points have exactly the same ground elevation, the point with maximum M[i,j] is uniquely defined, and is a local maximum. It is however possible that many local maxima exist (there can be as many as N(na) of them). Dr. Isulo, an alien computer scientists, suggests the following algorithm: Start at an arbitrary point (i, j). While the current point is not a local maximum, move to its neighbour with the highest ground elevation. 2. [3 marks] Show how to construct a n x n map where Dr. Isulos algorithm will run in O(n) time. Hint: think of a shape that's a 6 letter word starting with 's'. 3. [6 marks] Design an O(n) time prune and search algorithm that takes the map M as input, and returns a point (i,j) that is a local maximum. Hint: use four subproblems and spend O(n) time determining which one to recurse on