CS代考程序代写 chain database algorithm computational biology AI The University of Sydney

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.
– 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 23 The 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 23 The 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 23 The 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 23 The 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 23 The 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 23 The 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 19 0 1 3 4 5 7 10 13 15 18 19 23 Analyze recurrence via recursion tree log2n T(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 Sydney Page 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 21 0 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 Sydney Page 22 Mergesort 1. 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 S divide O(1) A L G O R I T H M S sort 2T(n/2) A G L O R H I M S T merge 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 T A G H I The University of Sydney Page 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 A The University of Sydney Page 25 auxiliary 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 Sydney Page 26 auxiliary 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 The University of Sydney Page 27 auxiliary 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 Sydney Page 28 auxiliary 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 L The University of Sydney Page 29 auxiliary 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 Sydney Page 30 auxiliary 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 The University of Sydney Page 31 auxiliary 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 Sydney Page 32 auxiliary 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 exhausted smallest A G L O R H I M S T A G H I L M O R S The University of Sydney Page 33 auxiliary 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 exhausted smallest A G L O R H I M S T A G H I L M O R S T The University of Sydney Page 34 auxiliary 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 exhausted second 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 # comparisons auxiliary array Page 35 Mergesort 1. 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 S divide O(1) A L G O R I T H M S sort 2T(n/2) A G L O R H I M S T merge 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. 0 T(én/2ù) + T(ën/2û) + O(n) – Solution: T(n) = ? The University of Sydney if n=1 otherwise T(n) = Page 37 Proof by unrolling ìc T(n)=ïí 2T (n / 2) + cn if n=1 otherwise ïî%"$"# ! 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 Sydney Page 38 Proof by unrolling ìc T(n)=ïí 2T (n / 2) + cn if n=1 otherwise ïî%"$"# ! 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) ® cn 2 (of size n/2) ® cn 4 (of size n/4) ® cn log2n ... 2k (of size n/2k) ® cn ... n(of size 1) ® cn Page 39 T(n/4) T(n/2) T(n/4) T(1) T(1) The University of Sydney T(1) T(1) Proof by unrolling ìc T(n)=ïí 2T (n / 2) + cn if n=1 otherwise ïî%"$"# ! 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) ® cn 2 (of size n/2) ® cn 4 (of size n/4) ® cn log2n ... 2k (of size n/2k) ® cn ... n(of size 1) ® cn cn log2n Page 40 T(n/4) T(n/2) T(n/4) T(1) T(1) The University of Sydney T(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) £íT n/2 + T n/2 + n otherwise !! î solve left half solve right half ï (é ù) (ë û) ï " $! #! $! %! ! " $! #! $! %! ! & merging – Solution: T(n) = O(n log2 n). The University of Sydney Page 41 Counting Inversions The 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. – Songsiandkinvertedifiak.
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 83 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. – Sort points in 2d-strip by their y-coordinate. L 5 7 6 4 3 1 21 9 d = min(9, 21) 2 The University of Sydney d Page 84 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. – Sort points in 2d-strip by their y coordinate. – Only check distances of those within 11 positions in sorted list! L 5 7 6 4 3 1 21 9 d = min(9, 21) 2 The University of Sydney d Page 85 Closest Pair of Points – Definition: Let si be the point in the 2d- strip, with the ith smallest y-coordinate. 31 39 j 29 30 27 28 26 25 2 rows i 1⁄2d 1⁄2d 1⁄2d The University of Sydney d d Page 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 i 1⁄2d 1⁄2d 1⁄2d 31 39 k 29 30 27 28 26 25 The University of Sydney d d Page 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 rows i 1⁄2d 1⁄2d 1⁄2d 31 39 k 29 30 27 28 26 25 – 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 Sydney d d 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. 31 39 k 29 30 27 28 26 25 – Proof: 2 rows i 1⁄2d 1⁄2d 1⁄2d – 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. ▪ Fact: Still true if we replace 12 with 7. The University of Sydney d d Page 89 Closest Pair Algorithm Closest-Pair(p1, ..., pn) { If |P|≤ 3 then compute closest-pair brute force else Compute separation line L such that half the points are 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 Sydney Page 90 Closest Pair of Points: Analysis – Running time T(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 Sydney Page 91 Sort P by x-coordinates Þ Px Sort P by y-coordinates Þ Py Closest-Pair(Px,Py) { If |P|≤ 3 then compute closest-pair brute force else O(n log n) Compute separation line L Px,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-coordinate O(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 L 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. The University of Sydney } Page 92 Closest Pair of Points (improved): Analysis – Running time Preprocessing: 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 Sydney Page 93 Solving recursions Unrolling and the Master method The University of Sydney Page 94 Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: The University of Sydney Page 95 Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: T(n) The University of Sydney Page 96 Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: n2 The University of Sydney Page 97 T(n/4) T(n/2) Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: n2 (n/4)2 (n/2)2 The University of Sydney Page 98 T(n/16) T(n/8) T(n/8) T(n/4) Example of recursion tree Solve 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 Sydney Page 99 ... Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: 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 Sydney Page 100 ... Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: n2 n2 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 Sydney Page 101 ... Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: n2 n2 5/16 n2 25/256 n2 (n/4)2 (n/2)2 (n/16)2 (n/8)2 (n/8)2 (n/4)2 O(1) The University of Sydney Page 102 ... Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: n2 n2 5/16 n2 25/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 series The University of Sydney Page 103 ... Aside: geometric series 1 + x + x2 + ... = 1 for x<1 1-x 1 + x + x2 + ... + xn = 1-xn+1 for x11 1-x The University of Sydney Page 104 Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: n2 n2 5/16 n2 25/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 Sydney Page 105 Total = = O(n2) geometric series ... The master method The master method applies to recurrences of the form T(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 115 Idea of master theorem Recursion tree: f(n) f(n/b) ... a ... f(n/b2) a f(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 cases T(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 and 4(cn/2)3 ≤ cn3 (reg. cond.) for c = 1/2. Solution: T(n) = Q(n3) The University of Sydney Page 117 Integer Multiplication The 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. Multiply 11111101 + 1 0 101 010 1 1 111 110 1 0 101 001 0 0 1 0 1 1 0 1 1 0 0 1 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 0 * 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 0 Add 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 AH AL BH BL The University of Sydney Page 120 B B=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+AL B=BH ·2n/2+BL ® A · B = (AH · 2n/2 + AL) · (BH · 2n/2 + BL) AH AL BH BL The University of Sydney Page 121 B 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 B=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 just shifts. The University of Sydney AH AL BH BL B Page 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 AH AL BH BL B B=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 calls add, shift "$! #! $! %! ! " #! %! ! The University of Sydney Page 123 Karatsuba Multiplication [1960] – Multiplytwon-bitintegers A AH AL A = AH · 2n/2 + AL Observation: B BH BL B=BH ·2n/2+BL A·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 +ALBL Theorem: [Karatsuba-Ofman, 1962] 3 multiplications of n/2-bit numbers + additions, subtractions and shifts. The University of Sydney Page 124 Karatsuba: Recursion Tree Applying 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)=ìí 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

Related Posts