DESIGN AND ANALYSIS

OF ALGORITHMS

UNIT - II

1
 DESIGN AND ANALYSIS OF ALGORITHMS

DISJOINT SETS

DISJOINT SET OPERATIONS:

Set:
A set is a collection of distinct elements. The Set can be represented, for examples,
asS1={1,2,5,10}.

Disjoint Sets:
The disjoints sets are those do not have any common element.
For example S1= {1,7,8,9} and S2={2,5,10}, then we can say that S1 and S2 are two
disjointsets.

Disjoint Set Operations:

The disjoint set operations are
1. Union
2. Find

Disjoint set Union:

If Si and Sj are two disjoint sets, then their union Si U Sj consists of all the elements x
suchthat x is in Si or Sj.

FIND:
Example:
S1={1,7,8,9} S2={2,5,10}
S1 U S2={1,2,5,7,8,9,10}
Given the element I, find the set containing i.
Example:
S1 = {1,7,8,9} S2 = {2,5,10} S3 = {3,4,6}
Then,
Find(4)= S3 Find(5) = S2 Find(7) = S1

Set Representation:
The set will be represented as the tree structure where all children will store the address
of parent / root node. The root node will store null at the place of parent address. In the
given set of elements any element can be selected as the root node, generally we select
the first node as the root node.

Example:
S1={1,7,8,9} S2={2,5,10} s3={3,4,6}

2
 DESIGN AND ANALYSIS OF ALGORITHMS

Then these sets can be represented as

Disjoint Union:
To perform disjoint set union between two sets Si and Sj can take any one root andmake
it sub-tree of the other. Consider the above example sets S1 and S2 then the union of S1
and S2 can be represented as any one of the following.

Find:
To perform find operation, along with the tree structure we need to maintain the name of
each set. So, we require one more data structure to store the set names. The data structure
contains two fields. One is the set name and the other one is the pointer toroot.

UNION AND FIND ALGORITHMS:

In presenting Union and Find algorithms, we ignore the set names and identify sets just
by the roots of trees representing them. To represent the sets, we use an array of 1 to n
elements where n is the maximum value among the elements of all sets. The indexvalues
represent the nodes (elements of set) and the entries represent the parent node. For the
root value the entry will be ‘-1’.

3
 DESIGN AND ANALYSIS OF ALGORITHMS

Example:
For the following sets the array representation is as shown below.

ALGORITHM FOR UNION OPERATION:

To perform union the SimpleUnion(i,j) function takes the inputs as the set roots i and j .
Andmake the parent of i as j i.e, make the second root as the parent of first root.

Algorithm SimpleUnion(i,j)
{
P[i]:=j;
}
ALGORITHM FOR FIND OPERATION:

The SimpleFind(i) algorithm takes the element i and finds the root node of i. It starts
at Iuntil it reaches a node with parent value -1.

Algorithms SimpleFind(i)
{
while( P[i]≥0) do i:=P[i]; return i;
}

Analysis of SimpleUnion(i,j) and SimpleFind(i):

Although the SimpleUnion(i,j) and SimpleFind(i) algorithms are easy to state, their
performance characteristics are not very good. For example, consider the sets

Then if we want to perform following sequence of operations Union(1,2) ,

Union(2,3)…….Union(n-1,n) and sequence of Find(1), Find(2)……… Find(n).
The sequence of Union operations results the degenerate tree as below.

4
 DESIGN AND ANALYSIS OF ALGORITHMS

Since, the time taken for a Union is constant, the n-1 sequence of union can be processed
intime O(n). And for the sequence of Find operations it will take time complexity of

We can improve the performance of union and find by avoiding the creation of
degeneratetree by applying weighting rule for Union.

Weighting rule for Union:

If the number of nodes in the tree with root I is less than the number in the tree with the
root j, then make ‘j’ the parent of i; otherwise make ‘i' the parent of j.

To implement weighting rule we need to know how many nodes are there in every tree.
To do this we maintain “count” field in the root of every tree. If ‘i' is the root then count[i]
equals to number of nodes in tree with root i.
Since all nodes other than roots have positive numbers in parent (P) field, we can
maintain count in P field of the root as negative number.

5
 DESIGN AND ANALYSIS OF ALGORITHMS

Algorithm WeightedUnion(i,j)
//Union sets with roots i and j , i≠j using the weighted rule
// P[i]=-count[i] and p[j]=-count[j]
{
temp:= P[i]+P[j];
if (P[i]>P[j]) then
{
// i has fewer nodes
P[i]:=j;P[j]:=temp;
}
else
{
// j has fewer nodes
P[j]:=i;P[i]:=temp;
}
}

Collapsing rule for find:

If j is a node on the path from i to its root and p[i]≠root[i], then set P[j] to root[i].
Considerthe tree created by WeightedUnion() on the sequence of 1≤i≤8.
Union(1,2), Union(3,4), Union(5,6) and Union(7,8)

6
 DESIGN AND ANALYSIS OF ALGORITHMS

Now process the following eight find operations Find(8), Find(8) ....................... Find(8)
If SimpleFind() is used each Find(8) requires going up three parent link fields for a total
of 24moves .
When Collapsing find is used the first Find(8) requires going up three links and resetting
three links. Each of remaining seven finds require going up only one link field. Then the
total cost is now only 13 moves.( 3 going up + 3 resets + 7 remaining finds).

Algorithm CollapsingFind(i)
// Find the root of the tree containing element i
// use the collapsing rule to collapse all nodes from i to root.
{
r:=i;
while(P[r]>0) do r:=P[r]; //Find root while(i≠r)
{
//reset the parent node from element i to the root
s:=P[i];P[i]:=r;
i:=s;
}
}

7
 DESIGN AND ANALYSIS OF ALGORITHMS

BACKTRACKING

BACKTRACKING
The general method—8 queens problem—Sum of subsets—Graph coloring

BACKTRACKING
 It is one of the most general algorithm design techniques.

 Many problems which deal with searching for a set of solutions or for a optimal
solution satisfying some constraints can be solved using the backtracking
formulation.

 To apply backtracking method, tne desired solution must be expressible as an n-

tuple (x1…xn) where xi is chosen from some finite set Si.

 The problem is to find a vector, which maximizes or minimizes a criterion

function
P(x1….xn).

 The major advantage of this method is, once we know that a partial vector
(x1,…xi)
will not lead to an optimal solution that (mi+1.........mn) possible test vectors may
be
ignored entirely.

 Many problems solved using backtracking require that all the solutions satisfy a
complex set of constraints.

 These constraints are classified as:

i) Explicit constraints.
ii) Implicit constraints.

1) Explicit constraints:

Explicit constraints are rules that restrict each Xi to take values only from a
given set.Some examples are,
Xi>=0 or Si = {all non-negative real
nos.}Xi =0 or 1 or Si={0,1}.
Li <= Xi<=Ui or Si= {a: Li<= a<=Ui}
 All tupules that satisfy the explicit constraint define a possible solution space for I.

2) Implicit constraints:
The implicit constraint determines which of the tuples in the solution space I can
actuallysatisfy the criterion functions.

8
 DESIGN AND ANALYSIS OF ALGORITHMS

Algorithm:

Algorithm IBacktracking (n)

// This schema describes the backtracking procedure .All solutions are generated in
X[1:n]
//and printed as soon as they are determined.
{
k=1
;
While (k 0) do
{
if (there remains all untried
X[k] belongs to T (X[1],[2],…..X[k-1]) and Bk (X[1],…..X[k])) is true ) then
{
if(X[1],……X[k] )is the path to the answer node)
Then write(X[1:k]);
k=k+1; //consider the next step.
}
else k=k-1; //consider backtracking to the previous set.
}
}
 All solutions are generated in X[1:n] and printed as soon as they are determined.

 T(X[1]…..X[k-1]) is all possible values of X[k] gives that X[1],… X[k-1] have
already
been chosen.

 Bk(X[1]………X[k]) is a boundary function which determines the elements of

X[k]
which satisfies the implicit constraint.

 Certain problems which are solved using backtracking method are,

1. N-Queens problem.
2. Sum of Subsets
3. Graph coloring

N-QUEENS PROBLEM:
This 8 queens problem is to place n-queens in an ‘N*N’ matrix in such a way that no
two
queens attack each otherwise no two queens should be in the same row, column,
diagonal.

Solution:
 The solution vector X (X1…Xn) represents a solution in which Xi is the column
of theth row where I th queen is placed.

 First, we have to check no two queens are in same row.

9
 DESIGN AND ANALYSIS OF ALGORITHMS

 Second, we have to check no two queens are in same column.

 The function, which is used to check these two conditions, is [I, X (j)], which gives
position of the I th queen, where I represents the row and X (j) represents the
column position.

 Third, we have to check no two queens are in it diagonal.

 Consider two dimensional array A[1:n,1:n] in which we observe that every

element on the same diagonal that runs from upper left to lower right has the same
value.

 Also, every element on the same diagonal that runs from lower right to upper left
has the same value.

 Suppose two queens are in same position (i,j) and (k,l) then two queens lie on the
same diagonal , if and only if |j-l|=|I-k|.

STEPS TO GENERATE THE SOLUTION:

Initialize x array to zero and start by placing the first queen in k=1 in the first row.
To find the column position start from value 1 to n, where ‘n’ is the no. Of
columns
or no. Of queens.
If k=1 then x (k)=1.so (k,x(k)) will give the position of the k th queen. Here we have
tocheck whether there is any queen in the same column or diagonal.
For this considers the previous position, which had already, been found out.
Checkwhether
X (I)=X(k) for column |X(i)-X(k)|=(I-k) for the same diagonal.
If any one of the conditions is true then return false indicating that k th queen
can’t
be placed in position X (k).
For not possible condition increment X (k) value by one and precede d until
theposition is found.
If k=1 then x (k)=1.so (k,x(k)) will give the position of the k th queen. Here we have
tocheck whether there is any queen in the same column or diagonal.
For this considers the previous position, which had already, been found out.
Checkwhether
X (I)=X(k) for column |X(i)-X(k)|=(I-k) for the same diagonal.
If any one of the conditions is true then return false indicating that k th queen
can’t
be placed in position X (k).
For not possible condition increment X (k) value by one and precede d until
theposition is found.
If the position X (k) n and k=n then the solution is generated completely.
If k<n, then increment the ‘k’ value and find position of the next queen.
If the position X (k)>n then k th queen cannot be placed as the size of the matrix
is
‘N*N’.
So decrement the ‘k’ value by one i.e. we have to back track and after the position of
10
 DESIGN AND ANALYSIS OF ALGORITHMS
the previous queen.

Algorithm:

Algorithm place (k,I)

//return true if a queen can be placed in k th row and I th column. otherwise it returns
false.
//X[] is a global array whose first k-1 values have been set. Abs ® returns the absolute
value
//of r.
{
For j=1 to k-1 do
If ((X [j]=I) //two in same
column.Or (abs (X [j]-I)=Abs (j-
k)))
Then return
false;
Return true;
}

Algorithm Nqueen (k,n)

//using backtracking it prints all possible positions of n queens in ‘n*n’ chessboard. So
//that they are non-tracking.
{
For I=1 to n do
{
If place (k,I) then
{
X [k]=I;
If (k=n) then write (X
[1:n]);Else
nquenns(k+1,n) ;
}
}
}

Example: 4 queens.
Two possible solutions are

Solutin-1 Solution 2
(2 4 1 3) (3 1 4 2)

11
 DESIGN AND ANALYSIS OF ALGORITHMS

SUM OF SUBSETS:

 We are given ‘n’ positive numbers called weights and we have to find all
combinations of these numbers whose sum is M. this is called sum of subsets
problem.

 If we consider backtracking procedure using fixed tuple strategy , the elements

X(i) of the solution vector is either 1 or 0 depending on if the weight W(i) is
included or not.

 If the state space tree of the solution, for a node at level I, the left child corresponds
to X(i)=1 and right to X(i)=0.

Example:
 Given n=6,M=30 and W(1…6)=(5,10,12,13,15,18).We have to generate all
possible
combinations of subsets whose sum is equal to the given value M=30.

 In state space tree of the solution the rectangular node lists the values of s, k, r,
where s is the sum of subsets,’k’ is the iteration and ‘r’ is the sum of elements after
‘k’ in the original set.

 The state space tree for the given problem is,

Ist solution is A -> 1 1 0 0 1 0

IInd solution is B -> 1 0 1 1 0 0

12
 DESIGN AND ANALYSIS OF ALGORITHMS
III rd solution is C -> 0 0 1 0 0 1

 In the state space tree, edges from level ‘i’ nodes to ‘i+1’ nodes are labeled with
the
values of Xi, which is either 0 or 1.

 The left sub tree of the root defines all subsets containing Wi.

 The right subtree of the root defines all subsets, which does not include Wi.

Generation of state space tree:

Maintain an array X to represent all elements in the set.

The value of Xi indicates whether the weight Wi is included or not.

Sum is initialized to 0 i.e., s=0.

We have to check starting from the first node.

Assign X(k)<- 1.

If S+X(k)=M then we print the subset because the sum is the required output.

If the above condition is not satisfied then we have to check S+X(k)+W(k+1)<=M. If so, we
have to generate the left sub tree. It means W(t) can be included so the sum will be
incremented and we have to check for the next k.

After generating the left sub tree we have to generate the right sub tree, for this we
have to check S+W(k+1)<=M. Because W(k) is omitted and W(k+1) has to be
selected.

Repeat the process and find all the possible combinations of the subset.

Algorithm:

Algorithm sumofsubset(s,k,r)
{
//generate the left child. note s+w(k)<=M since Bk-1 is
true.X{k]=1;
If (S+W[k]=m) then write(X[1:k]); // there is no recursive call here as
W[j]>0,1<=j<=n.Else if (S+W[k]+W[k+1]<=m) then sum of sub (S+W[k], k+1,r-
W[k]);
//generate right child and evaluate Bk.
If ((S+ r- W[k]>=m)and(S+ W[k+1]<=m)) then
{ X{k]=0;
13
 DESIGN AND ANALYSIS OF ALGORITHMS
sumofsubset (S, k+1, r- W[k]);
}}

GRAPH COLORING:

 Let ‘G’ be a graph and ‘m’ be a given positive integer. If the nodes of ‘G’ can be
colored in such a way that no two adjacent nodes have the same color. Yet only ‘M’
colors are used. So it’s called M-color ability decision problem.
 The graph G can be colored using the smallest integer ‘m’. This integer is referred
to
as chromatic number of the graph.
 A graph is said to be planar iff it can be drawn on plane in such a way that no two
edges cross each other.
 Suppose we are given a map then, we have to convert it into planar. Consider each
and every region as a node. If two regions are adjacent then the corresponding
nodes are joined by an edge.

Consider a map with five regions and its graph.

1 is adjacent to 2, 3, 4.
2 is adjacent to 1, 3, 4, 5
3 is adjacent to 1, 2, 4
4 is adjacent to 1, 2, 3, 5
5 is adjacent to 2, 4

Steps to color the Graph:

 First create the adjacency matrix graph(1:m,1:n) for a graph, if there is an edge
between i,j then C(i,j) = 1 otherwise C(i,j) =0.

14
 DESIGN AND ANALYSIS OF ALGORITHMS

 The Colors will be represented by the integers 1,2,…..m and the solutions will be
stored in the array X(1),X(2),… ,X(n) ,X(index) is the color, index is the node.

 Here formula is used to set the color

is,X(k) = (X(k)+1) % (m+1)

 First one chromatic number is assigned ,after assigning a number for ‘k’ node, we
have to check whether the adjacent nodes has got the same values if so then we
have to assign the next value.

 First one chromatic number is assigned ,after assigning a number for ‘k’ node, we
have to check whether the adjacent nodes has got the same values if so then
wehave to assign the next value.
 Repeat until all the possible combinations colors are found
 The function which is used to check the adjacent nodes and same color

is,If(( Graph (k,j) == 1) and X(k) = X(j))

1 2

4 3

N= 4
M= 3
Adjacency Matrix:

 The problem is to color the given graph of 4 nodes using 3 colors.

 Node-1 can take the given graph of 4 nodes using 3 colors.
 The state space tree will give all possible colors in that ,the numbers which are
insidethe circles are nodes ,and the branch with a number is the colors of the
nodes.

15
 DESIGN AND ANALYSIS OF ALGORITHMS

Algorithm:

Algorithm mColoring(k)
// the graph is represented by its Boolean adjacency matrix G[1:n,1:n] .All assignments
//of
1,2, ........... ,m to the vertices of the graph such that adjacent vertices are assigned
//distinctintegers are printed. ’k’ is the index of the next vertex to color.
{
repeat
{
// generate all legal assignment for X[k].
Nextvalue(k); // Assign to X[k] a legal color.
If (X[k]=0) then return; // No new color possible.
If (k=n) then // Almost ‘m’ colors have been used to color the ‘n’ vertices
Write(x[1:n]);
Else
mcoloring(k+1);
}until(false);
}
Algorithm Nextvalue(k)
// X[1],……X[k-1] have been assigned integer values in the range[1,m] such that
//adjacent values have distinct integers. A value for X[k] is determined in the
//range[0,m].X[k] is assigned the next highest numbers color while maintaining
//distinctness form the adjacent vertices of vertex K. If no such color exists, then X[k] is
0.
{
repeat
{
X[k] = (X[k]+1)mod(m+1); // next highest color.

16
 DESIGN AND ANALYSIS OF ALGORITHMS
If(X[k]=0) then return; //All colors have been
used.
For j=1 to n do

{
// Check if this color is distinct from adjacent color.
If((G[k,j] 0)and(X[k] = X[j]))
// If (k,j) is an edge and if adjacent vertices have the same
color.Then break;
}
if(j=n+1) then return; //new color found.
} until(false); //otherwise try to find another color.
}

The time spent by Nextvalue to determine the children is

(mn)Total time is = (mn n).

17