Problem 2 Consider an n x n grid: all points in the plane with integer coordinates (x, y) with 0 h(vo). If yes, go there. Repeat this to get to V2, V3, ... until you reach a local maximum. 3. Here is an algorithm of the divide-and-conquer type. For simplicity assume that n is of the form 2k, so we will not have problems dividing repeatedly by 2. Consider the vertical line consisting of points of the form (n/2, y). Find the vertex vi on this line with the largest value of h(v). Now if h(vi) is a local maximum we are done. Else vi has either a left neighbor or a right neighbor with a larger h value. Suppose for example that it is on the left, then we will continue the search on the left half. Consider a horizontal line of vertices the form (x, n/2), in this left half, and find the vertex V2 on it with the largest value of h(U). If it is a local maximum we are done. Else v2 has either an upper neighbor or a lower neighbor with a larger h value. Suppose for example that it is an upper neighbor, then the problem is reduced to the top left quarter of the original square: a square of size n/2. Call the algorithm recursively on this square. (a) (5 points) Show an example in which Algorithm 2 takes 12(n) steps. (b) (10 points) Write up a recursive estimate for the running time of Algorithm 3. (c) (10 points) Solve this recursion, showing that the running time of Algorithm 3 is O(n). Problem 2 Consider an n x n grid: all points in the plane with integer coordinates (x, y) with 0 h(vo). If yes, go there. Repeat this to get to V2, V3, ... until you reach a local maximum. 3. Here is an algorithm of the divide-and-conquer type. For simplicity assume that n is of the form 2k, so we will not have problems dividing repeatedly by 2. Consider the vertical line consisting of points of the form (n/2, y). Find the vertex vi on this line with the largest value of h(v). Now if h(vi) is a local maximum we are done. Else vi has either a left neighbor or a right neighbor with a larger h value. Suppose for example that it is on the left, then we will continue the search on the left half. Consider a horizontal line of vertices the form (x, n/2), in this left half, and find the vertex V2 on it with the largest value of h(U). If it is a local maximum we are done. Else v2 has either an upper neighbor or a lower neighbor with a larger h value. Suppose for example that it is an upper neighbor, then the problem is reduced to the top left quarter of the original square: a square of size n/2. Call the algorithm recursively on this square. (a) (5 points) Show an example in which Algorithm 2 takes 12(n) steps. (b) (10 points) Write up a recursive estimate for the running time of Algorithm 3. (c) (10 points) Solve this recursion, showing that the running time of Algorithm 3 is O(n)