Microsoft PowerPoint – CSE101 3 Divide-and-Conquer.pptx
O. Braun
1Divide‐and‐Conquer
Divide‐And‐Conquer
Mergesort
O. Braun
2Divide‐and‐Conquer
Divide‐and‐Conquer: Basic Idea
Because Divide‐and‐Conquer creates at least two subproblems,
a Divide‐and‐Conquer algorithm makes multiple recursive calls.
O. Braun
3Divide‐and‐Conquer
Divide‐and‐Conquer: Mergesort
11, 9, 7, 2, 13, 12, 6
11, 9, 7, 2 13, 12, 6
11, 9 7, 2 13, 12 6
11 9 7 2 13 12 6
9, 11 2, 7 12, 13 6
2, 7, 9, 11 6, 12, 13
2, 6, 7, 9, 11, 12, 13
divide divide
divide dividedivide divide
divide divide divide divide divide divide divide
conquer
combine combine combine combine combine combinecombine
combine combine combine combine
combine combine
Mergesort(A[1..n])
1 if(n == 1) then return(A[1]);
2 B[1..n/2] := Mergesort(A[1..n/2]);
3 C[1..n/2] := Mergesort(A[n/2+1..n]);
4 return(Merge(B[1..n/2],C[1..n/2]));
O. Braun
4Divide‐and‐Conquer
Mergesort: Correctness
Mergesort(A[1..n])
1 if(n == 1) then return(A[1]);
2 B[1..n/2] := Mergesort(A[1..n/2]);
3 C[1..n/2] := Mergesort(A[n/2+1..n]);
4 return(Merge(B[1..n/2],C[1..n/2]));
Prove (strong induction on n).
• Base Case (n=1): When n=1, then Mergesort returns A[1] which is sorted by itself.
• Strong Induction Hypothesis: Suppose n>2. Assume that Mergesort(A[1..n/2]) and
Mergesort(A[n/2+1..n]) each return a sorted array. (Remember: In strong induction, you assume that
the statement you want to show holds for all integers n’ with k < n’ < n. We use strong induction
whenever a recursive algorithm acting on an input of size n makes calls with inputs of size other than
n-1.)
• Induction Step: Mergesort is called on two instances of size n/2. By the IH, this returns two sorted
arrays, B is the sorted first half of A, and C is the sorted second half of A. Because the function
Merge is correct, this outputs the sorted version of the input A.
Mergesort returns a sorted array
that contains the elements A[1..n].
C
or
re
ct
ne
ss
O. Braun
5Divide‐and‐Conquer
Mergesort: Time anaylsis
Ti
m
e
an
al
ys
isMergesort(A[1..n])
1 if(n == 1) then return(A[1]);
2 B[1..n/2] := Mergesort(A[1..n/2]);
3 C[1..n/2] := Mergesort(A[n/2+1..n]);
4 return(Merge(B[1..n/2],C[1..n/2]));
Let T(n) be the number of
comparisons.
Time analysis strategy:
“Unraveling the recurrence”
O. Braun
6Divide‐and‐Conquer
Master Theorem
Mergesort:
𝑇(𝑛) = 2 𝑇(𝑛/2) + (n-1) = 2 𝑇(𝑛/2) + O(n1)
a=2 b=2 d=1
a=bd
O(nd log n) = O(n log n)
O. Braun
7Divide‐and‐Conquer
Divide‐And‐Conquer
Multiplication of two
n‐digit numbers
O. Braun
8Divide‐and‐Conquer
One Multiplication of two 6‐digit numbers
467 322 319 269
140196600000
4205898000
04673220000
093464400
4205898
28039320
149201427618
Time: n2 multiplications
One multiplication of two 6-digit numbers can be done by „school multiplication“
with 6x6=36 multiplications of two digits (plus some additions and shifts):
O. Braun
9Divide‐and‐Conquer
Four Multiplications of two 3‐digit numbers
467 322 319 269
We could divide the multiplication of two 6-digit numbers
in four multiplications of two 3-digit numbers (plus some additions and shifts).
O. Braun
10Divide‐and‐Conquer
Four Multiplications of two 3‐digit numbers
467 322 319 269
We could divide the multiplication of two 6-digit numbers
in four multiplications of two 3-digit numbers (plus some additions and shifts).
O. Braun
11Divide‐and‐Conquer
Four Multiplications of two 3‐digit numbers
467 322 319 269
We could divide the multiplicatuion of two 6-digit numbers
in four multiplications of two 3-digit numbers (plus some additions and shifts).
Again, by „school multiplication“, one multiplication of two 3-digit numbers can be done
with 3x3=9 multiplications of two digits (plus some additions and shifts).
467 319
1401
4203
467
148973
So we come again to 4x9=36 multiplications of two digits no gain.
O. Braun
12Divide‐and‐Conquer
Solving the recurrence
O. Braun
13Divide‐and‐Conquer
Multiplication: Karatsuba‘s idea
Karatsuba‘s idea: Compute the same with only
three multiplication of two 3-digit numbers.
But how could that work?
467 322 319 269
We could divide the multiplicatuion of two 6-digit numbers
in four multiplications of two 3-digit numbers (plus some additions and shifts).
O. Braun
14Divide‐and‐Conquer
Multiplication: Karatsuba‘s idea
467 322 319 269
We could divide the multiplicatuion of two 6-digit numbers
in four multiplications of two 3-digit numbers (plus some additions and shifts).
A = 467x319
B = 322x269
C = (467-322)x(269-319) + A + B = 467x269 + 322x319 – 467x319 – 322x269 + A + B
= 467x269 + 322x319 – A – B + A + B
= 467x269 + 322x319
Karatsuba‘s idea: Compute the same with only
three multiplication of two 3-digit numbers.
But how could that work?
O. Braun
15Divide‐and‐Conquer
Multiplication: Karatsuba
Time: O(n1.58)
O. Braun
16Divide‐and‐Conquer
2019: World record
O(n2) School multiplication
1962 O(nlog23) A. Karatsuba,Y. Ofman
Multiplication of Many-Digital Numbers by Automatic Computers
Proceedings of the USSR Academy of Sciences 145, 293-294 (1962)
Physics-Doklady 7, 595-596 (1963)
1971 O(n log n log log n) A. Schönhage, V. Strassen
Schnelle Multiplikation großer Zahlen
Computing 7, 281-292 (1971)
2007 O(n log n 2O(log*n)) M. Fürer
Faster Integer Multiplication
Proceedings of the 39th annual ACM Symposium on Theory of Computing
(STOC), 55–67, San Diego, CA, June 11–13, 2007
SIAM Journal on Computing 39, 979–1005, 2009
2016 O(n log n 23log*n) D. Harvey, J. van der Hoeven, G. Lecerf
Even faster integer multiplication
arXiv:1407.3360 (2015)
2019 O(n log n) D. Harvey, J. van der Hoeven
Integer multiplication in time O(n log n)
https://hal.archives-ouvertes.fr/hal-02070778 (2019-04-12)
O. Braun
17Divide‐and‐Conquer
Iterated logarithm log*n
The iterated logarithm of n, written log*n, usually read "log star", is the number of times the logarithm function must
be iteratively applied before the result is less than or equal to 1:
The iterated logarithm grows at an extremely slow rate, much slower than the logarithm itself.
For all values of n relevant to counting the running times of algorithms implemented in practice (i.e., n ≤ 265536, which
is far more than the estimated number of atoms in the known universe), the iterated logarithm with base 2 has a value
no more than 5:
n lg* n
(−∞, 1] 0
(1, 2] 1
(2, 4] 2
(4, 16] 3
(16, 65536] 4
(65536, 265536] 5