PO PULAR PU B LICA TIONS

GRAPH AND TREE TRAVERSAL

ALGO RITHl\1S

(E""C hapter at a Glanc e

• Tr«:
A cC'nne.:ted cn~h wi:..1, n . . . ~..:le is c3.llc-d a tree. Generally, a graph that does not contain any
cycles is c.3..;le-j z..~ 3.:: .:E.: ~.i;h. 5.:i. '" e can say that a connected acyclic graph is a tree.

• ~tinimam ro5t spannin g tree: A minimum cost spanning tree T of an edge weighted graph
G c.:-:-::i:.5 a.J t.~e "~..ices of G with total cost of the edges are minimum . It may not be

T'" c ::.e:..-- x.s :::r fui .:!.:ng the minimum cost spanning tree of a weighted graph G:
I. P;-:..;·s -~i ::-ri:..'-.m
., K..~t..Z1. s A:J .:-rith.-:n
• DFS (Dept11 Fim Searcb):
In a ~-=-=-j; G = (V. E) Depth First Search (DFS) algorithm starts from a specific vertex u E: V,
v.!,i ch ~ ;:.:.e'.ed as tr.e current vertex. Then we traverse graph by any edge (u, v) incident to
the C'.!r~ : , C!'"..e,: u.. If L'ie ed.:e (u. v) leads to an already visited vertex v, then we backtrack
to cu~ , e:--..ex 11. O J:er~i se if edge (u, v) leads to an unvisited vertex v, then we move to v
ar.d "' bee~ ow- ne-N current -.ertex. This process is continued until we get no vertex in this
pa:.'i. At !.'::s pci:-tt. v.c surt backtrack ing. The process terminate s when backtrack ing leads
back to L~e 5'..U-.i::g "~ex ~ ith no -.ertex remai ning unvisited.
• BFS (b read:. f1nt Search):
Bread~ First sea:-:.h <BFS ) is a general technique for traversing a graph. It may be a directed
graph or &.'1 ur.d.:-ca-ed gra;:h. Brcalh First Search (BFS) starts from a given vertex of a graph,
v.hich is at IC""t el 0. In L"lC f:~ stage, ~ e visit all vertices at level I. In the second
stage, we
visit all vcr!i~ ar 5,C:C/Y..d le-.el. i.e.• vi~it the um·isittd venices, which are adjacent to the
vertices at _l~et I. M",1 M> :-'"- Tr.e BFS traversal terminate s when every vertex of that graph
has been -.·1~tcd. BFS me'j-A can label each vertex by the length of a shortest path (in terms
o f number of ~g.es) frr.,m the ~urting \'erteX up to that vertex.
• !'lietwork flow Diacrarn :
A flow ~etwork ':' • (V. f..) i, a d;re<.1ed graph in which each edge (u, v) E E has a
nonnegau ._-e capac.,ty au..,)~ 0 . If <u. vJ f E, we a\\ume that c(u. v) . O. W e di stingui~h

IJAA-82
 DESIGN AND ANALYSIS OF ALGORITHMS

two vertices in a flow network: a sources and a sink t. For convenience, we assume that every
vertex lies on some path from the source to the sink.
That is, for every vertex v EV, there is a path s --+ v --+ t. The graph is therefore connected,
and IEI ~ jVI - 1. We are now ready to define flows more formally. Let G = (V, E) be a flow
network with a capacity function c. Let s be the source of the network., and let t be the sink. A
flow in G is a real-valued function f: V x V --+ R that satisfies the following three properties:
Capacity constraint: For all u, v E V, we '.equire/ (u, v) :'.S du, v).
Skew symmetry: For all u, vE V, we requtref(u, v) = -f (v, u).
Flow conservation: For all u E V - {s, t}

Multiple Choice Type Questions

is •............... if graph is represented as adjacency

1 Complexity of BFS algorithm
li~t . [WBUT 2006, 2015]
2
a) 0 (n+ e) b) 0 (n ) c) 0 (log n) d) 0 (n + e log n)
Answer: (a)
2. BFS on a graph G = {V, E) has running time - [WBUT 2010, 2016]
a) o(IVI+ !El) b) o(lvl) c) o(jEI) d) none of these

Answer: (a)
3. Which of the following ls useful in traversing a given graph using BFS?
(WBUT2011]
a) stack b) linked list c) array d) queue
Answer: (d)

4. The diagonal of the adjacency matrix of a graph with a self-loop contai ns only
. . (WBUT 2011]
a) 1 b) 0 . c) -1 d) •
Answer: (b)

5. level order traversal of a rooted tree can be done by starting from the root and
performing [WBUT 2013]
a) depth first search b) breadth first search
c) pre-order traversal d} in-order traversal
Answer: {b)

~- An undirected graph G with n vertices and e edges is represented by adjacency

•st What is the time required to generate all the connected components?
(WBUT 201•]
a} O(n) b} O(e) c} O(e+ n} d } O(e2)
Answer: (c)
7. An ad· . ·
Jacency matrix representation of a graph cannot contain Information of
}
: ~~dea b} edge• [WBUT 2014]
) rectlon of edgea d) parallel edges
A D!lwer: (d)

ll.-\A-83
,

'..JIii
 POPULAR PUBLICATIONS

s. The data structure required for Breadth First Traversal on a graph is

[WBUT 2014]
a) queue b) stack c) array d) tree
Answe r : (a)

9. BFS on a graph has running time ~BUT 2014]

2
a) 0(/YI + !El) b) O(jYI) c) O(IEI) d) O(IY 1)
Answer: (a)

1...-_S_h_o_rt_An l.
__s_w_e_r_Typ~-=--e....;Q~u_e_s_ti_o_n_s_.....

1. Compare and contrast: Depth-first-search and Breadth-first search.

[WBUT 2004, 2007, 2012, 2017]
Answer:
Compare:
• Both BFS and DFS traverse or visit all the vertices of a connected graph.
• Both BFS and DFS are applicable on spanning tree, paths and cycles of
connected graphs.

Contrast:
DFS BFS
I. DFS cannot find a shortest path between two I. BFS finds the shortest path between two
vertices. vertices of a graoh.
2. DFS visits all nodes on path first and 2. But BFS is terminated if it reaches end of a
Backtrack when path ends. path in a graph.
3. In case of DFS we use stack operation. 3. To implement BFS we use queue structure
4. DFS can represent back edge i.e. an edge 4 . . BFS can represent the cross edge, i.e.
from descendent to ancestor. Let back_edge( v, cross_edge (v, w) denotes that w is in the
w) denote that w is an ancestor of v in the tree of same level as v or in the next level in the tree
discovery edges where v and w are two vertices of discovery edges where v and w are two
of the graph. ' - vertices of the graph.

2. Describe Floyd's algorithm for all pair shortest path problem.- Find its time
complexity. [WBUT 2005, 2011]
OR,
Write down Floyd's algorithm to find all paired shortest paths of a graph.
. [WBUT 2017]
OR,
Write an algorithm for all pair shortest path also compute its complexity.
· . - [WBUT 2018, 2019]
Answer:
Given a directed graph G = (V, E), where each edge (v, w) has a nonnegative cost
C[v, w], for all pairs of vertices (v, w) find tf:ie cost of the lowest cost path from v tow.
Floyd's algorithm takes as input the cost matrix C[v, w] · , ..
• C[v, w] = oo if (v, w) is not in E

DAA-84
i...fi:P i

OF AL GO RI TH MS
DE SIG N AN D AN AL YS IS

It returris as ou tpu t m v to w
v, w] co nta ini ng the co st of the low est co st pa th fro
• a dis tan ce ma tri x D[
an d ini tia lly D[ v, w] = C[ v,
w] st co st
P[ v, w] ho lds the int erm ed iat e ve rte x k on the lea
• a pa th ma tri x P, wh ere v, w].
led to the co st sto red in D[
pa th be tw een v an d w tha t k as an ind ex . On the k-t h ite rat ion ,
the D
ma tri x D, us ing
W e ite rat e N tim es ov er the pa ths on ly .
on to the Al l pa ir sh ort est pa th pro ble m, wh ere the
ma tri x co nta ins the sol uti
us e ve rti ces nu mb ere d l to
k. rti ce s
are the co st of go ing fro m i to j us ing on ly ve
co mp ing the k+ 1th
On the ne xt ite rat ion , we k-t h ite rat ion ) wi th the co st of us
in D[ i,j] on the l,j ] (to
nu mb ere d l .. k (st ore d is D[ i,k +l ] (to ge t fro m i to k+ l) plu s D[ k+
p, wh ich
ve rte x as an int erm ed iat e ste ·
ge t from k+ l to j).
st pa th, we ma int ain it.
If thi s res ult s in a low er co be en ex am ine d, so D[ v, w] co nta ins
the co st of
ble pa ths ha ve
Af ter N ite rat ion s, all po ssi ce ssa ry.
low est co st pa th fro m v to w us ing all ve rti ce s if ne
the
Al go rit lzm
Flo yd AP SP (N, C, D, P)
{
for i - 0 to N do
{
for j - 0 to N do
{ .
D[i][j] - C[i][j]
P[i][j] - -1
}
-D[i][i] - 0.0 ·
}
for k - 0 to N do
{
for i - 0 to N do
{
for j - 0 to N do
{
if ((D[i](k] + D[k][j] )< D[
i][ j]) the n
{
D[i][j] +- D[i][k] + D[k][j]
·P[i][i] +- k
}
}
}
}
} .
e alg or ith m d
The comp lex ity of the ab ov
t d eie nd s up on tw o ne ste d for loo ps . Fi rst on e is
oth er n
executed at mo st n2 time. An e f ohr loo p ha s tru:ee in_ner for loo p an d the tot al
complex ;ty s
execution time is n3. So, the o t e ab ov e alg or ith m is O
(n3).

DAA-85
 _eg~8.EQg_LJ_C AT IONS

. . um cost spanning tree using any algorithm: [WBUT 2007]

3. Find out the m1n1m

Answer:
Applying Krusbrs Algorithm.

Step l Step 2

Step 3 Step 4

Step S Step6

In step 6 we get the minimum cost spanning tree by kruskal's method and the minim.urn
cost is 99.

DAA-86
'
J
II
 GO RIT HM S
DE SIG N AN D ANALYSIS OF AL

l's alg ori thm .

the diff ere nce bet we en Pri m's algorithm and Kru ska
4. Wr ite dow n [W BU T 2007, 201 7]

Answer: Kruskal's
Prim's
Co mp are
Compare . I. Fin d the min imu m cos t spa nni ng.
I. Fin d the min imu m cost spanning. nni ng
the min imu m cos t spa nni ng 2. Ge ner ate the min imu m cos t spa
2. Ge ner ate
tree from a gra ph.
tree from a graph.
Co ntr ast
Contrast I. Ge ner ate the min imu m cos t spa nni
ng
min imu m cos t spa nni ng
I. Ge ner ate the igh ted
from a roo t nod e. tree stru1ing fro m a lea st we
tree star ting
edg es mu st be adj ace nt unt rav ers e 1101, cyc le for min g edg e.
Sel ect ion of be
2.
ich is alre ady cre ate d. 2. Th e sel ect ion of edg es ma y
to the tree wh
dis cre te.
2, 201 3, 201 5]
the ma x-f low min -cu t the ore m wit h an exa mp le. [W BU T 201
5. Explain
OR ,
is. [W BU T 201 4]
te the Ma x-f low min -cu t the ore m for net wo rk flo w ana lys
Sta
Answer: wit h sou rce s and sin k t, the n the
fol low ing
Tf f is a flow in a flow net wo rk G = (V, E)
conditions are equivalent:
1./ is a ma xim um flow in G.
no aug me ntin g paths.
2. The residual net wo rk G /co nta ins
3. Ill = c(S, T) for som e cut (S, T)
of G.

t-1-1/1-4-M " 4
> O, edo e
I/ I= 19. On ly pos itiv e flo ws are sho wn . If f (u, v)
A flo ~ I in G wit h val ue sep ara te the flo :,
Ia_bel~d by f (u, v) /c(u , v). (Th e sla sh not atio n is use d me rel y to
(u, v) is
ica te div isio n.) Iff (u v) < o edo e (u, v) is lab ele d onl y b y 1·ts
and c~pac1ty; it does not ind . : ' - ' 0

capacity. 12 12

Fi ure wh -
A cut (S, T) in the flow net wo rk ofvert1 '. ere S - _{s, vl, v2} and T = {v3 , v4, t }.
The vertices in Sa re black, and the ite. Th e net flo w acr oss (S, T) is
f
(S, T ) = 19, and the cap aci ty is c(S , T ) ~~6 ~n T are wh

DA A- 87
 POPULAR PUBLICATIONS

6. Define T o pological sorting. Write down the difference between Topologicat

sorting and DFS. [MODEL QUESTION]
Answer:
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices
such that for every directed edge uv, vertex u comes before v in the orderi!']g. Topological
Sorting for a graph is not possible if the graph is not a DAG.
For examp le, a topological sorting of the foll owin g graph is "5 4 2 3 l 0". There can be
more than o~e topological sorting for a graph. For exa~ple, anot~er top~logi_c~l sorting
of the foll owmg graph is "4 5 2 3 I O". T he fi rst vertex tn topological sorting 1s always a
vertex with in-degree as O (a vertex with no incoming edges).

3
Topologica l Sorting vs Depth First Traversal (DFS):
ln D FS. we pri nt a vertex and then recursively call DFS for its adj acent vertices. In
topological sorting, we need to print a vertex before its adjacent vertices. For example, in
the given graph, the vertex '5' should be printed before vertex ' O', but unlike DFS, the
vertex '4' should also be printed be fore vertex ' O'. So Topological sorting is d ifferent
from DFS. For example, a DFS of the shown graph is ''5 2 3 I O 4", but it is not a
topological sorting

Long Answer Type Questions

1. Write any algorithm for performing BFS over a directed graph. Comment on the
time-complexity of your algorithm. [WBUT 2004, 2011]
Answer:
BFS tra,·ersal a/goritltm ofa grapl,
In the BFS algorithm, we maintain a queue. When one or more than one vertices are
discovered, "e can store them into the queue. i.e., adjacent vertices of an explored vertex
are stored into the queue. Then we remove one vertex (say i) from front position of the
queue and store the adjacent vertices of i at the end of-the queue.
BFS(G, s)
{
Step 1 initialize vertices;
Step 2 Q = {s};
II O is a queue; initi alize to s
Step 3 while (Q not empty) then
{
· Step 3 .1 u = RemoveTop ( Q) ;
Step 3.2 for each v e u-adj do
(

DAA-88
 DESIGN AND ANALYSIS OF ALGORITHMS

Step 3 . 2 . 1 if (v- color - - WHITE) • then

step 3.2 . 1 . 1 v-color = GREY;
Step 3.2.2 v-d = u-d + l;
Step 3 .2.3 v - p = u;
Step 3.2.4 Enqueue{Q, v) ;
}
step 3 . 3u->color = BLACK;
}
}
Enqueue(Q, v)
{
step 1 if Q is full then
step 1.~ return - 1;
s t ep 2 else
step 2 . 1 Add adjacency vertices of v to Q;
}
Complexity ofBFSO algorithm
• BFS calculates the shortest-path distance from the source node . . .
• Shortest-path distance 8(s,v) = minimum number of edges from s to v, or ifv ts
00

not reachable from s

• BFS builds breadth-first tree, in which paths to root represent shortest paths in G .
- Thus we can use BFS to calculate shortest path from one vertex to another m
0( IVI + IEI ) ti~e •
• The space complexity for BFS _is equal to O(n) i.e. the total space for keeping n
vertices in the memory

2. Write an algorithm for finding a minimum spanning tree of an undirected acyclic

graph. Estimate the time-complexity of your algorithm. [WBUT 2004, 2006, 2008]
OR,
Write an algorithm for finding the minimum spanning tree of a graph. Discuss its
time complexity. · .. [WBUT 2009, 2016)
OR,
Wri~e an algo~ithm to find a minimum spanning tree {MST) for an undirected graph.
Est1m~te the time co_mplexity of your algorithm. [WBUT 2014, 2019]
Answer:
We can writ~ either P~m's or Kruskal's algorithm for minimum cost spanning tree. Here
we define Pnm's algorithm: ·
~ m~~mu~ cost spanning tree T of an edge weighted. graph G contains all the vertices of
~It tota cost of the edges are minimum. It may not be unique.

Prim 's algo~itl,m for minimum cost spanning tree

Input: A we1~~te~, undirected graph G = (V, E, w).
Ou~ut: A mm1mum cost spanning tree T.
Prim (V, E, w)
{
Step linitialize t reeT={};

DAA-89
 PO PU LA R PU BL ICA TIO NS

x fro m V.
St ep 2 Le t r be a ro ot ve rte
St ep 3 re : V;
St ep 4 U = (r} ;
St ep 5 wh ile / u / < n do
.
(
St ep 5.1 Fi nd (u ) e: U an d Fi nd (v ) e: V- U
v) e: E
su ch th at th e ed ge (u, th e le as t co st ed ge be tw ee n
St ep 5.2 if ((u , v) i s
U an d (U -V )) th en .
(
(u , v)}
St ep 5. 2. 1 T = T U{
St ep 5 . 2. 2 U= U U( v}
}
)
)

edges.
Complexity
the G = (V ,E) has n nu mb er of nodes an d (n-1) nu mb er of
Th e spanning tre e of we have to put (n-1) nu mb er of
ed ge s in the set
ve alg ori thm in Ste p 5.2 . l
Now, in the abo n) tim e to keep
So it req uir es O( n) tim es. Sim ilarly in Ste p 5.2.2 requires O(
To ne by on e.
n nodes in the set U. tw o no des u an d v fro m set s U an d V- U and
ing to fin d ou t
Now, in Step 5.1 , we are try wh ile loo p is exe cut ed at mo st (n- 1) tim
es
tim e. In Ste p 5, the
each Find() requires O( l) on s wh ich are also ex ecu ted n tim es.
So the
p the re are ins tru cti
and within the while loo 2
cut ion tim e of wh ile loo p is O( n ).
exe
's Al go rith m is O(n2).
So the time co mp lex ity of Prim
es t pa th.
Dij ks tra 's alg ori thm for finding out the sh ort
3. a) Write do wn the [W BU T 2008, 2011]

Answer: noc:fes of a
fin ds the sho rte st pa ths fro m a sin gle sou rce to all oth er
Dijkstra's alg ori thm It sol ve s the sin gle -so urc e sho
rtest-paths
h wi th po sit ive we igh ts.
weighted dig rap ge weights
ted , dir ect ed gra ph G = (V, E) for the cas e in wh ich all ed
problem on a we igh E E. Di jks tra 's
, we ass um e tha t w( u, v) ~ 0 for eac h ed ge (u, v)
are nonnegative. So m th~ source
s a set S of ver tic es wh ose final sho rte st- pa th we igh ts fro
algorithm maintain _E V - S
ten nin ed . Th e alg ori thm rep eat ed ly sel ect s the ve rte x u
s h~ve already bee n de vin g u. In
rte st- pat h est im at~ ad ds u to S, an d rel ax es all ed ge s lea
.with the minimum sho d by their d
me nta tio n, we use a mi n-p rio rit y qu eu e Q of ve rti ces , ke ye
the following imple
values.
DIJKSTRA (G, w, s)
{
(G s)
INITIALIZE-SINGLE-SOURCE '
S+ -0
Q +- V [G]
wbileQ'l:0 do
DAA-90·
 DESIGN AND ANALYSIS OF ALGORm-IMS

{
u +- EXTRACT-MIN(Q)
S +-Su {u}
for each vertex v E Adj[u] do
{
RELAX (u, v, w)
}
}
}
RELAX(u, v, w)
{
if d[v] > d[u] + w(u, v) then
{
d[v] +- d[u] + w(u, v)
7t[V] +- U
} .

iN°ITIALIZE-SINGLE-~OURCE(G, s)
{ .
for each vertex v E V [G] do
{
d[v] +- oo
1t[v] +-NIL
}
d[s] +- 0
}

b) Prove that the time complexity of Dijkstra's algorithm is

·3(n-2)(n-1)!2 = o( n2 ) . (WBUT 2008, 2011]
I

Answer: · 2
With adjacency matrix representation, the running time is O(n ) By using an adjacency
list representation and a partially ordered tree data structure for organizing the set ·v - S,
the complexity can be shown to be 0(e log n) where e is the number of edges and n is the
number of vertices in the digraph.

4. Apply the KMP algorithm for the pattern p = "ab~baca" and string
s = "bacbabababacaab". Show every step. [WBUT 2013]
Answer: ·
Let us execute the KMP algorithm to find whether 'p'
occurs in 'S'.
Initially : !1 = size of S = 15;
m ;:; size of p=7

· DAA-91 ·
 POPULAR PVSUCATIO~S

Step 1: i = l . -:{ = 0
· ',.. :--
..... ~ n ( l ] \\ i•· ~ -l
- •-,· - ~t ~r l J
s~r;bac~3bababacaab
PJ::::m a r 3 t_, a Ca
;--: : J .::-cs fo."'l rnJ~.:h "· i:h S[ l]. · p· \I, ill t--e shi f:?J or.I! rosition to the right.

Stt:p 1: i = ~. 'i = 0
,,..,-;-:,_~:-; r [ I ] ,, i:.h S[ 2]
S:~:.~ ~ a c b ab ab ab a ca ab
P.:!::.;>m a b 3 b a c a

Step 3: i = 3 . 4 = I
c.:--;:-l."irg p [ 2 J "i:.h S[ 3] p [ 2 J does not match "ith S[ 3]
s~~gba c babababacaab
P1::~m ab ab a ca
B.::..:'.,.:-2.:~ir ~ 0n r. c0mr:iring p [ l ] and S[ 3 ]

Step -4: i = -t. 'i = 0

c.:--:-.;:-3.;:~ p [ 1] ,1.i:h S[ -t] p [I] dves not match ,,ith S[ 4]
s~~g~acbabababacaab
P.1::cr.1 1 b a b a c a

Step 5: i = 5 • q =0
c~:::;:-2..~r.g r [ l ] ,,ith S[ 5]
~~n~bacbabababacaab
P:?.-:t.er.i a b a b a c a

Step 6: i = 6 , q = 1
c~~p.:i:tg p [ 1 ] "iai S[ 6] p [ 2 J matches \\ith S[ 6 J
s ~~gbacb ab ababacaab
Pa:tem a b a b a c a

Sttp 7: i = 7 , q = 1
c..~;-~r.g p [ 3 ] \\iili S[ 7] p [ 3 ] marches ,,ith S[ 7)
S~ngbacbababab a caab
Pa~..e:n a b a b a c a

Step 8: i = 8 , q = 3
evrr.~.ari-~g p ( 4 ) \\ ith S[ 8 ] p [ 4 ] matches with S[ 8 ]
Stringbacbabababacaab
Par.em a b a b a c a

Step 9: i = 9 • q = 4
ccrn;,arir.g p ( S] ~ith S[ 9] p [ 5] matches with S[ 9]
DAA-92

II
 DESIG~ A.ND Ai.,ALYSIS OF ALGORITHMS

S~ngbacbabababacaab
Panern a b a b a c a

Step 10: i = IO . q = 5
comparing p [ 6] with S[ I O] p [ 6] does n ' t matches with S[ I O]
String b a c b a b a b a b a ca a b
Pattern ab a b a ca
Backtracking on p, comparing p [ 4 ] with S[ I O ] because after mismatch q = n[ 5 ] = 3
Step 11: i = 11 , q = 4
comparing p [ 5 ] with S[ 1 1 ]
&ri~bacbabababacaab
Pattern a b a b a c a

Step 12: i = 12 , q = 5
comparing p [ 6] with S[ I 2] p [ 6] matches with S[ I 2]
S~ngbacbabababacaab
Pattern a b a b a c a

Step 13: i = 13 , q = 6
comparing p [ 7 ] with S[ I 3 ] p [ 7 ] matches with S[ 1 3 ]
Stringbacbabababacaab
Pattern a b a b a c a
pattern ' p' has been found to completely occur in string ' S'. The total number of shifts
that took place for the match to be found are: i - m = 13-7 = 6 shifts~

5. a) Write the string matching algorithm due to Knuth, Morris and Pratt. Analyze
its time complexity. [WBUT 2014]
OR,
Write Knuth-Morirs-Pratt algorithm for string matching problem. [WBUT 2015]
Answer:
KMP-MATCHER(T, P)
I n = length(T ]
2 m =length[P]
3 1t = COMPUTE-PREFIX-FUNCTION(P)
4 q = 0 // Number of characters matched.
5 for i +- I to n // Scan the text from left to right.
6 do while q > 0 and P[tj + I] :I= T [i]
7 do q = 1t[q] // Next character does not match.
8 ifP[q+l]=T[i]
~O then q = q + 1 //Next character matches.
if q = m // Is all of P matched?
11
then print "Pattern occurs with shift" i - m
l2 q = 1t[q] //Look for the next match.
COMPUTE-PREFIX-FUNCTION(P)
DAA-93
POPU LAR PUBL ICATIONS

I m - /ength[P]
2 n(l ] - 0
3 k+- 0
4 for q +- 2 tom
5 do while k > 0 and P[k + I] -:I= P[q]
6 do k -n[k]
7 ifP[k + l] = P[q]
8 then k - k + I
9 1r[q] - k
IO retur n 1r

Rum ,iJig-time a11aly sis

dures. Proving these
We begin with an analysis of the runni ng times of these proce
procedures correct will be more complicated.
using the potential
The running time of COMPUTE-PREFIX-FUNCTION is 0 (m),
current state k of the
method of amortized analysis. We associate a potential of k with the
decreases k whenever
algorithm. This potential has an initial value of O; by line 3. Line 6
k can never become
it is executed, since n[k] < k. Since n[k] ~ 0 for all k, however,
ases k by at most one
negative. The only other line that affects k is line 8, which incre
ing the for loop, and
during each execution of the for loop body. Since k < q upon enter
always holds. We can
since q is incremented in each iteration of the for loop body, k < q
sponding decrease
pay for each execution of the while loop body on line 6 with the corre
tial function by at most
in the potential function, since 1t[k] < k. Line 8 increases the poten
Since the number of
one, so that the amortized cost of the loop body on lines 5-9 is 0(1).
is at least as great as
outer-loop iterations is 0 (m), and since the final potential funct ion
time of COMPUTE-
the initial potential function, the total actual worst-case running
the value of q as the
PREFIX-FUNCTION is 0 (m). A similar. amortized analysis, using
TCHER is 0 (n).
potential function, shows that the matching time of KMP-MA
r than 8, we have
Compared to FINITE-AUTOMATON-MATCHER, by using 1t rathe
reduced the time for preprocessing the pattern from O(m II I) to
0 (m), while keeping
the actual matching time bounded by 0 (n).
finding the maximum flow
b) Trace the execution of Ford-Fulkerson algorithm for
12 [WBU T 2014]
in the following graph.
V, t - - - - - . c V3

DAA-94
 DESIGN AND ANALYSIS OF ALGORITHM S

Answer:
(a)

ct 13 4/14
v. 4/

11/16
(b)
s 7/

13
v. 4/
11/1
A

(c)
11/16

8/13
v. 4/
11/14

(d) 11/16

12/13 v. 4/4
11/14

The execution of the basic Ford-Fulkerson algorithm: (a}-(d) Successive iterations of the
while loop. The left side of each part shows the residual network G1 from line 4 with a
shaded augmenting path p. The right side of each part shows the new flow f that result
from adding fp to f. The residual network in (a) is the input network G. (e) The residual
network at the last while loop test. It has no augmenting paths, and the flow f shown in
(d) is therefore a maximum flow.

6. Describe _the Depth first search algorithm for a given graph and explain its time
complexity. t------+( · [WBUT 2016]
U V W

DAA-95
P9PULAR__f_UOLl(;_ATIO NS

· \n.s" l't·:
\l \ \\ II \' w u V w

I
I I
I I
I I
I I

~ y z y X y
X z z
ta)
(b) (c)
u V \\' u
u V w V w

I I
I I
I I
I I

X y z X y z y
X z
(d) (e) (f)
u V
u V w u
\V V w

X y z X y z X y z
(g) (h) .
u u (i)
V w V w u V w

I
I
I
I

X y z X y z y
X z
(j) (k) (I)
u V w u V w u V w

C ,'
I I
I I
I I
I I

... \B
,
X y z X y z z y z
(m) (n)
u (o)
V w

DAA-96
X y
(p)
 DESIGN AND ANALYSIS OF ALGORITI-IMS

the above figure, the progress of the depth-first-s earch algorithm DFS is shown ste? by
1
~ p on the given graph. As edges are explored by the algorithm, they are shown as either
:headed (if they are tree edges) or dashed (otherwise). Non-tree edges ar:e labeled B, ~, ~r
F according to ~hether th_ey are. b~ck, _cross, or forward edges. Timestamps within
vertices indicate discovery ti_me/fimsh~ng times. . _
The following pseudoc°?e 1s the baste ~epth-first-s_earch algonthI:1. The mput graph G
may be undirected or directed. The vanable time 1s a global vanable that we use for
timestamping.
DFS(G) .
I for each vertex u E G. V
2 u.color = WHITE
3 u. ;r=NIL
4 time= 0
5 for each vertex u E G. V
6 if u.co/or = = WHITE
7 DFS-VISIT. G; u/
DFS-VISIT(G , u)
1 time = time + l
2 u.d=time
3 u.color= GRAY
4 for each ve G.Adj[u]
5 if v.color = = Wl IITE
6 V. ,r = U
7 DFS-VISIT (G, v)
8 u.color = BLACK
9 time =time + I
10 u./= time
The loops on lines 1- 3 and lines 5-7 of DFS take time 0(V) , exclusi,·e of the time to
execute the calls to DFS-VISIT. The procedure DFS-VISIT is called ex.1ctly once for
each vertex v e V, since the vertex u on which DFS-VISIT is invoked must ~ '-' hite an.:i
the ~rst thing DFS-VISIT does is paint vertex u gray.
~nng an execution of DFS-VISIT (G,v), the loop on lines 4-7 e'.\~.:ut~ l A~1\"]'time s.
Smee,
.LI
~, AdJ1v]I= 0(£)
The total cost of executing lines 4-7 of DFS-VISIT is<::)( E) . ~ runnin~ time of DFS is
therefore 0(V + £).
 POPULAR PUBLICATIONS

. ·ng Prim's algorithm for the graph giv

7. Find the minimum cost span~mg tre~ u,s1 d K kal's algorithm. en
below. Write down the complexity of Pnm 5 an rus [WBUT
1-----:----- -\ 5 2017]
4
3

6
2
Answer:
Minimum cost spanning tree (MST) of the graph .
There is no weight between node I and node 2. So, we assume that it is 3 and node l is
the starting node.
4
3
3

6
The cost is = 2+2+6+3+3 = 16

Complexity of Prim's and Kruskal's algorithm:

Time Complexity of the Prim's algorithm is O(V2) . If the input graph is represented using
adjacency list, then the time complexity of Prim's algorithm can be reduced to O(E log V)
with the help of binary heap. The performance of Prim's algorithm depends on how we
implement the min-priority queue Q.
Time Complexity of the Kruskal's algorithm is O(ElogE) or O(ElogV). Sorting of edge$
takes O(ELogE) time. After sorting, we iterate through all edges and apply find-union
algorithm. The find and union operations can take at most O(LogV) time. So overall
complexity is O(ELogE + ELogV) time. The value ofE can be at most O(V2), so O(LogV)
are O(LogE) same. Therefore, overall time complexity is O(ElogE) or O(ElogV).

8. Write short notes on the following:

a) Dijkstra's Algorithm . [WBUT 2013, 2018, 20191
b) Kruskal's algorithm for finding MST [WBUT 2014]
c) Minimum spanning tree [WBUT 2015]
d) BFS and DFS .[WBUT.2015, 2017, 2o19J
e) Ford - Fulkerson algorithm [WBUT 2017, 20 181
Answer:
a) Dijkstra's Algorithm:
Refer to Question No. 3(a) ofLong Answer Type Questions.

DAA-98
I DESIGN AND ANALYSIS OF ALGORITHMS

) I(ruskal's algorithm for finding MST:

~efer to Question No. 3 of Short Answer Type Questions.

c) Minimum spanning tree:

A spanning tree of a graph G =(v,E) is a connected subgraph with IVI
:- 1 edges
nning all of V. The cost (or weight) of a tree is the sum of the length of the edges in
:~a tree. A minimum spanning tree (MST) is a spanning tree with minimum cost. It is
: 11 known and easy to show that a spanning tree can be found in polynomial time. If W*
:notes the weight ( cost) of the minimup} spanning tree, then we must have
W* ~ L * since deleting any edge from the optimal tour results in a spanning tree.
The minimum spanning tree can be used to _find a feasible traveling salesman tour in
polynomial time. .
Two methods are there for finding the minimum cost spanning tree of a weighted graph
G:
I. Prim's Algorithm_
2. Kruskal's Algorithm

Kruskal's Algorithm: Examines edges in mondecreasing order of their lengths and

include them in MST if the added edge does not form cycle with the edges already
chosen.' The proof of the algorith~ uses tire path potimality conditions. Attractive
algorithm if the edges are already sorted in increasing order of their lengths. The
precedure ofKruskal's algorithm is shqwn in figure below. ·
-----r2

{a)agrapq = (V, E)and weightwij, 'li(i,J) e V

Procedure·. Krusk a l' s Al gont Fig: A small-scale example of MST

. hm
Input: graph G =(V,E) , weight wg, 'v(i,j) e V
Output: spanning tree T
Begin
T ~rp; .

A~ E; //A: eligible edges

While ITI < IVl-1 do
I Chooseanedge( u,v) ~argmin {wgl(i,j)eA}:

I DAA-99
 POPULAR PUBLICATIONS

Af--A\{(u,v)};
output spanning tree T;
end

d) BFS and DFS:

Breadth first search algorithm:
I. Select an unvisited node v, visit it, have it as a root in a BFS. Its level . .
current level. IS called the
2. F~~m eac~ _node x in th~ ~urrent_ level, in the order in which the level
v1s1ted. V1s1t all the unv1S1ted neighbours of x. The newly -yisited noctes°ode Were
level fonn a new level. This new level becomes the next current level from this
3. Repeat step 2 for all the unvisited vertices. ·
4. Repeat fom1 step I until no more vertices are remaining.
S1cp I:
We will start search
from node A. Insert
A in the queue
Q

I
Step 2:
Adjacent nodes to A will be
obtained and will be inserted
in the Q. Delete A from Q
!
and print iL

Q
\
IBICID

Step 3:

1 1 1

Step 4:

·DAA-100
 DESIGN AND ANALYSIS OF ALGORITHM S

Step S:
Q

IDIEIFIG
IEIFIGIH

1e

Step 6 :
·e
As there is no unvisited node
IS
remaining we will delete the
vertices from queue and print

Hence we get a sequence as A, B, C, ?, E, F, G, H.

Deptlt first search traversal
I I. Select an unvisited node v, visit it and treat it as current node.
I 2. Find an unvisited neighbor of the current node, visit it and make it as new current
node.
3. If current node has no unvisited neighbours back track to its parent and make it a new
\ current node.
4. Repeat the step 2 and 3 until no more nodes can be visited.
5. Repeat from step I for the remaining nodes.
For exam pie: Step 1:

We will start search

from node A. We
will start searching
in depth - first
manner.

Step 2:

Edge A-B

I DAA-101

~ ·
POPULAR PUBLICATIONS

S1cp 3

A-8-C

s1~p 4

A-8-C-F

S1cp 5:

A-8-C-F-E
Now, there is no
reachable node, further
hence we will pop the
nodes and search for a

---H node from which we can

proceed.

Step 6.

A-8-C-F-E-A-D

Step 7:

A-8-C-F-E
A-D-G-H

Hence we obtain DFS sequence as A, B, C, F, E, D, G, H.

DAA-102
 DESIGN AND ANALYSIS OF ALGORITHMS

) Ford-Fulkerson algorithm:
~ach iteration of the Ford-Fulkerson method, we _find some augmenting path p ~nd
•ncrease the flow f on each edge of p by the residual capacity cj(p). The followmg
!mplementation of the method computes the maximum flow in a graph G=(V,E) by
~pdating the flow J[u, v] between each pair (u,v) of vertices that are connected by an
edge. If u and v are not connected by an edge in either direction, we assume implicitly
thatf[u,v]=O. The capacities c(u,v) are assumed to be given along with the graph, and
c(u,v)=O if (u,v) ~ E .The residual capacity cju,v) is computed in accordance with the
fonnula .
cju, v)= c{u, v) -f(u,v/ .· . .
The expression cj(p) m the code 1s actually Just a temporary variable that stores the
residual capacity of the path p.
FORD-FULKERSON(G,s, t)
I for each edge (u, v) E E[G]
2 dof[u, v] - 0
3 f[v, u] - 0
4 while there exists a path p from s to t in the residual network Gf
5 do cj(p) - min {c/u, v): (u, v) is inp}
6 for each edge (u, v) inp
7 dof[u, v] - f[u, v] + cj(p)
8 /(v, u] - -f[u, v]
The FORD-FULKERSON algorithm simply expands on the FORD-FULKERSON
METHOD pseudocode given earlier. Lines 1-3· initialize the flow /to 0. The while loop
of lines 4-8 repeatedly finds an augmenting path p in G1 and augments flow f along p by
the residual capacity cj(p). When no augmenting paths exist, the flow f is a maximum
flow.

9. Given a flow network G = (V, E), let f1 and f2 be functions from V x V to R. The
flow sum f1 + f2 is the function from V x V to R defined by (f1 + f 2)(u, v) = f1(u, v) +
f2(u, v) for all u, v e V. If f1 and f 2 are flows in G, which of the three flow properties
must the flow sum f1 + f 2 satisfy, and which might it violate? [MODEL QUESTION]
Answer: · ·
The flow sum (f1 + f2)satisfies skew symmetry and flow conservation, but might violate
the capacity constraint.
-VV:e ~ve proofs for skew symmetry and flow conservation and an example that shows a
violation of the cap~city constraint.
Let f (u, v) = (f1 + f2)(u, v).
For skew symmetry:
f (u, v) = f1(U, v) + fi(u, v)
= - f1(v, u) - f2(v, u) (skew symmetry)
= - (f1(v, u) + f2(v, u))
, =- f(v, u).

DAA-103
 POPULAR PUBLICATIONS

For flow conservation, let u e V -{s, t}:

Lf(u,v)= L(fr(u,v)+ fi(u,v))
veV veV

= Lfr(u,v)+Lfi(u,v)
11eV ve/1

= 0+0 {flow conservation)

=0
For the capacity constraint, let V = {s, t}, E = {(s, t)}, and c(s, t) = 1.
Let f,(s, t)=fi(s, t)= l. Then f 1 and f2 obey tqe capacity constraint, but (f1 + f2)(u, v)=2,
which violates the capacity constraint. ·

10. Let f be a flow in a network, and let a be a real number. The scalar flow product,
denoted af, is a function from V >< V to R defined by (a f)(u, v) = a · f {u, v).
Prove that the flows in a network form a convex set. That is, show that if f1 and f2
are flows, then so is a f 1 + (1 - a) f 2 for all a in the range 0 :Sa :S 1.
[MODEL QUESTION]
Answer:
To see that the flows form a convex set, we show that if f 1 and f2 are flows, then so is a f 1
+ ( I - a) f2 for all a such that O ~a~ 1. ·
For the capacity constraint, first observe that a~ I implies that I - a~ 0. Thus, for any u,
VE V,
We have, a f 1(u, v) + (I - a) fi(u, v) ~ 0 . f 1(u, v) + 0. (1 - a) f2(u, v) = o·:
Since f 1(u, v) ~ c(u, v) and f2(u, v) ~ c(u, v), we also have
a f 1(u, v) + (I - a) f2(u, v) ~ ac(u, v) + .(I - a)c(u, v)
=(a+ (I - a))c(u, v) = c(u, v).
For skew symmetry, we have f 1(u, v) = - f 1(v, u)
and fi(u, v) = -f2(v, u) for any u, v E V. ·
Thus, we have
·a f 1(u, v) + (I - a) fi(u, v) = -af1(v, u)-(1 - a) f2(v, u) = -(a f1(v, u) + (1 - a) f2(v, u)).

13. Write the Rabin-Karp algorithm and analysis the complexity. .

[MODEL QUE~TION]
Answer:
Algorithm: . .
The following procedure makes these ideas precise. The inputs to the procedure are the
text T, the pattern P, the radix d to use (which is typically taken to be Ii:: I), and the prime
q to use.

RABIN-KARP-MATCHER (T, P, d, q)
I n - length[T]
2 m - tength[P]
3 h-r modq
1

4 p-o
5 lo-0
DAA-104
 DESIGN AND ANALYSIS OF ALGORITHMS

for; - l to m II Preprocessing.
6 do p +- (dp + P[i]) mod q
7 . tO +- (dtO + T [i]) mod q
! for s +- 0 to n - m
do if p = ts
//Matching.

10 then if_P [l . ..m] = T[s+ l .. s+m]

11 then print "Pattern occurs with shift" s
12 ifs< n- m
13 then ts+l +- (d(ts-T[s + l]h) + T[s + m + 11) mod q
14 b"n and Karp have proposed a string-matching algorithm that performs well iri practice
1
Rad that also generalizes to other algorithms for related problems, such as two-
:~ ensional pattern matching. The Rabin-Karp algorithm uses 0 (m) preprocessing time,
a~: its worst-case running time is 0 ((n-m+ I )m).

DAA-105