Advanced Algorithms Analysis

and Design

By

Nazir Ahmad Zafar

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Lecture No 14

Designing Algorithms using

Divide & Conquer Approach

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Today Covered
Divide and Conquer?
• A General Divide and Conquer Approach
• Merge Sort algorithm
• Finding Maxima in 1-D, and 2-D
• Finding Closest Pair in 2-D

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Divide and Conquer Approach

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 A General Divide and Conquer Algorithm
Step 1:
• If the problem size is small, solve this problem
directly
• Otherwise, split the original problem into 2 or more
sub-problems with almost equal sizes.
Step 2:
• Recursively solve these sub-problems by applying
this algorithm.
Step 3:
• Merge the solutions of the sub- problems into a
solution of the original problem.

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Time Complexity of General Algorithms
• Time complexity:
 2T(n/2) + S(n) + M(n) , n  c
T(n)= 
b ,n<c

– where S(n) is time for splitting

– M(n) is time for merging
– b and c are constants
Example
• Binary search
• Quick sort
• Merge sort
Dr Nazir A. Zafar Advanced Algorithms Analysis and Design
 Merge-sort

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Merge-sort
Merge-sort is based on divide-and-conquer approach
and can be described by the following three steps:
Divide Step:
• If given array A has zero or one element, return S.
• Otherwise, divide A into two arrays, A1 and A2,
• Each containing about half of the elements of A.
Recursion Step:
• Recursively sort array A1, A2
Conquer Step:
• Combine the elements back in A by merging the sorted
arrays A1 and A2 into a sorted sequence.
Dr Nazir A. Zafar Advanced Algorithms Analysis and Design
 Visualization of Merge-sort as Binary Tree
• We can visualize Merge-sort by means of binary
tree where each node of the tree represents a
recursive call
• Each external node represents individual elements
of given array A.
• Such a tree is called Merge-sort tree.
• The heart of the Merge-sort algorithm is conquer
step, which merge two sorted sequences into a
single sorted sequence
• The merge algorithm is explained in the next

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Sorting Example: Divide and Conquer Rule
• Sort the array [14, 10, 4, 8, 2, 12, 6, 0] in the
ascending order
Solution:
• Divide

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Contd..

• Recursion and Conquer

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Merge-sort Algorithm

Merge-sort(A, f, l)
1. if f < l
2. then m = (f + l)/2
3. Merge-sort(A, f, m)
4. Merge-sort(A, m + 1, l)
5. Merge(A, f, m, l)

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Merge-sort Algorithm
Merge(A, f, m, l)
1. T[f..l] \\declare temporary array of same size
2. i  f; k  f; j  m + 1 \\initialize integers i, j, and k
3. while (i  m) and (j  l)
4. do if (A[i]  A[j]) \\comparison of elements
5. then T[k++]  A[i++]
6. else T[k++]  A[j++]
7. while (i  m)
8. do T[k++]  A[i++] \\copy from A to T
9. while (j  l)
10. do T[k++]  A[j++] \\copy from A to T
11. for i  f to l
12. do A[i]  T[i] \\copy from T to A
Dr Nazir A. Zafar Advanced Algorithms Analysis and Design
 Analysis of Merge-sort Algorithm
• Let T(n) be the time taken by this algorithm to sort
an array of n elements dividing A into sub-arrays
A1 and A2.
• It is easy to see that the Merge (A1, A2, A) takes
the linear time. Consequently,
T(n) = T(n/2) + T(n/2) + θ(n)
T(n) = 2T (n/2) + θ(n)
• The above recurrence relation is non-homogenous
and can be solved by any of the methods
– Defining characteristics polynomial
– Substitution
– recursion tree or
– master method

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Analysis: Substitution Method
n
T (n)  2.T ( )  n
2
n n n
T ( )  2.T ( 2 ) 
2 2 2
n n n
T ( 2 )  2.T ( 3 )  2
2 2 2
n n n
T ( 3 )  2.T ( 4 )  3 . . .
2 2 2

n n n
T ( k 1 )  2.T ( k )  k 1
2 2 2

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Analysis of Merge-sort Algorithm
n n
T (n)  2.T ( )  (n)  2 .T ( 2 )  n  n
2

2 2
n
T (n)  2 .T ( 2 )  n  n
2

2
n
T (n)  2 .T ( 3 )  n  n  n
3

2
...

n
T (n)  2 .T ( k )  n
k
n  .
 n
. .
2 k  times
Dr Nazir A. Zafar Advanced Algorithms Analysis and Design
 Analysis of Merge-sort Algorithm
n
T (n)  2 .T ( k )  n
k
n  .
 n
. .
2 k  times
n
T (n)  2 .T ( k )  k .n
k

2
Let us suppose that : n  2 k  log 2 n  k

Hence, T (n)  n.T (1)  n. log 2 n  n  n. log 2 n

T (n)  (n. log 2 n)

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Searching: Finding Maxima in 1-D

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 A Simple Example in 1-D
Finding the maximum of a set S of n numbers

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Time Complexity

 2T(n/2) + 1 , n > 2

T(n) =  1 ,n2

• Assume n = 2k, then

T(n) = 2T(n/2) + 1 = 2(2T(n/4) + 1) + 1
= 22T(n/22) + 2 + 1
= 22(2T(n/23) + 1) + 2 + 1
= 23T(n/23) + 22 + 21 + 1
:
= 2k-1T(n/2k-1)+2k-2 +…+ 22 + 21 + 1
= 2k-1T(2) + 2k-2 +…+ 22 + 21 + 1
= 2k-1 + 2k-2 +…+ 4 + 2 + 1 = 2k - 1 = n – 1 = (n)
Dr Nazir A. Zafar Advanced Algorithms Analysis and Design
 Finding Maxima in 2-D using
Divide and Conquer

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 How to Find Maxima in 2-D
L

P2
P3

P1
P4

SL SR

{P1, P2} both maximal in SL and {P3} only maxima in SR

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design
 Merging SL and SR
L

P2
P3

P1
P4

SL SR

After Merging Maximal in SLand SR we get {P2, P3} only maximal

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design
 Divide and Conquer for Maxima Finding Problem

P1
P2
P12
P6
P3

P10

The maximal points of SL and SR

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design
 Divide and Conquer for Maxima Finding Problem

P1
P2
P12
P3 P6

P10

P3 is not maximal point of SL

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design
 2-D Maxima Finding Problem

P1
P2
P12
P6
P3
P10

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Algorithm: Maxima Finding Problem
Input: A set S of 2-dimensional points.
Output: The maximal set of S.
Maxima(P[1..n])
1. Sort the points in ascending order w. r .t. X axis
2. If |S| = 1, then return it, else
find a line perpendicular to X-axis which separates S
into SL and SR, each of which consisting of n/2 points.
3. Recursively find the maxima’s SL and SR
4. Project the maxima’s of SL and SR onto L and sort
these points according to their y-values.
5. Conduct a linear scan on the projections and discard
each of maxima of SL if its y-value is less than the y-
value of some maxima’s of SR .

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Time Complexity


2T(n/2) + O(n) + O(n) ,n2
T(n) =  1 ,n<2

Assume n = 2k, then

T(n) = 2T(n/2) + n + n
= 2(2T(n/4) + n/2 + n/2) + n + n
= 22T(n/22) + n + n + n + n
= 22T(n/22) + 4n
= 22(2T(n/23) + n/4 + n/4) + 4n
= 23T(n/23) + n + n + 6n

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Time Complexity
T(n) = 23T(n/23) + n + n + 6n
.
.

T(n) = 2kT(n/2k) + 2kn

= 2kT(2k/2k) + 2kn Since n = 2k

Hence
T(n) = 2k + 2kn
T(n) = 2k + 2kn n = 2k  k = log(n)
T(n) = n + [Link] = ([Link])

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Necessary Dividing Problem into two Parts?

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Maximal Points: Dividing Problem into four Parts
Maximal points in S11 = {P1}
Maximal points in S12 = {P3, P4}
Maximal points in S21 = {P5, P6}
Maximal points in S22 = {P7, P8}

P3
P7
P5
P1

P4
P6
P8

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Maximal Points: Dividing Problem into four Parts

A1
A2
Merging S12, S12
A1 = {P3, P4}
P3
P7
Merging S21, S22
A2 = {P7, P8}

P4
P8

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Maximal Points: Dividing Problem into four Parts

A
Merging S12, S12
A1 = {P3, P4}
P3
P7
Merging S21, S22
A2 = {P7, P8}

Merging A1, A2 P8
A = {P3, P7, P8}

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Finding Closest Pair in 2-D

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Closest Pair in 2-D using Divide and Conquer
Problem
The closest pair problem is defined as follows:
• Given a set of n points
• Determine the two points that are closest to each
other in terms of distance.
• Furthermore, if there are more than one pair of
points with the closest distances, all such pairs
should be identified.

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Closest Pair: Divide and Conquer Approach
• First we sort the points on x-coordinate basis, and
divide into left and right parts
p1 p2 ... pn/2 and pn/2+1 ... Pn
• Solve recursively the left and right sub-problems
• Let d = min {di, dr},
• How do we combine
two solutions to
sub-problems?
d

PL PR

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Closest Pair: Divide and Conquer Approach
• How do we combine two solutions?
– Let d = min {di, dr}, where d is distance of closest
pair where both points are either in left or in right
– Something is missing. We have to check where
one point is from left and the other from the right.
– Such closest-pair can only be in a strip of width
2d around the dividing line, otherwise the points
would be more than d units apart.
• Combining solutions:
• Finding the closest pair in a strip of width 2d,
knowing that no one in any two given pairs is
closer than d

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Closest Pair: Divide and Conquer Approach
• Combining solutions:
• For a given point p from one partition, where can
there be a point q from the other partition, that can
form the closest pair with p?
• How many points can there be p

in this square?
– At most 4
• Algorithm for checking the strip:
– Sort all the points in the strip on the y-coordinate
– For each point p only 7 points ahead of it in the
order have to be checked to see if any of them is
closer to p than d

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Closest Pair: Divide and Conquer Approach
1. Partition the strip into
squares of length d/2
d
as shown in the picture.
2. Each square contains at
most 1 point by d/2 d/2 d/2 d/2
definition of d.
3. If there are at least 2 d/2
squares between points d/2
then they can not be
the closest points.
4. There are at most 8
squares to check. L
Dr Nazir A. Zafar Advanced Algorithms Analysis and Design
 Closest Pair: Divide and Conquer Approach
Closest-Pair(P, l, r)
01 if r – l < 3 then return ClosestPairBF(P)
02 q  (l+r)/2
03 dl  Closest-Pair(P, l, q-1)
04 dr  Closest-Pair(P, q, r)
05 d  min(dl, dr)
06 for i  l to r do
07 if P[q].x - d  P[i].x  P[q].x + d then
08 append P[i] to S
09 Sort S on y-coordinate
10 for j  1 to size_of(S)-1 do
11 Check if any of d(S[j],S[j]+1), ...,
d(S[j],S[j]+7) is smaller than d, if so set
d to the smallest of them
12 return d
Dr Nazir A. Zafar Advanced Algorithms Analysis and Design
 Closest Pair: Divide and Conquer Approach
Running Time
• Running time of a divide-and-conquer algorithm
can be described by a recurrence
– Divide = O(1)
– Combine = O(n lg n)
– This gives the recurrence given below
– Total running time: O(n log2 n)

n n3

T ( n)   n
2T ( 2 )  n log n otherwise

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Improved Version: Divide and Conquer Approach

• Sort all the points by x and y coordinate once

• Before recursive calls, partition the sorted lists
into two sorted sublists for the left and right
halves, it will take simple time O(n)
• When combining, run through the y-sorted list
once and select all points that are in a 2d strip
around partition line, again time O(n)
• New recurrence:
n n3

T ( n)   n
2T ( 2 )  n otherwise

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design

 Conclusion
• Brute Force approach is discussed, design of some
algorithms is also discussed.
• Algorithms computing maximal points is
generalization of sorting algorithms
• Maximal points are useful in Computer Sciences
and Mathematics in which at least one component
of every point is dominated over all points.
• In fact we put elements in a certain order
• For Brute Force, formally, the output of any sorting
algorithm must satisfy the following two conditions:
– Output is in decreasing/increasing order and
– Output is a permutation, or reordering, of input.

Dr Nazir A. Zafar Advanced Algorithms Analysis and Design