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 12n. 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[1n/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[1n/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[1n/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[1n/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[1n/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[1n/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[1n/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[1n/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[1n/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[1n/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(en/2u) + T(en/2u) + O(n) Solution: T(n) = ? The University of Sydneyif n=1 otherwise T(n) =Page 37 Proof by unrollingicT(n)=ii 2T (n / 2) + cnif n=1 otherwiseii%”$”# ! 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 unrollingicT(n)=ii 2T (n / 2) + cnif n=1 otherwiseii%”$”# ! 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 icT(n)=ii 2T (n / 2) + cnif n=1 otherwiseii%”$”# ! 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. i 0 if n=1 T(n) iT n/2 + T n/2 + n otherwise!!i solve left half solve right halfi (e u) (e u) i ” $! #! $! %! ! ” $! #! $! %! !&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 Googles ranking function.
Rank aggregation for meta-searching on the Web.
Nonparametric statistics (e.g., Kendalls 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 12n points on each side.
L
The University of Sydney Page 79
Closest Pair of Points
Algorithm.
Divide: draw vertical line L so that roughly 12n 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 12n 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 i12d 12d 12d 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 i12d 12d 12d 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 rowsi12d 12d 12d 3139 k 29 30 27 28 2625 Proof: No two points lie in same 12d-by-12d box. Two points at least 2 rows apart have distance 3 2(12d) = 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 rowsi12d 12d 12d No two points lie in same 12d-by-12d box. Two points at least 2 rows aparthave distance 3 2(12d) = 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) = aT(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) = aT(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) = aT(n/b) + f(n)
size n cost f(n)
size n/b cost af(n/b)
size (n/b2) cost a2f(n/b2)
size 1
cost wT(1)
Branching factor a
height logb n
The University of Sydney
width w = alogb n = nlogb a
Page 108
Three common cases
T(n) = aT(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) = aT(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
nlogbae =nlog28e =O(n3e)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 (contd)
[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 af(n/b)
cf(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+BLAB=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)=ii 0 if n=1
i 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.