DIVIDE AND CONQUER
lecture5
Divide-and-Conquer
The most-well known algorithm design strategy:
1. Divide instance of problem into two or more
smaller instances
2. Solve smaller instances recursively
3. Obtain solution to original (larger) instance by
combining these solutions
Divide-and-Conquer Technique (cont.)
a problem of size n
(instance)
subproblem 1 subproblem 2
of size n/2 of size n/2
a solution to a solution to
subproblem 1 subproblem 2
a solution to It general leads to a
the original problem recursive algorithm!
General Divide-and-Conquer Recurrence
T(n) = aT(n/b) + f (n) where f(n) (nd), d 0
Master Theorem: If a < bd, T(n) (nd)
If a = bd, T(n) (nd log n)
If a > bd, T(n) (nlog b a )
Note: The same results hold with O instead of .
Examples: T(n) = 4T(n/2) + n T(n) ? (n^2)
T(n) = 4T(n/2) + n2 T(n) ? (n^2log n)
T(n) = 4T(n/2) + n3 T(n) ? (n^3)
Divide-and-Conquer Examples
Sorting: mergesort and quicksort
Matrix multiplication: Strassen’s algorithm
Mergesort
Split array A[0..n-1] into about equal halves and
make copies of each half in arrays B and C
Sort arrays B and C recursively
Merge sorted arrays B and C into array A as follows:
Repeat the following until no elements remain in one of the
arrays:
compare the first elements in the remaining unprocessed
portions of the arrays
copy the smaller of the two into A, while incrementing the
index indicating the unprocessed portion of that array
Once all elements in one of the arrays are processed, copy
the remaining unprocessed elements from the other array
into A.
Mergesort Example
8 3 2 9 7 1 5 4
8 3 2 9 7 1 5 4
8 3 2 9 71 5 4
8 3 2 9 7 1 5 4
3 8 2 9 1 7 4 5
2 3 8 9 1 4 5 7
1 2 3 4 5 7 8 9
Analysis of Mergesort
The recurrence relation to number of key
comparison is:
T(n) = 2T(n/2) + Cmerge(n) for n>1 , C(1)=0
The worst case is:
T(n) = 2 T(n/2) + (n-1)
Apply the master theorem the result is : Θ(n log n)
Quicksort
Select a pivot (partitioning element) – here, the first element
Rearrange the list so that all the elements in the first s
positions are smaller than or equal to the pivot and all the
elements in the remaining n-s positions are larger than or
equal to the pivot (see next slide for an algorithm)
p
A[i]p A[i]p
Exchange the pivot with the last element in the first (i.e., )
subarray — the pivot is now in its final position
Sort the two subarrays recursively
Quicksort Example
Analysis of Quicksort
Best case: split in the middle — Θ(n log n)
T(n) = 2T(n/2) + n
Worst case: sorted array! — Θ(n2)
T(n) = T(n-1) + Θ(n)
Average case: random arrays — Θ(n log n)
Conventional Matrix Multiplication
Brute-force algorithm
c00 c01 a00 a01 b00 b01
= *
c10 c11 a10 a11 b10 b11
a00 * b00 + a01 * b10 a00 * b01 + a01 * b11
=
a10 * b00 + a11 * b10 a10 * b01 + a11 * b11
8 multiplications Efficiency class in general: (n3)
4 additions
Calculate matrix multiplication
Algorithm_Matrix_Mul (A[0…n-1, 0… n-1], b[0…n-1,0…n-1])
for i=0 to n-1 do
for j=0 to n-1 do
c[i,j] = 0
for k=0 to n-1 do
c[i,j]:=c[i,j] + A[i,k]*b[k,j]
return c
Mathematical analysis
Step1: the input size is the order of matrix.
Step2: basic operation is in inner most loop so:
c[i,j]:=c[i,j] + A[i,k]*b[k,j]
Step3: Σ n-1k=0 1
Step 4:
M(n) = outermost loop * inner loop * innermost loop
= Σ n-1i=0 Σ n-1j=0 Σ n-1k=0 1
=n3
This means time complexity is ϴ(n3)
Strassen’s Matrix Multiplication
Strassen’s algorithm for two 2x2 matrices (1969):
c00 c01 a00 a01 b00 b01
= *
c10 c11 a10 a11 b10 b11
m1 + m4 - m5 + m7 m3 + m5
=
m2 + m4 m1 + m3 - m2 + m6
m1 = (a00 + a11) * (b00 + b11)
m2 = (a10 + a11) * b00
m3 = a00 * (b01 - b11)
7 multiplications
m4 = a11 * (b10 - b00)
m5 = (a00 + a01) * b11 18 additions
m6 = (a10 - a00) * (b00 + b01)
m7 = (a01 - a11) * (b10 + b11)
Strassen’s Matrix Multiplication
Strassen observed [1969] that the product of two
matrices can be computed in general as follows:
C00 C01 A00 A01 B00 B01
= *
C10 C11 A10 A11 B10 B11
M1 + M4 - M5 + M7 M3 + M5
=
M2 + M4 M1 + M3 - M2 + M6
Formulas for Strassen’s Algorithm
M1 = (A00 + A11) (B00 + B11)
M2 = (A10 + A11) B00
M3 = A00 (B01 - B11)
M4 = A11 (B10 - B00)
M5 = (A00 + A01) B11
M6 = (A10 - A00) (B00 + B01)
M7 = (A01 - A11) (B10 + B11)
Analysis of Strassen’s Algorithm
If n is not a power of 2, matrices can be padded with
zeros.
Number of multiplications:
M(n) = 7M(n/2), M(1) = 1
Solution: M(n) = nlog 27 ≈ n2.807 vs. n3 of brute-force alg.
Algorithms with better asymptotic efficiency are known
but they are even more complex and not used in
practice.
Why don’t CS profs ever stop talking about sorting?!
1. Computers spend more time sorting than anything else,
historically 25% on mainframes.
2. Sorting is the best studied problem in computer
science, with a variety of different algorithms known.
3. Most of the interesting ideas we will encounter in the
course can be taught in the context of sorting, such as
divide-and-conquer, randomized algorithms, and lower
bounds.
You should have seen most of the algorithms - we will
concentrate on the analysis.
Applications of Sorting
One reason why sorting is so important is that once a
set of items is sorted, many other problems become
easy.
For example searching: Binary search lets you test
whether an item is in a dictionary in O(log n) time.
Speeding up searching is perhaps the most important
application of sorting.
Continue
Closest pair: Given n numbers, find the pair which are
closest to each other.
Once the numbers are sorted, the closest pair will be next to
each other in sorted order, so an O(n) linear scan completes
the job.
Element uniqueness: Given a set of n items, are they all
unique or are there any duplicates?
Sort them and do a linear scan to check all adjacent pairs.
This is a special case of closest pair above.
Continue
Frequency distribution – Mode: Given a set of n
items, which element occurs the largest number of
times?
Sort them and do a linear scan to measure the
length of all adjacent runs.
Median and Selection: What is the kth largest item
in the set?
Once the keys are placed in sorted order in an
array, the kth largest can be found in constant time
by simply looking in the kth position of the array.
Assignment
Apply quicksort to the following list (step by step
like lecture)
1 2 3 4 5 6
