Efficient Algorithms: Divide and Conquer Techniques
Using the Divide and Conquer approach, this lecture discusses strategies for efficiently solving problems such as counting inversions in arrays and integer multiplication. By dividing tasks into smaller subproblems, sorting, merging, and efficiently counting operations, the algorithms presented optimize time complexity for various computational challenges.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Example 2 Counting Inversions Goal: Given array a[], count the number of pairs (i,j) such that i < j but a[i] > a[j]. Input: Array a[] = {6, 2, 4, 1, 5, 3, 7, 8} Answer = 9
How to count inversions more efficiently? b[] = {6, 2, 4, 1}, 5 inversions c[] = {5, 3, 7, 8}, 1 inversion For each number in b, want to know how many numbers in c are smaller. 6: 2, 2: 0, 4: 1, 1: 0, result = 2+0+1+0 = 3. Much easier if c[] is sorted! Idea: Can sort the arrays when we are counting inversions.
Sort&Count Sort&Count(a[]) 1. IF Length(a) < 2 THEN RETURN (a[], 0). (Base Case) 2. Partition a[] evenly into two arrays b[], c[]. (Divide) 3. (b[], count_b) = Sort&Count(b[]) 4. (c[], count_c) = Sort&Count(c[]) (Conquer) 5. (a[], count_bc) = Merge&Count(b[], c[]). (Merge) 6. RETURN a[], count_b+count_c+count_bc.
Merge&Count b[] = {1, 2, 4, 6} c[] = {3, 5, 7, 8} {1, 2, 3, 4, 5, 6, 7, 8} When 4 goes into the array, pointer in c[] is pointing at 5 (2nd element), so 4 is larger than 1 element in c[]. When 6 goes into the array, pointer in c[] is pointing at 7 (3rd element), so 6 is larger than 2 elements in c[].
Merge&Count Merge&Count(b[], c[]) 1. a[] = empty 2. i = 1, j = 1 3. count = 0 4. WHILE i <= Length(b[]) OR j <= Length(c[]) 5. IF b[i] < c[j] THEN 6. a.append(b[i]); i = i+1 7. count = count + (j - 1) 8. ELSE 9. a.append(c[j]); j = j+1 10. RETURN a[], count The i-th element of a[] is smaller than c[j], but larger than c[1,2, , j-1]
Running Time Merging still take O(n) time, so we still have T(n) = 2T(n/2) + A n for some constant A > 0 T(n) = O(n log n)
Example 3 Integer Multiplication Input: two positive integers a, b Output: a b multiply(a, b) 1. RETURN a*b? What if a = 73489553479834257983745 and b = 197878967893267834267324789? Na ve algorithm: O(n2) time (learned in elementary school)
Divide and Conquer a = 123,456 b = 654,321 How to divide? Write a = 123,000 + 456, b = 654,000 + 321. Then a*b = 123*654*106 + (123*321+456*654)*103 + 456*321.
First attempt Partition a = a1*10n/2+a2, b = b1*10n/2+b2 Recursively compute A = a1*a2, B = a2*b1, C = a1*b2, D = a2*b2 Output A*10n+(B+C)*10n/2+D Multiply(a, b) 1. (wlog assume n = length(a) = length(b), pad 0 for the shorter number) 2. IF Length(a) <= 1 THEN RETURN a*b 3. Partition a into a = a1 * 10n/2+a2, b = b1*10n/2+b2 4. A = Multiply(a1, b1) 5. B = Multiply(a2, b1) 6. C = Multiply(a1, b2) 7. D = Multiply(a2, b2) 8. RETURN A*10n+(B+C)*10n/2 + D Need an algorithm for adding long numbers. Standard algorithm suffices (O(n))
Improving the algorithm To make a divide and conquer algorithm faster 1. Make the merging step faster 2. Make the sub-problems smaller 3. Reduce the number of sub-problems Observation: (a1*b2+a2*b1) = (a1+a2)*(b1+b2) a1*b1 a2*b2
Improved Algorithm Partition a = a1*10n/2+a2, b = b1*10n/2+b2 Recursively compute A = a1*b1, B = a2*b2, C = (a1+a2)*(b1+b2) Output A*10n+(C-A-B)*10n/2+B Multiply(a, b) 1. (wlog assume n = length(a) = length(b), pad 0 for the shorter number) 2. IF Length(a) <= 1 THEN RETURN a*b 3. Partition a into a = a1 * 10n/2+a2, b = b1*10n/2+b2 4. A = Multiply(a1, b1) 5. B = Multiply(a2, b2) 6. C = Multiply(a1+a2, b1+b2) 7. RETURN A*10n+(C-A-B)*10n/2 + B
Master Theorem Cheat sheet for simple recursions Theorem: If T(n) = aT(n/b) + f(n), then 1. If f(n) = O(nc), c < logba ? ? = (?log??) 2. If f(n) = (nclogtn), c = logba ? ? = ?log??log?+1? 3. If f(n) = (nc), c > logba ? ? = (??)
