PLEASE ANSWER PART 3

Problem 2: (page limit: 3 pages) You are given an n x n matrix A with unknown values and your goal is to find an entry that is a local maximum with smallest number of queries to individual entries. An entry Aij is a local maximum if it is not smaller than any of its neighbors (top, bottom, left or right if they exist) i.e. Ajj = max{Ai,j, Ai-1,j, Aij-1, Ai+1,j, Ai,j+1}. You only need to find a local maximum, not the global maximum. Note that there may be multiple local maxima. Try out your strategy at the following link (solve this version in 90 or fewer queries): https://tzamos.com/ pf.html?N=30&M=30. 1. Design an algorithm to find a local maximum in O(n) number of queries. (Hint: Start by thinking about a strategy for the ID array first, and then extend it to the 2D setting.) 2. Prove the correctness of your algorithm. 3. Analyze the time complexity of your algorithm by finding a recurrence for the number of queries and solving it. You don't need to show your work for this part. Problem 2: (page limit: 3 pages) You are given an n x n matrix A with unknown values and your goal is to find an entry that is a local maximum with smallest number of queries to individual entries. An entry Aij is a local maximum if it is not smaller than any of its neighbors (top, bottom, left or right if they exist) i.e. Ajj = max{Ai,j, Ai-1,j, Aij-1, Ai+1,j, Ai,j+1}. You only need to find a local maximum, not the global maximum. Note that there may be multiple local maxima. Try out your strategy at the following link (solve this version in 90 or fewer queries): https://tzamos.com/ pf.html?N=30&M=30. 1. Design an algorithm to find a local maximum in O(n) number of queries. (Hint: Start by thinking about a strategy for the ID array first, and then extend it to the 2D setting.) 2. Prove the correctness of your algorithm. 3. Analyze the time complexity of your algorithm by finding a recurrence for the number of queries and solving it. You don't need to show your work for this part