Algorithm Design by Éva Tardos and Jon Kleinberg • Slides by Kevin Wayne • Copyright © 2004 Addison Wesley5. Divide-and-ConquerDivide et impera.Veni, vidi, vici. - Julius Caesar2Divide-and-ConquerDivide-and-conquer.! Break up problem into several parts.! Solve each part recursively.! Combine solutions to sub-problems into overall solution.Most common usage.! Break up problem of size n into two equal parts of size !n.! Solve two parts recursively.! Combine two solutions into overall solution in linear time.Consequence.! Brute force: n2.! Divide-and-conquer: n log n.Algorithm Design by Éva Tardos and Jon Kleinberg • Slides by Kevin Wayne • Copyright © 2004 Addison Wesley5.1 Mergesort4Obvious sorting applications.! List files in a directory.! Organize an MP3 library.! List names in a phone book.! Display Google PageRank results.Problems become easier once sorted.! Find the median.! Find the closest pair.! Binary search in a database.! Identify statistical outliers.! Find duplicates in a mailing list.Non-obvious sorting applications.! Data compression.! Computer graphics.! Interval scheduling.! Computational biology.! Minimum spanning tree.! Supply chain management.! Simulate a system of particles.! Book recommendations on Amazon.! Load balancing on a parallel computer.. . .SortingSorting. Given n elements, rearrange in ascending order.5MergesortMergesort.! Divide array into two halves.! Recursively sort each half.! Merge two halves to make sorted whole.mergesortdivideA L G O R I T H M SA L G O R I T H M SA G L O R H I M S TA G H I L M O R S TJon von Neumann (1945)O(n)2T(n/2)O(1)6MergingMerging. Combine two pre-sorted lists into a sorted whole.How to merge efficiently?! Linear number of comparisons.! Use temporary array.Challenge for the bored. In-place merge. [Kronrud, 1969]A G L O R H I M S TA G H Iusing only a constant amount of extra storage7A Useful Recurrence RelationDef. T(n) = number of comparisons to mergesort an input of size n.Mergesort recurrence.Solution. T(n) = O(n log2 n).Assorted proofs. We describe several ways to prove this recurrence.Initially we assume n is a power of 2 and replace ! with =. ! T(n) " 0 if n =1T n /2# $( )solve left half1 2 4 3 4 + T n /2% &( )solve right half1 2 4 3 4 + nmerging{otherwise' ( ) * ) 8Proof by Recursion TreeT(n)T(n/2)T(n/2)T(n/4)T(n/4)T(n/4) T(n/4)T(2) T(2)T(2) T(2) T(2) T(2) T(2) T(2)nT(n / 2k)2(n/2)4(n/4)2k (n / 2k)n/2 (2). . .. . .log2nn log2n ! T(n) =0 if n =12T (n /2)sorting both halves1 2 4 3 4 + nmerging{otherwise" # $ % $9Proof by TelescopingClaim. If T(n) satisfies this recurrence, then T(n) = n log2 n.Pf. For n > 1: ! T(n)n=2T (n /2)n+ 1=T(n / 2)n /2+ 1=T(n / 4)n /4+ 1 + 1L=T(n / n)n /n+ 1 + L+ 1log2n1 2 4 3 4 = log2n ! T(n) =0 if n =12T (n /2)sorting both halves1 2 4 3 4 + nmerging{otherwise" # $ % $ assumes n is a power of 210Proof by InductionClaim. If T(n) satisfies this recurrence, then T(n) = n log2 n.Pf. (by induction on n)! Base case: n = 1.! Inductive hypothesis: T(n) = n log2 n.! Goal: show that T(2n) = 2n log2 (2n). ! T(2n) = 2T (n) + 2n= 2n log2n + 2n= 2n log2(2n) "1( ) + 2n= 2n log2(2n)assumes n is a power of 2 ! T(n) =0 if n =12T (n /2)sorting both halves1 2 4 3 4 + nmerging{otherwise" # $ % $ 11Analysis of Mergesort RecurrenceClaim. If T(n) satisfies the following recurrence, then T(n) ! n "lg n#.Pf. (by induction on n)! Base case: n = 1.! Define n1 = $n / 2% , n2 = "n / 2#.! Induction step: assume true for 1, 2, ... , n–1. ! T(n) " T (n1) + T (n2) + n" n1lg n1# $ + n2lg n2# $ + n" n1lg n2# $ + n2lg n2# $ + n= n lgn2# $ + n" n( lgn# $%1 ) + n= n lg n# $ ! n2= n /2" #$ 2lg n" #/ 2" #= 2lg n" #/ 2% lg n2$ lg n" #&1 ! T(n) " 0 if n =1T n / 2# $( )solve left half1 2 4 3 4 + T n /2% &( )solve right half1 2 4 3 4 + nmerging{otherwise' ( ) * ) log2nAlgorithm Design by Éva Tardos and Jon Kleinberg • Slides by Kevin Wayne • Copyright © 2004 Addison Wesley5.3 Counting Inversions13Music site tries to match your song preferences with others.! You rank n songs.! Music site consults database to find people with similar tastes.Similarity metric: number of inversions between two rankings.! My rank: 1, 2, …, n.! Your rank: a1, a2, …, an.! Songs i and j inverted if i < j, but ai > aj.Brute force: check all &(n2) pairs i and j.YouMe1 43 2 51 32 4 5A B C D ESongsCounting InversionsInversions3-2, 4-214ApplicationsApplications.! Voting theory.! Collaborative filtering.! Measuring the "sortedness" of an array.! Sensitivity analysis of Google's ranking function.! Rank aggregation for meta-searching on the Web.! Nonparametric statistics (e.g., Kendall's Tau distance).15Counting Inversions: Divide-and-ConquerDivide-and-conquer.4 8 10 21 5 12 11 3 76 916Counting Inversions: Divide-and-ConquerDivide-and-conquer.! Divide: separate list into two pieces.4 8 10 21 5 12 11 3 76 94 8 10 21 5 12 11 3 76 9Divide: O(1).17Counting Inversions: Divide-and-ConquerDivide-and-conquer.! Divide: separate list into two pieces.! Conquer: recursively count inversions in each half.4 8 10 21 5 12 11 3 76 94 8 10 21 5 12 11 3 76 95 blue-blue inversions 8 green-green inversionsDivide: O(1).Conquer: 2T(n / 2)5-4, 5-2, 4-2, 8-2, 10-26-3, 9-3, 9-7, 12-3, 12-7, 12-11, 11-3, 11-718Counting Inversions: Divide-and-ConquerDivide-and-conquer.! Divide: separate list into two pieces.! Conquer: recursively count inversions in each half.! Combine: count inversions where ai and aj are in different halves,and return sum of three quantities.4 8 10 21 5 12 11 3 76 94 8 10 21 5 12 11 3 76 95 blue-blue inversions 8 green-green inversionsDivide: O(1).Conquer: 2T(n / 2)Combine: ???9 blue-green inversions5-3, 4-3, 8-6, 8-3, 8-7, 10-6, 10-9, 10-3, 10-7Total = 5 + 8 + 9 = 22.1913 blue-green inversions: 6 + 3 + 2 + 2 + 0 + 0Counting Inversions: CombineCombine: count blue-green inversions! Assume each half is sorted.! Count inversions where ai and aj are in different halves.! Merge two sorted halves into sorted whole.Count: O(n)Merge: O(n)10 14 18 193 7 16 17 23 252 117 10 11 142 3 18 19 23 2516 17 ! T(n) " T n /2# $( )+ T n /2% &( )+ O(n) ' T(n) = O(n log n)6 3 2 2 00to maintain sorted invariant20Counting Inversions: ImplementationPre-condition. [Merge-and-Count] A and B are sorted.Post-condition. [Sort-and-Count] L is sorted.Sort-and-Count(L) { if list L has one element return 0 and the list L Divide the list into two