RankSelection ProblemSelection By SortingD&C Selection ExampleSlide 6Time ComplexityClosest Pair Of PointsApplicationsAir Traffic ControlSimple SolutionDivide-And-Conquer SolutionExampleSlide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22RankRank of an element is its position in ascending key order.[2,6,7,8,10,15,18,20,25,30,35,40]rank(2) = 0rank(15) = 5rank(20) = 7Selection Problem•Given n unsorted elements, determine the k’th smallest element. That is, determine the element whose rank is k-1.•ApplicationsMedian score on a test.•k = ceil(n/2).Median salary of Computer Scientists.Identify people whose salary is in the bottom 10%. First find salary at the 10% rank.Selection By Sorting•Sort the n elements.•Pick up the element with desired rank.•O(n log n) time.D&C Selection ExampleUse 3 as the pivot and partition.rank(pivot) = 5. So pivot is the 6’th smallest element.Find kth element of:3 2 8 0 11 10 1 2 9 7 1a1 2 1 0 2 4 11 9 7 83 10aD&C Selection Example•If k = 6 (k-1 = rank(pivot)), pivot is the element we seek.•If k < 6 (k-1 < rank(pivot)), find k’th smallest element in left partition.•If k > 6 (k-1 > rank(pivot)), find (k-rank(pivot)-1)’th smallest element in right partition.1 2 1 0 2 4 11 9 7 83 10aTime Complexity•Worst case arises when the partition to be searched always has all but the pivot.O(n2)•Expected performance is O(n).•Worst case becomes O(n) when the pivot is chosen carefully.Partition into n/9 groups with 9 elements each (last group may have a few more)Find the median element in each group.pivot is the median of the group medians.This median is found using select recursively.Closest Pair Of Points•Given n points in 2D, find the pair that are closest.Applications•We plan to drill holes in a metal sheet. •If the holes are too close, the sheet will tear during drilling.•Verify that no two holes are closer than a threshold distance (e.g., holes are at least 1 inch apart).Air Traffic Control•3D -- Locations of airplanes flying in the neighborhood of a busy airport are known.•Want to be sure that no two planes get closer than a given threshold distance.Simple Solution•For each of the n(n-1)/2 pairs of points, determine the distance between the points in the pair.•Determine the pair with the minimum distance.•O(n2) time.Divide-And-Conquer Solution•When n is small, use simple solution.•When n is largeDivide the point set into two roughly equal parts A and B.Determine the closest pair of points in A.Determine the closest pair of points in B.Determine the closest pair of points such that one point is in A and the other in B.From the three closest pairs computed, select the one with least distance.Example•Divide so that points in A have x-coordinate <= that of points in B.A BExample•Find closest pair in A.A B•Let d1 be the distance between the points in this pair.d1Example•Find closest pair in B.A Bd1•Let d2 be the distance between the points in this pair.d2Example•Let d = min{d1, d2}.A Bd1•Is there a pair with one point in A, the other in B and distance < d?d2Example•Candidates lie within d of the dividing line.A B•Call these regions RA and RB, respectively.RARBExample• Let q be a point in RA.A BRARBq• q need be paired only with those points in RB that are within d of q.y.Example•Points that are to be paired with q are in a d x 2d rectangle of RB (comparing region of q).A BRARBq•Points in this rectangle are at least d apart. d2dExampleA BRARBq•So the comparing region of q has at most 6 points.• So number of pairs to check is <= 6| RA | = O(n).d2dTime Complexity•Create a sorted by x-coordinate list of points.O(n log n) time.•Create a sorted by y-coordinate list of points.O(n log n) time.•Using these two lists, the required pairs of points from RA and RB can be constructed in O(n) time.•Let n < 4 define a small instance.Time Complexity•Let t(n) be the time to find the closest pair (excluding the time to create the two sorted lists). •t(n) = c, n < 4, where c is a constant.•When n >= 4, t(n) = t(ceil(n/2)) + t(floor(n/2)) + an,where a is a constant.•To solve the recurrence, assume n is a power of 2 and use repeated substitution.•t(n) = O(n log