Algorithm design techniques

Greedy Divide
Divide and
and Dynamic
Dynamic Branch
Branch and
and Randomized
Randomized
Back
Back tracking
tracking
algorithm conquer
conquer programming
programming bound
bound algorithm
algorithm
Bin packing algorithm
Consider N items of size S1, S2, S3, … , SN. Values of Si

lies between 0 and 1.

Bin packing algorithm packs these items in the fewest

number of bins, where each bin has unit capacity.

Bin packing algorithm
Example
Let S = {0.2, 0.5, 0.4, 0.7, 0.1, 0.3, 0.8}
Optimal number of Bins = 3

0.3
0.8 0.5

0.7 0.1
0.2 0.4

B1 B2 B3
Theorems
Theorem 1:
There are three simple algorithms that guarantee that

the number of bins used is not more than twice the

optimal. The algorithms are
 Next fit
 First fit
 Best fit
 Bin packing algorithm

Online Algorithm Offline Algorithm

Online Algorithm – Next fit
Statement : Check to see whether the new item fits in
the same bit as the last item. If it does not, a new bin is
created.

Example
Item list : 0.2, 0.5,0.4,0.7,0.1,0.3,0.8
Bin capacity: 1 unit
Online Algorithm – Next fit
Step 1: Read 0.2 and place in Bin 1.
Step 2: Read 0.5 and place in Bin 1 because 0.2+0.5 < 1
Step 3: Read 0.4 . Cannot be placed in Bin 1 since 0.2+05+0.4
> 1. So create B2 and place 0.4 in B2.
Empty Empty Empty
0.1
Empty Empty
0.5
0.7 0.8

0.2 0.4 0.3

B1 B2 B3 B4 B5
Online Algorithm – Next fit
Optimal number of bins = 3
Actual number of bins from next fit algorithm = 5

Theorem 2
Let M be the optimal number of bins required to pack a
list of N items. Then the next fit never uses more that
2M.
Online Algorithm – First fit
Statement : The first strategy scans the bins in order and
place the new item in the first bin that is large enough to
hold it. A new bin is created only when the results of
previous placements have left no other alternative
Advantages
Simple to implement
Best case O(N2)
Worst and average case O(NlogN)
Disadvantage
Wastage of memory
Online Algorithm – First fit
Example
Item list : 0.2, 0.5,0.4,0.7,0.1,0.3,0.8
Bin capacity: 1 unit

Empty Empty Empty

0.1 Empty
0.3
0.5
0.8
0.4 0.7
0.2

B1 B2 B3 B4
Online Algorithm – Best fit
Statement : The best fit strategy places a new item in
the highest among all bins instead of placing in the
first spot that is found
Advantage
Performance is better than next fit and first fit
Less wastage of memory
Disadvantage
Does not perform better for Random inputs
Online Algorithm – Best fit
Example
Item list : 0.2, 0.5,0.4,0.7,0.1,0.3,0.8
Bin capacity: 1 unit

Empty Empty
0.3
0.1 Empty

0.5 0.5 0.8

0.2 0.4

B1 B2 B3 B4
Offline Algorithm
Statement : In offline algorithm, all items are read first

and sorted placing the largest items first. Apply first fit
or best fit for the sorted list. The resultant algorithm is
called first fit decreasing or best fit decreasing. This is
optimal solution.
Offline Algorithm
Example
Item list : 0.2, 0.5, 0.4, 0.7, 0.1, 0.3, 0.8
Sorted list : 0.8, 0.7, 0.5, 0.4, 0.3, 0.2, 0.1

0.2 0.3 0.1

0.4
0.8 0.7
0.5

B1 B2 B3
Divide and conquer
Divide : Smaller sub problems are solved recursively
Conquer : Solution to the original problem is then
formed from the solutions to the sub problems.
Examples
Merge sort
Quick sort
Binary search
Matrix multiplication
Divide and conquer
Problem of size n

Sub problem of size n/2 Sub problem of size n/2

Solution to sub problem 1 Solution to sub problem 2

Solution to original
problem
Divide and conquer – Closest point problem
Closest point problem is to find the closest pair of points
in a list of P points given in a plane. Let P1 = (X1, Y1) and
P2 = (X2, Y2) then distance between P1 and P2 is given by

If there are N points then we have to compute

N(N-1) / 2 distances
( e.g for 200 points, 19,900 distances)
Time can be reduced using divide and conquer approach
Divide and conquer – Closest point problem
Divide N points into two halves
Example 100 on left and 100 on right

Number of computations can be reduced to

2*[(100*99)/2] = 9900 = 50% (appox)

Conquer by merging the minimum of two halves.
Divide and conquer – Closest point problem
6 6 dc
1 1
8 13 8 13
7
7
2 2
9 dL 9
3 12 3 12
14 dR 14
10 10
4 4

5 15 5 15
11 11

PL PR
Divide and conquer – Closest point problem
Δ= min(dL,dR) dc
6
If dc < Δ, then dc is 1
8 13
7
computed 2
Two methods used to dL 9
3 12
compute the distance
dR 14
between two points in Δ 10
4
 Brute force method
 Sort by ‘y’ coordinate 5 15
11
method
Δ Δ
PL PR
Divide and conquer – Closest point problem
Routine for Brute force
// loop untill all points on strip are considered
for (i=0; i<Numpoints in strip; i+1)
// compare the current point with next point
for(j=i+1; j<Numpoints in strip; j+1)
// if distance is less then recalculate Δ
if (dist(pi, pj)< Δ)
Δ= Dist(Pi, Pj);
Divide and conquer – Closest point problem
Routine for Sort by Y coordinate
// loop untill all points on strip are considered
for (i=0; i<Numpoints in strip; i+1)
// compare the current point with next point
for(j=i+1; j<Numpoints in strip; j+1)
// Eliminates the need for additional computations
if (dist(pi, pj)< Δ)
break;
else
// if distance is less then recalculate Δ
if (dist(pi, pj)< Δ)
Δ= Dist(Pi, Pj);
Advantage
Reduced computational time compared to Brute force technique
 Selection problem
Problem statement:
Given an array of A of n elements , A[0] to A[n-1], find the k th largest
element in the array.
Example
Consider the array A of 25 elements
Find the 13th largest element in the array.
1 14 11 15 13 23 17 4 19 6 0 10 8 3 2 9 21 12 22 16 24 18 5 20 7

Direct solution
Sort the elements
Find A[12]
Time complexity O(n logn)
 Selection problem – Divide and
conquer approach
To reduce the time complexity
Divide and conquer approach is used
Finds the kth elements without sorting all the given data
Solution

1 14 11 15 13 23 17 4 19 6 0 10 8 3 2 9 21 12 22 16 24 18 5 20 7

Divide the 25 elements into groups of 5 elements

1 14 11 15 13 23 17 4 19 6 0 10 8 3 2 9 21 12 22 16 24 18 5 20 7

Group 1 Group 2 Group 3 Group 4 Group 5

Selection problem – Divide and
conquer approach
Find the median of each group.
Median are M = [13,17,3,16,18]
Find a pivot element which is equal to median of
median.
Pivot element is V = 16
Let L = elements less than pivot in each group
Let E = elements equal to pivot in each group
Let G = elements greater than pivot in each group
 Selection problem – Divide and
conquer approach
In the example
L = [1,14,11,15,13,4,6,0,10,8,3,2,9,12,5,7]; Size = 16
E=[16] ; Size = 1
G=[23,17,19,21,22,24,18,20] ; Size = 8

1 14 11 15 13 4 6 0 10 8 3 2 9 12 5 7 16 23 17 19 21 22 24 18 20

V
L G
Divide and conquer – Multiplying
integers
 Consider X and Y to be two large integers to be multiplied
 In order to perform multiplication split X into two halves, namely
XL and XR
 Similarly Y is split into two halves, YL and YR
 Example
If X = 1234, Y = 5678
XL= 12; XR = 34
YL = 56; YR=78
X = 102+ XR
Y = 102 + YR
XY = XL YL104+(XLYR+ XR YL)102+ XRYR
Divide and conquer – Multiplying integers
XY = XL YL104+(XLYR+ XR YL)102+ XRYR
The above equation consists of four multiplications of
half size of original number. So time complexity
associated is 4T(N/2).
Overall time complexity is
T(N)=4T(N/2) + O(N)
The above time complexity can be reduced by making
the following modification
Divide and conquer – Multiplying integers
Rewrite
XLYR+ XR YL = (XL- XR)(YL- YR) + XLYL+ XR YR

Instead of using two multiplications , we can use one

multiplication and two previous computed results.
Advantage
Overall time complexity is
T(N)=3T(N/2) + O(N)
Divide and conquer –Matrix multiplication
Consider multiplication of two matrices A and B of
NxN size.
Traditional technique requires O(N3) time complexity
Modified algorithm is called Strassen’s algorithm
requires less time
Basic idea is to divide each matrix into four quadrant
=
Divide and conquer –Matrix multiplication
Consider two matrices

A = B=

Then the eight N/2 and N/2 matrices are

A1,1 = A1,2 = A2,1 = A2,2 =

B1,1 = B1,2 = B2,1 = B2,2 =

Divide and conquer –Matrix multiplication
Time complexity of the modified algorithm

T(N)=8T(N/2) + O(N2)
Additional modification to reduce the time

Time complexity of the modified algorithm

T(N)=7T(N/2) + O(N2)
Dynamic programming
This is a technique for solving problems with
overlapping sub problems.
Smaller problems are solved once and the results are
recorded in a table
The final solution is obtained from the table of results
for smaller problems.
Example
Ordering of matrix multiplication
All pairs shortest path algorithm
Dynamic programming –
Ordering matrix multiplication
Consider multiplication of four matrices with the
following dimension
A0[2x3]
A1[3x6]
A2[6,4]
A3[4,5]
It is required to compute A0 x A1 x A2 x A3
Different combinations require different number of
multiplication
Dynamic programming –
Ordering matrix multiplication
Different combinations for multiplication
(A0[2x3] x (A1[3x6] x A2[6x4])) x A3[4x5]
Number of multiplications required is
(2*3*4)+(3*6*4)+(2*4*6) = 136
(A0[2x3] x A1[3x6]) x (A2[6x4] x A3[4x5])
Number of multiplication required is
(2*3*6)+(2*6*4)+(2*4*5) = 124
Dynamic programming is used to find the optimal
computational order
Dynamic programming –
Ordering matrix multiplication
T matrix Formula
A0 A1 A2 A3 For K=I to J
{
A0 0 36 84 124
(Answer) T[I,J] = min {T[I,K]
+T[K+1,J],
A1 - 0 72 132
I.row+K.col+J.col]
}
A2 - - 0 120
Minimum number of
multiplications required
A3 - - - 0
= 124
Backtracking
Backtracking is a kind of search technique.
The basic idea is to construct solutions one component at
a time and evaluate such partially constructed solutions as
follows
If the partially constructed solution can be developed
further by following the problem constructs, then the
remaining options are considered for next component
If there is no option for the next component , no alternatives
for any remaining components need to be considered
Backtracking is done to replace the last component of the
partially constructed solution with next option.
Backtracking – Turnpike reconstruction
problem
The trunpike reconstruction problem is to reconstruct
a point set from the distances.
Application in physics and molecular biology
 Let D be the set of distances and assume |D| = M =
(N(N-1))/2
Let D = {1,2,2,2,3,3,3,4,5,5,5,6,7,8,10}
Since |D| = 15, N = 6.
Backtracking – Turnpike reconstruction
problem
Step 1: Start the algorithm by setting X1=0
Since the largest element in D is 10; X6 = 10
Remove 10 from D
 The resultant points placed on x-axis and the
remaining distances are shown
D = {1,2,2,2,3,3,3,4,5,5,5,6,7,8}

X1 = 0 X6 = 10
Backtracking – Turnpike reconstruction
problem
Step 2: The largest element in D is 8, which means x5
= 8 or x2 = 2.
Since both the choices lead to solutions, we can
choose any one
Remove 8 ,2 from D
D = {1,2,2,3,3,3,4, 5,5,5,6,7}

X1 = 0 X5 = 8 X6 = 10
Backtracking – Turnpike reconstruction
problem
Step 3: Since 7 is the largest value in D, which means x4 =
7 or x2=3
If we set X4 = 7 then the distances (X6-X4=10-7=3 and
X5-x4=8-7=1) must be in D
If we set X2=3 then the distances (x2-x1=3-0=3 and x5-
x2=8-3=5) must be in D
Since these distances are in D, either choice x2=3 or x4=7
can be selected
Take any one choice and proceed . If it does not lead to a
solution then we need to backtrack and find other choice
Backtracking – Turnpike reconstruction
problem
Step 3a: Let x4 = 7
Remove the distance 3,1 from D
The resultant points and distance sets are given as follows

X1 = 0 D = {1,2,2,3,3,3,4,5,5,5,6} X4 = 7 X5 = 8 X6 = 10

Next largest value D is 6. If we set x3=6 then the distance (x4-x3=7-6=1) is

not in D.
If X2=4 then (X2-X1) = 4 and (x5-x2) = 8-4=4. Two fours are not present in
D.
Therefore step3a does not lead to the solution.
Backtracking – Turnpike reconstruction
problem
Step 3b: Set x2=3 then the distances (x2-x1=3-0=3 and
x5-x2=8-3=5) are in D. Since, 3 and 5 are in D, the
solution proceeds as per step 3b.
Remove 3 and 5 from D and the modified solution is

X2 = 3 X5 = 8 X6 = 10
X1 = 0
D = {1,2,2,3,3, 4,5,5,6}
Backtracking – Turnpike reconstruction
problem
Step 4 : The largest value in D is 6 which means X4=6
or X3=4
Setting x3=4 is not possible since D has only one
occurrence of 4
Therefore set x4 = 6
Remove the distance 4,2,3

X1 = 0 X2 = 3 X4 = 6 X5 = 8 X6 = 10

D = {1,2,3,5,5}
Backtracking – Turnpike reconstruction
problem
Step 5: The only remaining choice is x3 = 5. Set x3 = 5.
Remove {5,3,2,1} from D since
X6-X3=5
X5-X3=3
X4-X3=1
X3-X2=2
Final Solution

X1 = 0 X2 = 3 X3 = 5 X4 = 6 X5 = 8 X6 = 10