Mailam Engineering College
(Approved by AICTE, New Delhi, Affiliated to Anna University, Chennai & Accredited by
National Board of Accreditation (NBA, New Delhi
Mailam (Po), Villupuram (Dt). Pin: 604 304
DEPARTMET !" C!MP#TER APP$%CAT%!&
UnitII [2 & 16 Marks]
&u'(e)t %n)*arge +!D Prin)ipal
Prepared By
[Link] Devi AP / MCA
1
&u'(e)t ame: De,ign an- anal.,i, o/ algorit*m,
&u'(e)t Co-e: MC0122
3ear: 1021 4 1023
&eme,ter: %%
Prepare- 5.: Mr,. A. &u'at*ra De6i, MCA, M.P*il.,
Mailam Engineering College
(Approved by AICTE, New Delhi, Affiliated to Anna University, Chennai
& Accredited by National Board of Accreditation (NBA, New Delhi
Mailam (Po), Villupuram (Dt). Pin: 604 304
DEPARTMET !" C!MP#TER APP$%CAT%!&
DESIGN AND ANALYSIS OF ALGORITHMS MC9223
Part 4 A
2. 7*at i, -i6i-e an- )on8uer te)*ni8ue. 9DEC :20 ; <21=
The al!orith" wor#s by a f$nction to co"p$te on %n& inp$ts the divide'and'con($er
strate!y s$!!ests splittin! the inp$ts in to &#& distinct s$bsets, )<#<n, yieldin! %#& s$b'
proble"s* The s$b'proble"s "$st be solved, and then a "ethod "$st be fo$nd to co"bine
s$b'sol$tions into a sol$tion of the whole* If the s$b'proble"s are still relatively lar!e, then
the divide'and con($er strate!y can possibly be reapplied*
1. +o> -oe, -i6i-e an- )on8uer algorit*m >or?@ 9A# <21=
Three +teps of the Divide and Con($er Approach
Divide the proble" into two or "ore s"aller s$b'proble"s*
Con($er the s$b'proble"s by solvin! the" rec$rsively*
Co"bine the sol$tions to the s$b'proble"s into the sol$tions for the ori!inal
proble"*
3. De/ine )ontrol a',tra)tion.
A control abstraction we "ean a proced$re whose flow of control is clear b$t whose
pri"ary operations are by other proced$res whose precise "eanin!s are left $ndefined*
4. Bi6e t*e Control a',tra)tion /or Di6i-eCan- )on8uer.
Al!orith" DAnd(
,
if s"all(p then ret$rn +(-
else
,
divide . into s"aller instance / ), / 0, / #, # )-
Apply D and C to each of these s$bproble"s
1et$rn co"bine (DAnd C(/) DAnd C(/0,'''', DAnd ((/#-
2
2
Prepared By
[Link] Devi AP / MCA
2
#%T %% D%V%DE AD C!D#ER MET+!D AD BREED3 MET+!D
Divide and con($er "ethodolo!y 3 4er!e sort 3 5$ic# sort 3 Binary search 3 Binary
tree traversal 3 4$ltiplication of lar!e inte!ers 3 +trassen&s "atri6 "$ltiplication 3 7reedy
"ethod 3 .ri"&s al!orith" 3 8r$s#al&s al!orith" 3 Di9#stra&s al!orith"*
E. $i,t out t*e appli)ation, o/ -i6i-e an- )on8uer te)*ni8ue,@
The applications of divide and con($er techni($es are as follows,
4er!e sort
5$ic# sort
Tree traversals
Binary search
4atri6 "$ltiplication'+trassen&s al!orith"
6. 7rite t*e algorit*m o/ -i6i-e an- )on8uer te)*ni8ue,@
Calc$latin! a: ; a) ; < ; an')
A=7>1IT?4 1ec$rsive+$"(A@:**n')A
BBInp$tC An array A@:**n')A of orderable ele"ents
BB>$tp$tC the s$""ation of the array ele"ents
if n D )
ret$rn ( 1ec$rsive+$"(A@:** nB0 3 )A ; 1ec$rsive+$"(A@nB0 ** n3 )A
F. Dra> t*e ,tru)ture o/ -i6i-eCan-C)on8uer te)*ni8ue.
The divide'and'con($er techni($e is shown in the fi!$re, which depicts the case of
dividin! a proble" into two s"aller s$b'proble"s*
G. De/ine %nternal &orting.
It is $sed to sort s"all a"o$nt of data i*e* less than )::* Unsorted data&s are stored
in "ain "e"ory* +o first fetch the $nsorted data&s fro" "ain "e"ory and apply any one of
the internal sortin! techni($es* Einally store the sorted data&s in "ain "e"ory itself* B$bble
sort, +election sort, Insertion sort, ?eap sort, 5$ic# sort are the e6a"ples
0. De/ine EHternal &orting.
It is $sed to sort lar!e ($antity of data i*e* !reater than )::*Unsorted data&s are
stored in +econdary stora!e devices* Eetch $nsorted data&s fro" +econdary stora!e devices
into 4ain 4e"ory and apply any one of the E6ternal +ortin! techni($es* Then store the
sorted data&s in +econdary stora!e devices*
20. 7*i)* i, t*e /a,te,t ,ear)*ing te)*ni8ue@
Prepared By
[Link] Devi AP / MCA
3
If the list is in sorted order, Binary search is the fastest searchin! techni($e, b$t if
the list is not in sorted order, +e($ential search is the fastest searchin! techni($e*
22. 7*at are t*e /a)tor, to 'e )on,i-ere- >*ile )*oo,ing a ,orting te)*ni8ue@
The factors to be considered while choosin! a sortin! techni($e are
.ro!ra""in! ti"e
1$nnin! ti"e of the sortin! techni($e
N$"ber of co"parisons re($ired for sortin! the list
4ain or a$6iliary "e"ory space needed for the sortin! techni($e
21. 7*en i, ,orting met*o- ,ai- to 'e ,ta'le@
A sortin! "ethod is said to be stable when the n$"ber of co"parisons and n$"ber
of swaps does not depend on the order in which the ele"ents are present* The n$"ber of
co"parisons will be always co""on* There is no best case, worst case and avera!e case*
All are the sa"e* +$ch a sortin! "ethod is called stable sortin!*
23. 7*at i, meant m. merge ,ort@
4er!e sort is an e6a"ple of divide'and'con($er techni($e* It sorts a !iven array
A@:**n')A by dividin! it into two halves A@:*@nB0A 3 )A and A@@nB0A**n ')A, sortin! each of
the" rec$rsively, and then "er!in! the two s"aller stored arrays into a sin!le sorted one*
24. 7*at i, meant '. Dui)? ,ort@
5$ic# sort is a well'#nown sortin! al!orith" developed by C* A* 1* ?oare that, on
avera!e, "a#es F(n lo! n co"parisons to sort n ite"s* ?owever, in the worst case, it
"a#es F (n
0
co"parisons* Typically, ($ic# sort is si!nificantly faster in practice than other
F(n lo! n al!orith"s, beca$se its inner loop can be efficiently i"ple"ented on "ost
architect$res, and in "ost real'world data, it is possible to "a#e desi!n choices which
"ini"iGe the probability of re($irin! ($adratic ti"e*
2E. +o> to )*oi)e o/ pi6ot element@
In ($ic# sort the left"ost ele"ent of the partition wo$ld often be chosen as the pivot
ele"ent* Unfort$nately, this ca$ses worst'case behavior on already sorted arrays, which is a
rather co""on $se'case* The proble" was easily solved by choosin! a rando" inde6 for
the pivot, choosin! the "iddle inde6 of the partition or choosin! the "edian of the first,
"iddle and last ele"ent of the partition for the pivot*
+electin! a pivot ele"ent is also co"plicated by the e6istence of inte!er overflow* If
the bo$ndary indices of the s$b'array bein! sorted are s$fficiently lar!e, the naHve
e6pression for the "iddle inde6, (left + right)/2, will ca$se overflow and provide an invalid
pivot inde6* This can be overco"e by $sin!, for e6a"ple, left + (right-left)/2 to inde6 the
"iddle ele"ent, at the cost of "ore co"ple6 arith"etic* +i"ilar iss$es arise in so"e other
"ethods of selectin! the pivot ele"ent*
26. +o> 8ui)? ,ort >or?,@
The basic idea of 5$ic# sort is to repeatedly divide the array into s"aller pieces, and
to rec$rsively sort those partitions* 5$ic# sort divides the c$rrent partition by choosin! an
ele"ent ' the pivot ' findin! which of the other ele"ents is s"aller or lar!er, sortin! the"
into two different s$b'partitions* Eor e6a"ple, say we have the inp$t (I,J,0,K,),L,M* ?ereNs
what happens in the first partitionin! r$n of a standard 5$ic# sort al!orith" (one that
always chooses the "iddle ele"ent of the c$rrent partition as the pivotC
2F. 7rite t*e operation, o/ 8ui)? ,ort@
Prepared By
[Link] Devi AP / MCA
4
DivideC .artition array A@l**rA into 0 s$barrays, A@l**s')A and A@s;)**rA s$ch that each
ele"ent of the first array is OA@sA and each ele"ent of the second array is P A@sA*
I"plicationC A@sA will be in its final position in the sorted array*
Con($erC +ort the two s$barrays A@l**s')A and A@s;)**rA by rec$rsive calls to
($ic#sort
Co"bineC No wor# is needed, beca$se A@sA is already in its correct place after the
partition is done, and the two s$barrays have been sorted*
2G. 7*at are t*e t*ree ,ituation, ma. ari,e -epen-ing upon t*e ,)anning in-i)e,
*a6e )ro,,e- in 8ui)? ,ort@
If scannin! indices I and 9 have not corssed, iQ 9 we si"ply e6chan!e A@iA and A@9A
and res$"es the scan by incre"entin! I and decre"entin! 9 respectivelyC
i 9
If the scannin! indices have crossed over , iD 9 we have partitioned the array after
e6chan!in! the pivot with A@9AC
Einally if the scannin! indices stop while pointin! to the sa"e ele"ent, iR9, the val$e
they are pointin! to "$st be e($al to p* Th$s we have partitioned the array
20. 7rite t*e e//i)ien). o/ 8ui)? ,ort@
Efficiency of 5$ic# sort Based on whether the partitionin! is balanced*
Best case: split in the "iddle S F( n lo! n
o C(n R 0C(nB0 ; F(n BB0 s$bproble"s of siGe nB0 each
Worst caseC sorted arrayT S F( n2
o C(n R C(n') ; n;) BB0 s$bproble"s of siGe : and n') respectively
Average caseC rando" arrays S F( n lo! n
10. De/ine 'inar. ,ear)*.
Binary search is one of the f$nda"ental al!orith"s in co"p$ter science* Binary
search is $sed to ($ic#ly find a val$e in a sorted se($ence* Binary search "aintains a
conti!$o$s s$bse($ence of the startin! se($ence where the tar!et val$e is s$rely located*
12. 7*at i, meant '. ,ear)* ?e. 6alue@
The search #ey val$e is initially the entire se($ence* At each step, the al!orith"
co"pares the "edian val$e in the search #ey val$e to the tar!et val$e* Based on the
co"parison and beca$se the se($ence is sorted, it can then eli"inate half of the search #ey
val$e* By doin! this repeatedly, it will event$ally be left with a search #ey val$e consistin!
of a sin!le ele"ent, the tar!et val$e*
11. +o> t*e ,ear)* ?e. 6alue >or?,@
It wor#s by co"parin! a search #ey 8 with the array&s "iddle ele"ent A@"A* If they
"atch, the al!orith" stops, otherwise the sa"e operation is repeated rec$rsively for the
first half of the array if 8 Q A@"A and for the second half if 8 D A@"A*
13. De/ine 'inar. tree. Bi6e eHample. 9DEC <20=
Prepared By
[Link] Devi AP / MCA
5
p all are p p . . . p all are p
A binary tree is a finite set of ele"ents that is either e"pty or is partitioned into
three dis9oint s$bsets* The first s$bset contains a sin!le ele"ent called root of the tree* The
other two s$bsets are the"selves binary trees, called left and ri!ht s$b trees of the ori!inal
tree* A left or ri!ht s$b tree can be e"pty and each ele"ent off the binary tree is called as
the node*
EHample:
14. 7*at i, meant '. 5inar. Tree Tra6er,al,@
A binary tree T is defined as a finite set of nodes that is either e"pty or consists of a
root and two dis9oint binary trees T= and T1 called, respectively, the left and ri!ht s$b'tree
of the root* Example: The hei!ht of a tree is defined as the len!th of the lon!est path fro"
the root to a leaf*
1E. 7*at i, PreCor-er tra6er,alU
.re'order traversal "eans the root is visited before the left and ri!ht s$b'trees are
visited* To traverse a binary tree in .re'order, followin! operations are carried'o$t*
Visit the root,
Traverse the left s$b'tree, and
Traverse the ri!ht s$b'tree*
Therefore, the .reorder traversal of the above tree will o$tp$tC
7, 1, 0, 3, 2, 5, 4, 6, , !, 10
16. 7*at i, %nCor-er tra6er,al@ 9DEC :22 ; <21=
In'order traversal "eans the root is visited after visitin! its left s$b'tree b$t before
visitin!* The ri!ht s$b'tree to traverse a binary tree in In'order, followin! operations is
carried'o$t*
Traverse the left "ost s$b'tree startin! at the left e6ternal node,
Visit the root, and
Traverse the ri!ht s$b'tree startin! at the left e6ternal node*
Therefore, the In'order traversal of the above tree will o$tp$tC
0, 1, 2, 3, 4, 5, 6, 7, !, , 10
1F. 7*at i, Po,tCor-er tra6er,al@
.ost'order traversal "eans the root is visited after visitin! the left and ri!ht s$b'
trees* To traverse a binary tree in .ost'order, followin! operations are carried'o$t*
Traverse all the left e6ternal nodes startin! with the left "ost s$btree which is then
followed by b$bble'$p all the internal nodes,
Prepared By
[Link] Devi AP / MCA
6
Traverse the ri!ht s$b'tree startin! at the left e6ternal node which is then followed
by b$bble'$p all the internal nodes, and
Visit the root*
Therefore, the .ostorder traversal of the above tree will o$tp$tsC
0, 2, 4, 6, 5, 3, 1, !, 10, , 7
1G. 7rite t*e /ormula /or /in-ing *eig*t o/ 5inar. Tree Tra6er,al,@
"a6,?ei!ht(T=, ?ei!ht(T12 ; )
10. 7rite t*e algorit*m /or /in-ing *eig*t o/ 5inar. Tree Tra6er,al,@
Eind the ?ei!ht of a Binary Tree
A=7>1IT?4 ?ei!ht(T
BBCo"p$tes rec$rsively the hei!ht of a binary tree
BBInp$tC A binary tree T
BB>$tp$tC The hei!ht of T
if T R
ret$rn 3)
else
ret$rn "a6,?ei!ht(T=, ?ei!ht(T12 ; )
30. De/ine &tra,,en:, MatriH Multipli)ation.
The +trassen&s 4atri6 4$ltiplication al!orith" discovered by Vol#er +trassen, and
$s$ally called +trassen&s Al!orith", which allows $s to "$ltiply two n'by'n "atrices with a
n$"ber of "$ltiplications that is a s"all "$ltiple of n
(ln JB(ln 0
, when n is of the for" 0
#
* This
"eans we will be able to "$ltiply "atrices $sin! abo$t n
0*W
"$ltiplications instead of n
K
*
32. 7rite t*e /ormula /or )al)ulating &tra,,en:, MatriH Multipli)ation@
c:: c:) a:: a:) b:: b:)
R X
c): c)) a): a)) b): b))
");"L'"I;"J "K;"I
R
"0;"L ");"K'"0;"M
") R (a:: ; a)) X (b:: ; b22
"0 R (a): ; a)) X b::
"K R a:: X (b:) ' b22
"L R a)) X (b): ' b00
"I R (a:: ; a:) X b22
"M R (a): ' a:: X (b:: ; b02
"J R (a:) ' a)) X (b): ; b22
It has 7 multiplications and ! additions
31. De/ine eHternal pat* lengt*@
The e6ternal path len!th E, is defines analo!o$sly as s$" of the distance of all e6ternal
nodes fro" the root*
33. De/ine internal pat* lengt*.
Prepared By
[Link] Devi AP / MCA
7
The internal path len!th %I& is the s$" of the distances of all internal nodes fro" the root*
34. 7*at i, Bree-. te)*ni8ue@ 9A# <22=
A !reedy techni($e is an al!orith" that follows the proble" solvin! he$ristic of
"a#in! the locally opti"al choice at each sta!e
with the hope of findin! a !lobal opti"$"*
In "any proble"s, a !reedy strate!y does not in !eneral prod$ce an opti"al sol$tion, b$t
nonetheless a !reedy he$ristic "ay yield locally opti"al sol$tions that appro6i"ate a !lobal
opti"al sol$tion in a reasonable ti"e* Eor e6a"ple, a !reedy strate!y for the travelin!
sales"an proble"
3E. 7*at -o .ou mean '. /ea,i'le ,olution ; optimal ,olution@ 9DEC <20=
A sol$tion for which all of the constraints in the +olver "odel are satisfied is called a
feasi"le solution#
The +olver proceeds by first findin! a feasible sol$tion, and then see#in! to i"prove
$pon it, chan!in! the decision variables to "ove fro" one feasible sol$tion to another
feasible sol$tion $ntil the ob9ective f$nction has reached its "a6i"$" or "ini"$"* This is
called an optimal solution#
36. $i,t out t*e appli)ation, o/ Bree-. Algorit*m,@
>pti"al sol$tionsC
o chan!e "a#in!
o 4ini"$" +pannin! Tree (4+T
o +in!le'so$rce shortest paths
o ?$ff"an codes
Appro6i"ationsC
o Travelin! +ales"an .roble" (T+.
o 8napsac# proble"
3F. 7*at i, meant '. ,panning tree@ 9A# <21=
+pannin! tree of a connected !raph $C a connected acyclic s$b!raph (tree of $ that
incl$des all of $&s vertices*
3G. 7*at i, meant '. Minimum &panning Tree (M&T)@
4ini"$" +pannin! Tree of a wei!hted, connected !raph $C is a spannin! tree of the
s"allest wei!ht, where the wei!ht of a tree is defined as the s$" of the wei!hts on all its
ed!es*
30. De/ine Prim:, algorit*m.
The pri"&s al!orith" constr$cts a "ini"$" spannin! tree thro$!h a se($ence of
e6pandin! s$b'trees* The initial s$b'tree in s$ch a se($ence consists of a sin!le verte6
selected arbitrarily fro" the set V of the !raph&s vertices* >n each iteration, we e6pand the
c$rrent tree in the !reedy "anner by si"ply attachin! to it the nearest verte6 not in that
tree* The al!orith" stops after all the !raph&s vertices have been incl$ded in the tree bein!
constr$cted*
40. 7*at i, meant '. 6erteH@
A verte6 is a YpointY on a shape, a corner where several faces (and ed!es co"e
to!ether* Each verte6 consists of infor"ation abo$t the shortest ed!e connectin! the verte6
to a tree verte6* +$ch infor"ation can be provided by attachin! two labels to a verte6*
Prepared By
[Link] Devi AP / MCA
8
42. +o> t*e Verti)e, )an 'e ,plit into t>o ,et,@
"rin#eC contains only the vertices that are not in the tree b$t are ad9acent to atleast
one tree verte6* These are candidates fro" which the ne6t tree verte6 is selected*
UnseenC are all the other vertices of the !raph, beca$se they are yet to be affected
by the al!orith"*
41. 7rite t*e t>o operation o/ prim:, algorit*m@
4ove $X fro" the set V 3 VT to the set of tree vertices VT
Eor each re"ainin! verte6 $ in that is connected to $X by a shorter ed!e than the $&s
c$rrent distance label, $pdate its label by $X and the wei!ht of the ed!e between $X
and $ respectively*
43. 7*at i, meant '. Iru,?al:, Algorit*m@
8r$s#al&s al!orith" loo#s at a "ini"$" spannin! tree for a wei!hted connected
!raph 7R(V,E as an acyclic s$b!raph with ZVZ ' ) ed!es for which the s$" of the ed!e
wei!hts is the s"allest*
44. 7*at i, meant '. Di(?,tra:, Algorit*m@
Di9#stra&s al!orith" finds shortest paths to a !raph&s vertices in order of their
distance fro" a !iven so$rce* Eirst, it finds the shortest path fro" the so$rce to a verte6
nearest to it, then to a second nearest, and so on* The best #nown al!orith" for the sin!le
so$rce shortest paths proble" is called Di9#stra&s al!orith"*
4E. Bi6e t*e re)urren)e relation o/ -i6i-eCan-C)on8uer@
The rec$rrence relation is
T(n R !(n
T(n) ; T(n0 ; ''''; T(n# ; f(n
46. "or t*e /ollo>ing arra., /in- t*e a6erage num'er o/ ?e. )ompari,on ma-e '.
'inar. ,ear)* in a ,u))e,,/ul ,ear)* in t*e arra.. (A,,ume t*at ea)* ?e. i,
,ear)*e- /or >it* t*e ,ame pro'a'ilit.)
94, 10, 1E, 30, 40, 41, 60, F0, G0, 00, 0E, 0G, 200 =.
Ti"e co"ple6ity for binary search R >(lo! n
?ere n R )K
Avera!e no* of #ey co"parisions R >(lo! 0)K
R lo!): )K B lo!): 0
R )*))L B :*K:)
R K*J
4F. >*at i, t*e -i//erent 'et>een merge ,ort an- 8ui)? ,ort@ 9A# <22=
In 4er!e +ort, the splittin! is trivial and the 9oinin! is hard and in 5$ic# +ort, the
splittin! is hard and the 9oinin! is trivial*
4er!e +ort is not an Inplace Al!orith" and in 5$ic# +ort is an Inplace +ort
Al!orith"*
Prepared By
[Link] Devi AP / MCA
4er!e sort is >(n lo! n and ($ic# sort is >(n lo! n* The two "ain differences are
that ) ($ic# sort can have a de!radation in perfor"ance if the pivot point is chosen
poorly (>(n
0
, 0 ($ic# sort does not re($ire the e6tra stora!e that "er!e sort does*
4G. +o> to merge t>o ,orte- arra.,@ 9A# <22=
Ass$"e, that both arrays are sorted in ascendin! order and we want res$ltin! array to
"aintain the sa"e order* Al!orith" to "er!e two arrays A@:**"')A and B@:**n')A into an
array C@:**";n')A is as followin!C
Introd$ce read'indices i, ( to traverse arrays A and B, accordin!ly* Introd$ce write'
inde6 ? to store position of the first free cell in the res$ltin! array* By defa$lt i R ( R
? R :*
At each stepC if both indices are in ran!e (i Q " and ( Q n, choose "ini"$" of
(A@iA, B@(A and write it to C@?A* >therwise !o to step L*
Increase ? and inde6 of the array, al!orith" located "ini"al val$e at, by one*
1epeat step 0*
Copy the rest val$es fro" the array, which inde6 is still in ran!e, to the res$ltin!
array*
Part 4 5
2. EHplain t*e ,orting met*o- u,ing Merge ,ort >it* )ompleHit.. &ort t*e /ollo>ing
num'er u,ing Merge ,ort G, 3, 1, 0, F, 2, E, 4
Mer!e s"rt is a# e$a%p&e "' divide(a#d()"#*uer te)h#i*ue. +t s"rts a !ive# array
A,-..#(1. by dividi#! it i#t" t/" ha&ves A,-.,#/2. 0 1. a#d A,,#/2...# (1.1 s"rti#! ea)h "' the%
re)ursive&y1 a#d the# %er!i#! the t/" s%a&&er st"red arrays i#t" a si#!&e s"rted "#e.
Elements $% Mer#e s$rt:
Di6i-e: +plit A down the "iddle into two s$bse($ences, each of siGe ro$!hly n%0*
Con8uer: +ort each s$bse($ence (by callin! 4er!e +ort rec$rsively on each*
Com'ine: 4er!e the two sorted s$bse($ences into a sin!le sorted list*
The dividin! process ends when we have split the s$bse($ences down to a sin!le
ite"* A se($ence of len!th one is trivially sorted* The #ey operation where all the wor# is
done is in the co"bine sta!e, which "er!es to!ether two sorted lists into a sin!le sorted
list* It t$rns o$t that the "er!in! process is ($ite easy to i"ple"ent*
A$B!R%T+M 4er!esort(A@:**n')A
BB+orts array A@:**n')A by rec$rsive "er!esort
BBInp$tC An array A@:**n')A of orderable ele"ents
BB>$tp$tC Array A@:**n')A sorted in nondecreasin! order
if n D )
BBdivide
copy A@:** nB0 3 )A to B@:** nB0 3 )A
copy A@ nB0 ** n 3 )A to C@:** nB0 3 )A
BBcon($er
4er!esort(B@:** nB0 3 )
4er!esort(C@:** nB0 3 )
BBco"bine
4er!e(B, C, A
Prepared By
[Link] Devi AP / MCA
1-
2he merging "' t/" s"rted arrays )a# be d"#e as. 2/" p"i#ters array i#di)es are
i#itia&i3ed t" p"i#t t" the 4rst e&e%e#ts "' the arrays bei#! %er!ed. 2he# the e&e%e#ts
p"i#ted t" are )"%pared a#d the s%a&&er "' the% is added t" a #e/ array bei#! )"#stru)ted5
a'ter that1 the i#de$ "' that s%a&&er e&e%e#t is i#)re%e#ted t" p"i#t t" its i%%ediate
su))ess"r i# the array it /as )"pied 'r"%.
2his "perati"# is )"#ti#ued u#ti& "#e "' the t/" !ive# arrays is e$hausted. A#d the
re%ai#i#! e&e%e#ts "' the "ther array are )"pied t" the e#d "' the #e/ array.
A$B!R%T+M 4er!e(B@:**p')A, C@:**(')A, A@:**p;(')A
BB4er!es two sorted arrays into one sorted array
BBInp$tC Arrays B@:**p')A and C@:**(')A both sorted
BB>$tp$tC +orted Array A@:**p;(')A of the ele"ents of B and C
i :- 9 :- # :
while i Q p and 9 Q ( do BBwhile both B and C are not e6ha$sted
if B@iA QR C@9A BBp$t the s"aller ele"ent into A
A@#A B@iA- i i ; )
else A@#A C@9A- 9 9 ; )
# # ; )
if i R p BBif list B is e6ha$sted first
copy C@9**(')A to A@#**p;(')A
else BBlist C is e6ha$sted first
copy B@i**p')A to A@#**p;(')A
Example:
Prepared By
[Link] Devi AP / MCA
11
Efciency of merge sort:
C6#7 8 2C6#/27 9 C%er!e6#7 '"r #:11 C617 8-.
C%er!e 6#7 the #u%ber "' ;ey )"%paris"#s per'"r%ed duri#! the %er!i#! sta!e. At
ea)h step1 e$a)t&y "#e )"%paris"# )"%paris"# is %ade1 a'ter /hi)h the t"ta& #u%ber i'
e&e%e#ts i# the t/" arrays sti&& #eeded t" be pr")essed is redu)ed by "#e. +# the /"rst )ase1
#either "' the t/" arrays be)"%es e%pty be'"re the "ther "#e )"#tai#s <ust "#e e&e%e#t.
2here'"re the /"rst )ase1 C%er!e 6#7 8 #(1
C/"rst 6#7 8 2C/"rst 6#/27 9 #(1 '"r #:11 C/"rst6178-.
C/"rst 6#78#&"!2#(#91
If the ti"e for the "er!in! operations is proportional to %n&, then the co"p$tin! ti"e
for "er!e sort is described by the rec$rrence relation*
&(n) % ' a n%()a) a constant
2&(n/2)+cn n*()c) a constant#
[hen %n& is a power of 0, nR 0\#, we can solve this e($ation by s$ccessive s$bstit$tion*
T(n R0(0T(nBL ;cnB0 ;cn
R LT(nBL;0cn
R L(0T(nBW;cnBL;0cn
X
X
R 0\# T();#Cn*
R an ; cn lo! n*
It is easy to see that if s\#QnQR0\#;), then T(nQRT(0\#;)* Therefore,
T(n)J!(n log n)
1. De/ine -i6i-e an- )on8uer met*o-. EHplain t*e ,orting met*o- u,ing Dui)? ,ort
>it* )ompleHit.. &ort t*e /ollo>ing num'er u,ing 8ui)? ,ort.
10, 40, E0, 2E, 20, 0E, G0, 00. 9DEC :20, A# ; DEC <22=
&i'i(e an( )$n*+er met,$(:
The al!orith" wor#s by a f$nction to co"p$te on %n& inp$ts the divide'and'con($er
strate!y s$!!ests splittin! the inp$ts in to &#& distinct s$bsets, )<#<n, yieldin! %#& s$b'
proble"s* The s$b'proble"s "$st be solved, and then a "ethod "$st be fo$nd to co"bine
s$b'sol$tions into a sol$tion of the whole* If the s$b'proble"s are still relatively lar!e, then
the divide'and con($er strate!y can possibly be reapplied*
-+i)k s$rt:
5$ic# sort is a well'#nown sortin! al!orith" developed by C* A* 1* ?oare that, on
avera!e, "a#es F(n lo! n co"parisons to sort n ite"s* ?owever, in the worst case, it
Prepared By
[Link] Devi AP / MCA
12
"a#es F (n
0
co"parisons* Typically, ($ic# sort is si!nificantly faster in practice than other
F(n lo! n al!orith"s, beca$se its inner loop can be efficiently i"ple"ented on "ost
architect$res, and in "ost real'world data, it is possible to "a#e desi!n choices which
"ini"iGe the probability of re($irin! ($adratic ti"e*
.i'$t element:
In ($ic# sort the left"ost ele"ent of the partition wo$ld often be chosen as the pivot
ele"ent* Unfort$nately, this ca$ses worst'case behavior on already sorted arrays, which is a
rather co""on $se'case* The proble" was easily solved by choosin! a rando" inde6 for
the pivot, choosin! the "iddle inde6 of the partition or choosin! the "edian of the first,
"iddle and last ele"ent of the partition for the pivot*
+electin! a pivot ele"ent is also co"plicated by the e6istence of inte!er overflow* If
the bo$ndary indices of the s$b'array bein! sorted are s$fficiently lar!e, the naHve
e6pression for the "iddle inde6, (left + right)/2, will ca$se overflow and provide an invalid
pivot inde6* This can be overco"e by $sin!, for e6a"ple, left + (right-left)/2 to inde6 the
"iddle ele"ent, at the cost of "ore co"ple6 arith"etic* +i"ilar iss$es arise in so"e other
"ethods of selectin! the pivot ele"ent*
/,e &i'i(e, 0$n*+er an( 0$m1ine 2teps in -+i)k s$rt
DivideC .artition array A@l**rA into 0 s$barrays, A@l**s')A and A@s;)**rA s$ch that each
ele"ent of the first array is OA@sA and each ele"ent of the second array is P A@sA*
I"plicationC A@sA will be in its final position in the sorted array*
Con($erC +ort the two s$barrays A@l**s')A and A@s;)**rA by rec$rsive calls to
($ic#sort
Co"bineC No wor# is needed, beca$se A@sA is already in its correct place after the
partition is done, and the two s$barrays have been sorted*
3l#$rit,m:
A$B!R%T+M 5$ic#sort(A@l**rA
BB+orts a s$barray by ($ic#sort
BBInp$tC A s$barray A@l**rA of A@:**n')A,defined by its left and ri!ht indices l and r
BB>$tp$tC The s$barray A@l**rA sorted in nondecreasin! order
if l Q r
s .artition (A@l**rA BB s is a split position
5$ic#sort(A@l**s')A
5$ic#sort(A@s;)**rA
+elect a pivot w*r*t* whose val$e we are !oin! to divide the s$b'list* (e*!*, p R A@lA*
Use the si"ple strate!y of selectin! the s$b'array&s first ele"ent pRA@lA*
1earran!e the list so that it starts with the pivot followed by a O s$b'list and a P
s$b'list* 1earran!in! can be done by different proced$resC scan fro" left'to'ri!ht
and ri!ht'to'left*
Prepared By
[Link] Devi AP / MCA
p
A[i]p A[i] p
13
Three sit$ations "ay arise dependin! $pon the scannin! indices have crossedC
If scannin! indices I and 9 have not corssed, iQ 9 we si"ply e6chan!e A@iA and
A@9A and res$"es the scan by incre"entin! I and decre"entin! 9 respectivelyC
i 9
If the scannin! indices have crossed over , iD 9 we have partitioned the array
after e6chan!in! the pivot with A@9AC
Einally if the scannin! indices stop while pointin! to the sa"e ele"ent, iR9,
the val$e they are pointin! to "$st be e($al to p* Th$s we have partitioned
the arrayC
A$B!R%T+M .artition (A@l **rA
[Link] a s$barray by $sin! its first ele"ent as a pivot
BBInp$tC A s$barray A@l**rA of A@:**n')A, defined by its left and ri!ht indices l and r (l Q r
BB>$tp$tC A partition of A@l**rA, with the split position ret$rned as this f$nction&s val$e
. A@lA
i l- 9 r ; )-
1epeat
repeat i i ; ) $ntil A@iADRp BBleft'ri!ht scan
repeat 9 9 3 ) $ntil A@9A QR pBBri!ht'left scan
if (i Q 9 BBneed to contin$e with the scan
swap(A@iA, a@9A
$ntil i DR 9 BBno need to scan
swap(A@lA, A@9A
ret$rn 9
E%%i)ien)4 $% -+i)k s$rt:
Based on whether the partitionin! is balanced*
Best caseC split in the "iddle S F( n lo! n
C(n R 0C(nB0 ; F(n BB0 s$b'proble"s of siGe nB0 each
Worst caseC sorted arrayT S F( n2
C(n R C(n') ; n;) BB0 s$b'proble"s of siGe : and n') respectively
Average caseC rando" arrays S F( n lo! n
>r
E%%i)ien)4 $% -+i)k s$rt:
Cbest(nR0 Cbest (nB0;n for nD), Cbest ()R:fs
Cworst(nR(n;);n;<;KR(n;)(n;0B0 'K ]F (n
0
Prepared By
[Link] Devi AP / MCA
14
p all are p p . . . p all are p
n')
Cav!(nR)Bn ^@(n;) ; Cav! (s ;Cav! (n')'sA for nD)
+R:
Cav! (:, Cav! ()R:
Cav! (n _0n ln n_)*KW n lo!0n*
Prepared By
[Link] Devi AP / MCA
15
Prepared By
[Link] Devi AP / MCA
16
Prepared By
[Link] Devi AP / MCA
17
Prepared By
[Link] Devi AP / MCA
18
Prepared By
[Link] Devi AP / MCA
1
3. Di,)u,, 5inar. ,ear)* u,ing -i6i-e an- )on8uer met*o-olog.. 9A# <21=
The binary search al!orith" can only be applied if the data are sorted* `o$ can
e6ploit the #nowled!e that they are sorted to speed $p the search*
The idea is analo!o$s to the way people loo# $p an entry in a dictionary or telephone
boo#* `o$ donNt start at pa!e ) and read every entryT Instead, yo$ t$rn to a pa!e
so"ewhere abo$t where yo$ e6pect the ite" to be* If yo$ are l$c#y yo$ find the ite"
strai!ht away* If not, yo$ #now which part of the boo# will contain the ite" (if it is there,
and repeat the process with 9$st that part of the boo#*
If always split the data in half and chec# the "iddle ite", yo$ halve the n$"ber of
re"ainin! ite"s to chec# each ti"e* This is "$ch better than linear search, where each
$ns$ccessf$l co"parison eli"inates 9$st one ite"*
It wor#s by co"parin! a search #ey 8 with the array&s "iddle ele"ent A@"A* If they
"atch, the al!orith" stops, otherwise the sa"e operation is repeated rec$rsively for the
first half of the array if 8 Q A@"A and for the second half if 8 D A@"AC
3[0] 5 5 5 3[m61] 3[m] 3[m71] 5 5 5 3[n61]5
893[m] 8 8:3[m]
3l#$rit,m:
A$B!R%T+M Binary+earch(A@:**n')A, 8
BBI"ple"ents nonrec$rsive binary search
BBInp$tC An array A@:**n')A sorted in ascendin! order and
BB a search #ey 8
BB>$tp$tC An inde6 of the array&s ele"ent that is e($al to 8
BB or 3) if there is no s$ch ele"ent
l :, r n 3 )
while l r do BBl and r crosses over can&t find 8*
" (l ; r B 0
if 8 R A@"A ret$rn " BBthe #ey is fo$nd
else
if 8 Q A@"A r " 3 )BBthe #ey is on the left half of the array
else l " ; )BB the #ey is on the ri!ht half of the array
ret$rn ')
Initially low R), hi!hR n,nDR:, and a@)AQRa@0AQR<<**QRa@nA*
If nR:, the while loop is not entered and is ret$rned*
>therwise we observe that each ti"e thro& the loop the possible ele"ents to be
chec#ed of or e($ality with 6 and a@lowA, a@low;)A,<<**,a@"idA,<<a@hi!hA*
If 6Ra@"idA, then the al!orith" ter"inates s$ccessf$lly*
>therwise, the ran!e is narrowed by either increasin! low to ("id;) or decreasin!
hi!h to ("id')*
Clearly, this narrowin! of the ran!e does not affect the o$tco"e of the search*
If low beco"es D than hi!h, then %6& is not present & hence the loop is e6ited*
Prepared By
[Link] Devi AP / MCA
2-
Example:
&ee? t*e 6alue 213
E%%i)ien)4 $% 1inar4 sear),:
;$rst 0ase 3nal4sis:
The worst case analysis incl$des all array ele"ents that do not contain a search #ey val$e*
C>or,t
(n)
J C>or,t
(nK1)L2
CCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCC
C>or,t
(n)
J M(log1n)
3'era#e 0ase 3nal4sis:
It is sli!htly s"aller than the worst case analysis*
The avera!e n$"ber of co"parison is s$ccessf$l search
C
.e,
a6g (n) J log1
nC2
The avera!e n$"ber of co"parison in the $ns$ccessf$l search is
0
n$
a'# <n= > l$#2
n71
?est 0ase 3nal4sis:
The best case analysis !ot the search #ey val$e in the sin!le search*
?est <n= > @<1=
Prepared By
[Link] Devi AP / MCA
21
4. Di,)u,, a'out 5inar. Tree Tra6er,al, an- it, propertie,. 7*at are t*e tra6er,al,
in 'inar. tree@ 9DEC :22 ; <A# <21=
A binary tree T is defined as a finite set of nodes that is either e"pty or consists of a
root and two dis9oint binary trees T= and T1 called, respectively, the left and ri!ht s$b'tree
of the root*
Co"pared to linear data str$ct$res li#e lin#ed lists and one di"ensional arrays,
which have a canonical "ethod of traversal, tree str$ct$res can be traversed in "any
different ways* +tartin! at the root of a binary tree, there are three "ain steps that can be
perfor"ed and the order in which they are perfor"ed defines the traversal type* These
steps areC perfor"in! an action on the c$rrent node, traversin! to the left child node, and
traversin! to the ri!ht child node*
Traversin! a tree involves iteratin! over all nodes in so"e "anner* Beca$se fro" a
!iven node there is "ore than one possible ne6t node, then, ass$"in! se($ential
co"p$tation, so"e nodes "$st be deferred 3 stored in so"e way for later visitin!* This is
often done via a stac# or ($e$e* As a tree is a self'referential data str$ct$re, traversal can
nat$rally be described by rec$rsion or, "ore s$btly, co rec$rsion, in which case the deferred
nodes are stored i"plicitly 3 in the case of rec$rsion, in the call stac#*
The na"e !iven to a partic$lar style of traversal co"es fro" the order in which
nodes are visited* 4ost si"ply, does one !o down first or across first Depth'first traversal is
f$rther classified by position of the root ele"ent with re!ard to the left and ri!ht nodes*
I"a!ine that the left and ri!ht nodes are constant in space, then the root node co$ld be
placed to the left of the left node (pre'order, between the left and ri!ht node (in'order, or
to the ri!ht of the ri!ht node (post'order* There is no e($ivalent variation in breadth'first
traversal 3 !iven an orderin! of children, Ybreadth'firstY is $na"bi!$o$s*
EHample
The hei!ht of a tree is defined as the len!th of the lon!est path fro" the root to a leaf*
.roble"C find the hei!ht of a binary tree*
A=7>1IT?4 ?ei!ht(T
BBCo"p$tes rec$rsively the hei!ht of a binary tree
BBInp$tC A binary tree T
BB>$tp$tC The hei!ht of T
if T R
ret$rn 3)
else
ret$rn "a6,?ei!ht(T=, ?ei!ht(T12 ; )
EHample:
Prepared By
[Link] Devi AP / MCA
22
PreCor-erC
)* Visit the root*
0* Traverse the left s$btree*
K* Traverse the ri!ht s$btree*
3l#$rit,m:
p$blic static void pre>rder(BinaryTreeNode t
,
if (t TR n$ll
,
visit(t-
pre>rder(t*leftChild-
pre>rder(t*ri!htChild-
2
2
Example $% pre6$r(er +sin# a1$'e 1inar4 tree:
.re'order traversal se($enceC E, B, A, D, C, E, 7, I, ? (root, left, ri!ht
%nCor-er (,.mmetri)C
)* Traverse the left s$btree*
0* Visit the root*
K* Traverse the ri!ht s$btree*
3l#$rit,m:
p$blic static void in>rder(BinaryTreeNode t
,
if (t TR n$ll
,
in>rder(t*leftChild-
visit(t-
in>rder(t*ri!htChild-
}
}
Example $% In6$r(er +sin# a1$'e 1inar4 tree:
In'order traversal se($enceC A, B, C, D, E, E, 7, ? ,I (left, root, ri!ht
Po,tCor-erC
)* Traverse the left s$btree*
0* Traverse the ri!ht s$btree*
K* Visit the root*
3l#$rit,m:
p$blic static void post>rder(BinaryTreeNode t
,
if (t TR n$ll
,
post>rder(t*leftChild-
post>rder(t*ri!htChild-
visit(t-
2
2
Prepared By
[Link] Devi AP / MCA
23
Example $% .$st6$r(er +sin# a1$'e 1inar4 tree:
.ost'order traversal se($enceC A, C, E, D, B, ?, I, 7, E (left, ri!ht, root
E%%i)ien)4:
C(n R n ; 6 R0n ; )
E. EHplain t*e &tra,,en:, MatriH Multipli)ation. 9A#, DEC :22 ; <21=
In the "athe"atical discipline of linear al!ebra, the +trassen al!orith", na"ed after
Vol#er +trassen, is an al!orith" $sed for "atri6 "$ltiplication* It is faster than the standard
"atri6 "$ltiplication al!orith" and is $sef$l in practice for lar!e "atrices, b$t wo$ld be
slower than the fastest #nown al!orith" for e6tre"ely lar!e "atrices*
=et A and B be the 0 nXn 4atri6* The prod$ct "atri6 CRAB is calc$lated by $sin! the
for"$la,
C (i ,9 R A(i,# B(#,9 for all %i& and 9 between ) and n*
The ti"e co"ple6ity for the "atri6 4$ltiplication is >(n\K* Divide and con($er
"ethod s$!!est another way to co"p$te the prod$ct of nXn "atri6*
[e ass$"e that N is a power of 0 *In the case N is not a power of 0 ,then eno$!h
rows and col$"ns of Gero can be added to both A and B *+> that the res$ltin! di"ension
are the powers of two* If nR0 then the followin! for"$la as a co"p$ted $sin! a "atri6
"$ltiplication operation for the ele"ents of A & B*
If nD0,Then the ele"ents are partitioned into s$b "atri6 nB0XnB0**since %n& is a
power of 0 these prod$ct can be rec$rsively co"p$ted $sin! the sa"e for"$la *This
Al!orith" will contin$e applyin! itself to s"aller s$b "atri6 $ntil %Na beco"e s$itable
s"all(nR0 so that the prod$ct is co"p$ted directly *
The for"$la are
c:: c:) a:: a:) b:: b:)
R X
c): c)) a): a)) b): b))
") ; "L ' "I ; "J "K ; "I
R
"0 ; "L ") ; "K ' "0 ; "M
") R (a:: ; a)) X (b:: ; b))
"0 R (a): ; a)) X b::
"K R a:: X (b:) ' b))
"L R a)) X (b): ' b::
"I R (a:: ; a:) X b))
"M R (a): ' a:: X (b:: ; b:)
"J R (a:) ' a)) X (b): ; b))
Prepared By
[Link] Devi AP / MCA
24
C)) R 4) ;4L '4I ;4J
C)0 R 4K ;4I
C0) R 40 ;4L
C00 R 4) '40 ;4K ;4M
7 m+ltipli)ati$ns
1! a((iti$ns
E6a"pleC
T(nR b nQR0 a &b are
JT(nB0;an\0 nD0 constant
Einally we !et T(n R>( n \lo!0J
EHample
L L L L
X
L L L L
.R(LXL;(L;LRML
5R(L;LLRK0
1RL(L'LR:
+RL(L'LR:
TR(L;LLRK0
UR(L'L(L;LR:
VR(L'L(L;LR:
C))R(ML;:'K0;:RK0
C)0R:;K0RK0
C0)RK0;:RK0
C00RML;:'K0;:RK0
+o the answer c(i,9 is K0 K0
K0 K0
=et A and B be two n X n "atrices, where n is a power of two "atrices can be
padded with rows and col$"ns of Geros* [e can divide A, B and their prod$ct C into fo$r
nB0 by nB0 s$b'"atrices each as followsC
The seven prod$cts of nB0 by nB0 "atrices are co"p$ted* =et $s eval$ate the
asy"ptotic efficiency of this al!orith"* If 4(n is the n$"ber of "$ltiplications "ade by
+trassen&s al!orith" in "$ltiplyin! two n6n "atrices where n is a power of 0, we !et the
followin! rec$rrence relation for itC
M<n= > 7M<nA2= %$r n:1, M<1=>15
T(n)J ' nNJ1 a ;' are
FT(nK1)LanO1 nP1 )on,tant
Prepared By
[Link] Devi AP / MCA
25
6. Di,)u,, a'out Multipli)ation, o/ large integer,:
The standard inte!er "$ltiplication ro$tine of two n'di!it n$"bers involves n
"$ltiplications of an n'di!it n$"ber by a sin!le di!it, pl$s the addition of n n$"bers, which
have at "ost 0n di!its* All in all, ass$"in! that each addition and "$ltiplication between
sin!le di!its ta#es >(), this "$ltiplication ta#es >(n
0
ti"eC
5$antity ti"e
) "$ltiplication n'di!it by )'di!it n >(n
0 additions 0n'di!it by n'di!it "a6n >(n
Total ti"e R nX>(n ; nX>(n R 0nX>(n R >(nX>(n R >(n
0
*
Now, as we have done with several proble"s in the past, letNs consider a divide'con($er
sol$tionC
I"a!ine "$ltiplyin! an n'bit n$"ber by another n'bit n$"ber, where n is a perfect
power of 0* (This will "a#e the analysis easier* [e can split $p each of these n$"bers into
two halves*
=et the first n$"ber be I, and the second be b* =et the Yleft halfY of the first n$"ber
be Ih and the Yri!ht halfY of the first n$"ber be Il* (h is for hi!h bits, l is for low bits* Assi!n
bh and bl si"ilarly* [ith this notation, we can set the sta!e for solvin! the proble" in a
divide and con($er fashion*
I 6 b R @(Ih 6 0
nB0
; IlA 6 @(bh 6 0
nB0
; blA
R Ih 6 bh 6 0
n
; (Il 6 bh ; Ih 6 bl 6 0
nB0
; Il 6 bl
[ritten in this "anner we have bro#en down the proble" of the "$ltiplication of 0
n'bit n$"bers into L "$ltiplications of nB0' bit n$"bers pl$s K additions* (Note that
"$ltiplyin! any binary n$"ber by an arbitrary power of two is 9$st a shift operation of the
bits* Th$s, we can co"p$te the r$nnin! ti"e T(n as followsC
T(n R LT(nB0 ; c (n
This has the sol$tion of T(n R c(n
0
by the 4aster Theore"*
Now, the ($estion beco"es, can we opti"iGe this sol$tion in any way* In partic$lar, is there
any way to red$ce the n$"ber of "$ltiplications done* +o"e clever !$ess wor# will reveal
the followin!C
=et .) R (Ih ; Il 6 (bh ; bl R Ih6bh ; Ih6 bl ; Il6bh ; Il6bl
.0 R Ih 6 bh , and
.K R Il 6 bl
Then we have the followin!C
I 6 b R .0 6 0
n
; @.) ' .0 3 .KA6 0
nB0
; .K*
Now, consider the wor# necessary in co"p$tin! .), .0 and .K* Both .0 and .K are
nB0'bit "$ltiplications* B$t, .) is a bit "ore co"plicated to co"p$te* [e do two nB0 bit
additions, and then one nB0'bit "$ltiplication*
Prepared By
[Link] Devi AP / MCA
26
After that, we do two s$btractions, and another two additions, each of which still ta#es >(n
ti"e* Th$s, o$r r$nnin! ti"e T(n obeys the followin! rec$rrence relationC
T(n R KT(nB0 ; c(n*
The sol$tion to this rec$rrence is T(n R c(n\(lo!0K, which is appro6i"ately T(n R
c(n
)*IWI
, a solid i"prove"ent*
F. 7rite algorit*m, /or Prim:, Algorit*m an- appl. t*e grap* to o'tain minimum
,panning tree. 9A# :22 ; <21=
.ri"Ns al!orith" is an al!orith" that finds a "ini"$" spannin! tree for a connected
wei!hted $ndirected !raph* This "eans it finds a s$bset of the ed!es that for"s a tree that
incl$des every verte6, where the total wei!ht of all the ed!es in the tree is "ini"iGed*
.ri"Ns al!orith" is an e6a"ple of a !reedy al!orith"* The al!orith" was developed
in )dK: by CGech "athe"atician Vo9tech barnf# and later independently by co"p$ter
scientist 1obert C* .ri" in )dIJ and rediscovered by Eds!er Di9#stra in )dId* Therefore it is
also so"eti"es called the DAP algorit*m, the AarnQ? algorit*m, or the Prim4AarnQ?
algorit*m.
+pannin! tree of a connected !raph $C a connected acyclic s$b!raph (tree of $ that
incl$des all of $&s vertices* 4ini"$" +pannin! Tree of a wei!hted, connected !raph $C is a
spannin! tree of the s"allest wei!ht, where the wei!ht of a tree is defined as the s$" of
the wei!hts on all its ed!es*
Brap* an- it, ,panning tree,R T2 i, t*e minimum ,panning tree
The pri"&s al!orith" constr$cts a "ini"$" spannin! tree thro$!h a se($ence of
e6pandin! s$btrees* The initial s$btree in s$ch a se($ence consists of a sin!le verte6
selected arbitrarily fro" the set V of the !raph&s vertices*
>n each iteration, we e6pand the c$rrent tree in the !reedy "anner by si"ply
attachin! to it the nearest verte6 not in that tree* The al!orith" stops after all the !raph&s
vertices have been incl$ded in the tree bein! constr$cted*
Prepared By
[Link] Devi AP / MCA
27
3BCDEI/FM .rim<C=
BB .ri"&s al!orith" for constr$ctin! a "ini"$" spannin! tree
BBInp$tC A wei!hted connected !raph 7 R(V,E
BB>$tp$tCET, the set of ed!es co"posin! a "ini"$" spannin! tree of 7
VT ,v:2
ET
Eor i ) to V ') do
Eind a "ini"$" wei!ht ed!e eX R (vX,$X a"on! all the ed!es (v,$
+$ch that v is in VT an $ is in V' VT
VT VT U ,$X2
ET ET U ,eX2
1et$rn ET
The al!orith" contin$o$sly increases the siGe of a tree, one ed!e at a ti"e, startin!
with a tree consistin! of a sin!le verte6, $ntil it spans all vertices*
Each verte6 consists of infor"ation abo$t the shortest ed!e connectin! the verte6 to
a tree verte6* +$ch infor"ation can be provided by attachin! two labels to a verte6*
The na"e of the nearest verte6 and the len!th of the correspondin! ed!e* Vertices
not ad9acent to any of the tree vertices can be !iven the g label indicatin! their hinfinitea
distance to the tree vertices and a n$ll label for the na"e of the nearest tree verte6*
Gerti)es )an 1e split int$ tH$ sets:
Erin!eC contains only the vertices that are not in the tree b$t are ad9acent to atleast
one tree verte6* These are candidates fro" which the ne6t tree verte6 is selected*
UnseenC are all the other vertices of the !raph, beca$se they are yet to be affected
by the al!orith"*
[ith s$ch labels, findin! the ne6t verte6 to be added to the c$rrent tree TR( VT, E T
beco"es a si"ple tas# of findin! a verte6 with the s"allest distance label in the set V' VT
After +e have identified a verte, u- to "e added to the tree +e need to perform t+o
operation:
4ove $X fro" the set V 3 VT to the set of tree vertices VT
Eor each re"ainin! verte6 $ in that is connected to $X by a shorter ed!e than the $&s
c$rrent distance label, $pdate its label by $X and the wei!ht of the ed!e between $X
and $ respectively*
+tart with a tree , T: ,consistin! of one verte6
Prepared By
[Link] Devi AP / MCA
28
Constr$ct a series of e6pandin! s$btrees T), T0, < Tn')* *At each sta!e constr$ct
Ti;) fro" Ti by
addin! the "ini"$" wei!ht ed!e connectin! a verte6 in tree (Ti to one not yet in
tree
choose fro" hfrin!ea ed!es
(this is the h!reedya stepT
>r (another way to $nderstand it
e6pandin! each tree (Ti in a !reedy "anner by attachin! to it the nearest verte6
not in that tree* (a verte6 not in the tree connected to a verte6 in the tree by an
ed!e of the s"allest wei!ht
Al!orith" stops when all vertices are incl$ded
Need priority ($e$e for locatin! the nearest verte6
Use $nordered array to store the priority ($e$eC
E%%i)ien)4: @<n2=
$se min-heap to store the priority ($e$e
.fficienc/: Eor !raph with n vertices and m ed!esC
(n ; m lo!n
0e/ decreases/deletion from min-heap
n+m1er $% sta#es
<min6,eap (eleti$ns=
n+m1er $% e(#es )$nsi(ere(
<min6,eap ke4 (e)reases=
D<m l$# n=
Time )ompleHit.
A si"ple i"ple"entation $sin! an ad9acency "atri6 !raph representation and
searchin! an array of wei!hts to find the "ini"$" wei!ht ed!e to add re($ires >(1
0
r$nnin! ti"e*
Usin! a si"ple binary heap data str$ct$re and an ad9acency list representation,
.ri"Ns al!orith" can be shown to r$n in ti"e >(. lo! 1 where E is the n$"ber of ed!es
and V is the n$"ber of vertices* Usin! a "ore sophisticated Eibonacci heap, this can be
bro$!ht down to >(. ; 1 lo! 1, which is asy"ptotically faster when the !raph is dense
eno$!h that . is i(1*
Prepared By
[Link] Devi AP / MCA
2
Prepared By
[Link] Devi AP / MCA
3-
Prepared By
[Link] Devi AP / MCA
31
G. EHplain in -etail a'out Di(?,tra:, Algorit*m. 9DEC :22 ; <21=
Eor a !iven verte6 called the so$rce in a wei!hted connected !raph, find shortest
paths to all its other vertices* In this sin!le'so$rce shortest paths proble" as#s for a fa"ily
of paths, each leadin! fro" the so$rce to a different verte6 in the !raph, tho$!ht so"e
paths "ay have ed!es in co""on* The best #nown al!orith" for the sin!le so$rce shortest
paths proble" is called Di(?,tra:, algorit*m.
+hortest .ath .roble"sC
All pair shortest paths (Eloyd&s al!orith"
+in!le +o$rce +hortest .aths .roble" (Di9#stra&s al!orith"C 7iven a
wei!hted !raph 7, find the shortest paths fro" a so$rce verte6 s to each of
the other vertices*
Di9#stra&s al!orith" finds shortest paths to a !raph&s vertices in order of their
distance fro" a !iven so$rce* Eirst, it finds the shortest path fro" the so$rce to a verte6
nearest to it, then to a second nearest, and so on*
Before its ith iteration co""ences, the al!orith" already identified the shortest
paths to i') other vertices nearest to the so$rce* These vertices, the so$rce and the ed!es
of the shortest paths leadin! to then fro" the so$rce fro" a s$btree Ti of the !iven !raph*
+ince all the ed!e wei!hts are nonne!ative, the ne6t verte6 nearest to the so$rce can be
fo$nd a"on! the vertices ad9acent to the vertices of Ti*
The set of vertices ad9acent to the vertices in Ti can be referred to as hfrin!e
verticesa they are the candidates fro" which Di9#stra&s al!orith" selects the ne6t verte6
nearest to the so$rce*
To identify the ith nearest verte6, the al!orith" co"p$tes, for every frin!e verte6 $,
the s$" of the distance to the nearest tree verte6 v and the len!th dv of the shortest path
fro" the so$rce to v and then selects the verte6 with the s"allest s$ch s$"*
To facilitate the al!orith"&s operation, we label each verte6 with two labels* The
n$"eric label d indicates the len!th of the shortest path fro" the so$rce to this verte6
fo$nd by the al!orith" so far*
when a verte6 is added to the tree, d indicates the na"e of the ne6t'to'last verte6
on s$ch a path, i*e* the parent of the verte6 in the tree bein! constr$cted* [ith s$ch
labellin! findin! the ne6t nearest verte6 $X beco"es a si"ple tas# of findin! a frin!e verte6
with the s"allest d val$e*
After identifyin! the verte6 $X to be added to the three, we need to perfor" two operationsC
4ove $X fro" the frin!e to the set of tree vertices*
Eor each re"ainin! frin!e verte6 $ that is connected to $X by an ed!e of wei!ht
w($X,$ s$ch that
d$X; w($X, $ Q d$ $pdate the labels of $ by $X and d$X; w($X, $, respectively*
The basic "ode of operation isC
Prepared By
[Link] Devi AP / MCA
32
)* Initialise - and pi,
0* +et & to e"pty,
K* [hile there are still vertices in VC&,
i* +ort the vertices in VC& accordin! to the c$rrent best esti"ate of their
distance fro" the so$rce,
ii* Add u, the closest verte6 in VC&, to &,
iii* RelaH all the vertices still in VC& connected to u
RelaHation
The relaHation process $pdates the costs of all the vertices, 6, connected to a
verte6, u, if we co$ld i"prove the best esti"ate of the shortest path to 6 by incl$din! (u,6)
in the path to 6*
A$B!R%T+M Di9#stra(7, s
BBInp$tC A wei!hted connected !raph 7 R QV, EDand a so$rce verte6 s
BB>$tp$tC The len!th dvof a shortest path fro" s to v and its pen$lti"ate verte6 pv for
every verte6 vin V
InitialiGe (5 BBinitialiGe verte6 priority in the priority ($e$e
/or every verte6 v in V -o
dv g- .v nullKK .v, the parent of vg
insert(5, v, dv BBinitialiGe verte6 priority in the priority ($e$e
ds :- Decrease(5, s, ds BB$pdate priority of s with ds, "a#in! ds, the
"ini"$"
VT j
/or i R: to ZVZ ') -o BBprod$ce ZVZ ') ed!es for the tree
$X Delete4in(5 BBdelete the "ini"$" priority ele"ent
VT VT# ,$X2 BBe6pandin! the tree, choosin! the locally best verte6
"or every verte6 $ in V 3VT that is ad9acent to $X -o
i/ d$X; w($X, $ Q d$
d$ d$; w($X, $- p$ $X
Decrease(5, $, d$
The ti"e efficiency of Di9#stra&s al!orith" depends on the data str$ct$re $sed for
i"ple"entin! the priority ($e$e and for representin! an inp$t !raph itself*
Prepared By
[Link] Devi AP / MCA
33
Prepared By
[Link] Devi AP / MCA
34
Prepared By
[Link] Devi AP / MCA
35
0. 7rite algorit*m, /or Iru,?al:, Algorit*m an- appl. t*e grap* to o'tain
minimum ,panning tree. 9A# :22=
8r$s#alNs al!orith" is a !reedy al!orith" in !raph theory that finds a "ini"$"
spannin! tree for a connected wei!hted !raph* This "eans it finds a s$bset of the ed!es
that for"s a tree that incl$des every verte6, where the total wei!ht of all the ed!es in the
tree is "ini"iGed* If the !raph is not connected, then it finds a minimum spanning forest#
This al!orith" first appeared in 2roceedings of the American 3athematical 4ociet/,
pp* LW3I: in )dIM, and was written by boseph 8r$s#al* >ther al!orith"s for this proble"
incl$de .ri"Ns al!orith", 1everse'Delete al!orith", and Borkv#aNs al!orith"*
8r$s#al&s al!orith" loo#s at a "ini"$" spannin! tree for a wei!hted connected
!raph 7R(V,E as an acyclic s$b!raph with ZVZ ' ) ed!es for which the s$" of the ed!e
wei!hts is the s"allest*
Ed!es are initially sorted by increasin! wei!htBnon decreasin! order of their wei!hts
+tart with an e"pty forestBs$b!raph
h!rowa 4+T one ed!e at a ti"e ' inter"ediate sta!es $s$ally have forest of trees
(not connected
at each sta!e add "ini"$" wei!ht ed!e a"on! those not yet $sed that does not
create a cycle
o at each sta!e the ed!e "ayC
e6pand an e6istin! tree
co"bine two e6istin! trees into a sin!le tree
create a new tree
o need efficient way of detectin!Bavoidin! cycles
al!orith" stops when all vertices are incl$ded
A$B!R%T+M 8r$s#al(7
BBInp$tC A wei!hted connected !raph $ % 51( .*
BB>$tp$tC ET, the set of ed!es co"posin! a "ini"$" spannin! tree of 7*
4ort . in nondecreasing order of the edge +eights
+(ei) 5% 6 5% +(ei7.7)
.& 8 ecounter 9 BBinitialiGe the set of tree ed!es and its siGe
: 9
>*ile encounter 5 717 - -o
: : +
if .& # 'ei:; is ac/clic
.& .& # 'ei:; 8 ecounter ecounter +
return .&
/ime 0$mplexit4:
[here . is the n$"ber of ed!es in the !raph and 1 is the n$"ber of vertices,
8r$s#alNs al!orith" can be shown to r$n in <(. lo! . ti"e, or e($ivalently, <(. lo! 1 ti"e,
all with si"ple data str$ct$res* These r$nnin! ti"es are e($ivalent beca$seC
Prepared By
[Link] Devi AP / MCA
36
. is at "ost 1
0
and is <(lo! 1*
Each isolated verte6 is a separate co"ponent of the "ini"$" spannin! forest* If we
i!nore isolated vertices we obtain 1 O .;), so lo! 1 is <(lo! .*
Eirst sort the ed!es by wei!ht $sin! a co"parison sort in <(. lo! . ti"e- this allows
the step Yre"ove an ed!e with "ini"$" wei!ht fro" 4Y to operate in constant ti"e* Ne6t,
we $se a dis9oint'set data str$ct$re to #eep trac# of which vertices are in which
co"ponents* [e need to perfor" >(. operations, two NfindN operations and possibly one
$nion for each ed!e* Even a si"ple dis9oint'set data str$ct$re s$ch as dis9oint'set forests
with $nion by ran# can perfor" >(. operations in <(. lo! 1 ti"e* Th$s the total ti"e is
<(. lo! . R <(. lo! 1*
.rovided that the ed!es are either already sorted or can be sorted in linear ti"e, the
al!orith" can $se "ore sophisticated dis9oint'set data str$ct$re to r$n in <(. l(1 ti"e,
where l is the e6tre"ely slowly !rowin! inverse of the sin!le'val$ed Ac#er"ann f$nction*
Prepared By
[Link] Devi AP / MCA
37
Anna #ni6er,it. Due,tion,
Part C A
)* [hat is divide and con($er techni($e* @1ef* No*C :)A
0* ?ow does divide and con($er al!orith" wor#U @1ef* No*C :0A
K* Define binary tree* 7ive e6a"ple* @1ef* No*C 0KA
L* [hat is In'order traversalU @1ef* No*C 0MA
I* [hat is 7reedy techni($eU @1ef* No*C KLA
M* [hat do yo$ "ean by feasible sol$tion & opti"al sol$tionU @1ef* No*C KIA
J* [hat is "eant by spannin! treeU @1ef* No*C KJA
W* what is the different between "er!e sort and ($ic# sortU @1ef* No*C LJA
d* ?ow to "er!e two sorted arraysU @1ef* No*C LWA
Part C 5
0* Define divide and con($er "ethod* E6plain the sortin! "ethod $sin! 5$ic# sort with
co"ple6ity* +ort the followin! n$"ber $sin! ($ic# sort*0:, L:, I:, )I, ):, :I, W:, d:*
@1ef*
No*C :0A
K* Disc$ss Binary search $sin! divide and con($er "ethodolo!y* @1ef* No*C :KA
L* Disc$ss abo$t Binary Tree Traversals and its properties* [hat are the traversals in binary
treeU @1ef* No*C :LA
I* E6plain the +trassen&s 4atri6 4$ltiplication* @1ef* No*C :IA
J* [rite al!orith"s for .ri"&s Al!orith" and apply the !raph to obtain "ini"$" spannin!
tree* @1ef* No*C :JA
W* E6plain in detail abo$t Di9#stra&s Al!orith"* @1ef* No*C :WA
d* [rite al!orith"s for 8r$s#al&s Al!orith" and apply the !raph to obtain "ini"$" spannin!
tree* @1ef* No*C :dA
Prepared By
[Link] Devi AP / MCA
38