Transcript Chapter 6 - K.f.u.p.m ocw

Divide and Conquer
• Reading Material: Chapter 6 (except
Section 6.9).
Divide and Conquer
• The divide and conquer paradigm consists of the
following steps
– Divide step: Input is partitioned into p  1 partitions, each of
size strictly less than n.
• Most common value of p = 2.
• p could be equal to one when part of the input is discarded (example?)
– Conquer step: Perform p recursive calls if the problem size is
greater than a specific threshold n0.
• n0 is usually 1, but could be greater than 1.
– Combine step: The solution to the p recursive calls are
combined to solve the problem for the union of the p partitions
of the input.
• In many, but not all cases, this step determines the time complexity of
the algorithm.
Recursive Merge Sort
• MergeSort(A,p,r)
if p < r then
q := (p+r)/2;
MergeSort(A,p,q);
MergeSort(A,q+1,r);
Merge(A,p,q,r);
end if;
• Assume that n is a power of two
–
–
–
–
–
What is the cost of MergeSort(A,j,j)?
What is the cost of MergeSort(A,1,n/2)?
What is the cost of MergeSort(A,n/2+1,n)?
What is the cost of Merge(A,1,n/2,n)?
What is the recurrence equation(s) describing the time
complexity? What is the solution?
Recursive Binary Search Algorithm
• BinarySearchRec(A,low,high)
if (low > high) then
return 0;
else
mid ← (low + high)/2;
if x = A[mid] then return mid
else if x < A[mid] then
return BinarySearchRec(A,low,mid-1);
else return BinarySearchRec(A,mid+1,high);
end if;
end if;
• Identify the divide, conquer and combine operations.
• If n = 2k – 1 , what is the recurrence equation and its
solution?
• Otherwise, what is the recurrence equation and its
solution?
Recursive MinMax algorithm
• Procedure MinMax(A,low,high)
if high – low = 1 then
if A[low] < A[high] then return (A[low],A[high])
else return (A[high],A[low])
end if
else
mid ← (low + high)/2;
(x1,y1) ← MinMax(A,low,mid);
(x2,y2) ← MinMax(A,mid+1,high);
x ← min{x1,x2};
y ← max{y1,y2};
return (x,y);
end if;
Analysis of Recursive MinMax
• Identify the divide, conquer, and combine
steps in the algorithm.
• Assuming n is a power of two, what is the
recurrence equation describing the time
complexity? What is the solution?
• What is the cost of the “straightforward”
algorithm?
Selection Problem
• Problem Statement: Find the kth smallest
element in the array
– A special case is to find the median of the array
• In case n is odd, the median is the (n+1)/2 th smallest
element
• In case n is even, the median is the n/2 th smallest
element
• What is the straightforward algorithm?
What is its time complexity?
A Better Algorithm
• If we can discard a constant fraction of the
elements after the divide step of every
recursive call, and recur on the rest of the
elements, the size of the problem decreases
geometrically
– E.g. if we assume that 1/3 of the elements are
discarded and that the algorithm spends a
constant time per element, we get
cn + (2/3)cn + (2/3)2 cn +…+ (2/3)j cn +…
Basic Idea of the Algorithm
• If the number of elements is less than a threshold, sort
and find the kth element
• Otherwise, partition the input into n/5 groups of five
elements each
– You may have a group of less than 5 elements if n does not
divide 5.
– Sort each group and extract its median.
– The median of medians is computed recursively.
• Partition the elements in A around the median into
three sets: A1, A2, and A3
• Where to look for the kth smallest element?
Example
• Find the 14th smallest element in the array
8 , 33 , 17 , 51 , 57 , 49 , 35 , 11 , 25 , 37 ,
14 , 3 , 2 , 13 , 52 , 12 , 6 , 29 , 32 , 54 , 5 ,
16 , 22 , 23 , 7 , 8 , 19 , 44 , 66
Algorithm Select
Input: Array A[1..n] and an integer k, 1≤ k ≤ n
Output: kth smallest element in A
Procedure select (A, low, high, k)
1. p := high – low + 1;
2. if p < 44 then sort A and return(A[k])
3. Let q =  p/5 . Divide A into q groups of 5 elements
each, discarding the possibly one additional group
with less than 5 elements
4. Sort the q groups individually extracting the median.
Let the set of medians be M
5. mm := select(M,1,q,q/2)
6. Partition A[low..high] into three array, A1={a|a<mm},
A2={a|a=mm}, and A3={a|a>mm}
7. case
1.
2.
3.
|A1|  k
: return select(A1,1,|A1|,k);
|A1| + |A2|  k : return mm;
|A1| + |A2| < k : return select(A3,1,|A3|,k–(|A1|+|A2|));
Analysis of the Selection Algorithm (1)
W
W
Z
Z
• Estimating the sizes of A1 and A3.
– A1’ = { x  A | x  mm}
– The size of W will give us the minimum number of
elements in A1’
– Hence, knowing the minimum size of A1’ will give us
an upper bound on the size of … which is equal to
…………….
Analysis of the Selection Algorithm (2)
• Now, we can write the recurrence relation
for the selection algorithm as follows:
• What do we use to solve this recurrence?
Quick Sort
• Procedure QuickSort(A,low,high)
if low < high then
w := split(A,low,high);
QuickSort(A,low,w-1);
QuickSort(A,w+1,high);
end if;
Split Algorithm
• Split(A,low,high)
i := low;
x := A[low];
for j := low + 1 to high do
if A[j]  x then
i := i + 1;
if i  j then
swap(A[i],A[j]);
end if;
end if;
end for;
swap (A[low],A[i]);
return i;
Quick Sort Complexity Analysis
• How many element comparisons are carried
out by the split procedure?
• Worst case analysis of Quick Sort:
• Best case analysis of Quick Sort:
Average Case Analysis of Quick Sort
• Assumption: All permutations of the input
are equally likely
– The input consists of n distinct elements
– This implies that the probability that any
element will be picked as a pivot is
• Let C(n) denote the number of comparisons
done by QuickSort on the average on input
of size n:
Comparative Results of Various
Sorting Algorithms
Multiplication of Large Integers
•
Let u and v be two n-bit integers, where n is a
power of 2
–
The traditional multiplication algorithm takes
–
Divide and conquer can be used to carry out the
multiplication as follows:
w
x u
• Divide each integer into 2 n/2-bit
portions as shown here
y
z v
•
•
u = w2n/2 + x and v = y2n/2 + z
The product now becomes
– Note that multiplying a number t by 2k is equivalent to shifting t
k bits to the left, which is (k) time.
•
How many additions and multiplications we have? What
is the recurrence equation?
Can We Do Better?
• Note that if we can reduce the number of
multiplications by 1, we will have
asymptotic improvement
• Consider evaluating wz + xy as follows:
wz + xy = (w + x) (y + z) – wy – xz
– Note that wy and xz have already been
computed. So no need to compute again
– What is the total number of multiplications
now? Rewrite the recurrence equation and
solve.
Matrix Multiplication
• Let A and B be 2 n  n matrices, assuming n
to be a power of 2. We would like to employ
divide and conquer to carry out the
multiplication of A and B.
– What is the traditional algorithm? How much
does it cost?
Recursive Version
A11

• Let A  
A
 21
A12 
B11

 and B  
A22 
 B21
B12 
 then:
B22 
 A11B11  A12 B21 A11B12  A12 B22 

A  B  
 A21B11  A22 B21 A21B12  A22 B22 
• What is the recurrence describing the cost of
carrying out the multiplication by computing
the number of multiplication operations? What
is the solution to the recurrence? Did we
achieve anything?
Strassen’s algorithm
• The idea is again exactly similar to that in
multiplying large numbers: we would like to
rewrite the product in a manner that will
reduce the number of multiplications
needed (even by one!)
Strassen’s Algorithm
D1   A11  A22 B11  B22 
D2   A21  A22 B11 
D3   A11 B12  B22 
D4   A22 B21  B11 
D5   A11  A12 B22 
D6   A21  A11 B11  B12 
D7   A12  A22 B21  B22 
 D1  D4  D5  D7
A  B  
D2  D4

D3  D5


D1  D3  D2  D6 
Analysis of Strassen’s Algorithm
• How many multiplications and
additions/subtractions are carried out?
• What is the recurrence equation describing
the cost? What is the recurrence solution?
• Is there any improvement?
Empirical Comparison
n
Multiplications
Additions
Traditional Alg.
100
1,000,000
990,000
Strassen’s Alg.
100
411,822
2,470,334
Traditional Alg.
1,000
1,000,000,000
999,000,000
Strassen’s Alg.
1,000
264,280,285
1,579,681,709
Traditional Alg.
10,000
1012
9.99  1011
Strassen’s Alg.
10,000
0.169  1012
1012