9/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A. Smith, K. Wayne Sofya Raskhodnikova Algorithm Design and Analysis LECTURE 11 Divide and Conquer • Merge Sort • Counting Inversions • Binary Search • Exponentiation Solving Recurrences • Recursion Tree Method9/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A. Smith, K. Wayne Divide 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/2. – Solve two parts recursively. – Combine two solutions into overall solution in linear time. • Consequence. – Brute force: Θ(n2). – Divide-and-conquer: Θ (n log n). Divide et impera. Veni, vidi, vici. - Julius Caesar9/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A. Smith, K. Wayne obvious applications problems become easy once items are in sorted order non-obvious applications Sorting • Given n elements, rearrange in ascending order. • Applications. – Sort a list of names. – Display Google PageRank results. – Find the median. – Find the closest pair. – Binary search in a database. – Find duplicates in a mailing list. – Data compression – Computer graphics – Computational biology. – Load balancing on a parallel computer. . . .9/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A. Smith, K. Wayne Mergesort – Divide array into two halves. – Recursively sort each half. – Merge two halves to make sorted whole. merge sort divide A L G O R I T H M S A L G O R I T H M S A G L O R H I M S T A G H I L M O R S T Jon von Neumann (1945) O(n) 2T(n/2) O(1)9/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A. Smith, K. Wayne Merging • 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] using only a constant amount of extra storage A G L O R H I M S T A G H I9/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A. Smith, K. Wayne Recurrence for Mergesort • T(n) = worst case running time of Mergesort on an input of size n. • Should be T( n/2 ) + T( n/2 ) , but it turns out not to matter asymptotically. • Usually omit the base case because our algorithms always run in time Θ(1) when n is a small constant. • Several methods to find an upper bound on T(n). T(n) = Θ(1) if n = 1; 2T(n/2) + Θ(n) if n > 1.9/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A. Smith, K. Wayne Recursion Tree Method • Technique for guessing solutions to recurrences – Write out tree of recursive calls – Each node gets assigned the work done during that call to the procedure (dividing and combining) – Total work is sum of work at all nodes • After guessing the answer, can prove by induction that it works.9/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A. Smith, K. Wayne Recursion Tree for Mergesort Solve T(n) = 2T(n/2) + cn, where c > 0 is constant. T(n) T(n/4) T(n/4) T(n/4) T(n/4) T(n/2) T(n/2) Τ(1) T(n / 2k) h = lg n #leaves = n9/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A. Smith, K. Wayne Recursion Tree for Mergesort Solve T(n) = 2T(n/2) + cn, where c > 0 is constant. T(n/4) T(n/4) T(n/4) T(n/4) T(n/2) T(n/2) Τ(1) T(n / 2k) cn h = lg n #leaves = n9/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A. Smith, K. Wayne Recursion Tree for Mergesort Solve T(n) = 2T(n/2) + cn, where c > 0 is constant. T(n/4) T(n/4) T(n/4) T(n/4) Τ(1) T(n / 2k) cn cn/2 cn/2 h = lg n #leaves = n9/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A. Smith, K. Wayne Recursion Tree for Mergesort Solve T(n) = 2T(n/2) + cn, where c > 0 is constant. Τ(1) T(n / 2k) cn cn/2 cn/2 cn/4 cn/4 cn/4 cn/4 h = lg n #leaves = n9/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A. Smith, K. Wayne Recursion Tree for Mergesort Solve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn cn/4 cn/4 cn/4 cn/4 cn/2 cn/2 Θ(1) h = lg n cn cn cn #leaves = n Θ(n) Total = Θ(n lg n) … T(n / 2k)9/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A. Smith, K. Wayne • Music 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. Counting Inversions You Me 1 4 3 2 5 1 3 2 4 5 A B C D E Songs Inversions 3-2, 4-29/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A. Smith, K. Wayne Applications – 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).9/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A. Smith, K. Wayne Counting Inversions: Algorithm • Divide-and-conquer 4 8 10 2 1 5 12 11 3 7 6 99/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A. Smith, K. Wayne Counting Inversions: Algorithm • Divide-and-conquer – Divide: separate list into two pieces. 4 8 10 2 1 5 12 11 3 7 6 9 4 8 10 2 1 5 12 11 3 7 6 9 Divide: Θ(1).9/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A. Smith, K. Wayne Counting Inversions: Algorithm • Divide-and-conquer – Divide: separate list into two pieces. – Conquer: recursively count inversions in each half. 4 8 10 2 1 5 12 11 3 7 6 9 4 8 10 2 1 5 12 11 3 7 6 9 5 blue-blue inversions 8 green-green inversions Divide: Θ(1). Conquer: 2T(n / 2) 5-4, 5-2, 4-2, 8-2, 10-2 6-3, 9-3, 9-7, 12-3, 12-7, 12-11, 11-3, 11-79/19/2008 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson, A.