Order StatisticsOrder StatisticSelection ProblemMinimum (Maximum)ProblemSimultaneous Minimum and MaximumSlide 7Slide 8General Selection ProblemSelection in Expected Linear TimeRandomized Quicksort: reviewRandomized-SelectAnalysisAverage-case AnalysisSlide 15Slide 16Average-case Analysis (Contd.)Slide 18Selection in Worst-Case Linear TimeGuaranteeing a Good SplitChoosing a PivotAlgorithm SelectWorst-case SplitSlide 24Recurrence for worst-case running timeSolving the recurrenceOrder StatisticsOrder StatisticsMany of the slides are from Prof. Plaisted’s resources at University of North Carolina at Chapel HillOrder Statisticith order statistic: ith smallest element of a set of n elements.Minimum: first order statistic.Maximum: nth order statistic.Median: “half-way point” of the set.»Unique, when n is odd – occurs at i = (n+1)/2.»Two medians when n is even.•Lower median, at i = n/2.•Upper median, at i = n/2+1.•For consistency, “median” will refer to the lower median.Selection ProblemSelection problem:»Input: A set A of n distinct numbers and a number i, with 1 i  n.»Output: the element x  A that is larger than exactly i – 1 other elements of A.Can be solved in O(n lg n) time. How?We will study faster linear-time algorithms.»For the special cases when i = 1 and i = n.»For the general problem.Minimum (Maximum)Minimum (A)1. min  A[1] 2. for i  2 to length[A]3. do if min > A[i] 4. then min  A[i] 5. return minMinimum (A)1. min  A[1] 2. for i  2 to length[A]3. do if min > A[i] 4. then min  A[i] 5. return minMaximum can be determined similarly.• T(n) = (n).• No. of comparisons: n – 1.• Can we do better? Why not?• Minimum(A) has worst-case optimal # of comparisons.ProblemAverage for random input: How many times do we expect line 4 to be executed?»X = RV for # of executions of line 4.»Xi = Indicator RV for the event that line 4 is executed on the ith iteration.»X = i=2..n Xi»E[Xi] = 1/i. How?»Hence, E[X] = ln(n) – 1 = (lg n).Minimum (A)1. min  A[1] 2. for i  2 to length[A]3. do if min > A[i] 4. then min  A[i] 5. return minMinimum (A)1. min  A[1] 2. for i  2 to length[A]3. do if min > A[i] 4. then min  A[i] 5. return minSimultaneous Minimum and MaximumSome applications need to determine both the maximum and minimum of a set of elements.»Example: Graphics program trying to fit a set of points onto a rectangular display.Independent determination of maximum and minimum requires 2n – 2 comparisons.Can we reduce this number? »Yes.Simultaneous Minimum and MaximumMaintain minimum and maximum elements seen so far.Process elements in pairs.»Compare the smaller to the current minimum and the larger to the current maximum.»Update current minimum and maximum based on the outcomes.No. of comparisons per pair = 3. How?No. of pairs  n/2.»For odd n: initialize min and max to A[1]. Pair the remaining elements. So, no. of pairs = n/2.»For even n: initialize min to the smaller of the first pair and max to the larger. So, remaining no. of pairs = (n – 2)/2 < n/2.Simultaneous Minimum and MaximumTotal no. of comparisons, C  3 n/2.»For odd n: C = 3n/2.»For even n: C = 3(n – 2)/2 + 1 (For the initial comparison). = 3n/2 – 2 < 3n/2.General Selection ProblemSeems more difficult than Minimum or Maximum.»Yet, has solutions with same asymptotic complexity as Minimum and Maximum.We will study 2 algorithms for the general problem.»One with expected linear-time complexity.»A second, whose worst-case complexity is linear.Selection in Expected Linear TimeModeled after randomized quicksort.Exploits the abilities of Randomized-Partition (RP).»RP returns the index k in the sorted order of a randomly chosen element (pivot).•If the order statistic we are interested in, i, equals k, then we are done.•Else, reduce the problem size using its other ability.»RP rearranges the other elements around the random pivot.•If i < k, selection can be narrowed down to A[1..k – 1].•Else, select the (i – k)th element from A[k+1..n].(Assuming RP operates on A[1..n]. For A[p..r], change k appropriately.)Randomized Quicksort: reviewQuicksort(A, p, r)if p < r thenq := Rnd-Partition(A, p, r);Quicksort(A, p, q – 1);Quicksort(A, q + 1, r)fiQuicksort(A, p, r)if p < r thenq := Rnd-Partition(A, p, r);Quicksort(A, p, q – 1);Quicksort(A, q + 1, r)fiRnd-Partition(A, p, r) i := Random(p, r); A[r]  A[i];x, i := A[r], p – 1;for j := p to r – 1 doif A[j]  x theni := i + 1; A[i]  A[j]fiod;A[i + 1]  A[r];return i + 1Rnd-Partition(A, p, r) i := Random(p, r); A[r]  A[i];x, i := A[r], p – 1;for j := p to r – 1 doif A[j]  x theni := i + 1; A[i]  A[j]fiod;A[i + 1]  A[r];return i + 15A[p..r]A[p..q – 1]A[q+1..r] 5 5Partition5Randomized-SelectRandomized-Select(A, p, r, i) // select ith order statistic. 1. if p = r2. then return A[p] 3. q  Randomized-Partition(A, p, r)4. k  q – p + 15. if i = k6. then return A[q]7. elseif i < k8. then return Randomized-Select(A, p, q – 1, i)9. else return Randomized-Select(A, q+1, r, i – k)Randomized-Select(A, p, r, i) // select ith order statistic. 1. if p = r2. then return A[p] 3. q  Randomized-Partition(A, p, r)4. k  q – p + 15. if i = k6. then return A[q]7. elseif i < k8. then return Randomized-Select(A, p, q – 1, i)9. else return Randomized-Select(A, q+1, r, i – k)AnalysisWorst-case Complexity:(n2) – As we could get unlucky and always recurse on a subarray that is only one element smaller than the previous subarray.Average-case Complexity:(n) – Intuition: Because the pivot is chosen at random, we expect that we get rid of half of the list each time we choose a random pivot q. »Why (n) and not (n lg n)?Average-case AnalysisDefine Indicator RV’s Xk, for 1  k  n.»Xk = I{subarray A[p…q] has exactly k elements}.»Pr{subarray A[p…q] has exactly k elements} = 1/n for all k = 1..n.»Hence, E[Xk] = 1/n. Let T(n) be the RV for the time required by Randomized-Select (RS) on A[p…q] of n elements.Determine an upper bound on E[T(n)].(9.1)Average-case AnalysisA call to RS may»Terminate