6.006 Intro to Algorithms Recitation 02 February 4, 20111D Peak FindingObjectiveGiven an array A with n elements, find the index i of the peak element A[i] where A[i] ≥ A[i − 1]and A[i] ≥ A[i + 1]. For elements on the boundaries of the array, the element only needs to begreater than or equal to its lone neighbor to be considered a peak. Or, say A[−1] = A[n] = ∞.AlgorithmGiven an array A with n elements:• Take the middle element of A, A[n2], and compare that element to its neighbors• If the middle element is greater than or equal to its neighbors, then by definition, that elementis a peak element. Return its indexn2.• Else, if the element to the left is greater than the middle element, then recurse and use thisalgorithm on the left half of the array, not including the middle element.• Else, the element to the right must be greater than the middle element. Recurse and use thisalgorithm on the right half of the array, not including the middle element.Runtime AnalysisWhen we recurse, we reduce size n array into sizen2array in O(1) time (comparison of middleelement to neighbors). Show recursion in the form of “Runtime of original problem” =“Runtimeof reduced problem” + “Time taken to reduce problem”. Then use substitution to keep reducingthe recursion.6.006 Intro to Algorithms Recitation 02 February 4, 2011T (n) = T (n2) + c (1)T (n) = T (n4) + c + c (2)T (n) = T (n8) + c + c + c (3)T (n) = T (n2k) + ck (4)Substitute k = log2n (5)T (n) = T (n2log2n) + c log2n (6)= T (1) + c log2n (7)= O(log n) (8)2D Peak FindingObjectiveGiven an nxn matrix M , find the indices of a peak element M[i][j] where the element is greaterthan or equal to its neighbors, M[i + 1][j], M[i − 1][j], M[i][j + 1], andM[i][j − 1]. For elementson the boundaries of the matrix, the element only needs to be greater than or equal to the neighborsit has to be considered a peak.AlgorithmGiven an nxn matrix M :• Take the ”window frame” formed by the first, middle, and last row, and first, middle, andlast column. Find a maximum element of these 6n elements, g = M [i][j].• If g is greater than or equal to its neighbors, then by definition, that element is a peak element.Return its indices (i, j).• Else, there’s an element that neighbors g that is greater than g. Note that this element can’tbe on the window frame since g is the maximum element on the window frame, thus thiselement must be in one of the four quadrants. Recurse and use this algorithm on the matrixformed by that quadrant (not including any part of the window frame)6.006 Intro to Algorithms Recitation 02 February 4, 2011Proof of CorrectnessClaim 1: If you recurse on a quadrant, there is indeed a global peak in that quadrant.Proof: The quadrant we selected contains an element larger than g. Thus we know that themaximum element in this quadrant must also be larger than g. Since g is the maximum elementsurrounding this quadrant, the maximum element in this quadrant must be larger than any elementsurrounding this quadrant. This element must be greater than or equal to all of its neighbors sinceit is greater than all elements within the quadrant and directly outside of the quadrant, so the max-imum element in this quadrant must be a global peak.Claim 2: If you find a peak on the submatrix, then that peak is a global peak.Proof: The window frame of the submatrix contains an element larger than g. Say m is themaximum element on the window frame. Since g is the largest element directly surrounding thesubmatrix, that means m is larger than all the elements surrounding the submatrix. If m is a peakin the submatrix and m is on the boundary, m must be a global peak since it is guaranteed that mis greater than any neighbors outside the scope of the submatrix. If m is a peak in the submatrixand m is not on the boundary, then clearly m is greater than or equal to its four neighbors and thusis a global peak.Claim 3: You will always find a peak on the submatrix6.006 Intro to Algorithms Recitation 02 February 4, 2011Proof: In the case that we don’t find a peak on the window frame of a matrix, we recurse totry to find a peak in a strictly smaller matrix. Eventually, if you keep not finding a peak, you willrecurse into a small enough matrix such that the window frame covers the entire matrix (i.e. if thenumber of rows and columns are both 3 or below). By claim 1, there is indeed a global peak inthis matrix if we recursed down to it. Since we’re examining the entire matrix, we must find thatglobal peak.By claim 2 and claim 3, using this algorithm, we will always find a peak and that peak will bea global peak.Runtime AnalysisWhen we recurse, we reduce nxn matrix inton2xn2matrix in O(n) time (finding the maximum of6n elements). Show recursion in the form of “Runtime of original problem” =“Runtime of reducedproblem” + “Time taken to reduce problem”. Then use substitution to keep reducing the recursion.T (n) = T (n2) + cn (9)T (n) = T (n4) + cn2+ cn (10)T (n) = T (n8) + cn4+ cn2+ cn (11)T (n) = T (1) + cn(1 +12+14+18...) (12)= O(n)
View Full Document
Unlocking...