The University of Sydney
Page 1
From Jeff Erickson, alogrithms.wtf
Lecture 3:
Divide & Conquer
William Umboh
School of Computer Science
The University of Sydney
Page 2
Fast Fourier Transform
General techniques in this course
– Greedy algorithms [Lecture 2]
– Divide & Conquer algorithms [today]
– Dynamic programming [19 and 26 Mar] – Network flow algorithms [2 and 9 Apr]
The University of Sydney
Page 3
Reduction: Powerful Idea in Algorithms
Problem A
The University of Sydney Page 4
Problem B
Solution A
Algorithm B
Divide-and-Conquer
– Divide-and-conquer [usually 3 parts]
1. Divide: Break up problem into several parts.
2. Conquer: Solve each part recursively.
3. Combine solutions to sub-problems into overall solution.
The University of Sydney
Page 5
Divide-and-Conquer
– Divide-and-conquer [usually 3 parts]
1. Divide: Break up problem into several parts.
2. Conquer: Solve each part recursively.
3. Combine solutions to sub-problems into overall solution.
The University of Sydney
Page 6
Divide-and-Conquer
– Divide-and-conquer [usually 3 parts]
1. Divide: Break up problem into several parts.
2. Conquer: Solve each part recursively.
3. Combine solutions to sub-problems into overall solution.
The University of Sydney
Page 7
Divide-and-Conquer
– Divide-and-conquer [usually 3 parts]
1. Divide: Break up problem into several parts.
2. Conquer: Solve each part recursively.
3. Combine solutions to sub-problems into overall solution.
The University of Sydney
Page 8
Divide-and-Conquer
– Divide-and-conquer [usually 3 parts]
1. Divide: Break up problem into several parts.
2. Conquer: Solve each part recursively.
3. Combine solutions to sub-problems into overall solution.
– Most common usage.
– Break up problem of size n into two equal parts of size 1⁄2n. – Solve two parts recursively.
– Combine two solutions into overall solution in linear time.
The University of Sydney
Page 9
Similar to proof by induction
Warmup: Searching
Input: A sorted sequence S of n numbers a1,a2,…,an, stored in an array A[1..n].
Question: Given a number x, is x in S?
0
1
3
4
5
7
10
13
15
18
19
23
The University of Sydney Page 10
Binary Search
– Compare x to the middle element of the array (A[n/2]).
– If A[n/2] = x then “Yes”
– Otherwise, if A[n/2] > x then recursively Search A[1…n/2-1]. – Otherwise, if A[n/2] < x then recursively Search A[n/2+1…n] 0 1 3 4 5 7 10 13 15 18 19 23The University of Sydney Page 11 Binary Search– Compare x to the middle element of the array (A[n/2]).– If A[n/2] = x then “Yes”– Otherwise, if A[n/2] > x then recursively Search A[1…n/2-1]. – Otherwise, if A[n/2] < x then recursively Search A[n/2+1…n]Example: x=1 (non-integers are rounded up) 0 1 3 4 5 7 10 13 15 18 19 23The University of Sydney Page 12 Binary Search– Compare x to the middle element of the array (A[n/2]).– If A[n/2] = x then “Yes”– Otherwise, if A[n/2] > x then recursively Search A[1…n/2-1]. – Otherwise, if A[n/2] < x then recursively Search A[n/2+1…n]Example: x=1 (non-integers are rounded up) 0 1 3 4 5 7 10 13 15 18 19 23The University of Sydney Page 13 Binary Search– Compare x to the middle element of the array (A[n/2]).– If A[n/2] = x then “Yes”– Otherwise, if A[n/2] > x then recursively Search A[1…n/2-1]. – Otherwise, if A[n/2] < x then recursively Search A[n/2+1…n]Example: x=1 (non-integers are rounded up) 0 1 3 4 5 7 10 13 15 18 19 23 The University of Sydney Page 14 Binary Search– Compare x to the middle element of the array (A[n/2]).– If A[n/2] = x then “Yes”– Otherwise, if A[n/2] > x then recursively Search A[1…n/2-1]. – Otherwise, if A[n/2] < x then recursively Search A[n/2+1…n]Example: x=1 (non-integers are rounded up)0 1 3 4 5 7 10 13 15 18 19 23 The University of Sydney Page 15 Binary Search– Compare x to the middle element of the array (A[n/2]).– If A[n/2] = x then “Yes”– Otherwise, if A[n/2] > x then recursively Search A[1…n/2-1]. – Otherwise, if A[n/2] < x then recursively Search A[n/2+1…n]Example: x=1 (non-integers are rounded up)0 1 3 4 5 7 10 13 15 18 19 23The University of Sydney Page 16 Binary Search– Compare x to the middle element of the array (A[n/2]).– If A[n/2] = x then “Yes”– Otherwise, if A[n/2] > x then recursively Search A[1…n/2-1]. – Otherwise, if A[n/2] < x then recursively Search A[n/2+1…n]Example: x=1 (non-integers are rounded up) 0 1 3 4 5 7 10 13 15 18 19 23The University of Sydney Page 17 Binary Search– Compare x to the middle element of the array (A[n/2]).– If A[n/2] = x then “Yes”– Otherwise, if A[n/2] > x then recursively Search A[1…n/2-1]. – Otherwise, if A[n/2] < x then recursively Search A[n/2+1…n]Example: x=1 (non-integers are rounded up)0 1 3 4 5 7 10 13 15 18 19 23The University of Sydney Page 18 Binary Search– Compare x to the middle element of the array (A[n/2]).– If A[n/2] = x then “Yes”– Otherwise, if A[n/2] > x then recursively Search A[1…n/2-1]. – Otherwise, if A[n/2] < x then recursively Search A[n/2+1…n]Example: x=1 (non-integers are rounded up)Analysis: T(n) = 1+ T(n/2)The University of Sydney Page 190 1 3 4 5 7 10 13 15 18 19 23 Analyze recurrence via recursion treelog2nT(n) = T(n/2)+O(1)T(n)T(n/2)T(n/4) T(n/2k) T(1)1 (of size n)1 (of size n/2)1 (of size n/4) …1(ofsize n/2k) …1 (of size 1)The University of SydneyPage 20 Binary Search– Compare x to the middle element of the array (A[n/2]).– If A[n/2] = x then “Yes”– Otherwise, if A[n/2] > x then recursively Search A[1…n/2-1]. – Otherwise, if A[n/2] < x then recursively Search A[n/2+1…n]Example: x=1 (non-integers are rounded up)Analysis: T(n) = 1+ T(n/2) = O(log n)The University of Sydney Page 210 1 3 4 5 7 10 13 15 18 19 23 Sorting– Sorting. Given n elements, rearrange in ascending order.Obvious 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….The University of SydneyPage 22Mergesort1. Divide array into two halves.2. Conquer: Recursively sort each half.3. Combine: Merge two halves to make sorted whole.John von Neumann (1945) A L G O R I T H M Sdivide O(1) A L G O R I T H M Ssort 2T(n/2) A G L O R H I M S Tmerge O(n) A G H I L M O R S T The University of Sydney Page 23 Merging– Merging. Combine two pre-sorted lists into a sorted whole.– How to merge efficiently?– Linear number of comparisons. – Use temporary array. A G L O R H I M S TA G H IThe University of SydneyPage 24 Merging– Merge.– Keep track of smallest unprocessed element in each sorted half.– Insert smallest of two elements into auxiliary array. – Repeat until done.smallest smallest A G L O R H I M S T AThe University of SydneyPage 25auxiliary array Merging– Merge.– Keep track of smallest unprocessed element in each sorted half.– Insert smallest of two elements into auxiliary array. – Repeat until done.smallest smallest A G L O R H I M S T A G The University of SydneyPage 26auxiliary array Merging– Merge.– Keep track of smallest unprocessed element in each sorted half.– Insert smallest of two elements into auxiliary array. – Repeat until done.smallest smallest A G L O R H I M S T A G HThe University of SydneyPage 27auxiliary array Merging– Merge.– Keep track of smallest unprocessed element in each sorted half.– Insert smallest of two elements into auxiliary array. – Repeat until done.smallest smallest A G L O R H I M S T A G H I The University of SydneyPage 28auxiliary array Merging– Merge.– Keep track of smallest element in each sorted half.– Insert smallest of two elements into auxiliary array. – Repeat until done.smallest smallest A G L O R H I M S T A G H I LThe University of SydneyPage 29auxiliary array Merging– Merge.– Keep track of smallest unprocessed element in each sorted half.– Insert smallest of two elements into auxiliary array. – Repeat until done.smallest smallest A G L O R H I M S T A G H I L M The University of SydneyPage 30auxiliary array Merging– Merge.– Keep track of smallest unprocessed element in each sorted half.– Insert smallest of two elements into auxiliary array. – Repeat until done.smallest smallest A G L O R H I M S T A G H I L M OThe University of SydneyPage 31auxiliary array Merging– Merge.– Keep track of smallest unprocessed element in each sorted half.– Insert smallest of two elements into auxiliary array. – Repeat until done.smallest smallest A G L O R H I M S T A G H I L M O R The University of SydneyPage 32auxiliary array Merging– Merge.– Keep track of smallest unprocessed element in each sorted half.– Insert smallest of two elements into auxiliary array. – Repeat until done.first half exhaustedsmallest A G L O R H I M S T A G H I L M O R SThe University of SydneyPage 33auxiliary array Merging– Merge.– Keep track of smallest unprocessed element in each sorted half.– Insert smallest of two elements into auxiliary array. – Repeat until done.first half exhaustedsmallest A G L O R H I M S T A G H I L M O R S T The University of SydneyPage 34auxiliary array Merging– Merge.– Keep track of smallest unprocessed element in each sorted half.– Insert smallest of two elements into auxiliary array. – Repeat until done.first half exhaustedsecond half exhausted A G L O R H I M S T A G H I L M O R S T Total # comparisons: O(n)The University of Sydney Note: runtime dominated by # comparisonsauxiliary array Page 35Mergesort1. Divide array into two halves.2. Conquer: Recursively sort each half.3. Combine: Merge two halves to make sorted whole.John von Neumann (1945) A L G O R I T H M Sdivide O(1) A L G O R I T H M Ssort 2T(n/2) A G L O R H I M S Tmerge O(n) A G H I L M O R S T The University of Sydney Page 36 A Useful Recurrence Relation– Definition: T(n) = number of comparisons to mergesort an input of size n.– Mergesort recurrence.0T(én/2ù) + T(ën/2û) + O(n)– Solution: T(n) = ? The University of Sydneyif n=1 otherwise T(n) =Page 37 Proof by unrollingìcT(n)=ïí 2T (n / 2) + cnif n=1 otherwiseïî%”$”# ! sorting both halves merging T(n)T(n/2)T(n/4) T(n/4)T(n/2k)T(1) T(1) T(1) T(1)1 (of size n)2 (of size n/2)4 (of size n/4)…2k (of size n/2k)…n (of size 1) T(n/4)T(n/2) T(n/4)T(1) T(1)T(1) T(1)The University of SydneyPage 38 Proof by unrollingìcT(n)=ïí 2T (n / 2) + cnif n=1 otherwiseïî%”$”# ! sorting both halves merging T(n)T(n/2)T(n/4) T(n/4)T(n/2k)T(1) T(1) T(1) T(1)1 (of size n) ® cn2 (of size n/2) ® cn4 (of size n/4) ® cnlog2n…2k (of size n/2k) ® cn …n(of size 1) ® cn Page 39T(n/4)T(n/2) T(n/4)T(1) T(1)The University of SydneyT(1) T(1) Proof by unrolling ìcT(n)=ïí 2T (n / 2) + cnif n=1 otherwiseïî%”$”# ! sorting both halves merging T(n)T(n/2)T(n/4) T(n/4)T(n/2k)T(1) T(1) T(1) T(1)1 (of size n) ® cn2 (of size n/2) ® cn4 (of size n/4) ® cnlog2n…2k (of size n/2k) ® cn …n(of size 1) ® cn cn log2n Page 40T(n/4)T(n/2) T(n/4)T(1) T(1)The University of SydneyT(1) T(1)Need to be explicit about constant, cannot simply write O(1)!!!A Useful Recurrence Relation– Definition: T(n) = number of comparisons to mergesort an input of size n.– Mergesort recurrence. ì 0 if n=1 T(n) £íT n/2 + T n/2 + n otherwise!!î solve left half solve right halfï (é ù) (ë û) ï ” $! #! $! %! ! ” $! #! $! %! !&merging– Solution: T(n) = O(n log2 n). The University of SydneyPage 41 Counting InversionsThe University of Sydney Page 42 Counting Inversions– Musicsitetriestomatchyoursongpreferenceswithothers. – Youranknsongs.– Musicsiteconsultsdatabasetofindpeoplewithsimilartastes.– Similarity metric: number of inversions between two rankings. – Myrank: 1,2,…,n.– Your rank: a1, a2, …, an.– Songsiandkinvertedifi
Songs
Inversions 3-2, 4-2
A
B
C
D
E
Me
1
2
3
4
5
You
1
3
4
2
5
– Brute force: check all Q(n2) pairs i and k. The University of Sydney
Page 43
Applications
– 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).
The University of Sydney
Page 44
Counting Inversions: Divide-and-Conquer
– Divide-and-conquer.
1
5
4
8
10
2
6
9
12
11
3
7
The University of Sydney Page 45
Counting Inversions: Divide-and-Conquer
– Divide-and-conquer.
– Divide: separate list into two pieces.
1
5
4
8
10
2
6
9
12
11
3
7
Divide: O(1).
1
5
4
8
10
2
6
9
12
11
3
7
The University of Sydney
Page 46
Counting Inversions: Divide-and-Conquer
– Divide-and-conquer.
– Divide: separate list into two pieces.
– Conquer: recursively count inversions in each half.
1
5
4
8
10
2
6
9
12
11
3
7
1
5
4
8
10
2
6
9
12
11
3
7
5 blue-blue inversions 5-4, 5-2, 4-2, 8-2, 10-2
Divide: O(1).
Conquer: 2T(n/2) 6-3, 9-3, 9-7, 12-3, 12-7, 12-11, 11-3, 11-7
The University of Sydney
Page 47
8 green-green inversions
Counting Inversions: Divide-and-Conquer
– Divide-and-conquer.
– Divide: separate list into two pieces.
– Conquer: recursively count inversions in each half.
– Combine: count inversions where ai and ak are in different halves, and
return sum of three quantities.
1
5
4
8
10
2
6
9
12
11
3
7
1
5
4
8
10
2
6
9
12
11
3
7
5 blue-blue inversions 8 green-green inversions
9 blue-green inversions
5-3, 4-3, 8-6, 8-3, 8-7, 10-6, 10-9, 10-3, 10-7
Total = 5 + 8 + 9 = 22.
Divide: O(1). Conquer: 2T(n/2)
Combine: ???
The University of Sydney
Page 48
Counting Inversions: Combine
Combine: count blue-green inversions
– Assume each half is sorted.
– Merge two sorted halves into sorted whole.
– Simultaneously, count inversions where ai and ak are in different halves.
3
7
10
14
18
19
2
11
16
17
23
25
The University of Sydney
Page 49
632200
5 blue-blue inversions 8 green-green inversions
How many blue-green inversions?
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=6
3
7
10
14
18
19
2
11
16
17
23
25
two sorted halves
auxiliary array
The University of Sydney
Page 50
Total:
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=6
3
7
10
14
18
19
2
11
16
17
23
25
6
two sorted halves
auxiliary array
2
The University of Sydney
Page 51
Total: 6
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=6
3
7
10
14
18
19
2
11
16
17
23
25
6
two sorted halves
auxiliary array
2
The University of Sydney
Page 52
Total: 6
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=6
3
7
10
14
18
19
2
11
16
17
23
25
6
two sorted halves
auxiliary array
2
3
The University of Sydney
Page 53
Total: 6
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=5
3
7
10
14
18
19
2
11
16
17
23
25
6
two sorted halves
auxiliary array
2
3
The University of Sydney
Page 54
Total: 6
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=5
3
7
10
14
18
19
2
11
16
17
23
25
6
two sorted halves
auxiliary array
2
3
7
The University of Sydney
Page 55
Total: 6
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=4
3
7
10
14
18
19
2
11
16
17
23
25
6
two sorted halves
auxiliary array
2
3
7
The University of Sydney
Page 56
Total: 6
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=4
3
7
10
14
18
19
2
11
16
17
23
25
6
two sorted halves
auxiliary array
2
3
7
10
The University of Sydney
Page 57
Total: 6
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=3
3
7
10
14
18
19
2
11
16
17
23
25
6
two sorted halves
auxiliary array
2
3
7
10
The University of Sydney
Page 58
Total: 6
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=3
3
7
10
14
18
19
2
11
16
17
23
25
63
two sorted halves
auxiliary array
2
3
7
10
11
The University of Sydney
Page 59
Total: 6+3
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=3
3
7
10
14
18
19
2
11
16
17
23
25
63
two sorted halves
auxiliary array
2
3
7
10
11
The University of Sydney
Page 60
Total: 6+3
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=3
3
7
10
14
18
19
2
11
16
17
23
25
63
two sorted halves
auxiliary array
2
3
7
10
11
14
The University of Sydney
Page 61
Total: 6+3
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=2
3
7
10
14
18
19
2
11
16
17
23
25
63
two sorted halves
auxiliary array
2
3
7
10
11
14
The University of Sydney
Page 62
Total: 6+3
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=2
3
7
10
14
18
19
2
11
16
17
23
25
632
two sorted halves
auxiliary array
2
3
7
10
11
14
16
The University of Sydney
Page 63
Total: 6+3+2
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=2
3
7
10
14
18
19
2
11
16
17
23
25
632
two sorted halves
auxiliary array
2
3
7
10
11
14
16
The University of Sydney
Page 64
Total: 6+3+2
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=2
3
7
10
14
18
19
2
11
16
17
23
25
6322
two sorted halves
auxiliary array
2
3
7
10
11
14
16
17
The University of Sydney
Page 65
Total: 6+3+2+2
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=2
3
7
10
14
18
19
2
11
16
17
23
25
6322
two sorted halves
auxiliary array
2
3
7
10
11
14
16
17
The University of Sydney
Page 66
Total: 6+3+2+2
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=2
3
7
10
14
18
19
2
11
16
17
23
25
6322
two sorted halves
auxiliary array
2
3
7
10
11
14
16
17
18
The University of Sydney
Page 67
Total: 6+3+2+2
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=1
6322
two sorted halves
auxiliary array
3
7
10
14
18
19
2
11
16
17
23
25
2
3
7
10
11
14
16
17
18
The University of Sydney
Page 68
Total: 6+3+2+2
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=1
6322
two sorted halves
auxiliary array
3
7
10
14
18
19
2
11
16
17
23
25
2
3
7
10
11
14
16
17
18
19
The University of Sydney
Page 69
Total: 6+3+2+2
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
first half exhausted
i = 0
3
7
10
14
18
19
2
11
16
17
23
25
6322
two sorted halves
auxiliary array
2
3
7
10
11
14
16
17
18
19
The University of Sydney
Page 70
Total: 6+3+2+2
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=0
63220
two sorted halves
auxiliary array
3
7
10
14
18
19
2
11
16
17
23
25
2
3
7
10
11
14
16
17
18
19
23
The University of Sydney
Page 71
Total: 6+3+2+2+0
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=0
63220
two sorted halves
auxiliary array
3
7
10
14
18
19
2
11
16
17
23
25
2
3
7
10
11
14
16
17
18
19
23
The University of Sydney
Page 72
Total: 6+3+2+2+0
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=0
632200
two sorted halves
auxiliary array
3
7
10
14
18
19
2
11
16
17
23
25
2
3
7
10
11
14
16
17
18
19
23
25
The University of Sydney
Page 73
Total: 6+3+2+2+0+0
Merge and Count
– Merge and count step.
– Given two sorted halves, count number of inversions where ai and ak are
in different halves.
– Combine two sorted halves into sorted whole.
i=0
632200
two sorted halves
auxiliary array
3
7
10
14
18
19
2
11
16
17
23
25
2
3
7
10
11
14
16
17
18
19
23
25
The University of Sydney
Page 74
Total: 6+3+2+2+0+0=13
Counting Inversions: Combine
Combine: count blue-green inversions
– Assume each half is sorted.
– Count inversions where ai and ak are in different halves. – Merge two sorted halves into sorted whole.
632200
13blue-greeninversions: 6+3+2+2+0+0
Count: O(n) Merge: O(n)
3
7
10
14
18
19
2
11
16
17
23
25
2
3
7
10
11
14
16
17
18
19
23
25
Time: T(n) = 2T(n/2) + O(n) = O(n log n) The University of Sydney
Page 75
Counting Inversions: Implementation
– Pre-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 halves A and B (rA, A) ¬ Sort-and-Count(A)
(rB, B) ¬ Sort-and-Count(B)
(rC, L) ¬ Merge-and-Count(A, B)
returnr=rA +rB +rC andthesortedlistL }
Useful strategy: Strengthen inductive hypothesis
The University of Sydney
Page 76
Closest Pair of Points
The University of Sydney Page 77
Closest Pair of Points
– Closest pair. Given n points in the plane, find a pair with smallest Euclidean distance between them.
– Fundamentalgeometricprimitive.
– Graphics,computervision,geographicinformationsystems,molecular
modeling, air traffic control.
– Specialcaseofnearestneighbor,EuclideanMST,Voronoidiagram…
– Brute force. Check all pairs of points p and q with Q(n2) comparisons.
– 1-D version. O(n log n) easy if points are on a line.
– Assumption. No two points have same x coordinate.
The University of Sydney
Page 78
Closest Pair of Points
– Algorithm.
– Divide: draw vertical line L so that roughly 1⁄2n points on each side.
L
The University of Sydney Page 79
Closest Pair of Points
– Algorithm.
– Divide: draw vertical line L so that roughly 1⁄2n points on each side. – Conquer: find closest pair in each side recursively.
9
L
21
The University of Sydney Page 80
Closest Pair of Points
– Algorithm.
– Divide: draw vertical line L so that roughly 1⁄2n points on each side. – Conquer: find closest pair in each side recursively.
– Combine:
– find closest pair with one point in each side. – return best of 3 solutions.
8
9
L
21
The University of Sydney
Page 81
Closest Pair of Points
– Find closest pair with one point in each side, assuming that distance ≤ d.
9
L
21
d = min(9, 21)
The University of Sydney Page 82
Closest Pair of Points
– Find closest pair with one point in each side, assuming that distance < d.– Observation: only need to consider points within d of line L. 9 L 21 d = min(9, 21)The University of Sydney d Page 83Closest Pair of Points– Find closest pair with one point in each side, assuming that distance < d.– Observation: only need to consider points within d of line L. – Sort points in 2d-strip by their y-coordinate. L5 764 31 219d = min(9, 21) 2The University of Sydney d Page 84Closest Pair of Points– Find closest pair with one point in each side, assuming that distance < d.– Observation: only need to consider points within d of line L. – Sort points in 2d-strip by their y coordinate.– Only check distances of those within 11 positions in sorted list! L5 764 31 219d = min(9, 21) 2The University of Sydney d Page 85Closest Pair of Points– Definition: Let si be the point in the 2d- strip, with the ith smallest y-coordinate. 3139 j 29 30 27 28 2625 2 rows i1⁄2d 1⁄2d 1⁄2d The University of Sydneyd dPage 86 Closest Pair of Points– Definition: Let si be the point in the 2d- strip, with the ith smallest y-coordinate.– Claim: If |i – k| 3 12, then the distance between si and sk is at least d.2 rows i1⁄2d 1⁄2d 1⁄2d 3139 k 29 30 27 28 2625The University of Sydneyd dPage 87 Closest Pair of Points– Definition: Let si be the point in the 2d- strip, with the ith smallest y-coordinate.– Claim: If |i – k| 3 12, then the distance between si and sk is at least d.2 rowsi1⁄2d 1⁄2d 1⁄2d 3139 k 29 30 27 28 2625 – Proof:– No two points lie in same 1⁄2d-by-1⁄2d box.– Two points at least 2 rows apart have distance 3 2(1⁄2d) = d.▪ The University of Sydneydd Page 88 Closest Pair of Points– Definition: Let si be the point in the 2d- strip, with the ith smallest y-coordinate.– Claim: If |i – k| 3 12, then the distance between si and sk is at least d. 3139 k 29 30 27 28 2625 – Proof:2 rowsi1⁄2d 1⁄2d 1⁄2d– No two points lie in same 1⁄2d-by-1⁄2d box.– Two points at least 2 rows aparthave distance 3 2(1⁄2d) = d. ▪Fact: Still true if we replace 12 with 7. The University of Sydneydd Page 89Closest Pair AlgorithmClosest-Pair(p1, …, pn) {If |P|≤ 3 then compute closest-pair brute forceelseCompute separation line L such that half the pointsare on one side and half on the other side.d1 = Closest-Pair(left half) d2 = Closest-Pair(right half) d = min(d1, d2)Delete all points further than d from separation line L Sort remaining points by y-coordinate.Scan points in y-order and compare distance between each point and next 11 neighbors. If any of these distances is less than d, update d.return d. }O(n log n) 2T(n / 2)O(n)O(n log n)O(n) The University of SydneyPage 90 Closest Pair of Points: Analysis– Running timeT(n)£2T(n/2)+O(nlogn) ÞT(n)=O(nlog2n)– Question: Can we achieve O(n log n)?– Answer: Yes. Don’t sort points in strip from scratch each time.– Each recursive returns two lists: all points sorted by y coordinate, and all points sorted by x coordinate.– Sort by merging two pre-sorted lists. T(n)£2T(n/2)+O(n) Þ T(n)=O(nlogn)The University of SydneyPage 91 Sort P by x-coordinates Þ Px Sort P by y-coordinates Þ PyClosest-Pair(Px,Py) { If |P|≤ 3 then compute closest-pair brute force elseO(n log n)Compute separation line LPx,left = points to the left of L sorted by x-coordinate Py,left = points to the left of L sorted by y-coordinate Px,right= points to the right of L sorted by x-coordinate Py,right= points to the right of L sorted by y-coordinateO(n)O(n)2T(n / 2) O(n) O(n)d1 = Closest-Pair(Px,left,Py,left) d2 = Closest-Pair(Px,right,Py,right) d = min(d1, d2)Delete all points further than d from separation line LScan points in y-order and compare distance between each point and next 11 neighbors. If any of these distances is less than d, update d.return d. The University of Sydney}Page 92 Closest Pair of Points (improved): Analysis– Running timePreprocessing: O(n log n)T(n) = 2 T(n/2) + O(n) = O(n log n) Total running time: O(n log n)The University of SydneyPage 93 Solving recursionsUnrolling and the Master methodThe University of Sydney Page 94 Example of recursion treeSolve T(n) = T(n/4) + T(n/2) + n2:The University of Sydney Page 95 Example of recursion treeSolve T(n) = T(n/4) + T(n/2) + n2:T(n)The University of SydneyPage 96 Example of recursion treeSolve T(n) = T(n/4) + T(n/2) + n2:n2The University of SydneyPage 97T(n/4)T(n/2) Example of recursion treeSolve T(n) = T(n/4) + T(n/2) + n2:n2 (n/4)2(n/2)2 The University of SydneyPage 98T(n/16)T(n/8)T(n/8)T(n/4) Example of recursion treeSolve T(n) = T(n/4) + T(n/2) + n2:n2 (n/4)2(n/2)2 (n/16)2(n/8)2(n/8)2(n/4)2 O(1)The University of SydneyPage 99… Example of recursion treeSolve T(n) = T(n/4) + T(n/2) + n2:n2n2(n/4)2(n/2)2 (n/16)2(n/8)2(n/8)2(n/4)2 O(1)The University of SydneyPage 100… Example of recursion treeSolve T(n) = T(n/4) + T(n/2) + n2:n2n2 5/16 n2(n/4)2(n/2)2(n/16)2(n/8)2(n/8)2(n/4)2 O(1)The University of SydneyPage 101… Example of recursion treeSolve T(n) = T(n/4) + T(n/2) + n2:n2n2 5/16 n225/256 n2 (n/4)2(n/2)2(n/16)2(n/8)2(n/8)2(n/4)2O(1)The University of SydneyPage 102… Example of recursion treeSolve T(n) = T(n/4) + T(n/2) + n2:n2n2 5/16 n225/256 n2 (n/4)2(n/2)2(n/16)2(n/8)2 (n/8)2(n/4)2 O(1)Total =n2 (1+5/16+(5/16)2+(5/16)3+ …)geometric seriesThe University of SydneyPage 103… Aside: geometric series1 + x + x2 + … =1 for x<1 1-x1 + x + x2 + … + xn = 1-xn+1 for x11 1-xThe University of SydneyPage 104 Example of recursion treeSolve T(n) = T(n/4) + T(n/2) + n2:n2n2 5/16 n225/256 n2 (n/4)2(n/2)2(n/16)2(n/8)2 (n/8)2(n/4)2 O(1)n2 (1+5/16+(5/16)2+(5/16)3+ …)The University of SydneyPage 105Total == O(n2) geometric series… The master methodThe master method applies to recurrences of the formT(n) = a·T(n/b) + f(n) ,where a 3 1, b > 1, and f is asymptotically positive.
a = # subproblems
b = factor by which subproblem shrinks
f(n) = time to split and merge
The University of Sydney
Page 106
T(n) = a·T(n/b) + f(n)
size n
size n/b
size (n/b2)
size 1
Branching factor a
height logb n
The University of Sydney
width w = alogb n = nlogb a
Page 107
T(n) = a·T(n/b) + f(n)
size n cost f(n)
size n/b cost a·f(n/b)
size (n/b2) cost a2·f(n/b2)
size 1
cost w·T(1)
Branching factor a
height logb n
The University of Sydney
width w = alogb n = nlogb a
Page 108
Three common cases
T(n) = a·T(n/b) + f(n) Compare f(n) with nlogba:
Case 1:
If f(n) = O(nlogba – e) for any constant e>0 then f(n) grows polynomially slower than nlogba (by an ne factor).
Solution: T(n) = Q(nlogba) .
The University of Sydney Page 109
Idea of master theorem: Case 1
T(n) = a·T(n/b) + f(n)
f(n)
a
…
f(n/b2)
f(n/b)
f(n)
a f(n/b)
a2 f(n/b2)
nlogba T(1)
Q(nlogba) Page 110
logbn
f(n/b2)
f(n/b) f(n/b) a
f(n/b2) …
T(1)
CASE 1: The weight increases geometrically from the root to the leaves. The leaves hold a constant fraction of the total weight.
The University of Sydney
…
…
Three common cases
Case 1: Example
[Compare f(n) with nlogba]
T(n) = 8T(n/2) + 10n2
Þ a= 8, b=2 and f(n)=10n2
f(n) = 10n2
nlogba–e =nlog28–e =O(n3–e)fore=1>0.
Þ f(n) = O(nlogba – e) Þ Case 1 holds.
Solution: T(n) = Q(nlogba) = Q(n3) The University of Sydney
Page 111
Three common cases (cont’d)
[Compare f(n) with nlogba]
Case 2:
If f(n) = Q(nlogba logkn) for some constant k30 then f(n)
and nlogba grow at similar rates. Solution: T(n) = Q(nlogba logk+1n) .
The University of Sydney
Page 112
Idea of master theorem
Recursion tree:
f(n/b)
f(n/b2)
f(n) a f(n/b) …
a
… f(n/b2)
f(n/b)
f(n)
a f(n/b)
a2 f(n/b2)
nlogba T(1)
Q(nlogba h) Page 113
h = logbn f(n/b2)
T(1)
CASE 2: (k = 0) The weight is approximately the same on each of the logbn levels.
The University of Sydney
…
…
Three common cases
[Compare f(n) with nlogba]
Case 2: Example
T(n) = 2T(n/2) + n log n
Þ a= 2, b=2 and f(n)=n log n
f(n) = n log n = Q(nlogba logkn) = Q(n log n) for k=1 Þ Case 2 holds.
Solution: T(n) = Q(nlogba logk+1n) = Q(n log2 n)
The University of Sydney Page 114
Three common cases (cont.)
Case 3:
[Compare f(n) with nlogba]
If f(n) = W(nlogba +e) for some constant e > 0.
• f(n) grows polynomially faster than nlogba (by an ne
factor), and
• f(n) satisfies the regularity condition that a·f(n/b)
≤ c·f(n) for some constant c < 1. Solution: T(n) = Q(f(n)) .The University of Sydney Page 115Idea of master theoremRecursion tree:f(n)f(n/b) …a… f(n/b2)af(n)a f(n/b)a2 f(n/b2)nlogba T(1)Q(f(n))Page 116 f(n/b)f(n/b2)f(n/b) h = logbn f(n/b2)T(1)CASE 3: The weight decreases geometrically from the root to the leaves. The root holds a constant fraction of the total weight.The University of Sydney…… Three common casesT(n) = 4T(n/2) + n3[Compare f(n) with nlogba]a=4,b=2 Þ nlogba=n2and f(n)=n3.CASE 3: f(n) = W(n2 + e) for e = 1 and4(cn/2)3 ≤ cn3 (reg. cond.) for c = 1/2.Solution: T(n) = Q(n3) The University of SydneyPage 117 Integer MultiplicationThe University of Sydney Page 118 Integer Arithmetic– Add. Given two n-bit integers a and b, compute a + b. – O(n) bit operations.– Multiply. Given two n-bit integers a and b, compute a × b. – Brute force solution: Q(n2) bit operations. Multiply11111101 +1 0 101 0101 1 111 11010 101 0010 01011 011 0 011 0 1 011 0 1 0 001 0 1 0 1 0*10 0 1 0 1 0 01 01 0 1 0 1 0 1 01 10 0 0 1 0 1 00 11 0 1 0 1 01 10 0 0 1 00 11 0 1 01 10 0 00 01 01 10 0110100000Add 0000010 The University of Sydney Page 119 Divide-and-Conquer Multiplication: Warmup– To multiply two n-bit integers:– Given two numbers A and B with n bits each.– Partition the n bits into the n/2 “high” bits and the n/2 “low” bits.A A=AH ·2n/2+AL AHAL BHBLThe University of SydneyPage 120BB=BH ·2n/2+BL Divide-and-Conquer Multiplication: Warmup– To multiply two n-bit integers:– Given two numbers A and B with n bits each.– Reduce to multiplications of n/2 bit numbers– Partition the n bits into the n/2 “high” bits and the n/2 “low” bits.A A=AH ·2n/2+ALB=BH ·2n/2+BL ® A · B = (AH · 2n/2 + AL) · (BH · 2n/2 + BL) AHAL BHBLThe University of SydneyPage 121B Divide-and-Conquer Multiplication: Warmup– To multiply two n-bit integers:– Given two numbers A and B with n bits each.– Reduce to multiplications of n/2 bit numbers– Partition the n bits into the n/2 “high” bits and the n/2 “low” bits.A A=AH ·2n/2+ALB=BH ·2n/2+BL ® A · B = (AH · 2n/2 + AL) · (BH · 2n/2 + BL)=AH BH ·2n+AHBL ·2n/2+ALBH ·2n/2+ALBL– 4 multiplications of n/2-bit numbers: AHBH, AHBL, ALBH, ALBL ,additions and shifts. Multiplications by powers of 2 are justshifts. The University of Sydney AHALBHBLBPage 122 Divide-and-Conquer Multiplication: Warmup– To multiply two n-bit integers:– Given two numbers A and B with n bits each.– Reduce to multiplications of n/2 bit numbers– Partition the n bits into the n/2 “high” bits and the n/2 “low” bits.A A=AH ·2n/2+AL AHAL BHBLBB=BH ·2n/2+BL® A · B = (AH · 2n/2 + AL) · (BH · 2n/2 + BL)=AH BH ·2n+AHBL ·2n/2+ALBH ·2n/2+ALBL T(n) = 4T n/2 + Q(n) Þ T(n)=Q(n ) ()2!!recursive callsadd, shift”$! #! $! %! !” #! %! !The University of SydneyPage 123 Karatsuba Multiplication [1960]– Multiplytwon-bitintegersA AH AL A = AH · 2n/2 + ALObservation:B BH BLB=BH ·2n/2+BLA·B=AH BH ·2n+AHBL ·2n/2+ALBH ·2n/2+ALBL=AH BH ·2n+[AHBL +ALBH]·2n/2+ALBL=AHBH ·2n+[(AH+AL)·(BH+BL)-AHBH -ALBL]·2n/2 +ALBLTheorem: [Karatsuba-Ofman, 1962]3 multiplications of n/2-bit numbers + additions, subtractions and shifts.The University of Sydney Page 124 Karatsuba: Recursion TreeApplying Master Theorem, a = 3, b = 2, f(n) = n => nlog2 3 is polynomially larger than f(n)
=> T(n) = O(nlog2 3) = O(n1.59)
T(n)=ìí 0 if n=1
î 3T(n/2) + n otherwise
T(n)
T(n/2) T(n/2) T(n/2)
T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4)
1 × (n)
3 × (n/2)
9 × (n/4) …
3k ×(n/2k)
…
nlog2 3 × (2)
…
T(n/2k)
…
T(2) T(2) T(2) T(2)
T(2)
T(2) T(2) T(2)
The University of Sydney
Page 125
Summary: Divide-and-Conquer
– Divide-and-conquer.
– Break up problem into several parts.
– Solve each part recursively.
– Combine solutions to sub-problems into overall solution.
– Mastertheorem – Problems
This weeks quiz is all about solving recurrences!
The University of Sydney
Page 126
– – –
Merge Sort Closest pair Multiplication
Reviews
There are no reviews yet.