COMP20007 Design of Algorithms
Divide-and-Conquer Algorithms
Lars Kulik Lecture 9 Semester 1, 2021
1
Divide and Conquer
We earlier saw recursion as a powerful problem solving technique. The divide-and-conquer strategy tries to make the most of this:
1. Divide the given problem instance into smaller instances.
2. Solve the smaller instances recursively.
3. Combine the smaller solutions to solve the original instance.
This works best when the smaller instances can be made to be of equal size.
2
Split-Solve-and-Join Approach
problem of size n
sub-problem 1 of size n/2
sub-problem 2 of size n/2
a solution to sub-problem 1
a solution to sub-problem 2
a solution to the original problem
3
Binary Trees Again
An example of a binary tree, with empty subtrees marked with :
17
33 48
19 16 1114 26 20 38 31 18
25
This tree has height 4, the empty tree having height -1.
4
Binary Tree Concepts
Special trees have their external nodes only at level h and h + 1 for some h:
17
33 48
19 16 11 14 38 31
A full binary tree: Each node has 0 or 2 children.
17
33
48
11
18
19
16
14
26
20
38
31
A complete tree: Each level filled left to right.
5
Binary Tree Concepts
A non-empty tree T has a root Troot, a left subtree Tleft, and a right subtree Tright.
Recursion is the natural way of calculating the height:
function Height(T) if T is empty then
return −1 else
return max (Height(Tleft ), Height(Tright )) + 1
6
Binary Tree Concepts
It is not hard to prove that the number x of external nodes is always one greater than the number n of internal nodes.
The function Height makes a tree comparison (empty or non-empty?) per node (internal and external), so altogether 2n + 1 comparisons.
7
Binary Tree Traversal
Preorder traversal visits the root, then the left subtree, and finally the right subtree.
Inorder traversal visits the left subtree, then the root, and finally the right subtree.
Postorder traversal visits the left subtree, the right subtree, and finally the root.
Level-order traversal visits the nodes, level by level, starting from the root.
8
Binary Tree Traversal: Preorder
function PreorderTraverse(T) if T is non-empty then
visit Troot PreorderTraverse(Tleft) PreorderTraverse(Tright)
17
48 19 16 11 14
33
38 31 Visit order for the example: 17, 33, 19, 16, 38, 31, 48, 11, 14.
9
Binary Tree Traversal: Inorder
function InorderTraverse(T) if T is non-empty then
InorderTraverse(Tleft) visit Troot InorderTraverse(Tright)
17
48 19 16 11 14
33
38 31 Visit order for the example: 19, 33, 38, 16, 31, 17, 11, 48, 14.
10
Binary Tree Traversal: Postorder
function PostorderTraverse(T) if T is non-empty then
PostorderTraverse(Tleft) PostorderTraverse(Tright) visit Troot
17
48 19 16 11 14
33
38 31 Visit order for the example: 19, 38, 31, 16, 33, 11, 14, 48, 17.
11
Preorder Traversal Using a Stack
We could also implement preorder traversal of T by maintaining a stack explicitly.
push(T )
while the stack is non-empty do
T ← pop
visit Troot
if Tright is non-empty then
push(Tright )
if Tleft is non-empty then
push(Tleft )
In an implementation, the elements placed on the stack would not be whole trees, but pointers to the corresponding internal nodes.
12
Tree Traversal Using a Queue: Level-Order
Level-order traversal results if we replace the stack with a queue.
inject (T )
while the queue is non-empty do
T ← eject
visit Troot
if Tleft is non-empty then
inject (Tleft )
if Tright is non-empty then
17
48 19 16 11 14
33
38 31 Visit order for the example: 17, 33, 48, 19, 16, 11, 14, 38, 31.
inject (Tright )
13
The Closest Pair Problem Revisited
In Lecture 5 we gave a brute-force algorithm for the closest pair problem: Given n points in the Cartesian plane, find a pair with minimal distance.
The brute-force method had complexity Θ(n2). We can use divide-and-conquer to do better, namely Θ(n log n).
First, sort the points by x value and store the result in array byX.
Also sort the points by y value and store the result in array byY .
Now we can identify the x median, and recursively process the set PL of points with lower x values, as well as the set PR with higher x values.
14
The Closest Pair Problem Revisited
byY
m
•
•
x median
•
•
••• •
•
••
dR dL ••
• d = min(dL,dR)
dd
byX
15
The Closest Pair Problem Revisited
The recursive calls will identify dL, the shortest distance for pairs in PL , and dR , the shortest distance for pairs in PR .
Let m be the x median and let d = min(dL,dR). This d is a candidate for the smallest distance.
But d may not be the global minimum—there could be some close pair whose points are on opposite sides of the median line x = m.
For candidates that may improve on d we only need to look at those in the band m − d ≤ x ≤ m + d.
So pick out, from array byY, each point p with x-coordinate between m−d and m+d, and keep these in array S.
For each point in S, consider just its “close” neighbours.
16
The Closest Pair Problem Revisited
The following calculates the smallest distance and leaves the (square of the) result in minsq.
It can be shown that the while loop can execute at most 5 times for each i value—see diagram.
minsq ← d2
copyallpointsofbyY with|x−m|