11/24/23, 10:32 AM Divide and Conquer Algorithms
Divide and Conquer Algorithms
Student Outcomes
Define divide and conquer approach to algorithm design
Describe and answer questions about example divide and conquer algorithms
Binary Search
Quick Sort
Merge Sort
Integer Multiplication
Matrix Multiplication (Strassen's algorithm)
Maximal Subsequence
Apply the divide and conquer approach to algorithm design
Analyze performance of a divide and conquer algorithm
Compare a divide and conquer algorithm to another algorithm
Essence of Divide and Conquer
1. Divide problem into several smaller subproblems
Normally, the subproblems are similar to the original
2. Conquer the subproblems by solving them recursively
Base case: solve small enough problems by brute force
3. Combine the solutions to get a solution to the subproblems
And finally a solution to the orginal problem
4. Divide and Conquer algorithms are normally recursive
Binary Search
Recursive Binary Search
A Divide and Conquer Algorithm to find a key in an array:
-- Precondition: S is a sorted list
index binsearch(number n, index low, index high,
const keytype S[], keytype x)
if low ≤ high then
mid = (low + high) / 2
if x = S[mid] then
https://sites.radford.edu/~nokie/classes/360/divcon.html 1/9
11/24/23, 10:32 AM Divide and Conquer Algorithms
return mid
elsif x < s[mid] then
return binsearch(n, low, mid-1, S, x)
else
return binsearch(n, mid+1, high, S, x)
else
return 0
end binsearch
Divide: search lower or upper half
Divide: select lower or upper half
Conquer: search selected half
Combine: None
Performance:
T (n) = T (n/2) + Θ(1)
T (n) = Θ(lg n) (proved earlier)
Merge Sort
Recursive Merge Sort
A Divide and Conquer Algorithm to sort an array:
void mergesort(S: array of keytype)
len = S'length
if len > 1 then
-- Divide: Copy the arrays
mid: constant int := len / 2
rest: int len - mid
U: array(1..mid) of keytype := S(1..mid)
V: array(1..rest) of keytype := S(mid+1..n)
-- Conquire: Recursively sort
mergesort(U)
mergesort(V)
-- Combine: merge sorted arrays
merge(U, V, S)
end mergesort
void merge(L, R, S: array(<>) of keytype)
i, j, k: int := 1
lenL: constant int := L'length
lenR: constant int := R'length
while i <= lenL and j <= lenR
if L(i) < R(j) then
S(k) := L(i); i := i + 1;
else -- R(i) ≤ L(j) then
S(k) := R(j); j := j + 1;
k := k + 1
if i > lenL then S(k..lenL+lenR) := R(j..lenR)
else S(k..lenL+lenR) := L(i..lenL)
Time Performance:
T (n) = 2T (n/2) + Θ(n)
T (n) = Θ(n lg n) (by induction or master method)
https://sites.radford.edu/~nokie/classes/360/divcon.html 2/9
11/24/23, 10:32 AM Divide and Conquer Algorithms
Space Performance:
Requires θ(k/2) new space for each recursive call
Number of recursive calls until size 1: lg n
lg n
1
Space used for call with size n array: n ∑ i
= n(1 + 1/2 + 1/4 + …) = nΘ(2) = Θ(2n)
i=0
2
This extra space can be reused for next recursive call (think about the diagram)
Total space: Θ(3n)
Can we do better?
Recursive Merge Sort - Version 2
Uses global variable S
void mergesort2(low, high: int)
if low < high then
mid: constant int := (low + high) / 2
mergesort(low, mid)
mergesort(mid+1, high)
merge2(low, mid, high)
end mergesort2
-- Merges from S(LOW..MID) and S(MID+1..HIGH) to U(LOW..HIGH)
-- Then copies U(LOW..HIGH) back to S(LOW..HIGH)
void merge2(LOW, MID, HIGH: int)
U: array(LOW..HIGH) of keytype
i: int := LOW
j: int := MID
k: int := HIGH
while i <= MID and j <= HIGH
if S(i) < S(j) then
U(k) := S(i); i := i + 1;
else -- S(j) < S(i) then
U(k) := S(j); j := j + 1;
k := k + 1
if i > MID then U(k..HIGH) := S(j..HIGH)
else U(k..HIGH) := S(i..MID)
S(LOW..HIGH) := U(LOW..HIGH)
Time Performance:
T (n) = 2T (n/2) + Θ(n)
T (n) = Θ(n lg n) (by induction or master method)
Space Performance:
Never uses more than θ(n) extra space for call to merge
Extra space is reused for next call
Total space: Θ(2n)
But, how much space is required for the recursion?
Answer: ???
Another improvement: make S size 2n, and merge from one side to the other
Quick Sort
https://sites.radford.edu/~nokie/classes/360/divcon.html 3/9
11/24/23, 10:32 AM Divide and Conquer Algorithms
Quick Sort - Algorithm
Quicksort is another example of divide and conquer
Recursive Algorithm:
-- Assume global array S
void quicksort(low, high: int)
if low < high then
mid: constant int := (low + high) / 2
partition(low, high, pivot)
quicksort(low, pivot-1)
quicksort(pivot+1, high)
end quicksort
void partition(LOW, HIGH: int; PIVOTPOINT: out int)
j: int := LOW
pivot_item: keytype := S(j)
for i in LOW+1 .. HIGH loop
if S(i) < pivot_item then
j := j + 1
swap(S(i), S(j))
end if
end loop
PIVOTPOINT := j
swap(S(LOW), S(PIVOTPOINT))
end partition
Quick Sort - Worst Case Time Performance
Time Performance - Worst Case:
T (n) = T (n − 1) + T (0) + Θ(n)
T (n) = Θ(n )
2
(by induction)
Assume T (k) = k
2
+ Θ(k) for k < n
T (n) = T (n − 1) + Θ(n)
2
= (n − 1) + Θ(n)
2
= n − 2n + 1 + Θ(n)
2
= n + Θ(n) + Θ(n)
2
= n + Θ(n)
2
= Θ(n )
Actually: how do we know that this is worst case?
It could be proved, but we won't do it
Quick Sort - Expected Case Time Performance
Time Performance - Expected Case:
Assume all problem instances are equally likely
This means that any element is equally likely to be the pivot (ie returned by partition
Thus the expected value of T (n) is
https://sites.radford.edu/~nokie/classes/360/divcon.html 4/9
11/24/23, 10:32 AM Divide and Conquer Algorithms
n
1
T (n) = ∑[T (p − 1) + T (n − p)] + n − 1
n
p=1
n
1
= ∑ [T (p − 1) + T (n − p)] + n − 1
n
p=1
= Θ(n lg n)
See text for solution
Quick Sort - Best Case Time Performance
Time Performance - Best Case:
T (n) = 2T (n/2) + Θ(n)
T (n) = Θ(n lg n) (by induction or master method)
Why is this the best case: think about a recursion tree
Quick Sort - Constant Performance Time Performance
Time Performance: Constant proportion
What if pivot always divides by a constant proportion: say 10:90
T (n) = T (9n/10) + T (n/10) + Θ(n) = O(n lg n)
Think about the tree:
The shallow side of the tree terminates in log n levels 10
Each of these levels has weight cn
The deep side of the tree terminates in log n levels
10/9
Each of these levels has weight ≤ cn
The entire tree has weight O(cn log )n + cn log
10
n 10/9
= O(n lg n)
Quick Sort - Space Performance
Space Performance:
No extra space needed
Total space: Θ(n)
But, ... what about the space for ...?
Iterative Quick Sort
Can we write quicksort iteratively?
Push and pop the bounds of the half not currently sorted
Requires an explicit stack (or array to simulate a stack)
Explicit stack replaces recursion
Should you stack smaller or larger?
https://sites.radford.edu/~nokie/classes/360/divcon.html 5/9
11/24/23, 10:32 AM Divide and Conquer Algorithms
Quick Sort - Improving Time Performance
Partition from both ends
How can we avoid the worst case?
Better choice of pivot
Randomized: choose a random element as the pivot
Swap random element with first and use same algorithm
Each element has equally likely chance of being pivot
Particular characteristics of the data won't cause worst case
Median of 3: choose 3 elements at random and take their median
Or median of some other k
Use insertion sort when list gets small
Don't sort small lists and use insertion sort on entire list
One-Way, Stackless Quicksort!
Repeat pivoting until positions 1 .. L are filled with pivots
Store pivots as negative
Works for positive only
Matrix Multiplication
Divide and Conquer Example 2 - Matrix Multiplication
Input: A, B: Array(1 .. n ) of number
Output: C: Array(1 .. n ) := A x B
Remember how to multiply matrices?
Obvious algorithm: C has n entries, each of which multiples n pairs
2
cij = ∑ a ik bkj
k=1
Nested loop algorithm
Performance:
Simple Divide and Conquer Method
Break A into A11, A12, A21, A22
Break B into B11, B12, B21, B22
Break C into C11, C12, C21, C22
https://sites.radford.edu/~nokie/classes/360/divcon.html 6/9
11/24/23, 10:32 AM Divide and Conquer Algorithms
Let C = product of 2 n/2 by n/2 arrays
C 11 = A11 × B 11 + A12 × B 21
C 12 = A11 × B 12 + A12 × B 22
C 21 = A21 × B 11 + A22 × B 21
C 22 = A21 × B 12 + A22 × B 22
2
T (n) = Θ(1) + 8T (n/2) + Θ(n )
Θ(1) time to partition matrices
8 Multiplications of arrays of size n/2
Θ(n ) time to add n × n matrices
2
T (n) = Θ(n )
3
by master method
Strassen's Algorithm
Uses 7 rather than 8 multiplications of n/2 by n/2 arrays
Has more additions and subtractions of n/2 by n/2 arrays
Algorithm:
Create 10 n/2 by n/2 sum arrays: S1 .. S10
Recursively compute 7 product arrays: m .. m 1 7
Compute c , c , c , c by adding and subtracting combinations of m
11 12 21 22 i
Θ(1), ifn = 1
T (n) = {
2
7T (n/2) + Θ(n ), ifn > 1
Solution (by Master Method): T (n) = Θ(n
lg 7
) = Θ(n
2.81
)
Notice: Has higher constants
Faster solutions are known: T (n) = O(n
2.38
)
Large Integer Multiplication
Large Integer Multiplication
Assume integers with n digits
Implement with array with one digit per element [Ada bignumpkg]
Grade school algorithm: Θ(n 2
)
Naive divide and conquer:
4 2 0
1234 × 5678 = (12 × 56) × 10 + [(12 × 78) + (34 × 56)] × 10 + (34 × 78) × 10
Performance: T (n) = 4T (n/2) + Θ(n) = Θ(n ) 2
More generally: xy × wz = xw × 10 + (xz + yw) × 10 2k k
+ yz
Assume xy has 2k digits
This requires 4 multiplications
https://sites.radford.edu/~nokie/classes/360/divcon.html 7/9
11/24/23, 10:32 AM Divide and Conquer Algorithms
Improved divide and conquer - calculate three products to find result:
r = (x + y) × (w + z) = xw + (xz + yw) + yz
p = xw
q = yz
2k k
xy × wz = p × 10 + (r − p − q) × 10 + q
Performance: T (n) = 3T (n/2) + Θ(n) = Θ(n
lg 3
) by master method
Maximal Subarray
Example Divide and Conquer: Maximal-subarray Problem
Problem:
Input: A: Array(1 .. n) of numbers
Output: Indices i and j such that sum(A(i .. j)) has the maximum value
Assume some are negative
Otherwise problem is trivial
Example: A := (1, -100, 10, 20, -1, -5, 16, -23, 5)
Solution: i = ??, j = ??
Maximal Subarray: Example Scenario
Stock prices over n days (in the past)
Maximize profits
Will maximum solution sell/buy at global max/min? Not necessarily
Maximal Subarray: Brute Force Solution
How to solve by brute force?
Performance?
Maximal Subarray: Divide and Conquer Solution
Try splitting in half and solve each half
How to use partial solution in entire solution
What complications occur?
How to solve complications
https://sites.radford.edu/~nokie/classes/360/divcon.html 8/9
11/24/23, 10:32 AM Divide and Conquer Algorithms
Maximal Subarray Algorithm
Divide and Conquer Algorithm
maxsub(int[] S; low, high: int) return (lowIndex, highIndex, sum)
if low = high then
return (low, high, S(low))
else
mid = (low + high) / 2
(llow, lhigh, lsum) = maxsub(S, low, mid)
(rlow, rhigh, rsum) = maxsub(S, mid+1, high)
(mlow, mhigh, msum) = middlemaxsub(S, low, mid, high)
end if;
return triple with highest sum
end maxsub
middlemaxsub(int[] S; low, high, int) return (lowIndex, highIndex, sum)
start at mid and find bestleft and leftsum
start at mid and find bestright and rightsum
return (bestleft, bestright, rightsum+leftsum)
end middlemaxsub
Performance of Divide and Conquer Solution
Performance:
Base Case: T (1) = Θ(1)
Divide: Θ(1)
Conquer: 2T (n/2) and Θ(n)
Combine: Θ(1)
T (n) = 2T (n/2) + Θ(n)
Closed form: T (n) = …
Can we do better?
Yes! A Θ(n) algorithm exists! (Dynamic programming!)
https://sites.radford.edu/~nokie/classes/360/divcon.html 9/9
