UNIT II

Disjoint Sets: Disjoint set operations, union and find algorithms

Backtracking; General method, applications-n-queen problem, sum of subsets problem, graph
colouring.

Disjoint Set Operations :

Set: A set is a collection of distinct elements. The Set can be represented, for examples, as
S1={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 thatS1 and S2 are
two disjoint sets.

Disjoint Set Operations:

The disjoint set operations are
1. Union
2. Find
Disjoint set Union: If Si and Sj are tow disjoint sets, then their union Si U Sj
consists of all the elements x such that x is in Si or Sj.

Example:
S1= {1,7,8,9} S2= {2,5,10}
S1 U S2= {1,2,5,7,8,9,10}
Find:
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}
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
and make 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 storethe set names. The data structure contains
two fields. One is the set name and the other one is the pointer to root.

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 index values represent the nodes (elements of
set) and the entries represent the parent node. For the root value the entry will be ‘-1’.

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

i [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
p -1 -1 -1 3 2 3 1 1 1 2

Algorithm for Union operation:

To perform union the SimpleUnion(i,j) function takes the inputs as the set roots i and j .
And make the parent of i as j i., makethe 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 theroot node of i. It starts at I until it
reaches a node with parent value

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) algorithmsare easy to state, their performance
characteristics are not very good. For example, consider the sets

1 2 3 4 . . .n. . .

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

The sequence of Union operations results the degenerate tree as below.

n-1

n-2

Since, the time taken for a Union is constant, the n-1 sequence ofunion can be processed in time
O(n). And for the sequence of Findoperations it will take time
n
 complexity of O ( i ) = O(n2).
i1

We can improve the performance of union and find by avoidingthe creation of degenerate tree by
applying weighting rule for Union.

Weighting rule for Union:

If the number of nodes in the tree with root I is less than thenumber 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 negativenumber.

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 as 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]. Consider the tree
created by WeightedUnion () on thesequence of 1≤i≤8. Union (1,2), Union (3,4), Union (5,6) and
Union (7,8)

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 24
moves.
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 ito the root
s: =P[i];
P[i]: =r;
i: =s;
}
}

General Method:

Backtracking is used to solve problem in which a sequence of objects is chosen from a

specified set so that the sequence satisfies some criterion. The desired solution is
expressed as an n-tuple (x1, . . .., xn) where each xi Є S, S being a finite set.

The solution is based on finding one or more vectors that maximize, minimize, or satisfy
a criterion function P (x1, ........................... , xn). Form a solution and check at every
step if this has any chance of success. If the solution at any point seems not promising,
ignore it. All solutions require a set of constraints divided into two categories: explicit
and implicit constraints.

Explicit constraints are rules that restrict each xi to take on values only from a given set
Explicit constraints depend on the instance i of problem being solved. All tuples that
satisfy the explicit constraints define a possiblesolution space for i.

Implicit constraints are rules that determine which of the tuples in the solution space of
i satisfy the criterion function. Thus, implicit constraints describe the way in which the
xi’s must relate to each other.

For 8-queensproblem:

Explicit constraints using 8-tuple formation, for this problem are S= {1, 2, 3, 4, 5, 6, 7,8}.
The implicit constraints for this problem are that no two queens can be the same (i.e.,
all queens must be on different columns) and no two queens can be on the same
diagonal.

Backtracking is a modified depth first search of a tree. Backtracking algorithms

determine problem solutions by systematically searching the solution space for the given
problem instance. This search is facilitated by using a tree organization for the solution
space.
Backtracking is the procedure where by, after determining that a node can lead to
nothing but dead end, we go back (backtrack) to the nodes parent and proceed with the
search on the next child.
A backtracking algorithm need not actually create a tree. Rather, it only needs to keep
track of the values in the current branch being investigated. This is the way we
implement backtracking algorithm. We say that the state space tree exists implicitly in
the algorithm because it is not actually constructed.

Terminology:
Problem state is each node in the depth first search tree.
solution states are the problem states ‘S’ for which the path from the root node to ‘S’
defines a tuple in the solution space.
Answer states are those solution states for which the path from root node to s defines
a tuple that is a member of the set of solutions.

State space is the set of paths from root node to other nodes. State space tree is the tree
organization of the solution space. The state space trees are called static trees. This terminology
follows from the observation that the tree organizations are independent of the problem instance
being solved. For some problems it is advantageous to use different tree organizations for different
problem instance. In this case the tree organization is determined dynamically as the solution
space is being searched. Tree organizations thatare problem instance dependent are called dynamic
trees.
Live node is a node that has been generated but whose children have not yet been
generated.
E-node is a live node whose children are currently being explored. In other words, an E-
node is a node currently being expanded.
Dead node is a generated node that is not to be expanded or explored any further. All
children of a dead node have already been expanded.
Branch and Bound refers to all state space search methods in which all children of
an E-node are generated before any other live node can become the E-node.

Depth first node generation with bounding functions is called backtracking. State
generation methods in which the E-node remains the E-node until it is dead, lead to
branch and bound methods.

N-Queens Problem:

Let us consider, N = 8. Then 8-Queens Problem is to place eight queens on an 8 x 8

chessboard so that no two “attack”, that is, no two of them are on the same row, column,
or diagonal. All solutions to the 8-queens problem can be represented as 8-tuples (x1,
. . . ., x8), where xi is the column of the ith row where the ith queen is placed.

The explicit constraints using this formulation are Si = {1, 2, 3, 4, 5, 6, 7, 8}, 1 ≤i≤8
Therefore the solution space consists of 88-tuples.
The implicit constraints for this problem are that no two x i’s can be the same (i.e., all
queens must be on different columns) and no two queens can be on the same diagonal.
This realization reduces the size of the solution space from 88 tuples to 8! Tuples.
The promising function must check whether two queens are in the same column or
diagonal:

Suppose two queens are placed at positions (i, j) and (k, l) Then:
Column Conflicts: Two queens conflict if their xi values are identical.
Diagonal conflict: Two queens i and j are on the same diagonal
i – j = k –l
This implies, j – l = i –k
Diagonal conflict: i + j = k +l
This implies, j – l = k –i

Therefore, two queens lie on the same diagonal if and only if: |j – l|= |i – k|

Where, j be the column of object in row i for the ith queen and l be the column of object in row ‘k’
for the kthqueen.

To check the diagonal clashes, let us take the following tile configuration:

*
*
*
*
*
*
*
*

Suppose if we consider the below

i 1 2 3 4 5 6 7 8
xi 2 5 1 8 4 7 3 6
rd th
Let us consider for the case whether the queens on 3 row and 8 row are conflicting
or not. In this case (i, j) = (3, 1) and (k, l) = (8, 6)
Therefore:
|j – l|= |i – k | is |1 – 6|= |3 –8 | which is 5 =5
In the above example we have, |j – l|= |i – k| , so the two queens are attacking. This is
not a solution.

So, solution can be obtained by the following steps

Step1:
Add to the sequence the next number in the sequence 1, 2, . . . , 8 not yet used.

Step2:
If this new sequence is feasible and has length 8 then STOP with a solution. If thenew
sequence is feasible and has length less than 8, repeat Step1.

Step3:
If the sequence is not feasible, then backtrack through the sequence until we findthe most recent
place at which we can exchange a value. Go back to Step 1.

One way of finding 8 Queen problem is:

Step 1: If the reminder from dividing n by 6 is not 2 or 3 then the list is simply all even numbers
followed by all odd numbers which is not greater than N
Step 2: Otherwise, write separate lists of even and odd numbers (2,4,6,8… and 1,3,5,7….)
Step 3: If reminder is 2, switch the places of 1 and 3 and move 5 to the end of the odd number list
like (3,1,7,5)
Step 4: If reminder is 3, move 2 to the end of the even number list and move 1,3 in the end odd list
(4,6,8,2 and 5,7,1,3)
Step 5: Append odd list to the even list and place these queens in the rows given by the list.

One possible solution is : (2,4,6,8,3,1,7,5)

4 –Queens Problem:

Let us see how backtracking works on the 4-queens problem. We start with the root
node as the only live node. This becomes the E-node. We generate one child. Let us
assume that the children are generated in ascending order. Let us assume that the children
are generated in ascending order. Thus node number 2 of figure is generated and the path
is now (1). This corresponds to placing queen 1 on column 1. Node 2 becomes the E-
node. Node 3 is generated and immediately killed. The next node generated is node 8 and
the path becomes (1, 3). Node 8 becomes the E-node. However, it gets killed as all its
childrenrepresent board configurations that cannot lead to an answer node. We backtrack
to node 2 and generate another child, node 13. The path is now (1, 4). The board
configurations as backtracking proceeds is as follows:

1 1 1 1
. . 2 2 2
. . . . . 3

(a) (b) (c) (d)

1 1 1 1
2 . . . 2 2
3 3
. . . . . . 4
(e) (f) (g) (h)
The above figure shows graphically the steps that the backtracking algorithm goes
through as it tries to find a solution. The dots indicate placements of a queen, which were
tried and rejected because another queen was attacking.

In Figure (b) the second queen is placed on columns 1 and 2 and finally settles on column 1.
In figure (c) the algorithm tries all four columns and is unable to place the next queen
on a square. Backtracking now takes place. In figure (d) the second queen is moved to
the next possible column, column 4 and the third queen is placed on column 2. The
boards in Figure (e), (f), (g), and (h) show the remaining steps that the algorithm goes
through untila solution is found.
One solution is (2,4,1,3)

N Queen problem Algorithm:

Algorithm NQueen(k,n)
{
for i = 1 to n do
{
if (place(k,i)) then
{
x[k]=i
if(k= = n) then
write(x[i:n])
else
NQueens(k+1,n)
}
}
}
place(k,i)
{
for j= 1 to (k-1) do
{
if(x[j]=i) OR (Abs(x[j]-i)=Abs(j-k)) then
return False
}
return True
}

Complexity of this Algorithm is O(N!)

Sum of Subsets Problem:

Given positive numbers wi, 1 ≤ i ≤ n, and m, this problem requires finding all subsets of
wi whose sums are ‘m’. All solutions are k-tuples, 1 ≤ k ≤n.
 Explicit constraints:
xi Є {j | j is an integer and 1 ≤ j ≤n}.
Implicit constraints:
No two xi can be the same.
The sum of the corresponding wi’s be m.xi < xi+1 , 1 ≤ i < k (total order in indices) to
avoid generating multiple instances of the same subset (for example, (1, 2, 4) and (1, 4,
2)represent the same subset).
A better formulation of the problem is where the solution subset is represented by a
n- tuple (x1, .......................... , xn) such that xi Є {0,1}.
The above solutions are then represented by (1, 1, 0, 1) and the solution space is 2n distinct tuples.

Example: Draw the portion of the state space tree for sum of subsets problem for a given set of
integers N= (11, 13, 24, 7) whose sum of weights exactly equalent to 31 by backtracking algorithm

Solution:

The desired subsets are (11,13, 7) and (24,7).

The following figure shows a possible tree organization for two possible formulations of the solution
space for the case n =4.

0,55
x1=1 x1=0

11,44 0,44
x2=1 x2=0 x2=0

24,31 11,31 0,31

x3=1 x3=0 x3=1

48,7 24,7 24,7

X x4=1 x4=0 x4=1

31,0 24,0 31,0

Solution X Solution

One solution is (1,1,0,1)

Another solution is (0,0,1,1)

Algorithm Sum of Subsets Problem:

Algorithm sumofsubsets(s,k,r)
{
X[k]:=1;
if (s+w[k]=m) then write (x[1:k]);
else
if (s+w[k]+w[k+1]<=m) then
sumofsubsets(s+w[k],k+1,r-w[k]);
if ((s+r-w[k]>=m) and (s+w[k+1]<=m)) then
{
X[k]:=0;
sumofsubsets(s,k+1,r-w[k]);
}
}

Complexity of this Algorithm is O(2n)

Graph Coloring Problem:

Let G be a graph and m be a given positive integer. We want to discover whether 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. This is termed the m-colorabiltiy decision problem. The m-
colorability optimization problem asks for the smallest integer m for which the graph G
can be colored.

Note that if d is the degree of the given graph, then it can be colored with d+1 colors. The m-
colorability optimization problem asks for the smallest integer m for which the graph G can be
colored. The integer is referred to as the chromatic number of the graph.

For example, the following graph can be colored with three colors 1, 2 and 3.
The color of each node is indicated next to it. It can also be seen that thee colors are needed to
color this graph and hence this graph’s chromatic number is 3.

The function m-coloring will begin by first assigning the graph to its adjacency matrix,
setting the array x [] to zero. The colors are represented by the integers 1, 2, . . . m and
the solutions are given by the n-tuple (x1, x2, . . ., xn), where xi is the color of node i.

Example: Solve the following graph using graph coloring method with m = 3

1 2

4 3

Solution:
Graph coloring problem Algorithm:

Algorithm mcoloring(k)
{
repeat
{
nextvalue(k);
if (x[k] = 0) then return;
if (k=n) then
write(x[1:n]);
else
mcoloring(k+1);
}until(false);
}
Algorithm nextvalue(k)
{
Repeat
{
X[k]=(x[k]+1)mod(m+1);
if (x[k]=0) then
return;
for j:=1 to n do
{
if ((G[k,j]!=0) and (x[k]=x[j])) then break;
}
if (j=n+1) then return;
}until (false);
}
Complexity of this Algorithm is O(mv)
 IMPORTANT QUESTIONS
a) Write and explain find algorithm with collapsing rule.
1)
b) Describe the general method of backtracking. (8+7) M
2) a) What are union and find operations? Explain with suitable examples.
b) Explain about graph coloring algorithm. (8+7) M
3) Write an algorithm of n-queen’s problem and explain. 7M
4) a) Describe the Backtracking technique to the m-coloring graph. Explain with an example.
b) Write an algorithm of weighted union and also compute the time complexity of the
same. (8+7) M
5) a) Draw the state space tree for ‘m’ coloring when n=3 and m=3.
b) Write an algorithm for the 8-queens problem using backtracking. (8+7) M
6) Define static space tree. 2M
7) Write and explain general iterative backtracking method. 3M
8) Explain about 4-queens problem with backtrack solution. 5M