THE UNIVERSITY OF NEW SOUTH WALES
3. DIVIDE-AND-CONQUER
Raveen de Silva,
office: K17 202
Copyright By PowCoder代写 加微信 powcoder
Course Admin: ,
School of Computer Science and Engineering UNSW Sydney
Term 1, 2022
Table of Contents
1. Introductory Examples 1.1 Coin puzzle
1.2 Counting inversions
2. Recurrences
2.1 Framework
2.2 Master Theorem
3. Integer Multiplication
3.1 Applying D&C to multiplication of large integers 3.2 The Karatsuba trick
4. Sorting and selection
4.1 Quicksort and quickselect 4.2 Median of medians
Table of Contents
1. Introductory Examples 1.1 Coin puzzle
1.2 Counting inversions
2. Recurrences
2.1 Framework
2.2 Master Theorem
3. Integer Multiplication
3.1 Applying D&C to multiplication of large integers 3.2 The Karatsuba trick
4. Sorting and selection
4.1 Quicksort and quickselect 4.2 Median of medians
An old puzzle
We are given 27 coins of the same denomination; we know that one of them is counterfeit and that it is lighter than the others. Find the counterfeit coin by weighing coins on a pan balance only three times.
You can reduce the search space by a third in one weighing!
An old puzzle
Divide the coins into three groups of nine, say A, B and C. Weigh group A against group B.
If one group is lighter than the other, it contains the coun- terfeit coin.
If instead both groups have equal weight, then group C contains the counterfeit coin!
Repeat with three groups of three, then three groups of one.
Divide and Conquer
This method is called “divide-and-conquer”.
We have already seen a prototypical “serious” algorithm
designed using such a method: the Merge-Sort.
We split the array into two, sort the two parts recursively and
then merge the two sorted arrays.
We now look at a closely related but more interesting problem of counting inversions in an array.
Table of Contents
1. Introductory Examples 1.1 Coin puzzle
1.2 Counting inversions
2. Recurrences
2.1 Framework
2.2 Master Theorem
3. Integer Multiplication
3.1 Applying D&C to multiplication of large integers 3.2 The Karatsuba trick
4. Sorting and selection
4.1 Quicksort and quickselect 4.2 Median of medians
Counting the number of inversions
Assume that you have m users ranking the same set of n movies. You want to determine for any two users A and B how similar their tastes are (for example, in order to make a recommender system).
How should we measure the degree of similarity of two users A and B?
Lets enumerate the movies on the ranking list of user B by assigning to the top choice of user B index 1, assign to his second choice index 2 and so on.
For the ith movie on B’s list we can now look at the position (i.e., index) of that movie on A’s list, denoted by a(i).
Counting the number of inversions
a(9) = 3 a(4) = 8 a(7) = 5
Counting the number of inversions
A good measure of how different these two users are, is the total number of inversions, i.e., total number of pairs of movies i,j such that movie i precedes movie j on B’s list but movie j is higher up on A’s list than the movie i.
In other words, we count the number of pairs of movies i,j such that i < j (movie i precedes movie j on B′s list) but a(i) > a(j) (movie i follows movie j on A’s list, in positions a(i) and a(j) respectively).
For example 1 and 2 do not form an inversion because 1 = a(1) < a(2) = 11,
but 4 and 7 do form an inversion because 5 = a(7) < a(4) = 8.
Counting the number of inversions
An easy way to count the total number of inversions between two lists is to test each pair i < j of movies on one list, and add one to the total if they are inverted in the second list. Unfortunately this produces a quadratic time algorithm, T(n) = Θ(n2).
We now show that this can be done in a much more efficient way, in time O(n log n), by applying a divide-and-conquer strategy.
Clearly, since the total number of pairs is quadratic in n, we cannot afford to inspect all possible pairs.
The main idea is to tweak the Merge-Sort algorithm, by extending it to recursively both sort an array A and determine the number of inversions in A.
Counting the number of inversions
We split the array A into two (approximately) equal parts Alo = A[1..m] and Ahi = A[m + 1..n], where m = ⌊n/2⌋.
Note that the total number of inversions in array A is equal to the sum of the number of inversions I(Alo) in Alo (such as 9 and 7) plus the number of inversions I(Ahi) in Ahi (such as 4 and 2) plus the number of inversions I(Alo,Ahi) across the two halves (such as 7 and 4).
Counting the number of inversions
I (A) = I (Alo ) + I (Ahi ) + I (Alo , Ahi ).
The first two terms of the right-hand side are the number of inversions within Alo and within Ahi , which can be calculated recursively.
It seems that the main challenge is to evaluate the last time, which requires us to count the inversions which cross the partition between the two sub-arrays.
Counting the number of inversions
In our example, how many inversions involve the 6?
It’s the number of elements of Alo which are greater than 6,
but how would one compute this systematically?
The idea is to not only count inversions across the partition, but also sort the array. We can then assume that the subarrays Alo and Ahi are sorted in the process of counting I(Alo) and I(Ahi).
Counting the number of inversions
We proceed to count I(Alo,Ahi) (specifically, counting each inversion according to the lesser of its elements) and simultaneously merge as in Merge-Sort.
Each time we reach an element of Ahi , we have inversions with this number and each of the remaining elements in Alo. We therefore add the number of elements remaining in Alo to the answer.
Counting the number of inversions
On the other hand, when we reach an element of Alo, all inversions involving this number have already been counted.
We have therefore counted the number of inversions within each subarray (I(Alo) and I(Ahi)) as well as the number of inversions across the partition ((I(Alo,Ahi)), and adding these gives I(A) as required.
Clearly this algorithm has the same complexity as Merge-Sort, i.e. Θ(n log n).
Next: we look to generalise this method of divide and conquer.
Table of Contents
1. Introductory Examples 1.1 Coin puzzle
1.2 Counting inversions
2. Recurrences
2.1 Framework
2.2 Master Theorem
3. Integer Multiplication
3.1 Applying D&C to multiplication of large integers 3.2 The Karatsuba trick
4. Sorting and selection
4.1 Quicksort and quickselect 4.2 Median of medians
Table of Contents
1. Introductory Examples 1.1 Coin puzzle
1.2 Counting inversions
2. Recurrences
2.1 Framework
2.2 Master Theorem
3. Integer Multiplication
3.1 Applying D&C to multiplication of large integers 3.2 The Karatsuba trick
4. Sorting and selection
4.1 Quicksort and quickselect 4.2 Median of medians
Recurrences
Recurrences are important to us because they arise in estimations of time complexity of divide-and-conquer algorithms.
Recall that counting inversions in an array A of size n required us to:
recurse on each half of the array (Alo and Ahi ), and count inversions across the partition, in linear time.
Therefore the runtime T(n) satisfies
T (n) = 2T n + c n. 2
Recurrences
Let a ≥ 1 be an integer and b > 1 a real number, and suppose that a divide-and-conquer algorithm:
reduces a problem of size n to a many problems of smaller size n/b,
with overhead cost of f (n) to split up the problem and combine the solutions from these smaller problems.
The time complexity of such an algorithm satisfies
T (n) = a T n + f (n). b
Recurrences
Technically, we should be writing
T (n) = a T n + f (n)
but it can be shown that the same asymptotics are achieved if we ignore the rounding and additive constants.
Recurrences of the form T (n) = a T n + f (n) b
size of instance = n
size of instances = n/b
size of instances = n/b2 .
a many instances
….. ….. …
depth of recursion: log! 𝑛
size of instances = 1
Solving Recurrences
Some recurrences can be solved explicitly, but this tends to be tricky.
Fortunately, to estimate the efficiency of an algorithm we do not need the exact solution of a recurrence
We only need to find:
the growth rate of the solution i.e., its asymptotic
behaviour, and
the (approximate) sizes of the constants involved (more about that later)
This is what the Master Theorem provides (when it is applicable).
Table of Contents
1. Introductory Examples 1.1 Coin puzzle
1.2 Counting inversions
2. Recurrences
2.1 Framework
2.2 Master Theorem
3. Integer Multiplication
3.1 Applying D&C to multiplication of large integers 3.2 The Karatsuba trick
4. Sorting and selection
4.1 Quicksort and quickselect 4.2 Median of medians
Master Theorem
a ≥ 1 be an integer and and b > 1 be a real number;
f (n) > 0 be a non-decreasing function defined on the positive integers;
T(n) be the solution of the recurrence
T (n) = a T (n/b) + f (n).
Define the critical exponent c∗ = logb a and the critical polynomial nc∗.
Master Theorem
1. Iff(n)=O(nc∗−ε)forsomeε>0,thenT(n)=Θ(nc∗);
2. Iff(n)=Θ(nc∗),thenT(n)=Θ(nc∗ logn);
3. If f(n) = Ω(nc∗+ε) for some ε > 0,and for some c < 1 and some n0,
af (n/b)≤cf(n) (1) holds for all n > n0,then T (n) = Θ(f (n));
Prove that f (n) = Ω(nc∗+ε) is a consequence of (1).
Master Theorem
Theorem (continued)
4. If none of these conditions hold, the Master Theorem is NOT applicable.
Often, the proof of the Master Theorem can be tweaked to (asymptotically) solve such recurrences anyway! An example is T (n) = 2T (n/2) + n log n.
Master Theorem
Recall that for a,b > 1, loga n = Θ(logb n), so we can omit the base and simply write statements of the form f(n) = Θ(g (n) log n).
However, nloga x is not interchangeable with nlogb x – the base must be specified in such expressions.
Master Theorem
Let T (n) = 4 T (n/2) + n.
Then the critical exponent is c∗ = logb a = log2 4 = 2, so the
critical polynomial is n2.
Now, f (n) = n = O(n2−ε) for small ε (e.g. 0.1).
This satisfies the condition for case 1, so T(n) = Θ(n2).
Master Theorem
Let T (n) = 2T (n/2) + 5 n.
Then the critical exponent is c∗ = logb a = log2 2 = 1, so the
critical polynomial is n.
Now, f (n) = 5 n = Θ(n).
This satisfies the condition for case 2, so T (n) = Θ(n log n).
Master Theorem
Let T (n) = 3 T (n/4) + n.
Then the critical exponent is c∗ = log4 3 ≈ 0.7925, so the critical
polynomial is nlog4 3.
Now, f (n) = n = Ω(nlog4 3+ε) for small ε (e.g. 0.1). Also,af(n/b)=3f(n/4)=3/4n
Therefore the Master Theorem does not apply!
Master Theorem
Prove (2), that is, for all ε > 0, c > 0 and N > 0 there is some n > N such that
log2 n < c · nε.
Use L’Hˆopital’s rule to show that
log n → 0. nε
Master Theorem
Suppose T(n) satisfies the recurrence
T(n) = aT n + f (n) (3)
However, the T(n/b) term can itself be reduced using the recurrence as follows:
T n = aT n +f n b b2 b
Substituting into (3) and simplifying gives
T (n) = aaT n + f n + f (n)
= a2T n +af n+f(n). b2 b
Master Theorem
We have now established
T(n) = a2T n +af n+f(n). (4)
But why stop there? We can now reduce the T n/b2 term, again
using (3):
Tn=aTn+fn. b2 b3 b2
We now substitute this into (4) and simplify to get
T(n) = a2aT n +f n +af n+f(n)
= a3T n +a2 f n +af n+f(n).
b3 b2 b We can see a pattern emerging!
Master Theorem
Continuing in this way, we find that T(n)=akTn+ak−1f n +...+afn+f(n)
n k−1 n =akT bk +aif bi .
We stop when k = ⌊logb n⌋, since this gives n/bk ≈ 1.
⌊log n⌋−1 nbn
T(n)≈alogbnT + aif . blogb n bi
Master Theorem
Now we have
T(n)≈alogbnT + aif
We can use the identity alogb n = nlogb a to get:
⌊log n⌋−1 nbn
T(n)≈nlogbaT(1)+ aif i=0
Importantly, we have not assumed anything about f (n) yet! We will now analyse the sum S in the simplest case of the Master Theorem, namely Case 2.
Master Theorem: Case 2
Suppose f (n) = Θ nlogb a. Then ⌊log n⌋−1
b n S= aif bi
⌊logbn⌋−1 n b
i loga = aΘbi
⌊log n⌋−1
b nb i loga
using the sum property and scalar multiple property.
Master Theorem: Case 2
⌊log n⌋−1 b nb
S=Θai loga bi
=Θnloga ai b
⌊logbn⌋−1 1log a
as nlogb a is common to every term of the sum,
⌊log n⌋−1
blogb a i=0
Master Theorem: Case 2
⌊log n⌋−1 b a
b S=Θnloga i
blogb a i=0
⌊log n⌋−1 b a
=Θnloga i b
⌊logbn⌋−1 = Θ nlogb a 1
= Θ nlogb a ⌊logb n⌋ .
i=0 as blogb a = a,
Master Theorem: Case 2
Finally, we return to (5). Substituting our result for S gives T (n) ≈ nlogb a T (1) + Θ nlogb a ⌊logb n⌋
=Θnlogba logn
as logarithms of any base are equivalent,
completing the proof.
Master Theorem: Other cases
The proof of Case 1 is very similar to the above. The main difference is that 1 is replaced by (bε)i , forming a geometric series, which can be summed using the identity
1+r +r2 +...+rk−1 = rk −1. r−1
In Case 3, we need to prove that T (n) = Θ(f (n)), that is, both:
T (n) = Ω(f (n)), which follows directly from the recurrence T (n) = a T (n/b) + f (n), and
T(n) = O(f (n)) (not as obvious).
Master Theorem: Case 3
Prove that in Case 3, T(n) = O(f (n)).
You will need to bound
S= aif bi
i=0 from above. Try using the inequality
af n≤cf(n) b
to relate each term of S to f (n).
Table of Contents
1. Introductory Examples 1.1 Coin puzzle
1.2 Counting inversions
2. Recurrences
2.1 Framework
2.2 Master Theorem
3. Integer Multiplication
3.1 Applying D&C to multiplication of large integers 3.2 The Karatsuba trick
4. Sorting and selection
4.1 Quicksort and quickselect 4.2 Median of medians
Basics revisited: how do we add two integers?
CCCCC carry
X X X X X first integer
+ X X X X X second integer
-----------
XXXXXX result
Adding 3 bits can be done in constant time.
It follows that the whole algorithm runs in linear time i.e., O(n) many steps.
Basics revisited: how do we add two integers?
Can we add two n-bit numbers in faster than in linear time?
No! There is no asymptotically faster algorithm because we have to read every bit of the input, which takes O(n) time.
Basics revisited: how do we multiply two integers?
X X X X <- first input integer
* X X X X <- second input integer
XXXX X XXX
XX XX XXX X
--------------- XXXXXXXX
\ O(n^2) intermediate operations:
/ O(n^2) elementary multiplications
/ + O(n^2) elementary additions <- resultoflength2n
We assume that two X’s can be multiplied in O(1) time (each X could be a bit or a digit in some other base).
Thus the above procedure runs in time O(n2).
Basics revisited: how do we multiply two integers?
Can we multiply two n-bit numbers in linear time, like addition?
No one knows! “Simple” problems can actually turn out to be difficult!
Can we do it in faster than quadratic time? Let’s try divide and conquer.
Table of Contents
1. Introductory Examples 1.1 Coin puzzle
1.2 Counting inversions
2. Recurrences
2.1 Framework
2.2 Master Theorem
3. Integer Multiplication
3.1 Applying D&C to multiplication of large integers 3.2 The Karatsuba trick
4. Sorting and selection
4.1 Quicksort and quickselect 4.2 Median of medians
Multiplying large integers by divide-and-conquer
Split the two input numbers A and B into halves: A0, B0 - the least significant n/2 bits;
A1, B1 - the most significant n/2 bits.
A=A122 +A0 XX...XXX...X
B = B 2 n2 + B n n 1022
AB can now be calculated recursively using the following equation:
AB = A1B12n + (A1B0 + B1A0)2n2 + A0B0.
Multiplying large integers by divide-and-conquer
1: function Mult(A,B)
2: if |A|=|B|=1thenreturnAB
4: A1 ← MoreSignificantPart(A);
5: A0 ← LessSignificantPart(A);
6: B1 ← MoreSignificantPart(B );
7: B0 ← LessSignificantPart(B );
8: X←Mult(A0,B0);
9: Y←Mult(A0,B1);
10: Z←Mult(A1,B0);
11: W←Mult(A1,B1);
12: return W 2n +(Y +Z)2n/2 +X
13: end if
14: end function
Multiplying large integers by divide-and-conquer
How many steps does this algorithm take?
Each multiplication of two n digit numbers is replaced by four multiplications of n/2 digit numbers: A1B1, A1B0, B1A0, A0B0, plus we have a linear overhead to shift and add:
T (n) = 4T n + c n. 2
Let’s use the Master Theorem!
Multiplying large integers by divide-and-conquer
T (n) = 4T n + c n 2
The critical exponent is c∗ = log2 4 = 2, so the critical polynomial is n2.
Then f (n) = c n = O(n2−0.1), so Case 1 applies.
We conclude that T(n) = Θ(nc∗) = Θ(n2), i.e., we gained nothing with our divide-and-conquer!
Multiplying large integers by divide-and-conquer
Is there a smarter multiplication algorithm taking less than O(n2) many steps?
Remarkably, there is!
Table of Contents
1. Introductory Examples 1.1 Coin puzzle
1.2 Counting inversions
2. Recurrences
2.1 Framework
2.2 Master Theorem
3. Integer Multiplication
3.1 Applying D&C to multiplication of large integers 3.2 The Karatsuba trick
4. Sorting and selection
4.1 Quicksort and quickselect 4.2 Median of medians
In 1952, one of the most famous mathematicians of the 20th century, , conjectured that you cannot multiply in less than quadratic many elementary operations.
In 1960, , then a 23-year-old student, found an algorithm (later it was called “divide-and-conquer”) that multiplies two n-digit numbers in Θ nlog2 3 ≈ Θ(n1.58...) elementary steps, thus disproving the conjecture!!
Kolmogorov was shocked!
The Karatsuba trick
Once again we split each of our two input numbers A and B into halves:
A=A122 +A0 XX...XXX...X
B = B 2 n2 + B n n . 1022
Previously we saw that
AB = A1B12n + (A1B0 + A0B1)2n2 + A0B0,
but rearranging the bracketed expression gives
AB = A1B12n+((A1+A0)(B1+B0)−A1B1−A0B0)2n2 +A0B0, saving one multiplication at each round of the recursion!
The Karatsuba trick
1: function Mult(A,B)
2: if |A|=|B|=1thenreturnAB
4: A1 ← MoreSignificantPart(A);
5: A0 ← LessSignificantPart(A);
6: B1 ← MoreSignificantPart(B );
7: B0 ← LessSignificantPart(B );
8: U←A1+A0;
9: V←B1+B0;
10: X←Mult(A0,B0);
11: W←Mult(A1,B1);
12: Y←Mult(U,V);
13: return W 2n +(Y −X −W)2n/2 +X
14: end if
15: end function
The Karatsuba trick
How fast is this algorithm?
Addition takes linear time, so we are only concerned with the number of multiplications.
We need A1B1, A0B0 and (A1 + A0)(B1 + B0); thus
T (n) = 3 T n + c n. 2
The Karatsuba trick
Clearly, the run time T(n) satisfies the recurrence
T (n) = 3 T n + c n (6)
Now the critical exponent is c∗ = log2 3. Once again, we are in Case 1 of the Master Theorem, but this time
T(n) = Θnlog2 3 = Θ n1.58...
= o(n2), disproving Kolmogorov’s conjecture.
The Karatsuba trick
We can do even better, by splitting the input numbers A and B into more than two pieces.
In fact, f
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com