COMP251: Divide-and-Conquer (1)
Jérôme Waldispühl School of Computer Science
McGill University
Based on (Kleinberg & Tardos, 2005) and slides by K. Wayne & Snoeyink
Divide and Conquer • Recursiveinstructure
– Divide the problem into sub-problems that are similar to the original but smaller in size
– Conquer the sub-problems by solving them recursively. If they are small enough, just solve them in a straightforward manner.
– Combine the solutions to create a solution to the original problem
An Example: Merge Sort
Sorting Problem: Sort a sequence of n elements into non-decreasing order.
• Divide: Divide the n-element sequence to be sorted into two subsequences of n/2 elements each
• Conquer: Sort the two subsequences recursively using merge sort.
• Combine: Merge the two sorted subsequences to produce the sorted answer.
Sorting applications
Obvious applications.
・Organize an MP3 library.
・Display Google PageRank results.
・List RSS news items in reverse chronological order.
Some problems become easier once elements are sorted.
・Identify statistical outliers. ・Binary search in a database. ・Remove duplicates in a mailing list.
Non-obvious applications.
・Convex hull.
・Closest pair of points.
・Interval scheduling / interval partitioning.
・Minimum spanning trees (Kruskal’s algorithm).
・Scheduling to minimize maximum lateness or average completion time. ・…
5
18
26
32
6
43
15
9
1
1
6
9
15
18
26
32
43
6
18
26
32
18
26
32
6
43
15
9
1
1
9
15
43
18
26
32
6
43
15
9
1
18
26
6
32
15
43
1
9
18
26
32
6
43
15
9
1
18
26
32
6
43
15
9
1
18
26
32
6
43
15
9
1
Merge Sort – Example
Original Sequence
Sorted Sequence
Merge-Sort (A, p, r)
INPUT: a sequence of n numbers stored in array A OUTPUT: an ordered sequence of n numbers
MergeSort (A, p, r) // sort A[p..r] by divide & conquer
1 2 3 4 5
ifp
Merge(A, p, q, r)
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.
n1 ¬ q – p + 1 n2¬r–q fori¬1ton1
do L[i] ¬ A[p + i – 1] forj¬1ton2
do R[j] ¬ A[q + j] L[n1+1] ¬ ¥ R[n2+1] ¬ ¥
i¬1
j¬1 fork¬ptor
do if L[i] £ R[j] then A[k] ¬ L[i]
i¬i+1 else A[k] ¬ R[j]
j¬j+1
Termination:
•On termination, k = r + 1.
•By LI, A contains r – p + 1 smallest
elements of L and R in sorted order.
•L and R together contain r – p + 3 elements including the two sentinels. So all elements are sorted.
Analysis of Merge Sort
• RunningtimeT(n)ofMergeSort:
• Divide:computingthemiddletakesQ(1)
• Conquer:solving2subproblemstakes2T(n/2) • Combine:mergingnelementstakesQ(n)
• Total:
Þ T(n) = Q(n lg n)
T(n) = Q(1) if n = 1 T(n)=2T(n/2)+Q(n) ifn>1
A useful recurrence relation
Def. T (n) = max number of compares to mergesort a list of size ≤ n. Note. T (n) is monotone nondecreasing.
Mergesort recurrence.
T(n) ≤
0 if n = 1 T(!n/2″) + T(#n/2$) + n otherwise
Solution. T(n)isO(nlog2n).
Assorted proofs. We describe several ways to prove this recurrence. Initially we assume n is a power of 2 and replace ≤ with =.
8
Divide-and-conquer recurrence: proof by recursion tree
Proposition. If T (n) satisfies the following recurrence, then T (n) = n log2 n.
Pf 1.
T(n) =
0
2T(n/2) + n
T (n)
if n = 1 otherwise
assuming n is a power of 2
n=n
T (n / 2)
T (n / 2)
2 (n/2) 4 (n/4)
8(n/8)
= n
= n
= n
T (n / 4)
T (n / 4)
T (n / 4)
T (n / 4)
log 2 n
T(n/8) T(n/8) T(n/8) T(n/8)
T(n/8) T(n/8) T(n/8) T(n/8)
⋮
T(n) = n lg n
⋮
9
Proof by induction
Proposition. If T (n) satisfies the following recurrence, then T (n) = n log2 n.
T(n) =
0
2T(n/2) + n
if n = 1 otherwise
assuming n is a power of 2
P・f 2. [by induction on n]
・Base case: when n = 1, T(1) = 0.
・Inductive hypothesis: assume T(n) = n log n. 2
Goal: show that T(2n) = 2n log (2n). 2
T(2n) = 2 T(n) + 2n
= 2 n log2 n + 2n
= 2 n (log2 (2n) – 1) + 2n = 2nlog2(2n). ▪
10
Analysis of mergesort recurrence
Claim. If T(n) satisfies the following recurrence, then T(n) ≤ n !log2 n”.
T(n) ≤
0 if n = 1 T(!n/2″) + T(#n/2$) + n otherwise
Pf. [by strong induction on n]
・Base case: n = 1.
・Definen =#n/2$ andn =!n/2″. 12
・Induction step: assume true for 1, 2, … , n – 1.
n2 = dn/2e
n
12 22/2
T(n) ≤ T(n ) + T(n ) + n
l2 2 /2m
≤n!logn”+n!logn”+n 121222
≤ n !log n”+n !log n”+ n 1 2 2 2 2 2
2dlog ne dlog 2ne
= n!log2n2″ +n ≤ n (!log2 n” – 1)
+ n
log2n2 dlog2ne 1 dlog2 n2e dlog2 ne 1
n = dn/2e n2 = dn/2e
2
lm lm ldlogne m
= dn/2e
2 2dlog2 ne / 2
/2 =2dlog ne/2 = 2dlog2 ne / 2
=22/2 dlog nedlog2ne 1
2 2 =2dlog2ne/2
dlog n e dlog ne 1 dlog n2edlog ne 1
222 22
2
=n!log2n”. ▪
11
Arithmetic operations
Given 2 (binary) numbers, we want efficient algorithms to:
• Add 2 numbers
• Multiply 2 numbers (using divide-and-conquer!)
Integer addition
Addition. Given two n-bit integers a and b, compute a + b. Subtraction. Given two n-bit integers a and b, compute a – b.
Grade-school algorithm. Θ(n) bit operations.
1
1
1
1
1
1
0
1
1
1
0
1
0
1
0
1
+
0
1
1
1
1
1
0
1
1
0
1
0
1
0
0
1
0
Remark. Grade-school addition and subtraction algorithms are asymptotically optimal.
13
Integer multiplication
Multiplication. Given two n-bit integers a and b, compute a × b. Grade-school algorithm. Θ(n2) bit operations.
1
1
0
1
0
1
0
1
×
0
1
1
1
1
1
0
1
1
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
1
0
1
0
1
0
1
1
1
0
1
0
1
0
1
1
1
0
1
0
1
0
1
1
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
1
Conjecture. [Kolmogorov 1952] Grade-school algorithm is optimal. Theorem. [Karatsuba 1960] Conjecture is wrong.
14
Divide-and-conquer multiplication
T・o multiply two n-bit integers x and y:
・Divide x and y into low- and high-order bits. ・Multiply four 1⁄2n-bit integers, recursively.
Add and shift to obtain result.
m=#n/2$
a = ! x / 2m” b = x mod 2m c = ! y / 2m” d = y mod 2m
use bit shifting to compute 4 terms
(2m a + b) (2m c + d) = 22m ac + 2m (bc + ad) + bd 1234
y
Ex. x =10001101 y =11100001
abc
x
d
15
Divide-and-conquer multiplication
MULTIPLY(x, y, n) _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
IF (n = 1) RETURN x”y.
ELSE
m ← # n / 2 $.
a ← ! x / 2m”;
c ← ! y / 2m”;
e ← MULTIPLY(a, c, m). f ← MULTIPLY(b, d, m). g ← MULTIPLY(b, c, m). h ← MULTIPLY(a, d, m).
RETURN 22m e + 2m (g + h) + f. _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
b ← x mod 2m. d ← y mod 2m.
16
Divide-and-conquer multiplication analysis
Proposition. The divide-and-conquer multiplication algorithm requires Θ(n2) bit operations to multiply two n-bit integers.
Pf. Apply case 1 of the master theorem to the recurrence:
€
T(n) = 4T(n/2) + Θ(n) ⇒ T(n)=Θ(n2)
recursive calls add, shift
Next class!
17
Karatsuba trick
To compute middle term bc + ad, use identity: bc + ad = ac + bd – (a – b) (c – d)
m=#n/2$
a = ! x / 2m” b = x mod 2m c = ! y / 2m” d = y mod 2m
middle term
(2m a + b) (2m c + d) = 22m ac + 2m (bc + ad ) + bd
= 22m ac + 2m (ac + bd – (a – b)(c – d)) + bd
11323
Bottom line. Only three multiplication of n / 2-bit integers.
18
Karatsuba multiplication
KARATSUBA-MULTIPLY(x, y, n) _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
IF (n = 1) RETURN x”y.
ELSE
m ← # n / 2 $.
a ← ! x / 2m”;
c ← ! y / 2m”;
e ← KARATSUBA-MULTIPLY(a, c, m).
f ← KARATSUBA-MULTIPLY(b, d, m).
g ← KARATSUBA-MULTIPLY(a – b, c – d, m).
RETURN 22m e + 2m (e + f – g) + f. _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
b ← x mod 2m. d ← y mod 2m.
19
Karatsuba analysis
Proposition. Karatsuba’s algorithm requires O(n1.585) bit operations to multiply two n-bit integers.
Pf. Apply case 1 of the master theorem to the recurrence: T(n) = 3 T(n/2) + Θ(n) ⇒ T(n) = Θ(nlg 3) = O(n1.585).
Next class!
Practice. Faster than grade-school algorithm for about 320-640 bits.
20
Integer arithmetic reductions
Integer multiplication. Given two n-bit integers, compute their product.
problem
arithmetic
running time
integer multiplication
a×b
Θ(M(n))
integer division
a/b, amodb
Θ(M(n))
integer square
a2
Θ(M(n))
integer square root
!√a ”
Θ(M(n))
integer arithmetic problems with the same complexity as integer multiplication
21
History of asymptotic complexity of integer multiplication
year
algorithm
order of growth
?
brute force
Θ(n2)
1962
Karatsuba-Ofman
Θ(n1.585)
1963
Toom-3, Toom-4
Θ(n1.465), Θ(n1.404)
1966
Toom-Cook
Θ(n1 + ε)
1971
Schönhage–Strassen
Θ(n log n log log n)
2007
Fürer
n log n 2 O(log*n)
?
?
Θ(n)
number of bit operations to multiply two n-bit integers
used in Maple, Mathematica, gcc, cryptography, …
Remark. GNU Multiple Precision Library uses one of five different algorithm depending on size of operands.
22