Administrivia, Lecture 5SelectionAnalysis of Randomized-Select (9.2)Analysis of Randomized-Select (9.2, p. 188)Randomized SelectionSlide 8Worst-Case Linear-Time Selection (9.3)Worst-Case Linear-Time SelectionMore Careful ExpositionD/Q for ArithmeticMatrix MultiplicationStrassen’s Matrix MultiplicationBreakA Computational Geometry ExcursionDQ Closest PairSlide 18Slide 19Convex HullYet Another Geometric ProblemAdministrivia, Lecture 5•HW #2 was assigned on Sunday, January 20. It is due on Thursday, January 31. –Please use the correct edition of the textbook!•We have a quiz this Thursday (20 minutes) at the beginning of lecture•The DQMaxMin problem is treated in CLRS 9.1•Grading will drop the single worst HW or quiz.Selection•Recall: best pivot in QSort is the median–It is too expensive to find the median  we use a random element as the pivot instead•This leads to SELECTION:–Given a list L and a number k, Select (L, k) returns the kth smallest element of L–e.g., when k = |L|/2  Select(L,k) returns the median•What is an efficient algorithm?–Sorting + finding kth smallest  O(n log n) (can do better)•D/Q Recursion: use the “pivot” from QSort  “Randomized-Select” (CLRS 9.2, page 186)–if i<k, look in right part for (k-i)th smallest–if i>k, look in left part for kth smallestAnalysis of Randomized-Select (9.2)•Average-case time complexity•Inductive hypothesis:  Want :11)(}),(max{1)(nknOknkTnnT12/)()(2nnknOkTnncnT )(cnnOkkncnOcknnTnknknnk )(2)(2)(1112/112/Need for induction stepAnalysis of Randomized-Select (9.2, p. 188)•Want: anccncnanccnannncannnncannnnnncannnnnncankkncnOcknnTnknknnk242432214322432)22/34/(2(22)12/)(22/(2)1(22)(2)(2221112/112/ cn  cn/4 – c/2 – an  0  n(c/4 – a)  c/2Choose c s.t. c/4 – a > 0 c > 4a  T(n) = O(n)average-caseRandomized Selection•Worst case:– (n2) as in QSort analysis•But: Suppose we can guarantee a “good” pivot, e.g., such that n/4  i  3n/4 subproblem size  3n/4 •Let s(n)  time to find good pivot t(n)  s(n) + cn + t(3n/4)s(n) = find pivotcn = pivot, make subproblemt(3n/4) = solve subproblemRandomized Selection•Suppose further: S(n)  dn for some d t(n)  (c+d)n + t(3n/4)•Claim: t(n)  kn for some k would follow–Again, we use Constructive Induction (“Substitution”):–Induction Hypothesis: t(m)  km for m  n-1–Induction Step: t(n)  (c+d)n + k(3n/4) = (c+d+3k/4)n which we want to be equivalent to t(n)  kn–But this is true if k  4(c+d)Worst-Case Linear-Time Selection (9.3)•Of mostly theoretical interest•How to find a “good” median in linear time–divide into groups of 5 c1n–find the median of each group c2n/5–find the median of medians, recursively T(n/5)•Pivoting around this element gives at worst 3:7 splitWorst-Case Linear-Time Selection•Blum-Floyd-Pratt-Rivest-Tarjan, 1973–divide L into groups of 5 c1n–find the median of each group c2n/5–Let S = array of medians of each group c3n–find median of medians (i.e., median of S) recursively; use as pivot t(n/5)•Total work: t(n)  kn + t(n/5) + t(7n/10 + d)•In general: a(n)  kn + a(1n) + a(2n) + a(3n), with k, 1, 2, 3 constants s.t. 1 + 2+ 3 < 1, then a(n)  c*n for some c*  t(n) = O(n)More Careful Exposition•Recursive call has size  7n/10 + 6 (CLRS p. 191)–T(n)  (1), n  M (M = 140)–T(n)  T(n/5) + T(7n/10 + 6) + O(n), n > M•Prove linearity by substitution–Assume T(n)  cn for some constant c, and for all n  M–T(n)  cn/5 + c(7n/10 + 6) + an  cn/5 + c + 7cn/10 + 6c + an 9cn/10 + 7c + an  cn + (-cn/10 + 7c + an)–The induction step goes through if –cn/10 + 7c + an  0  pick c large enough so that c(n/10 - 7) > an n > MD/Q for Arithmetic•Multiplying Large Integers (Karatsuba-Ofman)–A = a0 + r1a1 + ... + rn-1an-1, r  radix–“classic” approach  (n2) work•Can we apply D/Q?–Let n = 2s, r = 10  radix–AB = xz + 10s(wz + xy) + 102swy–T(n) = 4T(n/2) +  (n)  a = 4, b = 2 in Master Method–T(n)  (n2)–Need to reduce # subproblems, i.e., want a < 4•Observation: r’ = (w+x)(y+z) = wy + (wz+xy) + xz–r’  (w+x)(y+z)–p  wy–q  xz–return 102sp + 10s(r’-p-q) + q–T(n)  O(n log23) = O(n1.59)Matrix Multiplication•A = […] , B = […] are n x n matrices•a11, a12, etc are n/2 x n/2 submatrices•M = AB = […]–where m11 = a11b11 + a12b21 etc.–Evaluation requires 8 multiplies, 4 adds•T(n) = 8T(n/2) + O(n)  (n3)Strassen’s Matrix Multiplicationp1 = (a21 + a22 - a11)(b22 - b12 + b11)p2 = a11b11p3 = a12b21p4 = (a11-a21)(b22-b12)p5 = (a21+a22)(b12 - b11)p6 = (a12-a21+a11-a22)b22p7 = a22(b11+b22-b12-b21)AB11 = p2 + p3AB12 = p1 + p2 + p5 + p6 AB21 = p1 + p2 + p4 + p7AB22 = p1 + p2 + p4 + p5 •T(n)  (n2.81) // 7 multiplies, 24 adds–Can get to 15 addsBreak•Question: Given the adjacency matrix of an undirected graph, describe a fast algorithm that finds all triangles in the graph. –(Why am I asking this now?)A Computational Geometry Excursion•Given simple polygon P, is x in P? (n) ?•Given n points in the plane, draw a simple n-gon through them (n log n) ?•Given n points in the plane, return their convex hull(n log n) ?Does it matter whether we must return vertices or return the polygon?•Given n points in the plane, return the closest pair (n log n) ?•Given n h-, v- segments, return all intersections O(f(n) + g(k)), where k = output size?•plane-sweep  “inductive” paradigmDQ Closest Pair•Naïve (n2) •D/Q Approach: (n log n)–(1) Split into two pointsets S1, S2 by x-coord  natural order–(2) Find closest pair distances d1, d2 in S1, S2 respectively without loss of generality, can assume d1<d2–(3) Merge the solutions Do we have to check all s1-s2 pairs, s1  S1,