Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

UNIT-II

Sets and Disjoint Set Union :set is a group of elements
...
If Si and Sj , I # j are two sets , these two sets are called pairwise
disjoint, when there is no element that is in both Si and Sj
For example n=10, elements are partitioned into 3 disjoint sets s1 = { 1, 7, 8, 9 } , s2 = { 2, 5,
10 } S3 = { 3, 4, 6}
Representation of sets as trees :
S1

S2

S3

1

5

3

7

9

8

2

10

4

6
0
0

Operations that can be performed on these set are

1
...
since all the sets are disjoint the sets Si and Sj are
replaced by Si U Sj in collection of sets
...
Find(i) : Given an element i, find the set containing i
...


Union and Find Operations :
If we want to obtain the union of S1 and S2
...

S1US2 could then have one of the representations
...

This can be done by keeping a pointer to the root of the tree representing that set
...

To determine which set an element is currently in, we follow parent links to the root of its
tree and use the pointer to the setname
...
Transitions to set names is done by determining that element i is in a
tree with root j, and j has a points to entry „k‟ in the set name table, then the set name is just
name[k]
...
This can be done using [Setname , pointer ] table
...
Then the find
and union operations can be defined as
Find(i) -> is to determine the root of the tree containing element i
...

The set elements are numbered 1 through n, we represent the tree nodes using an array p[1 :
n] , where n is maximum number of elements, the ith element of this array represents the tree
node that contains element I, i
...

The root nodes have a parent of -1
...

Example :- Find (6) starts at 6 and then moves to 6‟s parent 3
...

Algorithm SimpleFind(i)
{
While( p[i] >=0 ) do i := p[i];
Return I;
}
The operation Union( i , j ) is equally simple
...

adopting the convention that the first tree becomes a subtree of the second
...

Algorithm SimpleUnion( i, j)
{
P [ i ] := j ;
}
The simple union, find operations are easy to state but their performance characterstics are
not very good
...
( i
...

Suppose the following sequence of union and find operations are processed
...
Union ( n-1,n )
Find( 1) , Find( 2) , Find( 3) , …………
...

The sequence results in the degenerate tree
...
but each find requires a
sequence of parent pointers from the element to be found to the
root
...
the total time needed to process the n finds is
𝑛
( 𝑖=1 𝑖 = O( n2 )
We can improve the performance of union & find algorithms by
avoiding the creation of a degenerate trees
...


1Find

( 1)
,Find(
1) ,

Weighting Rule for Union( i, j ) :
If the number of nodes in the tree with root „I‟ is less than the number in the tree
with root j, then make j , the parent of I, otherwise make I the parent of j
...

……
...


n

initial
2

Union ( 1 , 3 )

Union( 1, 4)

……
1

2

4

n

2

3

5

1

3

Union( 1, n)
…
n

4

1

2

3

4

To implement the weighted rule, we need to know how many nodes are there in every tree,
for this we maintain a count field in the root of every tree
...
Since all nodes other
than the roots of trees have a +ve number in the p field, we can maintain the count in the p
field of the roots as a –ve number
...

{
Temp := p[i] + p[j] ;
If ( p[i] > p[j] ) then
{
// I has fewer nodes
P[i] := j; p[j] := temp ;
}
else

n

{
// j has fewer or equal nodes
P[j] := i ;

p[i] := temp;

}
}
Let Tbe a tree with m nodes created as a result of a sequence of unions each performed using
weighted union
...

The sequence of operations
, union( 5, 7) , union ( 1,5 )
[-1]

union(1,2) , union ( 3,4 ), union ( 5,6 ), union (7,8 ), union(1,3)

[-1]

1

2

[-1]
3

[-1]

[-1]

4

[-1]

5

6

[-1]
7

[-1]
8

Initially all are at height -1 trees
...
so the time to process a find is O(log
m)
...
An intermixed sequence of u-1 unions and f find
operations is to be processed, the time becomes O( u + f log u )
...


Collapsing Rule :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]
...
, Find(8) - eight Finds
...

When collapsing find is used
...

The total cost is now only 13 moves
...
However, it reduces the worst time over a sequence of finds
...

Algorithm CollapsingFind(i)
// find the root of the tree containing element I
...
Set „V‟ is finite , nonempty set of vertices, the set E is
set of pairs of vertices, these pairs are called edges
...
in an
undirected graph edge (u ,v ) same as ( v, u )
...
the graph G is said to be connected iff for every pair of distinct vertices u and v
in V(G) there is a path from u to v in G
...
And the graph G2 is not connected
...
By “ maximal” we mean that G
contains no other subgraph that is both connected and properly contains H
...


Graph Representation Using Adjacency Lists :
In this graph G is represented using „n‟ linked lists, the nodes in list „I‟ represent vertices that
are adjacent from vertex i
...
Adjacency list of
G1 is
Head Nodes
[1]

4

2

3

0

[2]

3

4

1

0

[3]

2

4

1

0

[4]

1

2

3

0

The vertices in each list are not required to be ordered
...
Head nodes
are sequential
...


Breadth First Search and Traversal :
there are two search( traversal) methods for graph
...
The vertex „v‟ is said to be unexplored
...
All newly visited vertices which are
not explored are kept at the end of unexplored list
...
Exploration continues until unexplored vertex is left
...


Algorithm BFS(v)
// A Breadth first search of G is carried out beginning at vertex v
...
The graph G and array visited[]
are
//global, visited[] is initialized to zero
...

} until ( false );
}
If BFS is used on a connected graph G, then all vertices in G get visited and the graph is
traversed
...
A complete
Traversal of graph can be made by repeatedly calling BFS each time with a new unvisited
starting vertex
...

{
for i := 1 to n do

// mark all vertices unvisited
...
The
exploration of vertex „v‟ is suspended as soon as a new vertex is reached
...
When this new vertex has been explored, the
exploration of v continues
...

Algorithm DFS (v)
// given an undirected graph G = ( V,E) with n vertices and array visited []
initially
//set to zero
...
G and Visited
are //global
...
If G is not connected, then at least one vertex of G is not visited
...

Algorithm DFT ( G, n)
// Depth First Traversal of G
...


Visited [i] := 0;
for i := 1 to n do
if ( visited [i] = 0 ) then DFS(i);

}

Example :
1
3

2

4

5

6

7

8

BFS ( 1 ) :- 1 2 3 4 5 6 7 8
DFS ( 1 ) :- 1 2 4 8 5 6 3 7

Connected Components :If G is a connected undirected graph, then all vertices of G
will get visited on the first call to BFS
...
So BFS determines whether G is connected or not
...
hence the connected
components of a graph can be obtained using BFT
...

Algorithm Comp(v)
//Connected Component of G is carried out beginning at vertex v
...
The graph
G //and array visited[], list L are global, visited[] is initialized to zero
...

} until ( false );
}

Algorithm ConComp( G, n)
// Connected Components using BFS
{
for i := 1 to n do

// mark all vertices unvisited
...

In the similar way DFT can also be used to find the connected components by modifying
DFS algorithm
...
BFS easily determines the existence of a
spanning tree
...
Call the resulting algorithm BFS*
...
the spanning tree obtained using BFS is called Breadth first spanning tree
...

} until ( false );

}
Similarly If DFS Is Modified by adding t := 0 and t = t U {(u,w)} when it terminates the
edges in t define a spanning tree for the undirected graph G, if G is connected
...


Algorithm DFSTree (v)
// Depth first spanning Tree using DFS
{
Visited [ v ] := 1;
t := 0;
for each vertex w adjacent from v do
{
If ( visited [w] = 0 ) then
{
t := t U { ( v , w ) }
DFS(w);
}
}
Example :

1
3

2

4

5

6

8

7

For the above Graph
Adjacency list is

BFS ( 1 )

DFS ( 1)

12 3
1

21 4 5
31 6 7

1
3

2

3

2

42 8
4

52 8

5

7

6

4

5

6

63 8
73 8

8

8

84 5 6 7
BFS ( 1 ) :- 1 2 3 4 5 6 7 8

DFS ( 1 ) :- 1 2 4 8 5 6

3 7

Articulation Point :The vertex v in a connected Graph G is an articulation point if and only if the deletion of
vertex v together with all edges incident to v disconnects the graph into two or more non –
empty components
...


7

6

1

5

4

7

3

8
10

9

The above graph is having two more articulation points
...


Biconnected Graph:A Graph G is biconnected if and only if it contains no articulation
points
...
On the other
hand if G has no articulation points then if any station i
fails we can still communicate between every two
stations not including station i
...
This can be
done only if we know the maximal sub graph of „G‟ that are biconnected
...
a maximal biconnectedsubgraph is a
biconnectedcomponent
...
That is the
entire graph
...
No edge can be in two different biconnected components
...
Since every
biconnected component of a connected graph G contains at least two vertices
...
let Vi, where Vi ≠a be
a vertex in Bi, 1 ≤ i ≤ k; add to G the edges ( Vi , Vi+1 ), 1 ≤ i ≤ k
...
The addition on edges corresponding to all
articulation points, hence G has no articulation points so it is biconnected
...

Example :- using addition scheme to make above graph biconnected graph requires to add
edges (4,10) and (10,9) ( correspond to 3) edge (1,5) ( correspond to 2 ) edge ( 6,7 ) (
correspond to 5 )

For each articulation point „a‟ do
{
Let B1, B2, …
...

in the depth first spanning tree of G there is a number outside each vertex
...

The edges of depth first spanning tree are called tree edges and the remaining edges of graph
are called back edges
...
so there are no cross edges relative to dfs tree
...
If „u‟ is any
other vertex, then it is not an articulation point iff from every child w of U it is possible to
reach an ancestor of u using only a path made up of descendents of w and a back edge
...

For each vertex u , define L[u] as
L[u] = min { dfn[u] , min { L[w] / w is a child of u } , min { dfn[w] / ( u,w) is a back
edge } }
So if u is not a root , then u is an articulation point iff u has a child w such that L[w] ≥ dfn[u]
...
So to
determine the articulation points, it is necessary to perform a depth first search of G and visit
the nodes in the resulting dfs tree in post order
...
It performs the dfs(G)
...
At the same time L[i] is computed
for each vertex in the tree
...

Initial call to ART is ART ( 1,0 )
...


Once the L[1:n] has been computed, the articulation points can be identified in O(n+e) time
...

Algorithm ART ( u , v )
// u is a start vertex for depth first search, v is its parent if any in the depth first spanning tree
...
n is the number of vertices in G
...
The edge ( u,w) together with all edges ( both tree, back )
encountered during this call to ART ( W , U ) forms a biconnected component
...

It //is assumed that the global array dfn is initialized to zero and that the global variable num
is //initialized to 1
...

{
dfn [u] := num ; L[u] := num ; num := num + 1;
for each vertex w adjacent from u do
{
If ( ( v # w) and dfn [] Add ( u , w) to the top of a stack S;
If ( dfn[w] = 0 ) then
{
If ( l[w] >= dfn [ u] ) then
{
Write ( “ new bicomponent “);
Repeat
{
Delete an edge from the top of Stack s;
Let this edge be ( x, y );
Write ( x , y ) ;
} until ( ( x, y ) = ( u , w) ) or ( ( x , y ) = ( w , u ) );
}
Bicomp( w, u); // w is unvisited
L[u] := min ( L[u] , L[w] );

}
else if ( w != v ) then L[u] := min ( L[u] , dfn[w] );
}
}

When the vertex u has been explored an edge (u, w) is added to stack
...
when it returns L[w] is computed
and compared with dfn[u]
...

Example :

1

Consider the graph

1

2
4

6

3
5

1

7
2

4

3

4

5
10

6
2

9

7

8

3

5

8
10

9

6

9
7

8

STACK
Bicomp( 1 ,0 ) L[1] = 1
Bicomp( 4 ,1 )
L[3] = 1

( 1, 4 )
( 4, 3 )

L[4] = 1

Bicomp ( 3 ,4 )

L[10]=4

1 ( 3,10 )

L[9]=5

Bicomp ( 10 ,3 )

Bicomp ( 9 ,3 )

2 (3,9)
Bicomp ( 2 ,3 ) L[2] = 1

( 3, 2 )

Bicomp( 5 ,2 ) L[5] = 6

(2,5)
3 ( 5, 6 )

L[6] = 8Bicomp ( 6 ,5 )

Bicomp ( 7 ,5 ) L[7] = 6
Bicomp( 8 ,7 ) L[8] = 6

3

C3

10

6

C2
9

(7,8)

5

C1
3

(5,7) 4

C3
5

1

5

7
4

2
C4
8

( 8, 5 )
(8,2)

2

C5
3

( 7 ,2 )
( 1,2 )



---

Title: DIGITAL ANALYSIS AND ALGORITHMS
Description: This pdf is very useful for the students of engineering who want to study daa for semesters.It contains only the required data so that students cannot get confusion.

Buy These NotesPreview