6.006- Introduction to AlgorithmsLecture 2Prof. Constantinos DaskalakisMenu• Problem: peak finding– 1 dimension– 2 dimensions• Technique: Divide and conquer• details about the 1stpset in the end of the lecturePeak Finding: 1D• Consider an array A[1…n] :• An element A[i] is a peak if it is not smaller than its neighbor(s). I.e., – if i ≠ 1, n : A[i]≥A[i-1] and A[i]≥A[i+1]– If i=1 : A[1] ≥ A[2]– If i=n : A[n] ≥ A[n-1]• Problem: find any peak.10 13 5 8 3 2 1Peak Finding: Ideas ?• Algorithm I:– Scan the array from left to right– Compare each A[i] with its neighbors– Exit when found a peak• Complexity: – Might need to scan all elements, so T(n)=(n)Peak Finding: Ideas II ?• Algorithm II:• Consider the middle element of the array and compare with neighbors– If A[n/2-1]>A[n/2]then search for a peak among A[1]… A[n/2-1]– Else, if A[n/2]<A[n/2+1]then search for a peak among A[n/2]… A[n]– Else A[n/2] is a peak! (since A[n/2-1]≤A[n/2] and A[n/2] ≥A[n/2+1] )• Running time ?Algorithm II: ComplexityAlgorithm II: Complexity• We have• Unraveling the recursion, T(n)= (1) + (1) +…+ (1) = (log n)• log n is much much better than n !RecursionTime for comparing A[n/2] with neighborslog2nT(n)= T(n/2) + (1)Time needed to find peak in array of length nDivide and Conquer• Very powerful design tool:– Divide input into multiple disjoint parts– Conquer each of the parts separately (using recursive call)• Occasionally, we need to combine results from different calls (not used here)• Consider a 2D array A[1…n, 1…m] :• An element A[i] is a 2D peak if it is not smaller than its (at most 4) neighbors.• Problem: find any 2D peak.Peak Finding: 2D10 8 53 2 17 136 8432D Peak Finding: Ideas?Algorithm I: use the 1D algorithm• Algorithm I:– For each column j, find its global maximum B[j]– Apply 1D peak finder to find a peak (say B[j]) of B[1...m]• Running time ?…is (nm)• Correctness:– B[j] not smaller than B[j-1], B[j+1]– For any k, B[k] not smaller than any element from the k-th column of A– Therefore, B[j] not smaller than any element from the columns j-1, j and j+1 of A– But this includes all neighbors of B[j] in A, so B[j] is a peak in A12 8 511 310 9628 4 112 9 6Algorithm I’: use the 1D algorithm• Observation: 1D peak finder uses only O(log m) entries of B• We can modify Algorithm I so that it only computes B[j] when needed !• Total time ?…only O(n log m) !– Need O(log m) entries B[j]– Each computed in O(n) time12 8 511 310 9628 4 112 9 6Algorithm II• Pick middle column ( j=m/2 )• Find global maximum a=A[i,m/2] in that column(and quit if m=1)• Compare a to b=A[i,m/2-1] and c=A[i,m/2+1]• If b>a then recurse on left columns• Else, if c>athen recurse on right columns• Else a is a 2D peak!ab cAlgorithm II: Example12 8 511 310 9628 4 1912a cb• Pick middle column ( j=m/2 )• Find global maximum a=A[i,m/2] in that column(and quit if m=1)• Compare a to b=A[i,m/2-1] and c=A[i,m/2+1]• If b>a then recurse on left columns• Else, if c>athen recurse on right columns• Else a is a 2D peak!Algorithm II: Correctness• Claim: If b>a, then there is a peak among the left columns• Proof (by contradiction):– Assume no peak on the left– Then b must have a neighbor b1 with higher value– And b1 must have a neighbor b2 with higher value– …– We have to stay on the left side – why?– (because we cannot enter the middle column)– But at some point, we would run out the elements of the left columns – Hence, we have to find a peak at some point12 8 511 310 9628 4 19abb1b2Algorithm II: Complexity• We haveT(n,m)= T(n,m/2) + (n)• Hence:• T(n,n)= (n) + (n) +…+ (n)RecursionScanning middle columnlog2m= (nlog m)Faster than O(n log n) ?• Idea:• Pictorially:read only O(n +m) elementsReading only O(n + m) elements, reduce an array ofcandidates to an array of candidatesFaster than O(n log n) ?• Hypothetical algorithm has recursion:• Hence:!Towards a linear-time algorithmWhat elements are useful to check?- suppose we find global max on the crossTowards a linear-time algorithmWhat elements are useful to check?- suppose we find global max on the cross- if middle element done!Towards a linear-time algorithmWhat elements are useful to check?- find global max on the cross- if middle element done!- o.w. two candidate sub-squares- determine which one to pick by looking at its neighbors not on the cross (as in Algorithm II)??Claim: The sub-square chosen by the above procedure (if any), always contains a peak of the large square.BUT: Claim 2: Not every peak of the chosen sub-square is necessarily a peak of the large square. Hence, it is hard to recurse…proof of claim 2 and fix to this algorithm provided in recitationFirst Problem Set• out tonight, by 9pm– part A: theory, due at 11.59pm, Sept 21st– part B: implementation, due at 11.59pm, Sept 23rd• deadline policy:– 6 days of credit can be used for delayed homework submission– at most 2 days can be used for the same deadline (total of 12 deadlines: 6psets x 2parts)• details on the class
View Full Document
Unlocking...