Daa (Design & Analysis of Algorithms)
Daa (Design & Analysis of Algorithms)
CHAPTER1BASICCONCEPTS
Algorithm
Performance of
ProgramsAlgorithm Design
GoalsClassificationofAlgorith
msComplexity of
AlgorithmsRateofGrowth
Analyzing
AlgorithmsThe Rule
of
SumsTheRuleofprod
ucts
TheRunningtimeofProgramsMeasuring
the running time of programsAsymptotic
Analyzing of
AlgorithmsCalculatingtherunningtimeofpro
grams
Generalrulesfor theanalysisofprograms
CHAPTER2Advanced DataStructuresandRecurrenceRelations
PriorityQueue,HeapandHeapsortHe
apSort
2.3
PriorityQueueimplementationusingheaptreeBinar
ySearchtrees
Balanced
TreesDictionar
y
DisjointSetOperations
Recurrence Relations – Iterative Substitution
MethodRecursionTree
TheGuess-andtest
TheMasterTheoremMethodC
old Form
expressionSolvingRecurrenc
erelations
CHAPTER3DivideAndConquer
GeneralMethod
ControlAbstractionofDivide and
ConquerBinarySearch
External and Internal path
lengthMergeSort
Strassen‟sMatrixMultiplicationQuickS
ort
StraightInsertionSort
CHAPTER4GreedyMethod
4.1 General
MethodControl
AbstractionKnapsack
I
ProblemOptimalStorageo
nTapes
JobSequencingwithdeadlinesOp
timal Merge
PatternsHuffmanCodes
II
GraphAlgorithms
CHAPTER5Dynamicprogramming
MultiStoragegraphsAllP
airsShortestpaths
TravelingSalesPersonproblemO
ptimalBinarySearchTree0/1Kna
psack
Reliabilitydesign
CHAPTER6BasicTraversalandSearchTechniques
Techniquesfortraversal
ofBinarytreeTechniquesforgraphs
RepresentationofGraphandDigraphsDepthFir
standBreadthFirstSpanningtrees
ArticulationPointsandbi-
connectedcomponentsArticulationpointsbyDepthFir
stSearch
Game
planningAlpha-
Beta
pruningAND/ORGr
aphs
CHAPTER7Backtracking
General
methodTermino
logy
N-Queens
problemSumofSub
sets
GraphColoring(forplanargraphs)Ha
miltonianCycles
0/1Knapsack
TravelingSalesPersonusingBacktracking
CHAPTER8BranchandBound
Generalmethod
LeastCost(LC)Search
ControlAbstractionforLC-
SearchBounding
The15-Puzzleproblem
LCSearchfor15-PuzzleProblemJob
Sequencing with
deadlinesTraveling Sales Person
problem0/1Knapsack
II
I
Chapter
1
BasicConcepts
Algorithm
supplied;Output:atleastonequantityisproduced;
Definiteness:eachinstructionmustbeclearandunambiguous;
Effectiveness:everyinstructionmustbesufficientlybasicthatitcaninprinciple be
carried out by a person using only pencil and paper. It is
notenoughthateachoperationbedefinite,butitmustalsobefeasible.
Werepresentalgorithmusingapseudolanguagethatisacombinationoftheconstructsofaprog
ramminglanguagetogetherwithinformalEnglishstatements.
Performanceofaprogram:
TimeComplexity:
The limiting behavior of the complexity as size increases is called the asymptotic
timecomplexity.Itistheasymptoticcomplexityofanalgorithm,whichultimatelydeterminest
hesizeofproblemsthatcanbesolvedbythealgorithm.
1
SpaceComplexity:
Data space: Data space is the space needed to store all constant and
variablevalues.Dataspacehastwocomponents:
Spaceneededbyconstantsandsimplevariablesinprogram.
Space needed by dynamically allocated objects such as arrays and
classinstances.
Thecompilerusedtocompletetheprogramintomachinecode.
Thecompileroptionsineffectatthetimeof compilation
Thetargetcomputer.
AlgorithmDesignGoals
1. TrytosaveTime
2. Tryto saveSpace
3. TrytosaveFace
ClassificationofAlgorithms
If„n‟isthenumberofdataitemstobeprocessedordegreeofpolynomialorthesizeofthefiletob
esortedorsearchedorthenumberofnodesinagraphetc.
2
n When the running time of a program is linear, it is generally the case
thata small amount of processing is done on each input element. This is
theoptimalsituationfor analgorithmthat mustprocessninputs.
ComplexityofAlgorithms
The complexity of an algorithm M is the function f(n) which gives the running
timeand/or storage space requirement of the algorithm in terms of the size „n‟ of
theinput data. Mostly, the storage space required by an algorithm is simply a multiple
ofthedatasize„n‟.Complexityshallrefertotherunningtimeofthealgorithm.
The function f(n), gives the running time of an algorithm, depends not only on
thesize „n‟ of the input data but also on the particular data. The complexity function
f(n)for certain casesare:
2. AverageCase :Theexpectedvalueoff(n).
3
RateofGrowth:
1. Big–OH(O)1,
2. Big–OMEGA(),
3. Big–THETA()and
4. Little–OH(o)
Big–OHO(UpperBound)
f(n) = O(g(n)), (pronounced order of or big oh), says that the growth rate of f(n)
islessthanorequal(<) that ofg(n).
Big–OMEGA(LowerBound)
f(n)=(g(n))(pronouncedomega),saysthatthegrowthrateoff(n)isgreaterthan or
equalto(>) that ofg(n).
1
In 1892, P. Bachmann invented a notation for characterizing the asymptotic behavior
offunctions.His inventionhascometo beknownasbigohnotation.
4
Big–THETA(Sameorder)
f(n) = (g(n)) (pronounced theta), says that the growth rate of f(n) equals (=)
thegrowthrate of g(n) [iff(n) =O(g(n)) and T(n)=(g(n)].
Little–OH(o)
T(n) = o(p(n)) (pronounced little oh), says that the growth rate of T(n) is less
thanthegrowth rateofp(n) [ifT(n)=O(p(n)) andT(n)(p(n))].
AnalyzingAlgorithms
Suppose„M‟isanalgorithm,andsuppose„n‟isthesizeoftheinputdata.Clearlythecomplexit
y f(n) of M increases as n increases. It is usually the rate of increase of f(n)we want
to examine. This is usually done by comparing f(n) with some
standardfunctions.Themostcommon computingtimesare:
NumericalComparisonofDifferentAlgorithms
Theexecutiontimeforsixofthetypicalfunctionsisgivenbelow:
n log2n n*log2n n2 n3 2n
1 0 0 1 1 2
2 1 2 4 8 4
4 2 8 16 64 16
8 3 24 64 512 256
16 4 64 256 4096 65,536
32 5 160 1024 32,768 4,294,967,296
64 6 384 4096 2,62,144 Note1
128 7 896 16,384 2,097,152 Note2
256 8 2048 65,536 1,677,216 ????????
5
Note2:The value hereis about500billiontimes the ageofthe universe
innanoseconds,assumingauniverseageof20 billionyears.
Graphoflogn,n,nlogn,n2,n3,2n,n!andnn
O(log n) does not depend on the base of the logarithm. To simplify the analysis,
theconvention will not have any particular units of time. Thus we throw away
leadingconstants. We willalso throw away low–order termswhile computing a Big–
Ohrunning time. Since Big-Oh is an upper bound, the answer provided is a
guaranteethat the program will terminate within a certain time period. The program
may stopearlierthanthis,but neverlater.
One way to compare the function f(n) with these standard function is to use
thefunctional „O‟ notation, suppose f(n) and g(n) are functions defined on the
positiveintegerswiththepropertythatf(n)isboundedbysomemultipleg(n)foralmostall
„n‟.Then,
f(n)=O(g(n))
Whichisreadas“f(n)isoforderg(n)”.Forexample,theorderofcomplexityfor:
LinearsearchisO(n)
BinarysearchisO(logn)
BubblesortisO(n2)
MergesortisO(nlogn)
Theruleofsums
Suppose that T1(n) and T2(n) are the running times of two programs
fragmentsP1andP2,andthatT1(n)isO(f(n))andT2(n)isO(g(n)).ThenT1(n)+T2(n),therunnin
gtimeof P1followedby P2is O(maxf(n),g(n)),thisiscalledasruleofsums.
For example, suppose that we have three steps whose running times are
respectivelyO(n2), O(n3) and O(n. log n). Then the running time of the first two steps
executedsequentially is O (max(n2, n3)) which is O(n3). The running
timeofallthreetogetheris O(max(n3,n.log n)) whichisO(n3).
6
Theruleofproducts
If T1(n) and T2(n) are O(f(n) and O(g(n)) respectively. Then T 1(n)*T2(n) is
O(f(n)g(n)). It follows term the product rule that O(c f(n)) means the same thing as
O(f(n))if„c‟isanypositiveconstant.Forexample,O(n 2/2)issameasO(n 2).
SupposethatwehavefivealgorithmsA 1–A5withthefollowingtimecomplexities:
A1 : n
A2 : n log
nA3 : n2
A4: n3
A5: 2n
Thetimecomplexityisthenumberoftimeunitsrequiredtoprocessaninputofsize
„n‟. Assuming that one unit of time equals one millisecond. The size of the
problemsthatcanbesolvedbyeachofthesefivealgorithmsis:
The speed of computations has increased so much over last thirty years and it
mightseem that efficiency in algorithm is no longer important. But, paradoxically,
efficiencymatters more today then ever before. The reason why this is so is that our
ambitionhasgrownwithourcomputingpower.Virtuallyallapplicationsofcomputingsimulati
onofphysicaldataaredemandingmorespeed.
Thefasterthecomputerrun,themoreneedareefficientalgorithmstotakeadvantage of their
power. As the computer becomes faster and we can handle
largerproblems,itisthecomplexityofanalgorithmthatdeterminestheincreaseinproblem
sizethatcanbeachievedwith an increasein computerspeed.
Suppose the next generation of computers is ten times faster than the
currentgeneration,fromthetablewecanseetheincreaseinsizeoftheproblem.
Insteadofanincreaseinspeedconsidertheeffectofusingamoreefficientalgorithm. By
looking into the following table it is clear that if minute as a basis forcomparison, by
replacing algorithm A4 with A3, we can solve a problem six timeslarger; by replacing
A4 with A2 we can solve a problem 125 times larger. Theseresults are for more
impressive than the two fold improvement obtained by a ten foldincrease in speed. If
an hour is used as the basis of comparison, the differences areevenmoresignificant.
7
Wethereforeconcludethattheasymptoticcomplexityofanalgorithmisanimportantmeasur
e ofthegoodness ofanalgorithm.
TheRunningtimeofaprogram
When solving a problem we are faced with a choice among algorithms. The basis
forthiscan beanyone ofthefollowing:
i. Wewouldlikeanalgorithmthatiseasytounderstand,codeanddebug.
ii. Wewouldlikeanalgorithmthatmakesefficientuseofthecomputer‟sresour
ces, especially,onethat runsasfastaspossible.
Measuringtherunningtimeofaprogram
The runningtimeofaprogramdependsonfactorssuchas:
1. Theinputtotheprogram.
3. The nature and speed of the instructions on the machine used to execute
theprogram,and
The running time depends not on the exact input but only the size of the input.
Formany programs, the running time is really a function of the particular input, and
notjustoftheinputsize. InthatcasewedefineT(n)tobe theworst caserunningtime,
i.e. the maximum overall input of size „n‟, of the running time on that input. We
alsoconsider Tavg(n) the average, over all input of size „n‟ of the running time on
thatinput. In practice, the average running time is often much harder to determine
thanthe worst case running time. Thus, we will use worst–case running time as
theprincipalmeasure oftimecomplexity.
Seeing the remarks (2) and (3) we cannot express the running time T(n) in
standardtimeunitssuchasseconds.Ratherwecanonlymakeremarksliketherunningtimeof
such and such algorithm is proportional to n 2. The constant of proportionality
willremain un-specified, since it depends so heavily on the compiler, the machine
andotherfactors.
AsymptoticAnalysisofAlgorithms:
Our approach is based on the asymptotic complexity measure. This means that
wedon‟t try to count the exact number of steps of a program, but how that
numbergrows with the size of the input to the program. That gives us a measure that
willwork for different operating systems, compilers and CPUs. The asymptotic
complexityiswritten using big-Onotation.
Rulesforusingbig-O:
The most important property is that big-O gives an upper bound only. If an
algorithmisO(n2),itdoesn‟thavetotaken2steps(oraconstantmultipleofn2).Butitcan‟t
8
take more than n2. So any algorithm that is O(n), is also an O(n 2) algorithm. If
thisseemsconfusing,thinkofbig-Oasbeinglike"<".Anynumberthatis<nisalso<n2.
1. Ignoring constant factors: O(c f(n)) = O(f(n)), where c is a constant;
e.g.O(20n3) =O(n3)
3. Upperboundonly:Ifa<bthenanO(a)algorithmisalsoanO(b)algorithm. For
example, an O(n) algorithm is also an O(n 2) algorithm (butnotviceversa).
4. n and log n are "bigger" than any constant, from an asymptotic view
(thatmeans for large enough n). So if k is a constant, an O(n + k)
algorithm
isalsoO(n),byignoringsmallerterms.Similarly,anO(logn+k)algorithmisalsoO(
logn).
Let us now look into how big-O bounds can be computed for some
commonalgorithms.
Example1:
Let‟sconsiderashortpieceofsourcecode:
x=3*y+2;z=
z+1;
If y, z are scalars, this piece of code takes a constant amount of time, which we
writeas O(1). In terms of actual computer instructions or clock ticks, it‟s difficult to
sayexactly how long it takes. But whatever it is, it should be the same whenever
thispieceofcodeisexecuted.O(1)meanssomeconstant,itmightbe5,or1or1000.
Example2:
2n2+5n–6=O(2n) 2n2+5n–6(2n)
2n2+5n–6=O(n3) 2n2+5n–6(n3)
2n2+5n–6=O(n2) 2n2+5n–6=(n2)
2n2+5n–6O(n) 2n2+5n–6(n)
2n2+5n–6(2n) 2n2+5n–6=o(2n)
2n2+5n–6(n3) 2n2+5n–6=o(n3)
2n2+5n–6=(n2) 2n2+5n–6o(n2)
2n2+5n–6=(n) 2n2+5n–6o(n)
9
Example3:
Ifthefirstprogramtakes100n2millisecondsandwhilethesecondtakes5n3milliseconds,then
mightnot5n3programbetterthan100n 2program?
5n3/100n2=n/20
for inputs n < 20, the program with running time5n 3willbe faster than those theone
with running time 100 n2. Therefore, if the program is to be run mainly on
inputsofsmallsize,wewouldindeedpreferthe program whose running timewasO(n3)
However, as „n‟ gets large, the ratio of the running times, which is n/20,
getsarbitrarily larger. Thus, as the size of the input increases, the O(n 3) program will
takesignificantly more time than the O(n 2) program. So it is always better to prefer
aprogramwhoserunningtimewiththelowergrowthrate.Thelowgrowthratefunction‟ssuch
asO(n)orO(nlogn)arealwaysbetter.
Example4:
Analysisofsimpleforloop
Nowlet‟sconsiderasimpleforloop:
for(i=1;i<=n;i++)
v[i]=v[i]+1;
This loop will run exactly n times, and because the inside of the loop takes
constanttime, the total running time is proportional to n. We write it as O(n). The
actualnumberofinstructionsmightbe50n,whiletherunningtimemightbe17nmicroseconds
. It might even be 17n+3 microseconds because the loop needs sometime to start
up. The big-O notation allows a multiplication factor (like 17) as well asan additive
factor (like 3). As long as it‟s a linear function which is proportional to
n,thecorrectnotationisO(n)andthecodeissaidtohavelinearrunningtime.
Example5:
Analysisfor nestedforloop
Nowlet‟slookatamorecomplicatedexample,anestedforloop:
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i,j]=b[i,j] *x;
The outer for loop executes N times, while the inner loop executes n times for
everyexecution of the outer loop. That is, the inner loop executes n n = n2times.
Theassignment statement in the inner loop takes constant time, so the running time
ofthecodeisO(n 2)steps.Thispieceofcodeissaidtohavequadraticrunningtime.
10
Example6:
Analysisofmatrixmultiply
Lets start with an easy case. Multiplying two n n matrices. The code to compute
thematrixproductC=A*Bis givenbelow.
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
C[i,j]=0;
for(k=1;k<=n;k++)
C[i,j]=C[i,j]+A[i,k]*B[k,j];
There are 3 nested for loops, each of which runs n times. The innermost
looptherefore executes n*n*n = n3times. The innermost statement, which contains
ascalar sum and product takes constant O(1) time. So the algorithm overall
takesO(n3)time.
Example7:
Analysisofbubblesort
Themainbodyofthecodeforbubblesortlookssomethinglikethis:
for(i=n-1;i<1;i--)
for (j=1;j<=i;j++)
if(a[j]>a[j+1])
swapa[j]anda[j+1];
This looks like the double. The innermost statement, the if, takes O(1) time.
Itdoesn‟tnecessarilytakethesametimewhentheconditionistrueasitdoeswhenitis false,
but both times are bounded by a constant. But there is an importantdifference here.
The outer loop executes n times, but the inner loop executes anumber of times that
depends on i. The first time the inner for executes, it runs i =n-1 times. The
secondtimeit runs n-2 times, etc. The totalnumber of times theinnerifstatement
executesistherefore:
(n-1)+(n-2)+... +3 +2+1
Thisisthesumofanarithmeticseries.
N1 2
(ni)n(ni) 2 n
n
i1 2 2
The value of the sum is n(n-1)/2. So the running time of bubble sort is O(n(n-
1)/2),which is O((n2-n)/2). Using the rules for big-O given earlier, this bound
simplifies toO((n2)/2) by ignoring a smaller term, and to O(n 2), by ignoring a
constant factor.Thus,bubblesort isanO(n2)algorithm.
11
Example8:
Analysisofbinarysearch
Binary search is a little harder to analyze because it doesn‟t have a for loop. But
it‟sstill pretty easy because the search interval halves each time we iterate the
search.Thesequence of searchintervalslookssomething likethis:
n,n/2,n/4,...,8,4,2,1
It‟snotobvioushowlongthissequenceis,butifwetakelogs,itis:log2n,log2n
- 1,log2n- 2,...,3,2,1,0
Sincethesecondsequencedecrementsby1eachtimedownto 0,itslengthmustbe
log2 n + 1. It takes only constant time to do each test of binary search, so the
totalrunningtime is justthe number of times thatwe iterate, which is
log2n+1.SobinarysearchisanO(log2n)algorithm.Sincethebaseofthelogdoesn‟tmatterina
nasymptoticbound,wecanwritethatbinarysearchisO(logn).
Generalrulesfortheanalysisofprograms
Ingeneraltherunningtimeofastatementorgroupofstatementsmaybeparameterizedbythe
inputsizeand/orbyoneormorevariables.Theonlypermissibleparameterfortherunningtimeof
thewholeprogramis„n‟theinputsize.
1. The running time of each assignment read and write statement can usually
betakentobeO(1).(Therearefewexemptions,suchasinPL/1,whereassignments
can involve arbitrarily larger arrays and in any language thatallowsfunction
callsinarraignmentstatements).
2. Therunningtimeofasequenceof statementsisdeterminedbythesumrule.
I.e. the running time of the sequence is, to with in a constant factor,
thelargest runningtimeofanystatement in thesequence.
12
Chapter
2
AdvancedDataStructuresand
RecurrenceRelations
PriorityQueue,HeapandHeapSort:
Heap is a data structure, which permits one to insert elements into a set and also
tofind the largestelementefficiently. Adatastructure, whichprovides these
twooperations,iscalled apriorityqueue.
MaxandMinHeapdatastructures:
A max heap is an almost complete binary tree such that the value of each node
isgreater thanorequaltothosein itschildren.
95 15
85 45 45 25
75 25 35 15 55 65 35 75
55 65 85 95 Minheap
Maxheap
A min heap is an almost complete binary tree such that the value of each node is
lessthan or equal to those in its children. Figure 2.1 shows the maximum and
minimumheaptree.
RepresentationofHeapTree:
Since heap is a complete binary tree, a heap tree can be efficiently represented
usingone dimensional array. This provides a very convenient way of figuring out
wherechildrenbelongto.
Therootofthetreeisinlocation1.
Theleftchildofanelementstoredatlocationicanbefoundinlocation2*i.
The right child of an element stored at location i can be found in
location2*i+1.
The parent of an element stored at location i can be found at
locationfloor(i/2).
13
For example let us consider the following elements arranged in the form of array
asfollows:
65 45 60 40 25 50 55 30
The elements of the array can be thought of as lying in a tree structure. A heap
treerepresentedusinga singlearraylooksasfollows:
x[1]
65 x[3]
x[2]
45 60
x[6] x[7]
x[4] 40 x[5] 25 50 55
x[8] 30
Figure2.2.HeapTree
Operationsonheaptree:
Themajoroperationsrequiredtobeperformedonaheaptree:
1. Insertion,
2. Deletionand
3. Merging.
Insertionintoaheaptree:
This operation is used to insert a node into an existing heap tree satisfying
theproperties of heap tree. Using repeated insertions of data, starting from an
emptyheaptree,one can buildupaheaptree.
For illustration, 35 is added as the right child of 80. Its value is compared with
itsparent‟s value, and to be a max heap, parent‟s value greater than child‟s value
issatisfied,henceinterchangeaswellasfurthercomparisonsarenomorerequired.
As another illustration, let us consider the case of insertion 90 into the resultant
heaptree.First,90willbeaddedasleftchildof40,when90iscomparedwith40it
14
requires interchange. Next, 90 is compared with 80, another interchange takes
place.Now, our process stops here, as 90 is now in root node. The path on which
thesecomparisonsandinterchangeshavetakenplacesareshownbydashedline.
ThealgorithmMax_heap_inserttoinsertadataintoamaxheaptreeisas follows:
Max_heap_insert(a,n)
{
//inserts the value in a[n] into the heap which is stored at a[1] to a[n-
1]integer i,n;
i=n;
item=a[n];
while((i>1)and(a[i/2]<item)do
{
a[i]=a[i/2 ];
//movetheparentdowni=
i/2 ;
}
a[i] = item
;returntrue;
}
Example:
Formaheapbyusingtheabovealgorithmforthegivendata40,80,35,90,45,50,
70.
1. Insert40:
40
2. Insert80:
80
40 80
40
80 40
3. Insert35:
80
40 35
15
4. Insert90:
90
80 90
80
90
40 35 80 35
40
90 40
5. Insert45:
90
80 35
40 45
6. Insert50:
90 90
50
80 35 80 50
35
40 45 50 40 45 35
7. Insert70:
90 90
70
80 50 80 70
50
40 45 35 70 40 45 35 50
Deletionofanodefromheaptree:
Any node can be deleted from a heap tree. But from the application point of
view,deleting the root node has some special importance. The principle of deletion is
asfollows:
Readtherootnodeintoatemporarystoragesay,ITEM.
Replace the root node by the last node in the heap tree. Then re-heap
thetreeasstatedbelow:
Let newly modified root node be the current node. Compare
itsvalue with the value of its two child. Let X be the child whose
valueis the largest. Interchange the value of X with the value of
thecurrentnode.
MakeXasthecurrentnode.
Continuere-heap,ifthecurrentnodeisnotanemptynode.
16
Thealgorithmfor theaboveisasfollows:
delmax(a,n,x)
//delete the maximum from theheapa[n]andstoreit inx
{
if(n=0)then
{
write (“heap is
empty”);returnfalse;
}
x= a[1];a[1]=a[n];
adjust (a, 1, n-
1);returntrue;
}
adjust(a,i,n)
// The complete binary trees with roots a(2*i) and a(2*i + 1) are combined with a(i) to form
asingle heap,1<i<n.Nonodehasan addressgreaterthann orlessthan1.//
{
j = 2 *i
;item=a[i];
while(j<n)do
{
if((j< n)and(a(j) <a (j +1))thenjj+1;
// compare left and right child and let j be the larger
childif(item >a(j))thenbreak;
// a position for item is
foundelsea[j /2]=a[j]//movethelargerchildupalevel
j =2*j;
}
a[j /2]=item;
}
Heretherootnodeis99.Thelastnodeis26,itisinthelevel3.So,99isreplacedby
26 and this node with data 26 is removed from the tree. Next 26 at root node
iscompared with its two child 45 and 63. As 63 is greater, they are interchanged.
Now,26 is compared with its children, namely, 57 and 42, as 57 is greater, so they
areinterchanged. Now, 26 appear as the leave node, hence re-heap is completed.
This isshownin figure2.3.
26 63
99
26 63
57
45 63
45 57
26
35 29 57 42
35 29 26 42
27 12 24 26
27 12 24
Figure 2.3.
17
Mergingtwoheaptrees:
Consider, two heap trees H1 and H2. Merging the tree H2 with H1 means to
includeall the node from H2 to H1. H2 may be min heap or max heap and the
resultant treewillbeminheapifH1isminheapelseitwillbemaxheap.
92 13
59 67 19 80
38 45 92 93 96
H1:maxheap H2:minheap
+
96
93 67
80 92 13 19
38 59 45 92 Resultantmaxheapaftermerging H1andH2
Figure2.4.Mergingoftwoheaps.
Applicationsofheaptree:
Theyaretwomainapplicationsofheaptreesknown:
1. Sorting(Heapsort)and
2. Priorityqueueimplementation.
18
HEAPSORT:
A heap sort algorithm works by first organizing the data to be sorted into a
specialtype of binary tree called a heap. Any kind of data can be sorted either in
ascendingorderorindescendingorderusingheaptree.Itdoesthiswiththefollowingsteps:
Algorithm:
This algorithm sorts the elements a[n]. Heap sort rearranges them in-place in non-
decreasingorder.Firsttransformtheelementsintoaheap.
heapsort(a,n)
{
heapify(a,n);
fori =n to2by–1do
{
temp =
a[I];a[i] =
a[1];a[1]=t;
adjust(a,1,i –1);
}
}
heapify(a,n)
//Readjust theelementsina[n]to form aheap.
{
forin/2to1by–1doadjust(a,i,n);
}
adjust(a,i,n)
//The complete binary treeswithrootsa(2*i)anda(2*i+1)arecombined
//witha(i)to formasingleheap,1<i<n. Nonodehasanaddressgreater
//thannorlessthan1.
{
j = 2 *i
;item=a[i];
while(j<n)do
{
if((j< n)and(a(j) <a (j +1))thenjj+1;
// compare left and right child and let j be the larger
childif(item >a(j))thenbreak;
// a position for item is
foundelsea[j /2]=a[j]//movethelargerchildupalevel
j =2*j;
}
a[j /2]=item;
}
19
TimeComplexity:
Each „n‟ insertion operations takes O(log k), where „k‟ is the number of elements
inthe heap at the time. Likewise, each of the „n‟ remove operations also runs in
timeO(log k), where „k‟ is the number of elements in the heap at the time. Since
wealwayshavek≤n,eachsuchoperationrunsinO(logn)timeintheworstcase.
Thus, for n elements it takes O(n log n) time, so the priority queue sorting
algorithmrunsinO(nlogn)timewhenweuseaheaptoimplementthepriorityqueue.
Example1:
Form a heap from the set of elements (40, 80, 35, 90, 45, 50, 70) and sort the
datausingheapsort.
Solution:
Firstformaheaptreefromthegivensetofdataandthensortbyrepeateddeletionoperation:
1. Exchangeroot90withthelastelement35ofthearrayandre-heapify
80
35 80
45 35
80 70 45 70
40 45 50 90 40 35 50 90
35
2. Exchangeroot80withthelastelement50ofthearrayandre-heapify70
50
50 70
45 70
45 50
40 35 80 90
40 35 80 90
3. Exchangeroot70withthelastelement35ofthearrayandre-heapify50
35
35 50
45 50
45 35
40 70 80 90
40 70 80 90
20
4. Exchangeroot50with thelast element40ofthearrayand re-heapify
45
40 45
40
45 35 40 35
50 70 80 90 50 70 80 90
5. Exchange root 45 with the last element 35 of the array and re-
heapify40
35 40
35
40 45 35 45
50 70 80 90 50 70 80 90
6. Exchange root 40 with the last element 35 of the array and re-
heapify35
40 35
40
35 45 40 45
50 70 80 90 50 70 80 90
Thesortedtree
Priorityqueueimplementationusingheaptree:
Priority queue can be implemented using circular array, linked list etc.
Anothersimplified implementation is possible using heap tree; the heap, however, can
berepresentedusinganarray.Thisimplementationisthereforefreefromthecomplexities of
circular array and linked list but getting the advantages of simplicitiesofarray.
As heap trees allow the duplicity of data in it. Elements associated with their
priorityvalues are to be stored in from of heap tree, which can be formed based on
theirpriority values. The top priority element that has to be processed first is at the
root;so it can be deleted and heap can be rebuilt to get the next element to be
processed,andsoon.
Process P1 P2 P3 P4 P5 P6 P7 P8 P9 P10
Priority 5 4 3 4 5 5 3 2 1 5
These processes enter the system in the order as listed above at time 0, say.
Assumethat a process having higher priority value will be serviced first. The heap
tree can beformed considering the process priority values. The order of servicing the
process issuccessivedeletion ofroots fromtheheap.
21
BinarySearchTrees:
A binary search tree has binary nodes and the following additional property. Given
anode t,each node to the left is “smaller” than t, and each node to the right
is“larger”.Thisdefinitionappliesrecursivelydowntheleftandrightsub-trees.Figure
showsabinarysearchtreewherecharactersarestoredinthenodes.
b h
a e g
c Inorder:abcdefgh
Figure2.5.BinarySearchtree
Figure 2.5 also shows what happens if you do an inorder traversal of a binary
searchtree: you will get a list of the node contents in sorted order. In fact, that‟s
probablyhowthenameinorderoriginated.
BinaryTreeSearching:
ThesearchoperationstartsfromrootnodeR,ifitemislessthanthevalueintheroot node R, we
proceed to the left child; if item is greater than the value in the nodeR, we proceed to
its right child. The process will be continued till the item is found orwe reach to a
dead end. The Figure 2.6 shows the path taken when searching for anode“c”.
b h
a e g
c Pathtofindc
Figure2.6.Searchingabinarytree
Whyusebinarysearchtrees?
Binarysearchtreesprovideanefficientwaytosearchthroughanorderedcollectionof items.
Consider the alternative of searching an ordered list. The search mustproceed
sequentially from one end of the list to the other. On average, n/2 nodesmustbe
comparedforanorderedlistthatcontainsnnodes.Intheworstcase,alln
22
nodes might need to be compared. For a large collection of items, this can get
veryexpensive.
The inefficiency is due to the one-dimensionality of alinked list. We would like tohave
a way to jump into the middle of the list, in order to speed up the searchprocess. In
essence, that‟s what a binary search tree does. The longest path we willever have to
search is equalto the height of the tree. The efficiency of abinarysearch tree thus
depends on the height of the tree. For a tree holding n nodes,
thesmallestpossibleheightislog(n).
To obtain the smallest height, a tree must be balanced, where both the left and
rightsub trees have approximately the same number of nodes. Also, each node
shouldhave as many children as possible, with all levels being full except possibly the
last.Figure2.7showsanexampleofawell-constructedtree.
c g
b d f h
Figure2.8.Adegeneratebinarysearchtree.
When nodes are being added and deleted in a binary search tree, it‟s difficult
tomaintain the balance of the tree. We willinvestigate methods of balancing trees
inthenextsection.
When adding nodes to a binary search tree,we must be carefulto maintain thebinary
search tree property. This can be done by first searching the tree to seewhether the
key we are about to add is already in the tree. If the key cannot
befound,anewnodeisallocatedandaddedatthesamelocationwhereitwouldgoif
23
the search had been successful. Figure 2.9 shows what happens when we add
somenodes toatree.
d d
d
b f b f
inserta inserte b f
a e
a
Figure2.9.Insertingnodesintoabinary searchtree.
Deletions from a binary search tree are more involved than insertions. Given a
nodetodelete,weneedtoconsiderthesetreecases:
1. Thenodeisaleaf
2. Thenodehas onlyonechild.
3. Thenodehastwochildren.
Case 1: It is easy to handle because the node can simply be deleted and
thecorresponding child pointer of its parent set to null. Figure 2.10
showsanexample.
b b
a c a c
Figure2.10.Deletingaleafnode.
b b
a c a e
e d f
d f
Figure2.11. Deletinganodethathasonechild.
24
Case3: Thenodetobedeletedhastwochildren,ismoredifficult.Wemustfind some node to
take the place of the one deleted and still
maintainthebinarysearchtreeproperty.Therearetwoobviouscases:
Theinorder predecessorofthedeletednode.
Theinordersuccessorofthedeletednode.
We can detach one of these nodes from the tree and insert it
wherethenodetobedeleted.
The predecessor of a node can be found by going down to the left once, and then
allthe way to the right as far as possible. To find the successor, an opposite traversal
isused:firsttotheright,andthendowntotheleftasfaraspossible.Figure2.12showsthepathta
kentofindboththepredecessorandsuccessorofanode.
e e
b i b i
a d g j a d g j
c f h c f h
Both the predecessor and successor nodes are guaranteed to have no more than
onechild, and they may have none. Detaching the predecessor or successor reduces
toeither case 1 or 2, both of which are easy to handle. In figure 2.13 (a), we delete
anodefromthetreeanduseitspredecessorasthereplacementandinfigure2.13(b),wedelete
anodefromthetreeanduseitssuccessorasthereplacement.
d f
b i b i
a c g j a d g j
f h c h
(a)Afterdeletingthepr (b)Afterdeletingthes
edecessor ofe. uccessorofe.
Figure2.13.Deletinganodethathastwochildren.
25
BalancedTrees:
For maximum efficiency, a binary search tree should be balanced. Every un-
balancedtreesarereferredtoasdegeneratetrees,socalledbecausetheirsearchingperforma
ncedegeneratestothatoflinkedlists.Figure2.14showsanexample.
a a
b i
c
b
d
h
e
c
f
g
g
(a) h d (b)
i f
e
Figure2.14.Adegeneratebinarysearchtree.
Thefirsttreewasbuiltbyinsertingthekeys„a‟through„i‟insortedorderintobinarysearch
tree. The second tree was built using the insertion sequence. a-g-b-f-c-e-d.This
pathological sequence is often used to test the balancing capacity of a tree.Figure
2.15shows what the tree in 2.14-(b) above would look like if itwerebalanced.
b h
a c f i
e g
Figure2.15BalancedTree
BalancingActs:
Therearetwobasicwaysusedtokeeptreesbalanced.
1) Usetreerotations.
2) Allownodestohavemorethan twochildren.
26
TreeRotations:
p
c b
t
b 4 a c
a 3
1 2 3 4
1 2 (a)RightRotation.
p
b
a
t a c
1 b
1 2 3 4
2 c
(a)LeftRotation.
3 4
Figure2.16.SingleRotations
Another type of rotation is known as a double rotation. Figure 2.17 shows the
twosymmetricalcases.
g
c c b
p
a 4 b 4 a c
1 b
a 3 1 2 3 4
2 3
1 2
(a)Left-RightRotation.
p
b
a a
t a c
1 c 1 b
1 2 3 4
b 4 2 c
2 3 3 4
(b)Right-LeftRotation.
Figure2.17.DoubleRotations
27
Both single and double rotations have one important feature: in order traversals
ofthe trees before and after the rotations are preserved. Thus, rotations help
balancetrees,butstillmaintainthebinarysearchtreeproperty.
Rotationsdon‟tguaranteeabalancedtree,howeverforexample,figure2.18showsa right
rotations that makes a tree more un-balanced. The trick lies in
determiningwhentodorotationandwhatkindofnotationstodo.
b a
b
a c
c
Figure2.18.Un-balancedrotation.
The Red-black trees have certain rules to be used todetermine when a how torotate.
Dictionary:
Examples:
2. Atelephonedirectorywithacollectionoftelephonenumbersandnames.
3. The list of students enrolled for the data structures course, compiler
andOperatingSystemcourse. Thelistcontains(CourseName,RollID)pairs.
Theabovelasttwoexamplesaredictionaries,whichpermittwoormore(key,element)pairsha
ving thesamekey.
OperationsonDictionaries:
Gettheelementassociatedwithaspecifiedkeyfromthedictionary.Forexamp
le,get(k)returnsthe element with thekeyk.
Insertorputanelementwithaspecifiedkeyintothedictionary.
Forexample,put(k,e)putstheelementewhosekeyiskintothedictionary.
Deleteorremoveanelementwithaspecifiedkey.
Forexample,remove(k)removesthe element with keyk.
28
DisjointSetOperations
DisjointSetOperationsSe
t:
A set is a collection of distinct elements. The Set can be represented,
forexamples, asS1={1,2,5,10}.
DisjointSets:
Thedisjointssetsarethosedo nothaveany commonelement.
ForexampleS1={1,7,8,9}andS2={2,5,10},thenwecansaythatS1andS2aretwodisjointset
s.
DisjointSetOperations:
Thedisjointsetoperationsare
1. Union
2. Find
DisjointsetUnion:
If Si and Sj are tow disjoint sets, then their union Si U Sj consists of all
theelementsxsuchthat xisin SiorSj.
Example:
S1={1,7,8,9} S2={2,5,10}
S1US2={1,2,5,7,8,9,10}
Find:
Giventheelement I, findthesetcontainingi.
Example:
S1={1,7,8,9} S2={2,5,10} s3={3,4,6}
Then,
Find(4)=S3 Find(5)=S2 Find97)=S1
SetRepresentation:
The set will be represented as the tree structure where all children will
storethe address of parent / root node. The root node will store null at the place of
parentaddress. In the given set of elements any element can be selected as the root
node,generallyweselectthefirstnodeastherootnode.
Example:
S1={1,7,8,9} S2={2,5,10} s3={3,4,6}
Thenthesesetscanberepresentedas
DisjointUnion:
ToperformdisjointsetunionbetweentwosetsSiandSjcantakeanyoneroot and
make it sub-tree of the other. Consider the above example sets S1 and
S2thentheunionofS1andS2canberepresentedasanyoneofthefollowing.
29
Find:
Toperformfindoperation,alongwiththetreestructureweneedto maintain
the nameofeachset.So,werequire onemore datastructure tostore the setnames. The
data structure contains two fields. One is the set name and the other
oneisthepointertoroot.
UnionandFindAlgorithms:
In presenting Union and Find algorithms, we ignore the set names
andidentify sets just by the roots of trees representing them. To represent the sets,
weuse an array of 1 to n elements where n is the maximum value among the
elementsof all sets. The index values represent the nodes (elements of set) and the
entriesrepresenttheparentnode.Fortherootvaluetheentrywill be„-1‟.
Example:
Forthefollowingsetsthearrayrepresentationisasshownbelow.
i [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
p -1 -1 -1 3 2 3 1 1 1 2
AlgorithmforUnionoperation:
To perform union the SimpleUnion(i,j) function takes the inputs as the
setrootsiandj.Andmaketheparentofiasji.e,makethesecondrootastheparentoffirstroot.
AlgorithmSimpleUnion(i,j)
{
P[i]:=j;
}
30
Algorithmforfindoperation:
TheSimpleFind(i)algorithmtakestheelementiandfindstherootnodeofi.ItstartsatIuntil
it reachesanodewith parentvalue-1.
AlgorithmsSimpleFind(i)
{
while(P[i]≥0)doi:=P[i];retur
ni;
}
Analysisof SimpleUnion(i,j)andSimpleFind(i):
Although the SimpleUnion(i,j) and SimpleFind(i) algorithms are easy to
state,theirperformancecharacteristicsarenotverygood.Forexample,considerthesets
1 2 3 4 .... .. n
Thenifwewanttoperformfollowingsequence ofoperations
Union(1,2),Union(2,3)…….Uni
on(n-1,n)andsequenceofFind(1),Find(2)………Find(n).
ThesequenceofUnionoperationsresultsthedegeneratetreeasbelow.
n-1
n-2
Since, the time taken for a Union is constant, the n-1 sequence of union can
beprocessedintimeO(n).AndforthesequenceofFindoperationsitwilltaketime
n
complexityofO( i)=O(n ).
i1
2
We can improve the performance of union and find by avoiding the creation
ofdegeneratetreeby applying weightingruleforUnion.
WeightingruleforUnion:
If the number of nodes in the tree with root I is less than the number in
thetreewiththerootj,thenmake„j‟theparentofi;otherwisemake„i'theparentofj.
31
To implement weighting rule we need to know how many nodes are there in
everytree. To do this we maintain “count” field in the root of every tree. If „i' is the
rootthencount[i]equalstonumberofnodesintreewithrooti.
Since all nodes other than roots have positive numbers in parent (P) field, we
canmaintaincount inPfieldofthe root as negativenumber.
AlgorithmWeightedUnion(i,j)
//Unionsetswithrootsiandj,i≠jusingtheweightedrule
//P[i]=-count[i]andp[j]=-count[j]
{
temp:=P[i]+P[j];
if(P[i]>P[j])then
{
// i has fewer
nodesP[i]:=j;
P[j]:=temp;
}
else
{
// j has fewer
nodesP[j]:=i;
P[i]:=temp;
}
Collapsingruleforfind:
Ifjisanodeonthepathfromi toitsrootand p[i]≠root[i],thensetP[j]to
root[i]. Consider thetree createdby WeightedUnion()onthe sequenceof
1≤i≤8.Union(1,2),Union(3,4),Union(5,6) andUnion(7,8)
32
Now process the following eight find
If SimpleFind() is used each Find(8) requires going up three parent link fields for
atotalof24 moves.
When Collapsing find is used the first Find(8) requires going up three links
andresetting three links. Each of remaining seven finds require going up only one
linkfield. Then the total cost is now only 13 moves.( 3 going up + 3 resets + 7
remainingfinds).
33
AlgorithmCollapsingFind(i)
//Findtherootofthetreecontainingelementi
//usethecollapsingruletocollapseallnodesfromitoroot.
{
r:=i;
while(P[r]>0) do r:=P[r]; //Find
rootwhile(i≠r)
{
//reset the parent node from element i to the
roots:=P[i];
P[i]:=r;
i:=s;
}
}
34
RecurrenceRelations
Recurrence Relation for a sequence of numbers S is a formula that relates all but
afinitenumberof termsofStopreviousterms ofthesequence,namely, {a 0,a1,a2,.
. . . . , an-1}, for all integers n with n ≥n0,where n0is a nonnegative
integer.Recurrencerelationsarealsocalledasdifferenceequations.
Sequences are often most easily defined with a recurrence relation; however
thecalculationoftermsbydirectlyapplyingarecurrencerelationcanbetimeconsuming. The
process of determining a closed form expression for the terms of asequence from its
recurrence relation is called solving the relation. Some guess
andcheckwithrespecttosolvingrecurrencerelationareasfollows:
Makesimplifyingassumptionsaboutinputs
Tabulatethefirstfewvaluesoftherecurrence
Lookforpatterns, guessasolution
Generalize the result to remove the
assumptionsExamples:Factorial,Fibonnaci,Quicksort,Binary
searchetc.
TheIterativeSubstitutionMethod:
T(n)=2(2T(n/22)+b(n/2))+bn
=22T(n/22)+2bn
PluggingthegeneralequationforTagainyieldstheequation.
T(n) =22(2T(n/23)+b(n/22))+2bn
=23T(n/23)+3bn
35
The hope in applying the iterative substitution method is that, at some point, we
willseeapatternthatcan beconvertedintoageneralclosed-form equation(withTonly
36
appearing on the left-hand side). In the case of merge-sort recurrence equation,
thegeneralformis:
T(n)=2iT(n/2i)+ibn
Notethatthegeneralformofthisequationshiftstothebasecase,T(n)=b,wheren=2i,thatis,w
heni=logn,whichimplies:
T(n)=b n+bnlogn.
Inotherwords,T(n)isO(nlogn).Inageneralapplicationoftheiterativesubstitution
technique, we hope that we can determine a general pattern for T(n)
andthatwecanalsofigureoutwhenthegeneralformofT(n)shiftstothe basecase.
TheRecursionTree:
In using the recursion tree method, we draw a tree R where each node represents
adifferent substitution of the recurrence equation. Thus, each node in R has a value
ofthe argument n of the function T (n) associated with it. In addition, we associate
anoverhead with each node v in R, defined as the value of the non-recursive part of
therecurrenceequation forv.
Forexample,considerthefollowingrecurrenceequation:
b ifn3
T(n)
n/3bn
3T ifn3
This is the recurrence equation thatwe get, for example, by modifying the mergesort
algorithm so that we divide an unsorted sequence into three equal – sizedsequences,
recursively sort each one, and then do a three-way merge of three sortedsequences
to produce a sorted version of the original sequence. In the recursion treeR for this
recurrence, each internal node v has three children and has a size and anoverhead
associated with it, which corresponds to the time needed to merge the sub-
problemsolutionsproducedbyv‟schildren.WeillustratethetreeRasfollows:
37
Overheadb
n
bn
bn
The overheads of the nodes of each level, sum to bn. Thus, observing that the
depthofR islog3n,wehavethat T(n) isO(n logn).
TheGuess-and-TestMethod:
Anothermethodforsolvingrecurrenceequationsistheguess-and-testtechnique.This
technique involves first making a educated guess as to what a closed-formsolution of
the recurrence equation might look like and then justifying the
guesses,usuallybyinduction.Forexample,wecanusetheguess-and-testmethodasakindof
“binary search” for finding good upper bounds on a given recurrence equation. Ifthe
justification of our current guess fails, then it is possible that we need to use afaster-
growing function, and if our current guess is justified “too easily”, then it
ispossiblethatweneedtouseaslower-growingfunction.However,usingthistechnique
requires case careful, in each mathematical step we take, in
tryingtojustifythatacertainhypothesisholdswithrespecttoourcurrent“guess”.
Example2.10.1:Considerthefollowingrecurrenceequation:
T(n)=2T(n/2)+bnlogn.(assumingthebasecaseT(n)=bforn<2)
This looks very similar to the recurrence equation for the merge sort routine, so
wemightmakethe following as ourfirstguess:
for some constant c>0. We can certainly choose c large enough to make this true
forthe base case, so consider the case when n > 2. If we assume our first guesses
aninductivehypothesisthatistrueforinputsizessmallerthann,thenwehave:
T(n)=2T(n/2)+b nlogn
≤2(c(n/2) log(n/2))+b nlogn
≤cn(logn–log 2)+bnlogn
≤cnlog n –cn +bnlogn.
Butthereisnowaythatwecanmakethislastlinelessthanorequaltocnlognforn≥2.Thus,thisfir
stguesswasnotsufficient.Letusthereforetry:
for some constant c > 0. We can again choose c large enough to make this true
forthebasecase,soconsiderthecasewhenn≥2.Ifweassumethisguessasan
38
inductivehypothesisthatistrueforinput sizessmallerthann,
thenwehaveinductivehypothesisthatistrueforinputsizessmallerthann,thenwehave:
T(n)=2T(n/2) +b nlogn
≤2(c(n/2)log2(n/2))+bnlogn
≤cn(log2n –2log n+1)+b nlogn
≤cnlog2n-2cnlogn+cn+bnlogn
≤cnlog2n
Providedc≥b.Thus,wehaveshownthatT(n)isindeedO(nlog 2n)inthiscase.
Wemusttakecareinusingthismethod.JustbecauseoneinductivehypothesisforT
(n)doesnotwork,thatdoesnotnecessarilyimplythatanotheroneproportionaltothisone
willnotwork.
This recurrence is the running time for the bottom-up heap construction. Which
isO(n).Nevertheless,ifwetrytoprovethisfactwiththemoststraightforwardinductive
hypothesis, we will run into some difficulties. In particular, consider thefollowing:
Firstguess: T(n)≤cn.
For some constant c > 0. We can choose c large enough to make this true for
thebase case, so consider the case when n ≥ 2. If we assume this guess as an
inductivehypothesisthatistrueofinputsizessmallerthann,thenwehave:
T(n)=2T(n/2)+logn
≤2(c(n/2)) +logn
=cn+logn
But there is no way that we can make this last line less than or equal to cn for n >
2.Thus, this first guess was not sufficient, even though T (n) is indeed O (n). Still,
wecanshowthisfactistruebyusing:
For some constant c > 0. We can again choose c large enough to make this true
forthe base case; in fact, we can show that it is true any time n < 8. So consider
thecase when n ≥ 8. If we assume this guess as an inductive hypothesis that is true
forinputsizessmallerthann,then wehave:
T(n)=2T(n/2)+logn
≤2c ((n/2) –log(n/2))+logn
=cn–2clogn+2c+logn
=c(n–log n) –clogn+2c+logn
≤c(n –logn)
TheMasterTheoremMethod:
39
Each of the methods described above for solving recurrence equations is ad hoc
andrequiresmathematicalsophisticationinordertobeusedeffectively.Thereis,nevertheles
s, one method for solving divide-and-conquer recurrence equations that isquite
generaland does notrequire explicit useof induction to apply correctly. Itisthe master
method. The master method is a “cook-book” method for determining theasymptotic
characterization of a wide variety of recurrence equations. It is used
forrecurrenceequationsoftheform:
c
T(n) ifnd
aT(n/b)f(n) ifnd
Whered >1isan integerconstant,a>0, c> 0,andb>1arerealconstants,andf
(n) isafunctionthatispositivefor n≥d.
The master method for solving such recurrence equations involves simply
writingdown the answer based on whether one of the three cases applies. Each case
isdistinguishedbycomparingf(n)tothespecialfunctionnloga(wewillshowlaterwhy
b
thisspecialfunctionissoimportant.
Themastertheorem:Letf(n)andT(n)bedefinedasabove.
(n)is n logba .
2. k
IfthereisaconstantK≥0,suchthatf(n)is nlogbalog n ,thenT(n)
is nlogbalogk1n .
3. If there are small constant > 0 and < 1, such that f (n)
nlogba
isandaf(n/b) <f(n),for n ≥ d,thenT(n) is(f(n)).
Case 1 characterizes the situation where f (n) is polynomial smaller than the
a
specialfunction,nlogb .
Case 3 characterizes the situation when f (n) is polynomially larger than the
specialfunction.
We illustrate the usage of the master method with a few examples (with each
takingtheassumptionthatT(n)=cforn<d,forconstantsc>1andd>1).
Example2.11.1:Considertherecurrence T(n)=4T(n/2) +n
Example2.11.2:ConsidertherecurrenceT (n)=2T(n/2)+nlogn
40
Example2.11.3:considertherecurrenceT(n)=T(n/3)+n
Example2.11.4:ConsidertherecurrenceT(n)=9T(n/3)+n 2.5
Inthiscase,nlogba=nlog9=n2.Thus,weareinCase3,sincef(n)is(n
3
2+
)(for
=1/2)andaf(n/b)=9(n/3) =(1/3) f(n).ThismeansthatT(n)is(n2.5)bythemastermetho
2.5 1/2
d.
SubstitutingintothistheequationS(k)=T(2 k),wegetthatS(k)=2S(k/
2) +k
CLOSEDFROMEXPRESSION
ThereexistsaclosedformexpressionformanysummationsSum
offirst nnaturalnumbers(Arithmeticprogression)
n
n(n1)
i12.......n 2
i1
Sumofsquaresoffirstnnaturalnumbers
n
n(n1)(2n1)
i 2
14 9.... ... n
6
i1
Sumofcubes
n 2 2
i 3 3 3 3
1 2 3 .......n 3
n(n1)
4
i1
Geometricprogression
n
2 2 2 2 .......2 2
i 0 1 2 n n1
1
i0
41
n
rn11
r i
r1
i0
n rn1
r i
r1
i1
SOLVINGRECURRENCERELATIONS
Example2.13.1. Solvethefollowingrecurrencerelation:
2 ,n1
T(n) n
2.T 7,n1
2
Solution: We first start by labeling the main part of the relation as Step
1:Step1: Assumen>1then,
n
T(n)2.T 7
2
n n
Step2:FigureoutwhatT is;everywhereyouseen,replaceitwith .
2 2
n n
T 2.T 7
2 22
NowsubstitutethisbackintothelastT(n)definition(lastlinefromstep1):
n
2.T
Tn2. 77
22
n
22.T 3.7
22
n
Step3:let'sexpandtherecursivecall,thistime,it'sT :
22
n n
T 2.T 7
22 23
NowsubstitutethisbackintothelastT(n)definition(lastlinefromstep2):
Tn2 n 7
2.2.T 7
23
42
n
23.T
7.7
23
Fromthis,first,wenoticethatthepowerof2willalwaysmatchi,current.Second,we notice
that the multiples of 7 match the relation 2 i– 1 : 1, 3, 7, 15. So, we
canwriteageneralsolutiondescribingthestateofT(n).
Step4:Dotheithsubstitution.
T(n)2 i.T
2 i1 .7
n
2i
However, how many times could we take these "steps"? Indefinitely? No… it
wouldstop when n has been cut in half so many times that it is effectively 1. Then,
theoriginaldefinitionoftherecurrencerelationwouldgiveustheterminatingconditionT
(1)=1andus restrictsizen=2i
n
When,1
2i
2in
log22ilog2n
i.log22log2n
ilog2n
Nowwecansubstitutethis"lastvaluefori"backintoaourgeneralStep4equation:
= log2n n
log n1 .7
2 2 2
.T 2log2n
= n.T(1)+(n- 1).7
= n.2+(n -1).7
= 9.n-7
ThisimpliesthatT(n)isO(n).
Example 2.13.2. Imagine that you have a recursive program whose run time
isdescribedbythefollowing recurrencerelation:
1 ,n1
T(n) n
2.T 4.n ,n1
2
43
Solve the relation with iterated substitution and use your solution to determine
atightbig-ohbound.
Solution:
Step1:Assumen>1then,
n
T(n)2.T 4.n
2
n
Step2:figureoutwhat T is:
2
n
T 2.T
n n
4.
2 22 2
NowsubstitutethisbackintothelastT(n)definition(lastlinefromstep1):
Tn2.
n n
2.T
4.4.n
22 2
2 n
= 2 .T 2.4.n
22
n
Step3:figureoutwhatT is:
2
2
n n n
T 4.
2.T
22 23 22
NowsubstitutethisbackintothelastT(n)definition(lasttimefromstep2):
n
n
Tn22.2.T 4. 2.4.n
23 22
3 n
=2 .T 3.4.n
23
Step4:Dotheithsubstitution.
n
Tn2i.T i.4.n
2i
The parameter to the recursive call in the last line will equal 1 when i = log 2n (usethe
same analysis as the previous example). In which case T (1) = 1 by the
originaldefinitionofthe recurrencerelation.
NowwecansubstitutethisbackintoaourgeneralStep4equation:
44
Tn2i.T n .4.n
i
2i
n
=2log2n.T logn. 4.n
2
2log2n
=n.T(1)4.n.log2n
=n + 4 . n . log2
nThisimpliesthatT(n)isO(nlogn).
Example2.13.3.
Writearecurrencerelationandsolvetherecurrencerelationforthe
following fragmentofprogram:
intfindmax(inta[],intstart, intend)
{
intmid,max1,max2;
if(start==end)
//easycase(2steps)re
turn(a[start]);
Solution:
TheRecurrenceRelationis:
T(n)=2, ifn =1
2T(n/2)+8, ifn >1
SolvingtheRecurrenceRelationbyiterationmethod:
Assumen>1thenT(n)=2T(n/2)+8
Step1:Substitutingn=n/2,n/4............... fornintherelation:
45
T(n/2) ]+8 (1)
46
T(n) =2[2 T(n/4) + 8] +8 (2)
8,Step2: Dotheithsubstitution:
T(n)=2iT(n/2i)+8(2i-1+...+22+2+1)
i1
=2iT(n/2i)+8( 2k)
k0
=2i T(n/2i)+8(2i-1)(theformulaforgeometricseries)Step3:
Defineiin termsofn:
Ifn=2i,theni=lognso,T(n/2 i)=T(1)=2
T(n)=2iT(n/2i)+8(2i-1)
=nT(1)+ 8(n-1)
=2n +8n-8=10n -8
function:T(n) =10n-8isO(n)
Example2.13.4. IfKisanonnegativeconstant,thenprovethattherecurrence
k n ,n1
T(n)
3.Tk .n ,n1
2
hasthefollowingsolution(fornapowerof2)
T(n)3k.nlog23-2k.n
Solution:
n
Assumingn>1,wehaveT(n)=3T K.n (1)
2
n
Substitutingn
forninequation(1),weget
2
n n n
T 3T k (2)
2 4 2
n
Substitutingequation(2)forT inequation(1)
2
47
n n
T(n)=33T k k.n
4 2
n 3
T(n)32T k.nk.n (3)
4 2
n
Substitutingn
fornequation(1)
4
n n n
T 3T k (4)
4 8 4
n
Substitutingequation(4)forT
inequation(3)
4
n n 3
T(n)3 2 3 k.n k.n
T k
8 4 2
n 9 3
3 T
3 k.nk.n (5)
k.n
84 2
Continuinginthismannerandsubstitutingn=2 i,weobtain
n 3i1 9kn 3
T(n) 3i T
k.n ................... k. nk.n
2i 2i 1 4 2
i
3 1
n1 rn1
n 2
T(n)3iT k.n
2
i
3
1
as
i0
ri
r1
2
n 3
=3iT 2. i
k.n2kn (6)
2i 2
Asn=2i,theni=log2nandbydefinitionasT(1)=k
3i
T(n)3ik2. .kn2kn
n
=3i 3k2kn
= 3k. 3log 2n 2 kn
=3knlog232kn
Example2.13.5. TowersofHanoi
48
The Towers of Hanoi is a game played with a set of donut shaped disks stacked
onone of three posts. The disks are graduated in size with the largest on the
bottom.The objective of the game is to transfer allthe disks frompostB to post
Amovingone disk at a time without placing a larger disk on top of a smaller one.
What is theminimumnumberofmovesrequiredwhentherearendisks?
In order to visualize the most efficient procedure for winning the game consider
thefollowing:
1. Move the first n-1 disks, as per the rules in the most
efficientmannerpossible,frompostBto postC.
2. Movetheremaining,largestdiskfrompostBtopostA.
3. Move the n - 1 disks, as per the rules in the most efficient manner
possible,frompostCtopostA.
Let mn be the number of moves required to transfer n disks as per the rules in
themostefficientmannerpossiblefromonepostto another.Step1 requiresmovingn
- 1 disks or mn-1 moves. Step 2 requires 1 move. Step 3 requires m n-1 moves
again.Wehavethen,
Because only one move is required to win the game with only one disk, the
initialcondition for this sequence is m1 = 1. Now we can determine the number of
movesrequired to win the game, in the most efficient manner possible, for any
number ofdisks.
m1= 1
m2= 2(1)+ 1= 3
m3= 2(3)+ 1= 7
m4= 2(7)+ 1= 15
m5=2(15)+1=31
m6=2(31)+1=63
m7=2(63)+1=127
m1=1
m2=2(1)+1 =2+1
m3=2(2+1)+1 =22+2+1
m4=2(22+2+1)+1 =23+22+2+1
m5=2(23+22+2+1)+1 =24+23+22+2+1
49
m6=2(24+23+22+2+1)+1 =25+24+23+22+2+1
m7=2(25+24+23+22+2+1)+1=26+25+24+23+22+2+1
Soweguessanexplicitformula:
Mk=2k-1+2k-2+......+22+2+1
ourformulaisthen
n1 k 2 n1 2n1
m
k 2
k0
21
ThisisnothingbutO(2n)
Thusprovidingan explicitformulaforthenumberofstepsrequiredtowintheTowers
ofHanoiGame.
Example2.13.6 Solvetherecurrencerelation
T(n)=5T(n/5)+n/lognUsingiterationmethod,
T(n)=25T(n/25)+n/log (n/5)+n/logn
=125T(n/125)+n/log(n/25)+n/log(n/5)+n/logn
Whenn=5k
=cn+log52nlog(k)
=cn+log52nlog (logn)
=(n log(logn))
Example2.13.7.
SolvetherecurrencerelationT(n)=3T(n/3+5)+n/2Usethesu
50
bstitutionmethod,guessthatthesolutionisT(n)=O(nlogn)
51
We need to prove T (n) < = c n log n for some c and all n >
no.Substitutec(n/3+5)log(n/3+5)forT(n/3+5)intherecurrenceT(n)<=3*c(
n/3+5)*(log(n/3+5))+n/2
If we take n0 as 15, then for all n > n0, n/3+5 <= 2n/3,
soT(n)<=(cn+15c)*(logn/3+log2)+n/2
<=cnlogn-(cn(log3-1)+n/2–15clogn-15c(log3-1)
<=cnlogn,bychoosinganappropriatelylargeconstantcWhichimplies
Similarly, by guessing T (n) >= c1 n log n for some c1 and all n > n0 and
substitutingintherecurrence,weget.
>=c1nlogn+n(0.5+c1(1-log3)+15c1+15c1(logn-log3)by choosing an
appropriately small constant c1 (say c1 = 0.01) and for all n > 3T(n)>=c1n
logn
n.Usingiterationmethod,
=8T(n/8)+n/log(n/4)+n/log(n/2)+n/logn
Whenn=2k
=cn+ nlog(k)
=cn+nlog (logn)
52
=(n log(logn))
Example2.13.9: Solvetherecurrencerelation:
T(n)=T(n/2)+T(n/4)+T(n/8)+n
Usethesubstitutionmethod,guessthatthesolutionisT(n)=O(nlogn).Weneedtoprove
T(n)<=cnlognforsomecandalln>no.
Substitutingtheguessinthegivenrecurrence,weget
T(n)<=c(n/2)log(n/2)+c(n/4)log(n/4)+c(n/8)log(n/8)+n
<=c(n/2)(logn-1)+c(n/4)(logn-2)+c(n/8)(logn-3)+n
<=cnlogn(1/2+1/4+1/8)–cn/2–cn/2–3cn/8+n
<=cnlogn
Example2.13.10:Solvetherecurrencerelation:T(n)=28T(n/3)+cn 3
nlog b nlog3
a 2
ax
Accordingtothelawofindices: ,wecanwriteax-y
ay
cn3 28
Itcanbewrittenas:h (n)=
O(nr)wherer<0f(n)forthesefromthetablecanbetake
nO(1)
T(n)nlog28 3 T(1)h(n)
28 T(1)0(1)nlog 28
nlog3 3
53
Example2.13.12:SolvetherecurrencerelationT(n)=T (n)+c. n>4
54
T(n)=T(n1/2)+C
T(n)1/2=T(n1/2)1/2+CT
(n1/2) = T (n1/4)+ C +
CT(n)=T(n1/4)+2c
T(n)=T(n1/2)+3c
=T(n1/2i)+ic
= T (n1/n) C log2
nT nn Clog2 n=(logn)
Example2.13.13:Solvetherecurrencerelation
1
n4
T(n)
2T(n)logn n4
T(n)
2 2T(n1/2)1/2logn logn
=4T(n1/4)+2logn1/2+lognT(n1/4)=
2T(n1/2)1/4+logn1/4
T(n)
42T n1/2
1/4
logn1/4 2logn 1/4logn
=8T(n1/8)+4logn1/4+2logn1/2+lognT(n1/8)=2T(
n1/2)1/8+logn1/8
T(n) 4
8 2T(n1/16)logn1/8 logn1/42logn1/2logn
=16T(n1/6)+8logn1/8+4logn1/4+2logn1/2+logn
i 1/2i1 1/2i2 1/2i3 i4
=2iT(n1/2 )2i1logn 2i2logn 2i3logn 2i4logn1/2
n
=2iT n1/ 2
i
ik
2ik logn1/2
k1
nT n1/n
n
lognk/n
k
2
=(logn)
55
56
Chapter
3
DivideandConquer
GeneralMethod
Divide and conquer strategy is as follows: divide the problem instance into two
ormore smaller instances of the same problem, solve the smaller instances
recursively,and assemble the solutions to form a solution of the original instance. The
recursionstops when an instance is reached which is too small to divide. When
dividing theinstance, one can either use whatever division comes most easily to hand
or investtimeinmakingthedivisioncarefullysothattheassemblyissimplified.
Divideandconqueralgorithmconsistsoftwoparts:
Traditionally, routines in which the text contains at least two recursive calls are
calleddivide and conquer algorithms, while routines whose text contains only one
recursivecallarenot.Divide–and–conquerisaverypowerfuluseofrecursion.
ControlAbstractionofDivideandConquer
DANDC(P)
{
ifSMALL(P)thenreturnS(p);else
{
divide p into smaller instances p1, p2, …. Pk, k
1;applyDANDCtoeachofthesesubproblems;
return(COMBINE(DANDC(p 1),DANDC(p2),….,DANDC(pk));
}
}
SMALL (P) is a Boolean valued function which determines whether the input size
issmall enough so that the answer can be computed without splitting. If this is
sofunction „S‟ is invoked otherwise, the problem „p‟ into smaller sub problems.
Thesesubproblemsp1,p2,...,pkaresolvedbyrecursiveapplicationofDANDC.
57
If the sizes of the two sub problems are approximately equal then the
computingtimeofDANDCis:
g(n) nsmalloth
T(n)=
2T(n/2)f(n) erwise
Where,T(n)isthetimeforDANDCon„n‟inputs
g(n)isthetimetocompletetheanswerdirectlyforsmallinputsandf(n)
isthetimeforDivideandCombine
BinarySearch
If we have „n‟ records which have been ordered by keys so that x 1 < x2 < … < xn
.When we are given a element „x‟, binary search is used to find the
correspondingelement from the list. In case „x‟ is present, we have to determine a
value „j‟ suchthat a[j] = x (successful search). If „x‟ is not in the list then j is to set
to zero (unsuccessfulsearch).
In Binary search we jump into the middle of the file, where we find key a[mid],
andcompare„x‟witha[mid].Ifx=a[mid]thenthedesiredrecordhasbeenfound.Ifx<a[mid]t
hen„x‟mustbeinthatportionofthefilethatprecedesa[mid],ifthereatall. Similarly, if
a[mid] > x, thenfurther search is only necessary inthat past ofthe file which follows
a[mid]. If we use recursive procedure of finding the middle keya[mid]oftheun-
searchedportionofafile,theneveryun-successfulcomparisonof
„x‟witha[mid]willeliminateroughlyhalftheun-searchedportionfromconsideration.
Since the array size is roughly halved often each comparison between„x‟and a[mid],
and since an array of length „n‟ can be halved only about log 2n times
beforereachingatriviallength,theworstcasecomplexityofBinarysearchisaboutlog 2n
Algorithm
AlgorithmBINSRCH(a,n,
x)
// array a(1:n)ofelements in increasingorder,n0,
// determinewhether„x‟ispresent,andifso,setjsuchthatx=a(j)
// elsereturnj
{
low :=1 ; high :=n
;while(low <high)do
{
mid:=|(low+high)/2|
if (x < a [mid]) then high:=mid –
1;elseif(x>a[mid]) thenlow:=mid+1
elsereturnmid;
}
return0;
}
low and high are integer variables such that each time through the loop either „x‟
isfoundorlowisincreasedbyatleastoneorhighisdecreasedbyatleastone.Thuswe have two
sequences of integers approaching each other and eventually low willbecome greater
than high causing termination in a finite number of steps if „x‟ is notpresent.
58
ExampleforBinarySearch
Letusillustratebinarysearchonthefollowing9elements:
Index 1 2 3 4 5 6 7 8 9
Elements -15 -6 0 7 9 23 54 82 101
Thenumberofcomparisonsrequiredforsearchingdifferentelementsisasfollows:
Numberofcomparisons=4
Continuing in this manner the number of element comparisons needed to find each
ofnineelementsis:
Index 1 2 3 4 5 6 7 8 9
Elements -15 -6 0 7 9 23 54 82 101
Comparisons 3 2 3 4 1 3 2 3 4
Noelementrequiresmorethan4comparisonstobefound.Summingthecomparisonsneeded
tofindallnine
itemsanddividingby9,yielding25/9orapproximately2.77comparisonspersuccessfulsearcho
ntheaverage.
There are ten possible ways that an un-successful search may terminate
dependinguponthevalueofx.
59
Ifx<a[1],a[1]<x<a[2],a[2]<x<a[3],a[5]<x<a[6],a[6]<x<a[7]or
a[7] < x < a[8] the algorithm requires 3 element comparisons to determine that
„x‟is not present. For all of the remaining possibilities BINSRCH requires 4
elementcomparisons. Thus the average number of element comparisons for an
unsuccessfulsearchis:
(3+3+3+4+4+3+3+3+4+4)/10=34/10=3.4
Successfulsearches un-successfulsearches
Θ(1), Θ(logn), Θ(logn) Θ(logn)
Best average worst best,averageandworst
Analysisforworstcase
LetT(n)bethetimecomplexityofBinarysearchThealgorit
Therefore,
T(0) = 0
T(n) = 1 ifx=a[mid]
= 1+T([(n+1)/2]–1) ifx<a[mid]
= 1+T(n–[(n+1)/2]) ifx>a[mid]
Let us restrict „n‟ to values of the form n = 2K– 1, where „k‟ is a non-
negativeinteger. The array always breaks symmetrically into two equal pieces plus
middleelement.
2K – 1 -1 2K – 1 -1
2K 1
n1 =2K–1
Algebraicallythisis 2K 11 for K>1
2 2
Giving,
T(0) = 0
T(2k–1) = 1 ifx=a[mid]
K-1
= 1+T(2 –1) ifx<a[mid]
k-1
= 1+T(2 –1) ifx>a[mid]
Intheworstcasethetestx=a[mid]alwaysfails,sow(0)=0
w(2k–1)=1+w(2k-1–1)
60
Thisisnowsolvedbyrepeatedsubstitution:
w(2k–1) = 1+w(2k-1–1)
= 1+[1+w(2k-2–1)]
= 1+[1+[1+w(2 k-3–1)]]
= .... .. ..
= .... .. ..
= i+w(2k-i–1)
1=n,soK=log2(n+1),so
Although it might seem that the restriction of values of „n‟ of the form 2 K–1
weakenstheresult.Inpracticethisdoesnotmatterverymuch,w(n)isamonotonicincreasing
function of „n‟, and hence the formula given is a good approximation
evenwhen„n‟isnot of theform2K–1.
ExternalandInternalpathlength:
The lines connecting nodes to their non-empty sub trees are called edges. A non-
empty binary tree with n nodes has n–1 edges. The size of the tree is the number
ofnodes itcontains.
When drawing binary trees, it is often convenient to represent the empty sub
treesexplicitly,sothattheycanbeseen.Forexample:
b c
The tree given above in which the empty sub trees appear as square nodes is
asfollows:
The square nodes are called as external nodes E(T). The square node version
issometimes called an extended binary tree. The round nodes are called internal
nodesI(T).A binary treewithn internalnodeshasn+1externalnodes.
The height h(x) of node „x‟ is the number of edges on the longest path leading
downfrom „x‟ in the extended tree. For example, the following tree has heights
writteninsideitsnodes:
61
3
1 2
0 0 1 0
0 0
The depth d(x) of node „x‟ is the number of edges on path from the root to „x‟. It
isthe number of internal nodes on this path, excluding „x‟ itself. For example,
thefollowingtreehasdepthswritteninsideitsnodes:
0
1 1
2 2 2 2
3 3
TheinternalpathlengthI(T)isthesumofthedepthsoftheinternalnodesof„T‟:
I(T) = d(x)
xI(T)
TheexternalpathlengthE(T)isthesumofthedepthsoftheexternalnodes:
E(T) = d(x)
x E(T)
Forexample,thetreeabovehasI(T)=4andE(T)=12.
AbinarytreeTwith„n‟internalnodes,willhaveI(T)+2n=E(T)externalnodes.Abinarytre
ecorrespondingtobinarysearchwhenn=16is
4 12
2 6 10 14
1 3 5 7 9 11 13 15
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 16
Externalsquarenodes,whichleadforunsuccessfulsearch.
search.C'Nbetheaveragenumberofcomparisonin anunsuccessfulsearch.
62
Thenwehave,
internalpathlengthoftree
CN1
N
ExternalpathlengthoftreeN1
C'N
1
CN 1 C'N1
N
Externalpathlengthisalways2Nmorethantheinternalpathlength.
MergeSort
Thisstrategyissosimple,andsoefficientbuttheproblemhereisthatthereseemsto be no
easy way to merge two adjacent sorted arrays together in place (The
resultmustbebuild upinaseparatearray).
The fundamental operation in this algorithm is merging two sorted lists. Because
thelists are sorted, this can be done in one pass through the input, if the output is
put inathirdlist.
The basic merging algorithm takes two input arrays „a‟ and ‟b‟, an output array
„c‟,and three counters, a ptr, b ptr and c ptr, which are initially set to the beginning
oftheir respective arrays. The smaller ofa[a ptr] and b[b ptr] is copied to the
nextentry in „c‟, and the appropriate counters are advanced. When either input list
isexhausted,theremainderoftheotherlistiscopiedto„c‟.
To illustrate how merge process works. For example, let us consider the array
„a‟containing 1, 13, 24, 26 and „b‟ containing 2, 15, 27, 38. First a comparison is
donebetween1and2.1iscopiedto„c‟.Incrementaptrandcptr.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
1 13 24 26 2 15 27 28 1
h jp ip
ptr tr tr
andthen2and13arecompared.2isaddedto„c‟.Incrementbptrandcptr.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
1 13 24 26 2 15 27 28 1 2
h jp ip
ptr tr tr
63
then13and15arecompared.13isaddedto„c‟.Incrementaptrandcptr.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
1 13 24 26 2 15 27 28 1 2 13
h jp ip
ptr tr tr
24and15arecompared.15isaddedto„c‟.Incrementbptrandcptr.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
1 13 24 26 2 15 27 28 1 2 13 15
h jp ip
ptr tr tr
24and27arecompared.24isaddedto„c‟.Increment aptrandcptr.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
1 13 24 26 2 15 27 28 1 2 13 15 24
h jp ip
ptr tr tr
26and27arecompared.26isaddedto„c‟.Increment aptrandcptr.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
1 13 24 26 2 15 27 28 1 2 13 15 24 26
h jp ip
ptr tr tr
Asoneofthelistsisexhausted.Theremainderofthebarrayisthencopiedto„c‟.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
1 13 24 26 2 15 27 28 1 2 13 15 24 26 27 28
hp jp ipt
tr tr r
Algorithm
AlgorithmMERGESORT(low,high)
//a(low:high)isaglobalarraytobesorted.
{
if(low<high)
{
mid:=(low+high)/2
//findswheretosplitthesetME
RGESORT(low,mid) //sort one
subsetMERGESORT(mid+1,high)//sorttheothersubset
MERGE(low,mid,high) //combinetheresults
}
}
64
AlgorithmMERGE (low,mid,high)
//a(low:high)isaglobalarraycontainingtwosortedsubsets
//in a(low:mid)andina(mid +1:high).
//Theobjective istomerge thesesortedsetsintosinglesorted
//setresidingina(low:high).AnauxiliaryarrayBisused.
{
h :=low; i := low; j:= mid +
1;while((h <mid)and(J<high))do
{
if(a[h]<a[j])then
{
b[i]:=a[h]; h:=h+1;
}
else
{
b[i]:=a[j];j:=j+1;
}
i:=i+1;
}
if(h >mid)then
for k:=jtohighdo
{
b[i]:=a[k];i:=i+1;
}
else
for k:=htomiddo
{
b[i]:=a[K];i:=i+l;
}
fork:=lowtohighdo
a[k]:=b[k];
}
Example
7,2,9,4|3,8,6,11,2,3,4,6,7,8, 9
7,2|9,42,4,7,9 3,8|6,11,3,6,8
65
TreeCallsofMERGESORT(1,8)
The following figure represents the sequence of recursive calls that are produced
byMERGESORT when it is applied to 8 elements. The values in each node are the
valuesofthe parameterslowandhigh.
1,8
1,4 5,8
TreeCallsofMERGE()
ThetreerepresentationofthecallstoprocedureMERGEbyMERGESORTisasfollows:
1,2,4 5,6,8
1,4,8
AnalysisofMergeSort
Wewillassumethat„n‟isapowerof2,sothatwealwayssplitintoevenhalves,sowesolve
forthe casen=2k.
T(1)=1
T(n)=2T(n/2)+n
Thisisastandardrecurrencerelation,whichcanbesolvedseveralways.Wewillsolvebysubstit
utingrecurrencerelationcontinuallyontheright–handside.
Wehave,T(n)=2T(n/2)+n
66
Sincewecansubstituten/2intothismainequation
2T(n/2) = 2(2(T(n/4))+n/2)
= 4T(n/4)+n
Wehave,
T(n/2) = 2T(n/4)+n
T(n) = 4T(n/4)+2n
Again,bysubstitutingn/4intothemainequation,weseethat
4T(n/4) = 4(2T(n/8))+n/4
= 8T(n/8)+n
Sowehave,
T(n/4) = 2T(n/8)+n
T(n) = 8T(n/8)+3n
Continuinginthismanner,weobtain:
T(n) = 2kT(n/2k)+K.n
Asn=2k,K=log2n,substitutingthisintheaboveequation
n
T(n)2log2 k k log n.n
T 2 2
2
=nT(1)+nlogn
= n log n +
nRepresentingthisinOnotation:
T(n)=O(nlogn)
We have assumed that n = 2k. The analysis can be refined to handle cases when
„n‟isnotapowerof2.Theanswerturnsouttobealmostidentical.
Although merge sort‟s running time is O(n log n), it is hardly ever used for
mainmemorysorts.The main problem is that merging two sorted lists requires
linearextra memory and the additional work spent copying to the temporary array
andback, throughout the algorithm, has the effect of slowing down the sort
considerably.TheBestandworstcasetimecomplexityofMergesortisO(nlogn).
Strassen’sMatrixMultiplication:
The usual way to multiply two n x n matrices A and B, yielding result matrix „C‟
asfollows:
67
Thisalgorithmrequiresn 3scalarmultiplication‟s(i.e.multiplicationofsinglenumbers)and
n3scalaradditions.Sowenaturallycannotimproveupon.
We apply divide and conquer to this problem. For example let us considers
threemultiplicationlikethis:
A11 A12 B11 B12 C11 C12
C
A A B B C
21 22 21 22 21 22
Thencijcanbefoundby theusualmatrixmultiplicationalgorithm,
Thisleadstoadivide–and–
conqueralgorithm,whichperformsnxnmatrixmultiplicationbypartitioningthematricesinto
quartersandperformingeight(n/2)x(n/2)matrixmultiplicationsandfour(n/2)x(n/2)matrixad
ditions.
T(1) = 1
T(n) = 8T(n/2)
WhichleadstoT(n)=O(n 3),wherenisthepowerof2.
Strassens insight was to find an alternative method for calculating the C ij,
requiringseven(n/2)x(n/2)matrixmultiplicationsandeighteen(n/2)x(n/2)matrixaddition
sandsubtractions:
B22)Q=(A21+A22)B11
R= A11(B12 – B22)S=
A22(B21- B11)T=
(A11+A12)B22
P +S –T+V
C12 = R +
TC21=Q+S
C22=P +R-Q+U.
Thismethodisusedrecursivelytoperformtheseven(n/2)x(n/2)matrixmultiplications,
then the recurrence equation for the number of scalar multiplicationsperformedis:
68
T(1) = 1
T(n) = 7T(n/2)
Solvingthisforthecaseofn=2 kiseasy:
T(2k) = 7T(2k–1)
= 72T(2k-2)
= -- -- --
= -- -- --
= 7iT(2k–i)
Puti=k
= 7kT(1)
= 7k
Thatis,T(n)= 7log2n
= nlog7
2
log7
= O(n 2) =O(2n.81)
QuickSort
The main reason for the slowness of Algorithms like SIS is that all comparisons
andexchanges between keys in a sequence w1, w2, . . . . , wntake place
betweenadjacent pairs. In this way it takes a relatively long time for a key that is
badly out ofplaceto work itsway intoitsproperposition in thesortedsequence.
Hoarehisdevisedaveryefficientwayofimplementingthisideaintheearly1960‟sthat
improves the O(n2) behavior of SIS algorithm with an expected performance thatisO(n
logn).
Inessence, the quick sortalgorithm partitions the original array byrearranging itinto
two groups. The first group contains those elements less than some arbitrarychosen
value taken from the set, and the second group contains those elementsgreater
thanorequaltothechosenvalue.
The chosen value is known as the pivot element. Once the array has been
rearrangedin this way with respect to the pivot, the very same partitioning is
recursively
appliedtoeachofthetwosubsets.Whenallthesubsetshavebeenpartitionedandrearranged,
theoriginal arrayissorted.
Thefunctionpartition()makesuseoftwopointers„i‟and„j‟whicharemovedtowardeachothe
rin thefollowingfashion:
Repeatedlyincreasethepointer„i‟untila[i]>=pivot.
Repeatedlydecreasethepointer„j‟untila[j]<=pivot.
69
Ifj>i,interchangea[j]witha[i]
Repeat the steps 1, 2 and 3 till the „i‟ pointer crosses the „j‟ pointer. If
„i‟pointer crosses „j‟ pointer, the position for pivot is found and place
pivotelementin„j‟pointerposition.
Itterminateswhentheconditionlow>=highissatisfied.Thisconditionwillbesatisf
iedonlywhenthearrayiscompletelysorted.
Here we choose the first element as the „pivot‟. So, pivot = x[low]. Now
itcalls the partition function to find the proper position j of the
elementx[low]i.e.pivot.Then wewill havetwosub-arraysx[low],x[low+1],....
.. .x[j-1]andx[j+1], x[j+2], x[high].
It callsitselfrecursivelytosorttheleftsub-arrayx[low],x[low+1], .. . ..
. . x[j-1] between positions low and j-1 (where j is returned by
thepartitionfunction).
Algorithm
AlgorithmQUICKSORT(l
ow,high)
/*sortstheelementsa(low),.... .,a(high)whichresideintheglobalarray A(1
:n) into ascending order a (n + 1) is considered to be defined and must be
greaterthan allelementsin a(1:n); A(n +1) =+*/
{
iflow<highthen
{
j:=PARTITION(a,low,high+1);
//JisthepositionofthepartitioningelementQUICKSORT(low, j–
1);
QUICKSORT(j+1,high);
}
}
AlgorithmPARTITION(a,m,p)
{
Va(m);im; jp; //A(m)isthepartitionelementdo
{
loopi:=i+1untila(i)>v // i moves left to
rightloopj:=j–1untila(j)<v // p moves right to
leftif(i< j)thenINTERCHANGE(a, i,j)
}while(i>j);
a[m]:=a[j];a[j]:=V;//thepartitionelement belongsatpositionPreturnj;
}
70
AlgorithmINTERCHANGE(a,i,j)
{
P:=a[i];
a[i] :=
a[j];a[j]:=p
;
}
Example
Select first element as the pivot element. Move „i‟ pointer from left to right in
searchof an element larger than pivot. Move the „j‟ pointer from right to left in
search of anelement smaller than pivot. If such elements are found, the elements are
swapped.This process continues till the „i‟ pointer crosses the „j‟ pointer. If „i‟ pointer
crosses „j‟pointer, the position for pivot is found and interchange pivot and element
at „j‟position.
Letusconsiderthefollowingexamplewith13elementstoanalyzequick sort:
1 2 3 4 5 6 7 8 9 10 11 12 13 Remarks
38 08 16 06 79 57 24 56 02 58 04 70 45
pivot i j swapi&j
04 79
i j swapi&j
02 57
j i
swap
(24 08 16 06 04 02) 38 (56 57 58 79 70 45)
pivot&
j
swap
pivot j,i
pivot&
j
(02 08 16 06 04) 24
pivot, swap
i
j pivot&
j
02 (08 16 06 04)
pivot i j swapi&j
04 16
j i
swap
(06 04) 08 (16)
pivot&
j
pivot,
i
j
swap
(04) 06
pivot&
j
04
pivot,
j,i
16
71
pivot,
j,i
(02 04 06 08 16 24) 38
(56 57 58 79 70 45)
72
pivot i j swapi&j
45 57
j i
swap
(45) 56 (58 79 70 57)
pivot&
j
45
pivot, swap
j,i pivot&
j
(58 79 57)
pivot i 70 j swapi&j
57 79
j i
swap
(57) 58 (70 79)
pivot&
j
57
pivot,
j,i
(70 79)
pivot, swap
i
j pivot&
j
70
79
pivot,
j,i
(45 56 57 58 70 79)
02 04 06 08 16 24 38 45 56 57 58 70 79
AnalysisofQuickSort:
Like merge sort, quick sort is recursive, and hence its analysis requires solving
arecurrence formula. We will do the analysis for a quick sort, assuming a random
pivot(andnocut off forsmallfiles).
The running time of quick sort is equal to the running time of the two recursive
callsplus the linear time spent in the partition (The pivot selection takes only
constanttime).Thisgivesthe basicquicksortrelation:
WorstCaseAnalysis
The pivot is the smallest element, all the time. Then i=0 and if we ignore
T(0)=1,whichisinsignificant,the recurrenceis:
73
Usingequation–(1)repeatedly,thus
74
T(n–1) = T(n –2)+ C(n –1)
-- - -- - --
Addingupalltheseequationsyields
n
T(n)T(1)
i2
i
=O(n2) - (3)
BestCaseAnalysis
In the best case, the pivot is in the middle. To simply the math, we assume that
thetwo sub-files are each exactly half the size of the original and although this gives
aslight over estimate, this is acceptable because we are only interested in a Big –
ohanswer.
Dividebothsidesbyn
Substituten/2for„n‟inequation(5)
Substituten/4for„n‟inequation(6)
T(2) T(1)
C - (8)
2 1
Weaddalltheequationsfrom4to8andnotethattherearelognofthem:
T(n)
Clogn - (9)
n T(
1)
1
Whichyields,T(n)=Cnlogn+n= O(nlogn) -
(10)Thisisexactlythesa
75
meanalysisasmergesort,hencewegetthesameanswer.
76
AverageCaseAnalysis
T(n)=comparisonsforfirstcallonquicksort
+
{Σ1<=nleft,nright<=n[T(nleft)+T(nright)]}n=(n+1)+2[T(0)+T(1)+T(2)+
-----+T(n-1)]/n
Subtractingbothsides:
Usingthemethodofsubsititution:
T(n)/(n+1) = 2/(n+1)+T(n-1)/n
T(n-1)/n = 2/n+T(n-2)/(n-1)
T(n-2)/(n-1) = 2/(n-1)+T(n-3)/(n-2)
T(n-3)/(n-2) = 2/(n-2)+T(n-4)/(n-3)
. .
. .
T(3)/4 = 2/4+T(2)/3
T(2)/3 = 2/3 + T(1)/2 T(1)/2 =2/2 +T(0)
Addingbothsides:
T(n)/(n+1)+[T(n-1)/n+T(n-2)/(n-1)+ ------------------ +T(2)/3+T(1)/2]
=[T(n-1)/n+T(n-2)/(n-1)+ ----------------- + T(2)/3 + T(1)/2]+T(0)+
[2/(n+1)+2/n +2/(n-1) + ------------- +2/4 +2/3]
Cancellingthecommonterms:
T(n)/(n+1)= 2[1/2 +1/3+1/4+ -------------- +1/n+1/(n+1)]
T(n)=(n+1)2[ 2kn1
1/k
=2(n+1)[ ]
=2(n+1)[log(n+1) –log2]
=2nlog(n+1)+log(n+1)-2n log2–log2
T(n)=O(nlogn)
3.8. Straightinsertionsort:
Straight insertion sort is used to create a sorted list (initially list is empty) and
ateachiterationthetopnumberonthesortedlistisremovedandputintoitsproper
77
place inthe sortedlist.This isdone bymoving alongthe
sortedlist,fromthesmallesttothelargestnumber,untilthecorrectplaceforthenew
numberislocated
i.e. until all sorted numbers with smaller values comes before it and all those
withlarger values comes after it. For example, let us consider the following 8
elements forsorting:
Index 1 2 3 4 5 6 7 8
Elements 27 412 71 81 59 14 273 87
Solution:
Iteration7: unsorted 87
Sorted 14 27 59 71 81 87 273 412
78
Chapter
4
GreedyMethod
GENERALMETHOD
Greedy is the most straight forward design technique. Most of the problems have
ninputs and require us to obtain a subset thatsatisfies some constraints. Any subsetthat
satisfies these constraints is called a feasible solution. We need to find a
feasiblesolution that either maximizes or minimizes the objective function. A feasible
solutionthatdoesthisiscalled anoptimalsolution.
For the problems that make decisions by considering the inputs in some order,
eachdecision is made using an optimization criterion that can be computed using
decisionsalready made. This version of greedy method is ordering paradigm. Some
problems likeoptimal storage on tapes, optimal merge patterns and single source
shortest path arebased on orderingparadigm.
CONTROLABSTRACTION
AlgorithmGreedy(a,n)
//a(1:n)containsthe„n‟inputs
{
solution:=; //initializethesolutiontoemptyfor
i:=1 tondo
{
x:=select(a);
iffeasible(solution,x)then
solution:=Union(Solution,x);
}
returnsolution;
}
Procedure Greedy describes the essential way that a greedy based algorithm will
look,once a particular problem is chosen and the functions select, feasible and union
areproperlyimplemented.
The function select selects an input from „a‟, removes it and assigns its value to
„x‟.Feasible is a Boolean valued function, which determines if „x‟ can be included into
thesolutionvector.ThefunctionUnioncombines„x‟withsolutionandupdatestheobjectivefunc
tion.
79
KNAPSACKPROBLEM
Letusapplythegreedymethodtosolvetheknapsackproblem.Wearegiven„n‟objectsandaknapsac
k.Theobject„i‟hasaweightwiandtheknapsackhasacapacity
„m‟.Ifafractionxi,0<xi<1ofobjectiisplacedintotheknapsackthenaprofitofpixiisearned.Theo
bjectiveistofill theknapsack thatmaximizesthetotalprofitearned.
Sincetheknapsackcapacityis„m‟,werequirethetotalweightofallchosenobjectstobeatmost
„m‟. Theproblemisstatedas:
n
maximizes p x i i
i1
n
Theprofitsandweightsarepositivenumbers.
Algorithm
If the objects are already been sorted into non-increasing order of p[i] / w[i] then
thealgorithmgivenbelowobtainssolutionscorrespondingtothisstrategy.
AlgorithmGreedyKnapsack(m,n)
//P[1:n]andw[1:n]containtheprofitsandweightsrespectivelyof
//Objectsorderedsothatp[i] /w[i]>p[i+1] / w[i+1].
//mistheknapsacksizeandx[1:n]isthesolutionvector.
{
for i:=1tondox[i]:=0.0 // initialize
xU:=m;
fori:=1tondo
{
if(w(i)>U) thenbreak;
x[i]:=1.0;U:=U –w[i];
}
if(i<n)thenx[i]:=U/w[i];
}
Runningtime:
Example:
Consider the following instance of the knapsack problem: n = 3, m = 20, (p 1, p2, p3)
=(25,24,15) and (w1,w2,w3)=(18,15,10).
80
1. First,wetrytofilltheknapsackbyselectingtheobjectsinsomeorder:
x1 x2 x3 wixi pixi
1/2 1/3 1/4 18x1/2+15x1/3+10x1/4 25x1/2+24x1/3+15x1/4=
=16.5 24.25
2. Select the object with the maximum profit first (p = 25). So, x 1 = 1 and
profitearned is 25. Now, only 2 units of space is left, select the object with next
largestprofit(p =24).So,x2=2/15
x1 x2 x3 wixi pixi
1 2/15 0 18x1+15x2/15 =20 25x1+24x 2/15=28.2
3. Consideringtheobjectsintheorderofnon-decreasingweightsw i.
x1 x2 x3 wixi pixi
0 2/3 1 15x2/3+ 10x1=20 24x2/3+15x1=31
4. Consideredtheobjectsintheorderoftheratiopi/wi.
Sort the objects in order of the non-increasing order of the ratio pi / xi. Select
theobject with the maximum pi / xi ratio, so, x2 = 1 and profit earned is 24. Now, only
5units of space is left, select the object with next largest p i / xi ratio, so x3 = ½ and
theprofitearned is7.5.
x1 x2 x3 wixi pixi
0 1 1/2 15x1+ 10x1/2=20 24x1+ 15x 1/2=31.5
Thissolutionistheoptimalsolution.
4.4. OPTIMALSTORAGEONTAPES
There are „n‟ programs that are to be stored on a computer tape of length „L‟.
Eachprogram „i‟ is of length li, 1 ≤ i ≤ n. All the programs can be stored on the tape if
andonlyifthesumofthelengthsoftheprogramsisatmost„L‟.
We shall assume that whenever a program is to be retrieved from this tape, the tape
isinitiallypositionedatthefront.Iftheprograms arestoredintheorder i=i1,i2,.. ...
,in,thetimet J neededtoretrieveprogramiJ isproportionalto
l
1k j
ik
81
If all the programs are retrieved equally often then the expected or mean retrieval
time(MRT)is:
1
.
n 1Jn
t
j
For the optimal storage on tape problem, we are required to find the permutation
forthe „n‟ programs so that when they are stored on the tape in this order the MRT
isminimized.
n J
d (I) l ik
J 1 K 1
Example
Letn=3,(l1,l2,l3)=(5,10,3).Thenfindtheoptimalordering?
Solution:
Therearen!=6possibleorderings.Theyare:
OrderingI d(I)
1,2,3 5+(5+10)+(5+10 +3) = 38
1,3,2 5+(5+3)+(5+3+10) = 31
2,1,3 10+(10+5)+(10 +5+3) = 43
2,3,1 10+(10+3)+(10 +3+5) = 41
3,1,2 3+(3+5)+(3+5+10) = 29
3,2,1 3+(3+10)+(3+10+5) = 34
The tape storage problem can be extended to several tapes. If there are m 1
tapes,To, ... ,Tm–1,thentheprograms
m1
aretobe distributedoverthesetapes.
TheobjectiveistostoretheprogramsinsuchawayastominimizeRT.
82
Algorithm:
Thealgorithmforassigningprogramstotapesisasfollows:
AlgorithmStore (n,m)
//nisthenumberofprogramsandmthenumberoftapes
{
j:=0; //nexttapetostoreonfor
i:=1 tondo
{
Print(„appendprogram‟,i,„topermutationfortape‟,j);j:=(j
+1) modm;
}
}
Onanygiventape,theprogramsarestoredinnon-decreasingorderoftheirlengths.
JOBSEQUENCINGWITHDEADLINES
When we are given a set of „n‟ jobs. Associated with each Job i, deadline di > 0
andprofit Pi> 0. For any job „i‟ the profit pi is earned iff the job is completed by
itsdeadline. Only one machine is available for processing jobs. An optimal solution is
thefeasiblesolution with maximumprofit.
Sort the jobs in „j‟ ordered by their deadlines. The array d [1 : n] is used to store
thedeadlines of the order of their p-values. The set of jobs j [1 : k] such that j [r], 1 ≤
r ≤k are the jobs in „j‟ and d (j [1]) ≤ d (j[2]) ≤ . . . ≤ d (j[k]). To test whether J U {i}
isfeasible, we have just to insert i into J preserving the deadline ordering and then
verifythatd[J[r]] ≤r,1≤r≤k+1.
Example:
Letn=4,(P1,P2,P3,P4,)=(100,10,15,27)and(d1d2d3d4)=(2,1,2,1).The
feasiblesolutionsandtheirvaluesare:
83
Algorithm:
AlgorithmGreedyJob(d,J,n)
//J isa setofjobsthatcanbe completedbytheirdeadlines.
{
J:={1};
fori:=2tondo
{
if(alljobsinJU{i}canbecompletedbytheirdeadlines)thenJ:=JU{i};
}
}
OPTIMAL MERGEPATERNS
Given„n‟sortedfiles,therearemanywaystopairwisemergethemintoasinglesortedfile. As,
different pairings require different amounts of computing time, we want todetermine an
optimal (i.e., one requiring the fewest comparisons) way to pair
wisemerge„n‟sortedfilestogether.Thistypeofmergingiscalledas2-waymergepatterns.To
merge an n-record file and an m-record file requires possibly n + m record moves,the
obvious choice choice is, at each step merge the two smallest files together. Thetwo-
waymergepatternscanberepresentedbybinarymergetrees.
Algorithm toGenerateTwo-wayMergeTree:
structtreenode
{
treenode *
lchild;treenode*rchild;
};
AlgorithmTREE(n)
//listisaglobalofnsinglenodebinarytrees
{
for i:=1ton –1do
{
ptnewtreenode
(ptlchild)least(list); // mergetwo
treeswithsmallestlengths
(ptrchild)least(list);
(pt weight) ((pt lchild) weight) + ((pt rchild)
weight);insert(list,pt);
}
returnleast(list); // Thetreeleftin lististhe merge
tree
}
84
Example1:
Suppose we are having three sorted files X1, X2 and X3 of length 30, 20, and 10
recordseach.Mergingofthefilescan be carried out asfollows:
TheSecondcaseisoptimal.
Example2:
Given five files (X1, X2, X3, X4, X5) with sizes (20, 30, 10, 5, 30). Apply greedy rule
tofind optimal way of pair wise merging to give an optimal solution using binary
mergetreerepresentation.
Solution:
20 30 10 5 30
X1 X2 X3 X4 X5
MergeX4andX3toget15recordmoves.CallthisZ1.
X1 X2 Z1 X5
20 30 15 30
5 10
MergeZ1andX1toget35recordmoves.CallthisZ2.
X2 Z2 X5
30 35 30
Z1 15 20 X1
X4 5 10 X3
85
MergeX2andX5toget60recordmoves.CallthisZ3.
Z2 Z3
35 60
Z1 15 20 30 30
X1 X5 X2
5 10
X4 X3
MergeZ2andZ3toget90recordmoves.Thisistheanswer. CallthisZ 4.
Z4
95
Z2 35 60 Z3
Z115 20 30 30
X1 X5 X2
5 10
X4 X3
Thereforethetotalnumberofrecordmovesis15+35+60+95=205.Thisisanoptimalmerge
pattern forthegivenproblem.
HuffmanCodes
Suppose that we have a file only with characters a, e, i, s, t, spaces and new lines,
thefrequency of appearance of a's is 10, e's fifteen, twelve i's, three s's, four t's,
thirteenbanksand onenewline.
Using a standard coding scheme, for 58 characters using 3 bits for each character,
thefilerequires174bitsto represent.Thisisshown in tablebelow.
86
Representingbyabinarytree,thebinarycodeforthealphabetsareasfollows:
a e i s l sp nl
The representation of each character can be found by starting at the root and
recordingthepath.Usea0toindicatetheleftbranchanda1toindicatetherightbranch.
Ifthecharacterciisatdepthdiandoccursfitimes,thecostofthecodeisequalto
d f i i
Withthisrepresentationthetotalnumberofbitsis3x10+3x15+3x12+3x3+3x4+3x13+3x1=174
A bettercodecanbeobtainedbywith thefollowingrepresentation.
nl
a e i s l sp
The basic problem is to find the full binary tree of minimal total cost. This can be
donebyusing Huffman coding(1952).
Huffman'sAlgorithm:
Example:
Theinitialforestwiththeweightofeachtreeisasfollows:
10 15 12 3 4 13 1
a e i s t sp nl
87
The two trees with the lowest weight are merged together, creating the forest,
theHuffman algorithm after the first merge with new root T 1 is as follows: The total
weightofthenewtreeisthesumoftheweightsoftheoldtrees.
10 15 12 4 13 4
a e i t sp T1
s nl
We again select the two trees of smallest weight. This happens to be T 1 and t,
whicharemergedintoanewtreewith root T2andweight8.
10 15 12 13 8
a e i sp T2
T1 t
s nl
In next step we merge T2 and a creating T3, with weight 10+8=18. The result of
thisoperationin
15 12 13 18
e i sp T3
T2 a
T1 t
s nl
After third merge, the two trees of lowest weight are the single node trees
representingiandtheblankspace.These treesmerged intothenewtreewith rootT 4.
15 25 18
e T4 T3
i sp T2 a
T1 t
s nl
88
ThefifthstepistomergethetreeswithrootseandT 3.Theresultsofthisstepis
25 33
T4 T5
i sp T3 e
T2 a
T1 t
s nl
Finally, the optimal tree is obtained by merging the two remaining trees. The
optimaltrees with rootT6is:
T6
0 1
T5 T4
0 1 0 1
T3 e i sp
0 1
T2 a
0 1
T1 t
0 1
s nl
The full binary tree of minimal total cost, where all characters are obtained in
theleaves, usesonly146bits.
A 001 10 30
E 01 15 30
I 10 12 24
S 00000 3 15
T 0001 4 16
Space 11 13 26
Newline 00001 1 5
Total: 146
89
GRAPHALGORITHMS
BasicDefinitions:
Graph G is a pair (V, E), where V is a finite set (set of vertices) and E is a
finitesetofpairsfrom V(setofedges).Wewilloftendenote n:=|V|,m:=|E|.
RepresentationofGraphs:
ConsidergraphG=(V,E),whereV={v 1,v2,….,vn}.
1, if(vi,vj)E,
ai,j
0, otherwise
Where default is some sensible value based on the meaning of the weight
function(for example, if weight function represents length, then default can be ,
meaningvaluelargerthananyothervalue).
Adjacency List: An array Adj [1 . . . . . . . n] of pointers where for 1 < v < n, Adj
[v]points to a linked list containing the vertices which are adjacent to v (i.e. the
verticesthat can be reached from v by a single edge). If the edges have weights then
theseweightsmayalsobestoredin thelinked listelements.
90
PathsandCycles:
Apathisasequenceofvertices(v1,v2,......,vk),whereforalli,(vi,vi+1)E.Apath is
simpleifallverticesinthepath aredistinct.
A(simple)cycleisasequenceofvertices(v1,v2,......,vk,vk+1=v1),whereforalli,(vi,vi+1) Eand
allverticesin thecyclearedistinctexcept pairv1,vk+1.
SubgraphsandSpanningTrees:
Subgraphs:AgraphG‟=(V‟,E‟)isasubgraphofgraphG=(V,E)iffV‟VandE‟
E.
The undirected graph G is connected, if for every pair of vertices u, v there exists
apath from u to v. If a graph is not connected, the vertices of the graph can be
dividedinto connected components. Two vertices are in the same connected
component ifftheyare connectedbyapath.
Lemma1:LetTbeaspanningtreeofagraphG.Then
1. AnytwoverticesinTareconnectedbyauniquesimplepath.
2. Ifanyedge isremovedfromT,thenTbecomesdisconnected.
3. IfweaddanyedgeintoT,thenthenew graphwillcontain acycle.
4. NumberofedgesinTisn-1.
MinimumSpanningTrees(MST):
A spanning tree for a connected graph is a tree whose vertex set is the same as
thevertex set of the given graph, and whose edge set is a subset of the edge set of
thegivengraph.i.e.,anyconnectedgraphwillhaveaspanningtree.
Weight of a spanning tree w (T) is the sum of weights of all edges in T. The
Minimumspanningtree(MST)isaspanningtreewiththesmallestpossibleweight.
91
G:
AgraphG:
Three(ofmanypossible)spannin gtreesfromgraphG:
2 2
4
G: 3 5 3
6
1 1
AweightedgraphG: TheminimalspanningtreefromweightedgraphG:
Herearesomeexamples:
To explain further upon the Minimum Spanning Tree, and what it applies to,
let'sconsideracoupleofreal-worldexamples:
2. Another useful application of MST would be finding airline routes. The vertices
ofthe graph would represent cities, and the edges would represent routes
betweenthe cities. Obviously, the further one has to travel, the more it will cost,
so MSTcan be applied to optimize airline routes by finding the least costly paths
with nocycles.
To explain how to find a Minimum Spanning Tree, we will look at two algorithms:
theKruskal algorithm and the Prim algorithm. Both algorithms differ in their
methodology,but both eventually end up with the MST. Kruskal's algorithm uses edges,
and Prim‟salgorithmusesvertexconnectionsin determiningtheMST.
Kruskal’sAlgorithm
Thisisagreedyalgorithm.Agreedyalgorithmchoosessomelocaloptimum(i.e.pickinganedg
ewiththeleastweightinaMST).
Kruskal's algorithm works as follows: Take a graph with 'n' vertices, keep on adding
theshortest (least cost) edge, while avoiding the creation of cycles, until (n- 1)
edgeshave been added. Sometimes two or more edges may have the same cost. The
order inwhich the edges are chosen, in this case, does not matter. Different MSTs may
result,buttheywillallhavethesametotalcost,whichwillalwaysbetheminimumcost.
92
Algorithm:
ThealgorithmforfindingtheMST,usingtheKruskal‟smethodisas follows:
AlgorithmKruskal(E,cost,n,t)
//EisthesetofedgesinG.Ghasnvertices.cost[u,v]isthe
//costofedge(u,v).„t‟isthesetofedgesintheminimum-costspanningtree.
//Thefinalcostisreturned.
{
Construct aheapoutof
theedgecostsusingheapify;fori:=1tondoparent [i] :=-
1;
//Each vertexisinadifferentset.
i :=0;mincost:=0.0;
while((i<n -1)and(heapnot empty))do
{
Deleteaminimumcostedge(u,v)fromtheheapandre-
heapifyusingAdjust;
j:=Find(u);k:=Find(v);if(jk
)then
{
i:=i+1;
t [i, 1] := u; t [i, 2] :=
v;mincost:=mincost+cost[u,v];U
nion(j,k);
}
}
if (i n-1) then write ("no spanning
tree");elsereturnmincost;
}
Runningtime:
The number of finds is at most 2e, and the number of unions at most n-
1.Including the initialization time for the trees, this part of the algorithm has
acomplexitythatisjustslightlymorethanO(n+e).
We can add at most n-1 edges to tree T. So, the total time for operations on T
isO(n).
Example1:
10 50
1 2
45 40 3
30 35
4 25 5
55
20 15
6
93
Arrangealltheedgesintheincreasing order oftheircosts:
Cost 10 15 20 25 30 35 40 45 50 55
Edge (1,2) (3,6) (4,6) (2,6) (1,4) (3,5) (2,5) (1,5) (2,3) (5,6)
TheedgesetTtogetherwiththeverticesofGdefineagraphthathasuptonconnected
components. Let us represent each component by a set of vertices in it.These vertex
sets are disjoint. To determine whether theedge (u, v) creates a cycle,we need to check
whether u and v are in the same vertex set. If so, then a cycle iscreated. If not then no
cycle is created. Hence two Finds on the vertex sets suffice.When an edge is included
in T, two components are combined into one and a union istobeperformedon the
twosets.
Thevertices1and
(1, 4) 30 Reject 4areinthesame
set,sotheedgeisrej
ected
(3, 5) 35 1 2 Thevertices3and
5areinthesame
4 {1,2,3,4,5,6} set,
5 3
sotheedgeiscombin
ed
6
94
MINIMUM-COSTSPANNINGTREES:PRIM'SALGORITHM
A given graph can have many spanning trees. From these many spanning trees,
wehavetoselectacheapestone.Thistreeiscalledasminimalcostspanningtree.
Minimal cost spanning tree is a connected undirected graph G in which each edge
islabeled with a number (edge labels may signify lengths, weights other than
costs).Minimal cost spanning tree is a spanning tree for which the sum of the edge
labels is assmallaspossible
The slight modification of the spanning tree algorithm yields a very simple algorithm
forfindinganMST.Inthespanningtreealgorithm,anyvertexnotinthetreebutconnected to it
by an edge can be added. Tofind a Minimal cost spanning tree, wemust be selective -
we must always add a new vertex for which the cost of the
newedgeisassmallaspossible.
This simple modified algorithm of spanning tree is called prim's algorithm for finding
anMinimalcostspanningtree.
Prim'salgorithmisanexampleofagreedyalgorithm.
Algorithm Algorithm
Prim(E, cost,n,t)
//EisthesetofedgesinG.cost[1:n,1:n]isthecost
//adjacency matrixofannvertexgraphsuchthatcost[i,j]is
//eitherapositiverealnumberorifnoedge(i,j)exists.
//Aminimumspanningtreeiscomputedandstoredasasetof
//edgesin thearrayt[1:n-1,1:2].(t [i,1],t [i,2])isanedgein
//theminimum-costspanningtree.Thefinalcostisreturned.
{
Let(k,l)bean
edgeofminimumcostinE;mincost:= cost[k,l];
t[1,1]:=k;t[1,2]:=l;
for i:=1 tondo
//Initializenearif
(cost[i,l]<cost[i,k])thennear[i]:=l;
else near [i] :=
k;near[k] :=near[l]:=0;
fori:=2 ton-1do //Findn- 2additionaledgesfort.
{
Letjbeanindexsuchthatnear[j]0and
cost [j,near[j]]isminimum;
t[i,1]:=j;t[i,2]:=near[j];mincost :=
mincost + cost [j, near [j]];near[j] :=0
for k:=1tondo //Update
near[].if((near[k]0)and(cost[k,near[k]]>cost[k,j]))
thennear[k]:=j;
}
returnmincost;
}
95
Runningtime:
WedothesamesetofoperationswithdistasinDijkstra'salgorithm(initializestructure, m times
decrease value, n - 1 times select minimum). Therefore, we get O(n 2) time when we
implement dist with array, O (n + E log n) when we implement itwithaheap.
For each vertex u in the graph we dequeue it and check all its neighbors in (1 +
deg(u))time.Thereforethe running timeis:
1degv n degv (nm)
vV v V
EXAMPLE1:
UsePrim‟sAlgorithmtofindaminimalspanningtreeforthe
graphshownbelowstartingwith thevertexA.
4
B D
4
3 2 1 2
4 E 1
A C 2 G
6
2 F 1
SOLUTION:
0 3 6
3 0 2 4
6 2 0 1 4 2
Thecostadjacencymatrixis 4 1 0 2 4
1
4 2 0 2
2 2 0 1
4 1 1 0
Thestepwiseprogressoftheprim‟salgorithmisasfollows:
Step1:
B 3 D Vertex A B C D E F G
Status 0 1 1 1 1 1 1
E Dist. 0 3 6
A G Next * A A A A A A
0 6
F
C
96
Step2:
4 D Vertex A B C D E F G
B 3
Status 0 0 1 1 1 1 1
Dist. 0 3 2 4
E
Next * A B B A A A
A 0 2 G
C
F
Step3:
Vertex A B C D E F G
B 3 1 D Status 0 0 0 1 1 1 1
Dist. 0 3 2 1 4 2
4 E Next * A B C C C A
A 0 2 G
C 2 F
Step4:
B 3 1 D Vertex A B C D F G
EStatus 0 0 0 1 1
2 E Dist. 0 3 2
1 1 2 2 4
A 0 2 4 G Next * A B C D C D
C 2 F
Step5:
Vertex A B C D E F G
B 3 1 D
Status 0 0 0 0 1 0 1
Dist. 0 3 2 1 2 2 1
2 E Next * A B C D C E
A 0 2 1 G
C 2 F
Step6:
Vertex A B C D E F G
B 3 1 D
Status 0 0 0 0 0 1 0
Dist. 0 3 2 1 2 1 1
2 E Next * A B C D G E
A 0 2 1 G
C 1 F
Step7:
Vertex A B C D E F G
B 3 1 D
Status 0 0 0 0 0 0 0
Dist. 0 3 2 1 2 1 1
2 E
A 0 2 1 G Next * A B C D G E
C 1 F
97
EXAMPLE2:
Consideringthefollowinggraph,findtheminimalspanningtreeusingprim‟salgorithm.
8
1 4 4
9
3 5
4
1
2 3 3
4
4 9 8
4 4 1
Thecostadjacent matrixis94 3 3
8 1 3 4
3 4
Theminimalspanningtree obtainedas:
Vertex1 Vertex2 1 4
2 4
4 1 3 5
3 4 3
5 3 2 3
1 2
ThecostofMinimal spanningtree=11.
Thestepsasperthealgorithmareasfollows:
Algorithmnear(J)=kmeans,thenearestvertextoJisk.
The algorithm starts by selecting the minimum cost from the graph. The minimum
costedgeis(2,4).
K=2,l=4
Mincost= cost(2,4)=1
T[1,1]=2
T[1,2]=4
98
fori=1to5 Nearmatrix Edgesadded tominspanning
tree:
Begin
T[1,1]=2
i=1 T[1,2]=4
iscost(1,4)< cost(1,2) 2
8<4,No
Thannear(1)=2 1 2 3 4 5
i=2
iscost(2,4)< cost(2,2) 2 4
1<,Yes
Sonear[2]=4 1 2 3 4 5
i=3
iscost(3,4)< cost(3,2) 2 4 4
1<4,Yes
Sonear[3]=4 1 2 3 4 5
i=4
iscost(4,4)<cost(4,2) 2 4 4 2
<1,no
Sonear[4]=2 1 2 3 4 5
i=5
iscost(5,4)< cost(5,2) 2 4 4 2 4
4<,yes
Sonear[5]=4 1 2 3 4 5
end
2 0 4 0 4
near[k]=near[l]=0
near[2]= near[4]=0 1 2 3 4 5
for i=2ton-1(4)do
i=2
forj=1to5
j=1
near(1)0andcost(1,near(1))2
0andcost(1,2)=4
j=2
near(2)=0
j=3
isnear(3)0
40andcost(3,4)=3
99
j=4
near(4)=0
J=5
Isnear(5)0
40andcost(4,5)=4
mincost=1+cost(3,4) T(2,1)= 3
=1+3=4 T(2,2)= 4
T(2,1)=3
T(2,2)=4 2 0 0 0 4
1 2 3 4 5
Near[j]=0
i.e.near(3)=0
for(k=1ton)
K=1
isnear(1)0,yes
20
andcost (1,2)>cost(1,3)
4>9,No
K=2
Is near(2) 0,No
K=3
Isnear(3)0,No
K=4
Is near(4)0,No
2 0 0 0 3
K=5
Isnear(5)0 1 2 3 4 5
40,yes
andiscost(5,4)> cost(5,3)
4>3,yes
thannear(5)=3
i=3
for (j=1to5)
J=1
isnear(1)02
0
cost (1,2)=4
J=2
Is near(2) 0,No
10
0
J=3
Is near(3)0,no
Near(3)=0
J=4
Isnear(4)0,no
Near(4)=0
J=5
Isnear(5)0
Near(5)=330,yes
Andcost(5,3)=3
Mincost=4+cost(5,3)
=4+3=7
T(3,1)=5
T(3,2)=3
2 0 0 0 0
Near (J) = 0 near (5) =
1 2 3 4 5
0for (k=1 to5)
k=1
isnear(1)0,yes
andcost(1,2)>cost(1,5)4
>,No
K=2
Is near(2)0no
K=3
Is near(3)0no
K=4
Isnear(4)0no
K=5
Isnear(5)0no
i=4
forJ=1to5J=
1
Isnear(1)0
20,yes
cost (1,2)=4
j=2
isnear(2)0,No
10
1
J=3
Is near(3)0,No
Near(3)=0
J=4
Is near(4)0,No
Near(4)=0
J=5
Is near(5)0,No
Near(5)=0
Choosingmincostfromthe
aboveit isonly'4'and
correspondingJ=1
Mincost=7+cost(1,2)
=7+4=11 0 0 0 0 0
T(4,1)=1 T (4, 1) = 1
T(4,2)=2 1 2 3 4 5 T (4, 2) = 2
Near(J)=0Near(1) =0
for(k=1to5)
K=1
Is near(1)0,No
K=2
Is near(2)0,No
K=3
Is near(3)0,No
K=4
Is near(4)0,No
K=5
Is near(5)0,No
End.
4.8.7.TheSingleSourceShortest-PathProblem:DIJKSTRA'SALGORITHMS
In the previously studied graphs, the edge labels are called as costs, but here we
thinkthem as lengths. In a labeled graph, the length of the path is defined to be the
sum ofthelengthsofitsedges.
In the single source, all destinations, shortest path problem, we must find a
shortestpath from a given source vertex to each of the vertices (called destinations) in
thegraphtowhichthereisapath.
10
2
shortest path between then (or one of the shortest paths) if there is more than
one.TheprincipleofoptimalityisthebasisforDijkstra‟salgorithms.
Dijkstra‟salgorithmdoesnotworkfornegativeedgesatall.
Thefigureliststheshortest pathsfromvertex1forafivevertexweighteddigraph.
8 0 1
4 2 1 3
1 2 5
2 4 5 3 1 3 4
3 4 3
1 4 1 2
Graph
6 1 3 4 5
Shortest Paths
Algorithm:
Algorithm Shortest-Paths(v,cost,dist,n)
//dist [j],1<j<n, is setto thelengthoftheshortestpath
//from vertex v tovertexjinthe digraphGwith nvertices.
//dist [v]isset to zero.G isrepresentedbyits
//costadjacencymatrixcost[1:n,1:n].
{
fori:=1 to ndo
{
S[i]:=false;
//InitializeS.d
ist[i]:=cost[v,i];
}
S[v]:=true;dist[v]:=0.0; // Put v in
S.fornum:=2to n–1do
{
Determinen-1pathsfromv.
Choose u from among those vertices not in S such that dist[u] is
minimum;S[u]:=true; //PutuisS.
for(eachw adjacentto uwithS[w] = false)do
if(dist[w]>(dist[u] +cost[u,w])then // Update
distancesdist[w]:=dist[u]+cost[u,w];
}
}
Runningtime:
Dependsonimplementationofdatastructuresfordist.
Buildastructurewithnelements A
atmostm=Etimesdecreasethevalueofanitem mB
„n‟timesselectthesmallestvalue nC
ForarrayA=O(n);B=O(1);C=O(n)whichgivesO(n 2)total.
ForheapA=O(n);B=O(logn);C=O(logn)whichgivesO(n+mlogn)total.
10
3
Example1:
Use Dijkstras algorithm to find the shortest path from A to each of the other
sixverticesin thegraph:
4
B D
4
3 2 1 2
4 E 1
A C 2 G
6
2 F 1
Solution:
0 3 6
3 0 2 4
6 2 0 1 4 2
Thecostadjacencymatrixis 4 1 0 2 4
4 2 0 2
1
2 2 0 1
4 1 1 0
Theproblemissolvedbyconsideringthefollowinginformation:
Status[v]willbeeither„0‟,meaningthattheshortestpathfromvtov 0hasdefinitely
beenfound;or„1‟,meaningthatithasn‟t.
Dist[v]willbeanumber,representingthelengthoftheshortestpathfromvto v0found
sofar.
Next[v] will be the first vertex on the way to v0 along the shortest path found
sofarfromvtov0
TheprogressofDijkstra‟salgorithmonthegraphshownaboveisasfollows:
Step1:
D Vertex A B C D E F G
B 3
Status 0 1 1 1 1 1 1
E Dist. 0 3 6
G Next * A A A A A A
A 0 6
F
C
Step2:
4 7 D Vertex A B C D E F G
B 3 Status 0 0 1 1 1 1 1
2 Dist. 0 3 5 7
E Next * A B B A A A
A 0 5 G
C
F
10
4
Step3:
Vertex A B C D E F G
B 3 6 D Status 0 0 0 1 1 1 1
Dist. 0 3 5 6 9 7
9 E G Next * A B C C C A
A 0 5
F 7
C
Step4:
B 3 7 D Vertex A B C D E F G
Status 0 0 0 0 1 1 1
8 E Dist. 0 3 5 6 8 7 10
A 0 5 10 G Next * A B C D C D
C 7 F
Step5:
Vertex A B C D E F G
B 3 6 D
Status 0 0 0 0 1 0 1
Dist. 0 3 5 6 8 7 8
8 E Next * A B C D C F
A 0 5 8 G
C 7 F
Step6:
Vertex A B C D E F G
B 3 8 D
Status 0 0 0 0 0 0 1
Dist. 0 3 5 6 8 7 8
8 E Next * A B C D C F
A 0 5 8 G
C 7 F
Step7:
Vertex A B C D E G
B 3 9 D
FStatus 0 0 0 0 0
0 0 8
8 E F
A 0 5 8 G Dist. 0 3 5 6 8 7
Next * A B C D C
C 7 F
10
5
Chapter
5
DynamicProgramming
Dynamic programming is a name, coined by Richard Bellman in 1955.
Dynamicprogramming, as greedy method, is a powerful algorithm design technique
that canbe used when the solution to the problem may be viewed as the result of a
sequenceof decisions. In the greedy method we make irrevocable decisions one at
atime,using a greedy criterion. However, in dynamic programming we examine the
decisionsequence to see whether an optimal decision sequence contains optimal
decisionsubsequence.
Dynamicprogrammingisbasedontheprincipleofoptimality(alsocoinedbyBellman). The
principle of optimality states that no matter whatever the initial stateand initial
decision are, the remaining decision sequence must constitute an optimaldecision
sequence with regard to the state resulting from the first decision. Theprinciple
implies that an optimal decision sequence is comprised of optimal
decisionsubsequences. Since the principle of optimality may notholdfor some
formulationsof some problems, it is necessary to verify that it does hold for the
problem
beingsolved.Dynamicprogrammingcannotbeappliedwhenthisprincipledoesnothold.
Thestepsinadynamicprogrammingsolutionare:
Verifythattheprincipleof optimalityholds
Setupthedynamic-programmingrecurrenceequations
Performatracebackstepinwhichthesolutionitselfisconstructed.
Dynamic programming differs from the greedy method since the greedy
methodproduces only one feasible solution, which may or may not be optimal, while
dynamicprogrammingproducesallpossiblesub-
problemsatmostonce,oneofwhichguaranteed to be optimal. Optimal solutions to sub-
problems are retained in a table,thereby avoiding the work of recomputing the
answer every time a sub-problem isencountered
The divide and conquer principle solve a large problem, by breaking it up into
smallerproblems which can be solved independently. In dynamic programming this
principleis carried to an extreme: when we don't know exactly which smaller
problems tosolve, we simply solve them all, then store the answers away in a table to
be usedlater in solving larger problems. Care is to be taken to avoid recomputing
previouslycomputedvalues,otherwisetherecursiveprogramwillhaveprohibitivecomplexit
y.Insomecases, the solutioncan be improved and inother cases, the
dynamicprogrammingtechniqueisthebestapproach.
106
Twodifficultiesmayariseinanyapplicationofdynamicprogramming:
2. Thenumberofsmallproblemstosolvemaybeun-acceptably large.
5.1 MULTISTAGEGRAPHS
Letthevertex„s‟isthesource,and„t‟thesink.Letc(i,j)bethecostofedge<i,j>.Thecostofapat
hfrom„s‟to„t‟isthesumofthecostsoftheedgesonthepath.Themultistage graph problem
is to find a minimum cost path from „s‟ to „t‟. Each set
Videfinesastageinthegraph.BecauseoftheconstraintsonE,everypathfrom„s‟to
„t‟ starts in stage 1, goes to stage 2, then to stage 3, then to stage 4, and so on,
andeventuallyterminatesinstagek.
ALGORITHM:
AlgorithmFgraph(G,k,n,p)
//Theinputisak-stagegraphG=(V,E)withnvertices
//indexedinorderorstages.Eisasetofedgesandc[i,j]
//isthecostof(i,j).p[1:k]isaminimumcostpath.
{
cost[n]:=0.0;
for j:=n-1to1 step–1do
{ //computecost[j]
let r be a vertex such that (j, r) is an
edgeof G and c [j, r] + cost [r] is
minimum;cost[j] :=c[j, r] + cost[r];
d[j]:=r:
}
p[1]:=1;p[k]:=n; // Find a minimum cost
path.for j:=2tok- 1dop[j] :=d [p [j-1]];
}
107
The multistage graphproblemcan also be solved using thebackward approach. Let
bp(i, j) be a minimum cost path from vertex s to j vertex in Vi. Let Bcost(i, j)
bethecostofbp(i,j).Fromthebackwardapproachweobtain:
AlgorithmBgraph(G,k,n,p)
//SamefunctionasFgraph
{
Bcost[1]:=0.0;
forj:=2tondo
{ //ComputeBcost[j].
Let r be such that (r, j) is an edge ofG
and Bcost [r] + c [r, j] is
minimum;Bcost[j]:=Bcost[r]+c[r,j];
D[j]:=r;
} //findaminimumcostpath
p[1]:=1;p[k]:=n;
forj:=k-1to2dop[j]:=d[p[j+1]];
}
ComplexityAnalysis:
EXAMPLE1:
Findtheminimumcostpathfromstotinthemultistagegraphoffivestagesshownbelow.Dothisfirstu
singforwardapproachandthenusingbackwardapproach.
2 4
6
2 6 9
9 2 5 4
1
3 4
7 7 2
7 10 12 t
s 1 3 3
4 11
2 5
5
8 11
11 6
5 8
FORWARDAPPROACH:
We use the following equation to find the minimum cost path from s to
t:cost(i,j)=min{c(j,l)+cost(i+1,l)}
l Vi+1
108
<j,l>E
cost(1,1)=min{c(1,2)+cost(2,2),c(1,3)+cost(2,3),c(1,4)+cost(2,4),
c(1,5)+ cost(2,5)}
=min{9+cost(2,2),7+cost(2,3),3+cost(2,4),2+cost(2,5)}
Nowfirststartingwith,
cost(2,2)=min{c(2,6)+cost(3,6),c(2,7)+cost(3,7),c(2,8)+cost(3,8)}
=min{4+cost(3,6),2+cost(3,7),1+cost(3,8)}
cost(3,6)=min{c(6,9)+cost(4,9),c(6,10)+cost(4,10)}
=min{6+cost(4,9),5+cost(4,10)}
cost(4,9)=min{c(9,12)+cost(5,12)}=min{4+0)=4
Therefore,cost(3, 6) = min{6+4,5+2}=7
cost(3,7)=min{c(7,9)+cost(4,9),c(7,10)+cost(4,10)}
=min{4+cost(4,9),3+cost(4,10)}
cost(4,9)=min{c(9,12) + cost(5,12)}=min{4+0}=4
Cost(4,10)=min{c(10,2)+cost(5,12)}=min{2+0}=2
Therefore,cost(3,7)=min{4+4,3+2}=min{8,5}=5
cost(3,8)=min{c(8,10)+cost(4,10),c(8,11)+cost(4,11)}
=min{5+cost(4,10),6+ cost(4+11)}
cost(4,11)=min{c(11,12)+cost(5,12)}=5
Therefore,cost(3,8)=min{5+2,6+5}=min{7,11}=7
Therefore,cost(2,2)=min{4+7,2+5,1+7}=min{11,7,8}=7
Therefore,cost(2,3)=min{c(3,6)+cost(3,6),c(3,7)+cost(3,7)}
=min{2+cost(3,6),7+cost(3,7)}
=min{2 +7,7+ 5} = min {9,12} =9
Therefore,cost(1,1)=min{9+7,7+9,3+18,2+15}
=min{16,16,21,17}=16
Theminimumcostpathis16.
109
Thepathis 1 2 7 10 12
or
1 3 6 10 12
BACKWARDAPPROACH:
Weusethefollowingequationtofindtheminimumcostpathfromttos:Bcost(i,J)=m
in {Bcost(i–1,l) +c(l,J)}
l vi –1
<l,j>E
Bcost(5,12)=min{Bcost(4,9)+c(9,12),Bcost(4,10)+c(10,12),
Bcost(4,11)+ c(11,12)}
=min{Bcost(4,9)+4,Bcost(4,10)+2,Bcost(4,11)+5}
Bcost(4,9)=min{Bcost(3,6)+c(6,9),Bcost(3,7)+c(7,9)}
=min{Bcost(3, 6)+6,Bcost(3,7)+4}
Bcost(3,6)=min{Bcost(2,2)+c(2,6),Bcost(2,3)+c(3,6)}
=min{Bcost(2, 2)+4,Bcost(2,3)+2}
Bcost(2,2)=min{Bcost(1,1)+c(1,2)}=min{0+9}=9
Bcost(2,3)=min{Bcost(1,1)+c(1,3)}=min{0+7}=7
Bcost(3,6)=min{9+4,7+2}=min{13,9}=9
Bcost(3,7)=min{Bcost(2,2)+c(2,7),Bcost(2,3)+c(3,7),
Bcost(2,5)+ c(5,7)}
Bcost(3,7)=min{9+2,7+7,2+11}=min{11,14,13}=11
Bcost(4,9)=min{9+6,11+4}=min{15,15}=15
Bcost(4,10)=min{Bcost(3,6)+c(6,10),Bcost(3,7)+c(7,10),
Bcost(3,8)+ c(8,10)}
Bcost(3,8)=min{Bcost(2,2)+c(2,8),Bcost(2,4)+c(4,8),
Bcost(2,5)+c(5,8)}
Bcost(2,4)=min{Bcost(1,1)+c(1,4)}=3
Bcost(3,8)=min{9+1,3+11,2+8}=min{10,14,10}=10
Bcost(4,10)=min{9+5,11+3,10+5}=min{14,14,15)=14
Bcost(4,11)=min{Bcost(3,8)+c(8,11)}=min{Bcost(3,8)+6}
=min{10+6} =16
110
Bcost(5,12)=min{15+4,14+2,16+5}=min{19,16,21}=16.
EXAMPLE2:
Find the minimum cost path from s to t in the multistage graph of five stages
shownbelow.Dothisfirstusingforwardapproachandthenusingbackwardapproach.
4 1
3
2 4 7
6 7
5
3 6
s 1 5 2 9 t
2 5
3
3 8
6
8 2
6
SOLUTION:
FORWARDAPPROACH:
cost(i,J)=min{c(j,l)+cost(i+1,l)}
l Vi+1
<J,l>E
cost(1,1)=min{c(1,2)+cost(2,2),c(1,3)+cost(2,3)}
=min{5+cost(2,2),2+cost(2,3)}
cost(2,2)=min{c(2,4)+cost(3,4),c(2,6)+cost(3,6)}
=min{3+cost(3,4), 3+cost(3,6)}
cost(3,4)=min{c(4,7)+cost(4,7),c(4,8)+cost(4,8)}
=min{(1+cost(4,7),4+cost(4,8)}
cost(4,7)=min{c(7,9)+cost(5,9)}=min{7+0)=7
cost(4,8)=min{c(8,9)+cost(5,9)}=3
Therefore,cost(3,4)= min{8,7}=7
cost(3,6)=min{c(6,7)+cost(4,7),c(6,8)+cost(4,8)}
=min{6+cost(4,7),2+cost(4,8)}=min{6+7,2+3}=5
cost(2,3)=min{c(3,4)+cost(3,4),c(3,5)+cost(3,5),c(3,6)+cost
(3,6)}
cost(3,5)=min{c(5,7)+cost(4,7),c(5,8)+cost(4,8)}=min{6+7,2+3}
=5
Therefore,cost(2,3)=min{13,10,13}=10
cost(1,1)=min{5+8,2+10}=min{13,12}=12
111
BACKWARDAPPROACH:
Bcost(i,J)=min{Bcost(i–1,l)=c(l,J)}
l vi–1
<l ,j>E
Bcost(5,9)=min{Bcost(4,7)+c(7,9),Bcost(4,8)+c(8,9)}
=min{Bcost(4, 7)+7,Bcost(4,8)+3}
Bcost(3,4)=min{Bcost(2,2)+c(2,4),Bcost(2,3)+c(3,4)}
=min{Bcost(2, 2)+3,Bcost(2,3)+6}
Bcost(2,2)=min{Bcost(1,1)+c(1,2)}=min{0+5}=5
Bcost(2,3)=min(Bcost(1,1)+c(1,3)}=min{0+2}=2
Therefore,Bcost(3,4)=min{5+3,2+6}=min{8,8}=8
Bcost(3,5)=min{Bcost(2,3)+c(3,5)}=min{2+5}=7
Bcost(3,6)=min{Bcost(2,2)+c(2,6),Bcost(2,3)+c(3,6)}
=min{5 +5,2+8}=10
Therefore,Bcost(4,7)=min{8+1,7+6,10+6}=9
Bcost(4,8)=min{Bcost(3,4)+c(4,8),Bcost(3,5)+c(5,8),
Bcost(3,6)+ c(6,8)}
=min {8+4,7+2,10+2} =9
Therefore,Bcost(5,9)=min{9+7,9+ 3}=12
Allpairsshortestpaths
In the all pairs shortest path problem, we are to find a shortest path between
everypair of vertices in a directed graph G. That is, for every pair of vertices (i, j),
we areto find a shortest path from i to j as well as one from j to i. These two paths
are thesamewhenGisundirected.
When no edge has a negative length, the all-pairs shortest path problem may
besolved by using Dijkstra‟s greedy single source algorithm n times, once with each
ofthenverticesasthesourcevertex.
The all pairs shortest path problem is to determine a matrix A such that A (i, j) is
thelength of a shortest path from i to j. The matrix A can be obtained by solving
nsingle-source problems using the algorithm shortest Paths. Since each application
ofthisprocedurerequiresO(n 2)time,thematrixAcanbeobtainedinO(n 3)time.
112
The dynamic programming solution, called Floyd‟s algorithm, runs in O (n 3)
time.Floyd‟s algorithm works even when the graph has negative length edges
(providedtherearenonegativelengthcycles).
Ak(i,j)={min{min{A k-1(i,k)+Ak-1(k,j)},c(i,j)}
1<k<n
AlgorithmAllPaths (Cost,A,n)
//cost[1:n,1:n]isthecostadjacencymatrixofagraphwhich
//nvertices;A[I,j]isthecostofashortestpathfromvertex
//itovertex j.cost[i,i]=0.0,for1<i<n.
{
fori:=1tondo
for j:=1tondo
A[i,j] :=cost[i,j]; //copycostintoA.for
k:=1tondo
fori:=1tondo
forj:=1tondo
A[i,j]:=min(A[i,j],A[i,k]+A[k,j]);
}
Example1:
6
1 2 0 4 11
4
0
Costadjacencymatrix(A ) =
6 0 2
3 11 2
3 0
3
Generalformula:min{A k-1(i,k)+Ak-1(k,j)},c(i,j)}
1<k<n
Step1:Solvingtheequationfor,k=1;
113
A1(1,1)=min{(Ao (1,1)+Ao (1,1)),c(1,1)}=min{0+0,0}=0
A1(1,2)=min{(Ao (1,1)+Ao (1,2)),c(1,2)}=min{(0+4),4}=4
A1(1,3)=min{(Ao (1,1)+Ao (1,3)),c(1,3)}=min{(0+11),11}=11
A1(2,1)=min{(Ao (2,1)+Ao (1,1)),c(2,1)}=min{(6+0),6}=6
A1(2,2)=min{(Ao (2,1)+Ao (1,2)),c(2,2)}=min{(6+4),0)}=0
A1(2,3)=min{(Ao (2,1)+Ao (1,3)),c(2,3)}=min{(6+11),2}=2
A1(3,1)=min{(Ao (3,1)+Ao (1,1)),c(3,1)}=min{(3+0),3}=3
A1(3,2)=min{(Ao (3,1)+Ao (1,2)),c(3,2)}=min{(3+4),}=7
A1(3,3)=min{(Ao (3,1)+Ao (1,3)),c(3,3)}=min{(3+11),0}=0
0 4 11
A =
(1)
2
6 0
3 7 0
Step2:Solvingtheequationfor,K= 2;
A2(1,1)=min{(A 1(1,2)+A1(2,1),c(1,1)}=min{(4+6),0}=0
A2(1,2)=min{(A 1(1,2)+A1(2,2),c(1,2)}=min{(4+0),4}=4
A2(1,3)=min{(A 1(1,2)+A1(2,3),c(1,3)}=min{(4+2),11}=6
A2(2,1)=min{(A(2,2)+A(2,1),c(2,1)}=min{(0+6),6}=6
A2(2,2)=min{(A(2,2)+A(2,2),c(2,2)}=min{(0+0),0}=0
A2(2,3)=min{(A(2,2)+A(2,3),c(2,3)}=min{(0+2),2}=2
A2(3,1)=min{(A(3,2)+A(2,1),c(3,1)}=min{(7+6),3}=3
A2(3,2)=min{(A(3,2)+A(2,2),c(3,2)}=min{(7+0),7}=7
A2(3,3)=min{(A(3,2)+A(2,3),c(3,3)}=min{(7+2),0}=0
0 4 6
A =
(2)
2
6 0
3 7 0
Step3:Solvingtheequationfor,k=3;
A3(1,1)=min{A 2(1,3)+A2(3,1),c(1,1)}=min{(6+3),0}= 0
A3(1,2)=min{A 2(1,3)+A2(3,2),c(1,2)}=min{(6+7),4}= 4
3 2 2
A (1,3)=min{A (1,3)+A (3,3),c(1,3)}=min{(6+0),6}= 6
A3(2,1)=min{A 2(2,3)+A2(3,1),c(2,1)}=min{(2+3),6}= 5
3 2 2
A (2,2)=min{A (2,3)+A (3,2),c(2,2)}=min{(2+7),0}= 0
A3(2,3)=min{A 2(2,3)+A2(3,3),c(2,3)}=min{(2+0),2}= 2
3 2 2
A (3,1)=min{A (3,3)+A (3,1),c(3,1)}=min{(0+3),3}= 3
A3(3,2)=min{A 2(3,3)+A2(3,2),c(3,2)}=min{(0+7),7}= 7
114
A3(3,3)=min{A 2(3,3)+A2(3,3),c(3,3)}=min{(0+0),0}=0
0 4 6
A(3)= 2
5 0
3 7 0
TRAVELLINGSALESPERSONPROBLEM
Let G = (V, E) be a directed graph with edge costs Cij. The variable cij is defined
suchthat cij > 0 for all I and j and cij = if < i, j> E. Let |V| = n and assume n > 1.
Atour of G is a directed simple cycle that includes every vertex in V. The cost of a
touris the sum of the cost of the edges on the tour. The traveling sales person
problem istofindatourofminimumcost.Thetouristobeasimplepaththatstartsandendsat
vertex1.
Let g (i, S) be the length of shortest path starting at vertex i, going through
allvertices in S, and terminating at vertex 1. The function g (1, V – {1}) is the length
ofanoptimalsalespersontour.Fromtheprincipal ofoptimalityit followsthat:
Generalizingequation1,weobtain(foriS)
The Equation can be solved for g (1, V – 1}) if we know g (k, V – {1, k}) for
allchoices ofk.
ComplexityAnalysis:
Foreachvalueof|S|therearen–1choicesfori.ThenumberofdistinctsetsSof
n2
sizeknotincluding1andiis k .
Hence,thetotalnumberofg(i,S)‟stobecomputedbeforecomputingg(1,V–{1})is:
n1 n2
n1k
k0
Tocalculatethissum,weusethebinominaltheorem:
(n2 (n2 (n2 (n2)
(n–1)
0 1 2 (n2)
Accordingtothebinominaltheorem:
(n2 (n2 (n2 (n2)
=2n-2
0 1 2
(n2)
Therefore,
115
n1 n2
n1k (n1)2n2
k0
Example1:
Forthefollowinggraphfindminimumcosttourforthetravelingsalespersonproblem:
1 2
0 10 15 20
Thecost adjacencymatrix=
5
0 9 10
6 13 0 12
8 9 0
3 4 8
Letusstartthetourfromvertex1:
Moregenerallywriting:
g(i,s)=min{cij +g(J,s–{J})} -
(2)Clearly
,g(i,) =ci1,1≤i≤n.So,
g(2,) =C21=5
g (3, ) = C31 =
6g(4,)=C41=8
Usingequation –(2)weobtain:
g(2,{3,4})= min{c23+g(3,{4}),c24+g(4,{3})}
=min{9+g(3,{4}), 10+g(4,{3})}
g(3,{4})=min{c34+g(4,)}=12+8=20
g(4,{3})=min{c43+g(3,)}=9+6=15
116
Therefore,g(2,{3,4})=min{9+20,10+15}=min{29,25}=25
g(3,{2,4})=min{(c32+g(2,{4}),(c34+g(4,{2})}
g(2,{4})=min{c24+g(4,)}=10+8=18
g(4,{2})=min{c42+g(2,)}=8+5=13
Therefore,g(3,{2,4})=min{13+18,12+13}=min{41,25}=25
g(2,{3})=min{c23+g(3,}=9+6=15
Therefore,g(4,{2,3})=min{8+15,9+18}=min{23,27}=23
35Theoptimaltouris:1, 2,4,3,1.
OPTIMALBINARYSEARCHTREE
Letusassumethatthegivensetofidentifiersis{a1,...,an}witha1<a2< <
an. Let p (i) be the probability with which we search for ai. Let q (i) be the
probabilitythattheidentifierxbeingsearchedforissuchthatai<x<ai+1,0<i<n(assumea0 = -
and an+1= +). We have to arrange the identifiers in a binary search tree
inawaythatminimizesthe expectedtotalaccesstime.
In a binary search tree, the number of comparisons needed to access an element
atdepth'd'isd+1,soif'ai'isplacedatdepth'di',thenwewanttominimize:
n
Pi(1di).
i1
Let P (i) be the probability with which we shall be searching for 'ai'. Let Q (i) be
theprobabilityofanun-successfulsearch.Everyinternalnoderepresentsapointwherea
successful search may terminate. Every external node represents a point where
anunsuccessfulsearchmayterminate.
Theexpectedcostcontributionfortheinternalnodefor'ai'is:
P(i)*level(ai).
Q(i)*level ((Ei)-1)
Theexpectedcostofbinarysearchtreeis:
117
n n
The computation of each of these c(i, j)‟s requires us to find the minimum of
mquantities. Hence, each such c(i, j) can be computed in time O(m). The total time
forallc(i,j)‟swithj –i=misthereforeO(nm –m2).
Thetotaltimetoevaluateallthec(i,j)‟sandr(i,j)‟sistherefore:
nmm On
1mn
2 3
Example 1: The possible binary search trees for the identifier set (a1, a2, a3) =
(do,if, stop) are as follows. Given the equal probabilities p (i) = Q (i) = 1/7 for all i,
wehave:
stop if
if do stop
do
Tree2
Tree1
do do
if stop
stop if
Tree3 Tree4
1 1 1 1 1 1 1
Cost(tree#1)= x1 x2 x3 x1 x2 x3 x3
7 7 7 7 7 7 7
123 1233 69 15
=
7 7 7 7 1
1 1 1 1 1 1
Cost(tree#2)= x1 x2 x2 x2 x2 x2 x2
7 7
7 7 7 7 7
122 2222 58 13
=
7 7 7 7
118
1 1 1 1 1 1 1
Cost(tree#3)= x1 x2 x3 x1 x2 x3
7 7 7 7 7 x3
7 7
123 1233 69 15
=
7 7 7 7 1
1 1 1 1 1 1
Cost(tree#4)= x1 x2 x3 x1 x2 x3 x3
7 7 7 7 7 7 7
Huffman coding tree solved by a greedy algorithm has a limitation of having the
dataonly at the leaves and it must not preserve the property that all nodes to the left
ofthe root have keys, which are less etc. Construction of an optimal binary search
treeis harder, because the data is not constrained to appear only at the leaves, and
alsobecause the tree mustsatisfy the binary searchtree property andit
mustpreservethepropertythatallnodestotheleftoftheroothavekeys,whichareless.
A dynamic programming solution to the problemof obtaining an optimalbinarysearch
tree can be viewed by constructing a tree as a result of sequence of decisionsby
holdingthe principleofoptimality. Apossible approach to this is to make
adecisionaswhichoftheai'sbearraignedtotherootnodeat'T'.Ifwechoose'ak'then is clear
that the internal nodes for a1, a2, . . . . . ak-1as well as the externalnodes for the
classes Eo, E1, . . . . . . . Ek-1 will lie in the left sub tree, L, of the root.The remaining
nodes will be in the rightsubtree, R. The structure of an optimalbinarysearchtreeis:
ak
L R
K K
i1 i0
n n
TheC(i,J)canbecomputedas:
C(i,J)=min{C(i,k-1)+C(k,J)+P(K)+w(i,K-1)+w(K,J)}
i<k<J
InitiallyC(i,i)=0andw(i,i)=Q(i)for0<i<n.
Equation (1) may be solved for C (0, n) by first computing all C (i, J) such that J - i
=1
Next, we can compute all C (i, J) such that J - i = 2, Then all C (i, J) with J - i =
3andsoon.
119
C (i, J) is the cost of the optimal binary search tree 'T ij' during computation we
recordthe root R (i, J) of each tree 'Tij'. Then an optimal binary search tree may
beconstructedfromtheseR(i,J).R(i,J)isthevalueof'K'thatminimizesequation(1).
We solve the problem by knowing W (i, i+1), C (i, i+1) and R (i, i+1), 0 ≤ i <
4;KnowingW(i, i+2),C(i,i+2)andR(i,i+2),0≤i<3andrepeatinguntilW(0,n),C(0,n) and
R(0,n)areobtained.
Theresultsaretabulatedtorecovertheactualtree.
Example1:
Let n = 4, and (a1, a2, a3, a4) = (do, if, need, while) Let P (1: 4) = (3, 3, 1, 1) and
Q(0:4) =(2,3,1,1,1)
Solution:
TableforrecordingW(i,j),C(i,j)andR(i,j):
Column
0 1 2 3 4
Row
0 2,0,0 3,0,0 1,0,0 1,0,0, 1,0,0
3 14,25,2 11,19,2
4 16,32,2
Thiscomputationiscarriedoutrow-wisefromrow0torow4.Initially,W(i,i)=Q
(i)andC(i,i)=0andR(i,i)=0,0<i<4.
SolvingforC(0,n):
W(0,1)=P(1) +Q (1)+W(0,0)=3+3+2=8
C(0,1)=W(0,1)+min{C(0,0)+C(1,1)}=8
R(0,1)=1(valueof'K'thatisminimumintheabove equation).
Nextwithi=1;soj=2;asi<k≤j,sothepossiblevaluefork=2W(1,2)=P(2) +Q
(2)+W(1,1) =3+1+3=7
C(1,2)=W(1,2)+min{C(1,1)+C(2,2)}=7
R(1,2)=2
Nextwithi=2;soj=3;asi<k≤j,sothepossiblevaluefork=3
120
W(2,3)=P(3) +Q (3)+W(2,2)=1+1+1=3
C(2,3)=W(2,3)+min{C(2,2)+C(3,3)}=3+[(0+0)]=3
R(2,3)=3
Nextwithi=3;soj=4;asi<k≤j,sothepossiblevaluefork=4W(3,4)=P(4)+Q(4)
+W(3,3)=1+1+1=3
C(3,4)=W(3,4)+min{[C(3,3)+C(4,4)]}=3+[(0+0)]=3
R(3,4)=4
Second,ComputingallC(i,j)suchthatj-
i=2;j=i+2andas0<i<3;i=0,1,2;i<k≤J.Startwithi=0;soj=2;asi<k≤J,sothepossiblevalue
sfork=1and2.
Startwithi=1;soj=4;asi<k≤j,sothepossiblevaluesfork=2,3and4.W(1,4)=P(4)+Q(4)+
W(1,3)=1+1+9=11
C(1,4)=W(1,4)+min{[C(1,1)+C(2,4)],[C(1,2)+C(3,4)],
[C(1,3)+ C(4,4)]}
=11+min{(0+8),(7+3),(12+0)}=11+8=19
R(1,4)=2
Startwithi=0;soj=4;asi<k≤j,sothepossiblevaluesfork=1,2,3and4.
121
W(0,4) = P(4)+Q (4)+W(0,3)=1+1+ 14 =16
C(0,4)=W(0,4)+min{[C(0,0)+C(1,4)],[C(0,1)+C(2,4)],
[C(0,2)+C(3,4)],[C(0,3)+C(4,4)]}
=16 +min [0+19,8+8,19+3,25+0]= 16+16=32
R(0,4)=2
From the table we see that C (0, 4) = 32 is the minimum cost of a binary search
treefor(a1,a2,a3,a4).Therootofthetree'T04'is'a2'.
Hence the left sub tree is 'T01' and right sub tree is T24. The root of 'T01' is 'a1' and
therootof'T24'isa3.
The left and right sub trees for 'T01' are 'T00' and 'T11' respectively. The root of T01
is'a1'
The left and right sub trees for T24 are T22 and T34
respectively.Theroot ofT24is'a3'.
nullTherootofT34isa4.
a2
T04 if
a1 a3
T 01 T24 do read
a4
T00 T11 T22 T34 while
Example2:
Consider four elements a1, a2, a3and a4with Q0= 1/8, Q1= 3/16, Q2= Q3= Q4=1/16
and p1 = 1/4, p2 = 1/8, p3 = p4 =1/16. Construct an optimal binary search
tree.Solvingfor C(0,n):
W(0,1)=P(1) +Q (1)+W(0,0)=4+3+2=9
C(0,1)=W(0,1)+min{C(0,0)+C(1,1)}=9+[(0+0)]=9
R(0,1)=1(valueof 'K'thatisminimumintheaboveequation).
Nextwithi=1;soj=2;asi<k≤j,sothepossiblevaluefork=2W(1,2)=P(2) +Q
(2)+W(1,1) =2+1+3=6
C(1,2)=W(1,2)+min{C(1,1)+C(2,2)}=6+[(0+0)]=6
R(1,2)=2
Nextwithi=2;soj=3;asi<k≤j,sothepossiblevaluefork=3W(2,3)=P(3) +Q
(3)+W(2,2) =1+1+1=3
C(2,3)=W(2,3)+min{C(2,2)+C(3,3)}=3+[(0+0)]=3
122
R(2,3)=3
Nextwithi=3;soj=4;asi<k≤j,sothepossiblevaluefork=4W(3,4)=P(4) +Q
(4)+W(3,3) =1+1+1=3
C(3,4)=W(3,4)+min{[C(3,3)+C(4,4)]}=3+[(0+0)]=3
R(3,4)=4
Startwithi=1;soj=4;asi<k≤j,sothepossiblevaluesfork=2,3and4.W(1,4) = P(4)+Q(4)
Fourth,ComputingallC(i,j)suchthatJ-i=4;j=i+4andas0<i<1;i=0;
i < k ≤ J. Start with i = 0; so j = 4; as i < k ≤ j, so the possible values for k = 1,
2,3and4.
123
=16+min[0 +18,9+8, 18+3,25+0]= 16 +17=33
R(0,4)=2
TableforrecordingW(i,j),C(i,j)andR(i,j)
Column
0 1 2 3 4
Row
0 2,0,0 1,0,0 1,0,0 1,0,0, 1,0,0
3 14,25,2 11,18,2
4 16,33,2
From the table we see that C (0, 4) = 33 is the minimum cost of a binary search
treefor (a1,a2,a3,a4)
Hence the left sub tree is 'T01' and right sub tree is T24. The root of 'T01' is 'a1' and
therootof'T24'isa3.
The left and right sub trees for 'T01' are 'T00' and 'T11' respectively. The root of T01
is'a1'
The left and right sub trees for T24 are T22 and T34
respectively.Theroot ofT24is'a3'.
null.TherootofT34isa4.
a2
T04 a2
a1 a3
T 01 T24 a1 a3
a4
T00 T11 T22 T34 a4
Example3:
WORD PROBABILITY
A 4
B 2
C 1
D 3
E 5
F 2
G 1
124
andallotherelementshavezeroprobability.
Solvingc(0,n):
2W(1,2) =P(2)+Q(2)+W(1,1)=2+0+0 =2
C(1,2)=W(1,2)+min{C(1,1)+C(2,2)}=2+[(0+0)]=2
R(1,2)=2
nextwithi=2;soj =3;asi<k ≤j, sothe possiblevaluefor k=3
4W(3,4) =P(4)+Q(4)+W(3,3)=3+0+0 =3
C(3,4)=W(3,4)+min{C(3,4)+C(4,4)}=3+[(0+0)]=3
R(3,4)=4
125
nextwithi=1;soj=3;asi<k≤j,sothepossiblevaluesfork=2and3.
5.W(2,5) =P(5)+Q(5)+W(2,4)=5+0+4=9
C(2,5)=W(2,5)+min{C(2,2)+C(3,5),C(2,3)+C(4,5),C(2,4)+C(5,5)}
=9+min{ 0+11,1+ 5,5+0}=14
R(2,5)=5
126
nextwithi=3;soj=6;asi<k≤j,sothepossiblevaluesfork=4,5and6.
nextwithi=4;soj=7;asi<k≤j,sothepossiblevaluesfork=5,6and7.
5.W(1,5)=P(5)+Q(5)+W(1,4)=5+0+6=11
C(1,5)=W(1,5)+min{C(1,1)+C(2,5),C(1,2)+C(3,5),C(1,3)+C(4,5)
C(1,4)+C(5,5)}
=11+min{0+14,2+11,4+ 5,10+0}=20
R(1,5)=4
Fifth,computingallc(i,j)suchthatj–i=5;j=i+5andas0≤i<3;
i=0,1,2,i<k≤j.Startwithi=0;soj=4;asi<k≤j,sothepossiblevaluesfork=1,2,3,4and5.
127
R(0,5)=2
W(1,7)=P(7)+Q(7)+W(1,6)=1+0+13=14
C(1,7)=W(1,7)+min{C(1,1)+C(2,7),C(1,2)+C(3,7),C(1,3)+C(4,7)
C(1,4)+C(5,7),C(1,5)+C(6,7),C(1,6)+C(7,7)}
=14+min{ 0+21,2 +18,4+12,10+4,20+1,21+0}=28
R(1,7)=5
Seventh, computing all c(i, j) such that j – i = 7 ;j = i + 7 and as 0 ≤ i< 1 ; i=0i <
k ≤ j. Start with i = 0 ; so j = 7; as i < k ≤ j, so the possible values for k = 1,
2,3,4,5,6and7.
0/1–KNAPSACK
We are given n objects and a knapsack. Each object i has a positive weight wi and
apositive value Vi. The knapsack can carry a weight not exceeding W. Fill the
knapsacksothatthevalueofobjectsin theknapsackisoptimized.
128
decisions on the xi are made in the order xn, xn-1, . . . .x1. Following a decision on
xn,we may be in one of two possible states: the capacity remaining in m – wnand
aprofit of pn has accrued. It is clear that the remaining decisions x n-1, . . . , x1 must
beoptimalwithrespecttotheproblemstateresultingfromthedecisiononx n.Otherwise,xn,.,x
1willnotbeoptimal.Hence, theprincipalofoptimalityholds.
Forarbitraryfi(y),i>0,thisequationgeneralizesto:
Fi(y)=max{fi-1(y),fi-1(y- wi)+pi} -- 2
Equation-2 can be solved for fn (m) by beginning with the knowledge fo (y) = 0 for
ally and fi (y) = - , y < 0. Then f1, f2, . . . fn can be successively computed
usingequation–2.
Whenthewi‟sareinteger,weneedtocomputefi(y)forintegery,0 <y<m.Sincefi
(y)=-
fory<0,thesefunctionvaluesneednotbecomputedexplicitly.Since eachficanbecomputedf
romfi-
1inΘ(m)time,ittakesΘ(mn)timetocomputefn.Whenthewi‟sarerealnumbers,fi(y)isneede
dforrealnumbersysuchthat0<y < m. So, fi cannot be explicitly computed for all y in
this range. Even when the wi‟sare integer, the explicit Θ (m n) computation of fn may
not be the most
efficientcomputation.So,weexploreanalternativemethodforbothcases.
Thefi(y)isanascendingstepfunction;i.e.,thereareafinitenumber ofy‟s,0=y 1
<y2 <... .<yk,suchthatfi(y1) < fi(y2)<.. .. .< fi (yk);fi (y)=-,y< y1; fi
(y) = f (yk), y > yk; and fi (y) = fi (yj), yj < y < yj+1. So, we need to compute only
fi(yj), 1 < j < k. We use the ordered set Si= {(f (yj), yj) |1 < j < k} to represent
fi(y).EachnumberofSiisapair(P,W), whereP=fi (yj) andW =yj.NoticethatS0=
{(0,0)}.WecancomputeS i+1fromSibyfirstcomputing:
Si1={(P, W)|(P–pi,W–wi)Si}
Now, Si+1can be computed by merging the pairs in S iand Si1 together. Note that
ifSi+1contains two pairs (Pj, Wj) and (Pk, Wk) with the property that Pj< Pkand Wj>Wk,
then the pair (Pj, Wj) can be discarded because of equation-2. Discarding orpurging
rules such as this one are also known as dominance rules. Dominated
tuplesgetpurged.Intheabove,(P k,Wk)dominates(Pj ,Wj ).
Example1:
Solution:
129
F1(6)=max(f0(6),f0 (6 –2) +1} = max{0, 0+1} =1
Therefore,F2(6)=max(1,1+2}=3
F2(2)=max{1,-+2}=1
Finally,f3(6)=max{3,1+5}=6
OtherSolution:
Forthegivendatawehave:
S0={(0,0)}; S01={(1,2)}
S1=(S0US0)={(0,0),(1,2)}
1
S11={(2,3), (3,5)}
S2=(S1US11)={(0,0),(1,2),(2,3),(3,5)}
X–5=0=>x=5. y–4=0=>y=4
X–5=1=>x=6. y–4=2=>y=6
X–5=2=>x=7. y–4=3=>y=7
X–5=3 =>x=8. y–4=5=>y=9
S3=(S2US2)={(0,0),(1,2),(2,3),(3,5),(5,4),(6,6),(7,7),(8,9)}
1
ByapplyingDominancerule,
S3=(S2US2)={(0,0),(1,2),(2,3),(5,4),(6,6)}
1
From(6,6)wecaninferthatthemaximumProfitpixi=6andweight xiwi =6
ReliabilityDesign
130
IfstageicontainsmicopiesofdeviceDi.Thentheprobabilitythatallmihavea
mi mi
malfunctionis(1-ri) .Hencethe reliabilityofstageibecomes1–(1 - r) i .
Thereliabilityofstage„i‟isgivenbyafunctioni(mi).
Wewishtosolve:
Maximize
1in
imi
Subject to C m C
1in
i i
mi>1andinterger,1< i<n
Letfi(x)representthe mJ
1ji
maximumvalueofSubjecttotheconstrains:
C m x
1ji
J J
and1<mj <uJ ,1<j<i
Once a value of mn has been chosen, the remaining decisions must be such as to
usetheremaining fundsC –Cnmnin an optimalway.
Theprincipleofoptimalityholdson
foranyfi(xi),i>1,thisequationgeneralizesto
131
fnx max imifi1xCimi
1miui
clearly, f0 (x) = 1 for all x, 0 < x < C and f (x) = -for all x <
0.LetSiconsistoftuplesoftheform(f,x),wheref=f i(x).
Thereisatmostonetupleforeachdifferent„x‟,thatresultfromasequenceof
decisionsonm1,m2,....mn.Thedominancerule(f1,x1)dominate(f2,x2)iff1≥f2andx1≤ x2.
Hence,dominatedtuplescanbediscardedfromSi.
Example1:
Design a three stage system with device types D1, D2 and D3. The costs are $30,
$15and $20 respectively. The Cost of the system is to be no more than $105.
Thereliabilityofeachdevice is0.9,0.8and 0.5respectively.
Solution:
We assume that if if stage I has mi devices of type i in parallel, then i (mi) =1 – (1-
ri)mi
Usingtheaboveequationcomputeu1,u2andu3.
10530301520
u 1 70 2
30 30
10515301520 55
u2 3
15 15
10520301520 60
u 3 3
20 20
We useSij i:stagenumberandJ:no.ofdevicesinstageimi
S 1 S 1 ,S 1
1 2
132
2 2
S 2 S ,S ,S
2
1 2 3
1111r1m1=1–(1–0.9)1=0.9
12110.92 0.99
60Therefore,S 1={(0.9,30),(0.99,60)}
f2(x){21*f1,22*f1,23*f1}
2111rI=1–(1mi –0.8)=1–0.2=0.8
1
22110.820.96
23110.830.992
S12{(0.8(0.9),3015),(0.8(0.99),6015)}={(0.72,45),(0.792,75)}
S22{(0.96(0.9),301515),(0.96(0.99),601515)}
={(0.864,60),(0.9504,90)}
S32{(0.992(0.9),30151515),(0.992(0.99),60151515)}
={(0.8928,75),(0.98208,105)}
S 2 S 2 ,S 2,S 2
1 2 3
ByapplyingDominanceruletoS2:
Therefore,S2={(0.72,45),(0.864,60),(0.8928,75)}
DominanceRule:
133
If Sicontains two pairs (f1, x1) and (f2, x2) with the property that f1 ≥ f2 and x1 ≤
x2,then (f1, x1) dominates (f2, x2), hence by dominance rule (f2, x2) can be
discarded.Discarding or pruning rules such as the one above is known as dominance
rule.Dominating tuples will be present inS iand Dominated tuples has to be
discardedfromSi.
x2)Case3:otherwisesimplywrite(f1,x1)
S2={(0.72, 45),(0.864,60),(0.8928,75)}
32110.52 0.75
33110.53 0.875
S130.5(0.72),4520,0.5(0.864),6020,0.5(0.8928),7520
S130.36,65,0.437,80,0.4464,95
S23{0.75(0.72),452020,0.75(0.864),602020,
0.75(0.8928),7520 20}
={(0.54,85),(0.648,100),(0.6696,115)}
S330.875(0.72),45202020,0.875(0.864),60202020,
0.875(0.8928),75202020
S33(0.63,105),1.756,120, 0.7812,135
Ifcostexceeds105,removethattuples
S3={(0.36,65),(0.437,80),(0.54,85),(0.648,100)}
OtherSolution:
Accordingtotheprincipleofoptimality:
Since,wecanassumeeachci>0,eachmimustbeintherange1≤mi≤ui.Where:
134
n
uiCCi C /C
J i
i
Usingtheaboveequationcomputeu1,u2andu3.
10530301520
u 1 70 2
30 30
10515301520 55
u2 3
15 15
10520301520 60
u 3 3
20 20
f3(105)=max{3(m3).f2(105–20m3)}
1m3u3
=max{3(1)f2(105-20),3(2)f2(105-20x2),3(3)f2(105-20x3)}
=max{0.5 f2(85),0.75f2(65),0.875f2(45)}
0.648.f2(85)=max{2(m2).f1(85-15m2)}
1m2u2
=max{2(1).f1(85-15),2(2).f1(85-15x2),2(3).f1(85- 15x3)}
=max{0.8 f1(70),0.96f1(55),0.992f1(40)}
0.8928f1(70)=max{1(m1).f0(70 -30m1)}
1m1u1
=max{1(1)f0(70-30),1(2) f0(70-30x2)}
=max{1(1)x1,1(2)x1}=max{0.9,0.99}=0.99
f1(55)=max {1(m1).f0(55-30m1)}
1m1u1
=max{1(1)f0(50-30),1(2)f0(50-30x2)}
f1(40)=max{1(m1).f0(40-30m1)}
1m1u1
=max{1(1)f0(40-30),1(2)f0(40-30x2)}
=max{1(1)x1,1(2)x-}=max{0.9,-}=0.9
135
f2(65)=max{2(m2). f1(65-15m2)}
1m2u2
=max{2(1)f1(65-15),2(2)f1(65-15x2),2(3)f1(65-15x3)}
=max{0.8f1(50),0.96f1(35),0.992f1(20)}
=max{0.8x0.9,0.96x0.9,-}=0.864
f1(50)=max{1(m1).f0(50-30m1)}
1m1u1
=max{1(1)f0(50-30),1(2)f0(50-30x2)}
0.9f1(35)=max1(m1).f0(35 -30m1)}
1m1u1
=max{1(1).f0(35-30),1(2).f0(35-30x2)}
=max{1(1)x1,1(2)x-}=max{0.9,-}=0.9
f1(20)=max{1(m1).f0(20-30m1)}
1m1u1
=max{1(1)f0(20-30),1(2)f0(20-30x2)}
f2(45)=max{2(m2).f1(45-15m2)}
1m2u2
=max{2(1)f1(45-15),2(2)f1(45-15x2),2(3)f1(45-15x3)}
=max{0.8f1(30),0.96 f1(15),0.992f1(0)}
=max{0.8x0.9,0.96x-,0.99x-}=0.72
f1(30)=max{1(m1).f0(30-30m1)}
1m1u1
=max{1(1)f0(30-30),1(2)f0(30-30x2)}
Similarly,f1(15)= -,f1(0)=-.
Thebestdesignhasareliability=0.648andCost =30
x 1+15x2+20x2=100.
TracingbackforthesolutionthroughS i„swecandeterminethat:m3=2,m2=2
and m1=1.
136
Chapter
6
BASICTRAVERSAL
ANDSEARCHTECHNIQUES
Search means finding a path or traversalbetween a start node and one of a set
ofgoalnodes.Searchisastudyofstatesandtheirtransitions.
TechniquesforTraversalofaBinaryTree:
A binary tree is a finite (possibly empty) collection of elements. When the binary
treeisnotempty,ithasarootelementandremainingelements(ifany)arepartitionedintotwobi
narytrees,whicharecalledtheleftandrightsubtrees.
Therearethreecommonwaystotraverseabinarytree:
1. Preorder
2. Inorder
3. postorder
In all the three traversal methods, the left subtree of a node is traversed before
theright subtree. The difference among the three orders comes from the difference in
thetimeat whichanodeisvisited.
InorderTraversal:
In the case of inorder traversal, the root of each subtree is visited after its left
subtreehas been traversed but before the traversal of its right subtree begins. The
steps fortraversingabinarytree ininordertraversalare:
1. Visit theleftsubtree,usinginorder.
2. Visittheroot.
3. Visittherightsubtree,usinginorder.
Thealgorithmforpreorder traversalisasfollows:
treenode=record
{
Typedata;
//Typeisthedatatypeofdata.Tre
enode *lchild;treenode*rchild;
}
137
algorithminorder(t)
//tis a binarytree.Eachnodeoft hasthreefields:lchild,data,andrchild.
{
ift 0then
{
inorder (t
lchild);visit (t);
inorder(trchild);
}
}
PreorderTraversal:
In a preorder traversal, each node is visited before its left and right subtrees
aretraversed. Preorder search is also called backtracking. The steps for traversing
abinarytree in preordertraversalare:
1. Visittheroot.
2. Visittheleftsubtree,usingpreorder.
3. Visittherightsubtree,usingpreorder.
Thealgorithmforpreorder traversalisasfollows:
AlgorithmPreorder(t)
//tis a binarytree.Eachnodeoft hasthreefields;lchild,data,andrchild.
{
ift 0then
{
visit(t);
Preorder (t
lchild);Preorder(trchild)
;
}
}
PostorderTraversal:
Inapostordertraversal,eachrootisvisitedafteritsleftandrightsubtreeshavebeentraversed.Thes
tepsfortraversingabinarytreeinpostordertraversalare:
1. Visittheleftsubtree,usingpostorder.
2. Visittherightsubtree,usingpostorder
3. Visittheroot.
Thealgorithmforpreorder traversalisasfollows:
AlgorithmPostorder(t)
//tis a binarytree.Eachnodeoft hasthreefields:lchild,data,andrchild.
{
ift 0then
{
Postorder (t
lchild);Postorder (t
rchild);visit(t);
}
}
138
Examplesforbinarytreetraversal/searchtechnique:
Example1:
Traversethefollowingbinarytreeinpre,post andin-order.
A
Preord eri ngof
thevertices:A,B,D,C,E,G,F,
B C
H, I.
D E F Postorderingofthevertices:D,B,
G,E,H,I,F,C, A.
Example2:
Traversethefollowingbinarytreeinpre,post,inorderandlevel order.
A • Preordertraversalyields:A,B,D
,C,E,G ,F,H,I
B C
• Postordertraversalyields:D,B,G
,E,H,I,F,C,A
D E F
• Inordertraversalyields:D,B,A
G H I ,E,G,C,H,F,I
• Levelordertraversalyields:A,B,C,
D,E,F ,G,H,I
BinaryTree Pre,Post,InorderandlevelorderTraversing
Example3:
Traversethefollowingbinarytreeinpre,post,inorderandlevelorder.
• Preordertraversalyields:
P
P ,F,B,H,G, S,R,Y,T,W,Z
F S
• Postordertraversalyields:
R
B,G,H,F,R,W,T,Z,Y,S,P
B H Y
• Inordertraversalyields:
G T Z B,F ,G,H,P,R,S,T,W,Y,Z
W • Levelordertraversalyields:P , F ,
S,B,H,R,Y,G , T,Z,W
BinaryTree Pre,Post,InorderandlevelorderTraversing
139
Example4:
Traversethefollowingbinarytreeinpre,post,inorderandlevelorder.
• Preordertraversalyields:2,7,2
2
,6,5,11,5,9,4
7 5
• Postordertravarsalyields:2,5,1
1,6,7,4,9,5,2
2 6 9
• Inordertravarsalyields:2,7,5
5 11 4 ,6,11,2,5,4,9
• Levelordertraversalyields:2,7,5,
2,6,9,5,11,4
BinaryTree Pre,Post,InorderandlevelorderTraversing
Example5:
Traversethefollowingbinarytreeinpre,post,inorderandlevelorder.
K L M • Levelordertraversalyields:A,B,C,
D,E,G,H,K,L, M
BinaryTree Pre,Post,InorderandlevelorderTraversing
NonRecursiveBinaryTreeTraversalAlgorithms:
At first glance, it appears we would always want to use the flat traversal
functionssince the use less stack space. But the flat versions are not necessarily
better. Forinstance, some overhead is associated with the use of an explicit stack,
which maynegate the savings we gain from storing only node pointers. Use of the
implicitfunction call stack may actually be faster due to special machine instructions
that canbeused.
InorderTraversal:
Initially push zero onto stack and then set root as vertex. Then repeat the
followingsteps untilthestackisempty:
2. Pop and process the nodes on stack if zero is popped then exit. If a vertex
withright son exists, then set right son of vertex as current vertex and return
tostepone.
140
ThealgorithmforinorderNonRecursivetraversalisasfollows:
Algorithminorder()
{
stack[1] =
0vertex=root
top: while(vertex≠0)
{
pushthe
vertexintothestackvertex=leftson
(vertex)
}
while(vertex≠0)
{
print the vertex
nodeif(rightson(vertex)≠0)
{
vertex =
rightson(vertex)gototop
}
pop the elementfromthestackandmadeit asvertex
}
}
PreorderTraversal:
Initially push zero onto stack and then set root as vertex. Then repeat the
followingsteps untilthestackisempty:
1. Proceed down the left most path by pushing the right son of vertex onto
stack,if any and process each vertex. The traversing ends after a vertex with
no leftchildexists.
2. Popthevertexfromstack,ifvertex≠0thenreturntosteponeotherwise exit.
Algorithmpreorder()
{
stack[1]: =
0vertex :=
root.while(vertex
≠0)
{
print vertex
nodeif(rightson(vertex)≠0)
push the right son of vertex into the
stack.if(leftson(vertex)≠0)
vertex:=leftson(vertex)
else
pop the elementfromthestackandmadeit asvertex
}
}
141
PostorderTraversal:
Initially push zero onto stack and then set root as vertex. Then repeat the
followingsteps untilthestackisempty:
1. Proceed down the left most path rooted at vertex. At each vertex of path
pushvertex on to stack and if vertex has a right son push–(right son of
vertex)ontostack.
2. Popandprocessthepositivenodes(leftnodes).Ifzeroispoppedthenexit.Ifanegativen
odeispopped,thenignorethesignandreturntostepone.
ThealgorithmforpostorderNonRecursivetraversalisasfollows:
Algorithmpostorder()
{
stack[1] :=
0vertex:=root
top:while(vertex≠0)
{
push vertex onto
stackif(rightson(vertex)≠0)
push -(vertex) onto
stackvertex:=leftson(vertex)
}
pop from stack and make it as
vertexwhile(vertex>0)
{
printthevertexnode
popfromstackand makeitasvertex
}
if(vertex<0)
{
vertex := -
(vertex)gototop
}
}
Example1:
Traverse the following binary tree in pre, post and inorder using non-
recursivetraversingalgorithm.
A
• Preo rde r t rav e rs al y ie
B C lds:A,B,D,G,K,H,L,M,C,E
D E • Postordertravarsalyields:K,G,L,
M,H,D,B,E,C,A
G H
• Inordertravarsalyields:
K,G,D,L,H,M,B,A,E, C
K L M
BinaryTree Pre,PostandInorderTraversing
142
InorderTraversal:
Initially push zero onto stack and then set root as vertex. Then repeat the
followingsteps untilthestackisempty:
1. Proceed down the left most path rooted at vertex, pushing eachvertex
ontothestackandstop when thereisnoleftsonofvertex.
2. Pop and process the nodes on stack if zero is popped then exit. If a vertex
withright son exists, then set right son of vertex as current vertex and return
tostepone.
Current
Stack Processednodes Remarks
vertex
A 0 PUSH0
K 0ABDG K POPK
G 0ABD KG POPGsinceKhasnorightson
E 0C KGDLHM B AE POPE
PostorderTraversal:
Initially push zero onto stack and then set root as vertex. Then repeat the
followingsteps untilthestackisempty:
1. Proceed down the left most path rooted at vertex. At each vertex of path
pushvertexontostackandifvertexhasarightsonpush-(rightsonofvertex)ontostack.
2. Popandprocessthepositivenodes(leftnodes).Ifzeroispoppedthenexit.Ifanegativen
odeispopped,thenignorethesignandreturntostepone.
143
Current
Stack Processednodes Remarks
vertex
A 0 PUSH0
PUSHtheleftmostpathofAwitha-
0A-C BD-HGK
veforrightsons
0A-C BD-H KG POPall+ve nodesKandG
H 0A-C BD KG Pop H
PUSHtheleftmostpathofHwitha-
0A-C BDH-ML KG
veforrightsons
0A-C BDH-M KGL POPall+ve nodesL
PreorderTraversal:
Initially push zero onto stack and then set root as vertex. Then repeat the
followingsteps untilthestackisempty:
1. Proceed down the left most path by pushing the right son of vertex onto
stack,if any and process each vertex. The traversing ends after a vertex with
no leftchildexists.
2. Popthevertexfromstack,ifvertex≠0thenreturntosteponeotherwiseexit.
Current
Stack Processednodes Remarks
vertex
A 0 PUSH0
PUSH the right son of each vertex
0CH ABDGK ontostackandprocesseachvertexintheleft
mostpath
H 0C ABDGK POPH
PUSH the right son of each vertex
0CM ABDGKHL ontostackandprocesseachvertexintheleft
mostpath
M 0C ABDGKHL POPM
PUSH the right son of each vertex
0C ABDGKHLM ontostackandprocesseachvertexintheleft
mostpath;Mhas noleftpath
C 0 ABDGKHLM Pop C
PUSH the right son of each vertex
ontostack and process each vertex in
0 ABDGKHLMCE
the leftmostpath;Chas
norightsonontheleft
mostpath
0 ABDGKHLMCE Stopsincestackisempty
144
Example2:
Traverse the following binary tree in pre, post and inorder using non-
recursivetraversingalgorithm.
2 • Preordertraversalyields:2,7,2,
6,5,11,5,9,4
7 5
• Postordertravarsalyields:2,5,1
2 6 9 1,6,7,4,9,5,2
5 11 4 • Inordertravarsalyields:2,7,5
,6,11,2,5,4,9
BinaryTree Pre,PostandInorderTraversing
InorderTraversal:
Initially push zero onto stack and then set root as vertex. Then repeat the
followingsteps untilthestackisempty:
2. Pop and process the nodes on stack if zero is popped then exit. If a vertex
withright son exists, then set right son of vertex as current vertex and return
tostepone.
Current
Stack Processednodes Remarks
vertex
2 0
0272
2 027 2
7 02 27
6 0265 27
5 026 275
11 02 275611
5 05 2756 112
9 094 27561125
4 09 275611254
0 2756112549 Stopsincestackisempty
PostorderTraversal:
Initially push zero onto stack and then set root as vertex. Then repeat the
followingsteps untilthestackisempty:
1. Proceed down the left most path rooted at vertex. At each vertex of path
pushvertexon to stack andif vertex has a right son push–(right son of
vertex)ontostack.
145
2. Pop and process the positive nodes (left nodes). If zero is popped then exit.
Ifanegativenodeispopped,thenignorethesignandreturntostepone.
Current
Stack Processednodes Remarks
vertex
2 0
02 -57 -62
2 02 -57-6 2
6 02 -57 2
02 -576 -115 2
5 02 -576-11 25
11 02 -57611 25
02-5 251167
5 025-9 251167
9 02594 251167
0 2511674952 Stopsincestackisempty
PreorderTraversal:
Initially push zero onto stack and then set root as vertex. Then repeat the
followingsteps untilthestackisempty:
1. Proceed down the left most path by pushing the right son of vertex onto
stack,if any and process each vertex. The traversing ends after a vertex with
no leftchildexists.
2. Popthevertexfromstack,ifvertex≠0thenreturntosteponeotherwiseexit.
Current
Stack Processednodes Remarks
vertex
2 0
056 272
6 0511 27265
11 05 27265
05 2726511
5 09 2726511
9 0 27265115
0 2726511594 Stopsincestackisempty
Techniquesforgraphs:
GivenagraphG=(V,E)andavertexVinV(G)traversingcanbedoneintwoways.
1. Depthfirstsearch
2. Breadthfirstsearch
3. D-search(DepthSearch)
146
Depthfirstsearch:
With depth first search, the start state is chosen to begin, then some successor of
thestart state, then some successor of that state, then some successor of that and so
on,tryingtoreach agoalstate.
If depth first search reaches a state S without successors, or if all the successors of
astate S have been chosen (visited) and a goal state has not get been found, then
it“backs up” that means it goes to the immediately previous state or
predecessorformally,thestatewhosesuccessorwas„S‟originally.
Forexampleconsiderthefigure.Thecircledlettersarestateandarrowsarebranches.
A
E
START J
S B
H G GOAL
C F
K
I
Suppose S is the start and G is the only goal state. Depth first search will first visit
S,then A then D. But D has no successors, so we must back up to A and try its
secondsuccessor, E. But this doesn‟t have any successors either, so we back up to A
again.But now we have tried all the successors of A and haven‟t found the goal state
G sowe must back to „S‟. Now „S‟ has a second successor, B. But B has no
successors, sowe back up to S again and choose its third successor, C. C has one
successor, F. Thefirst successor of F is H, and the first of H is J. J doesn‟t have any
successors, so weback up to H and try its second successor. And that‟s G, the only
goal state. So
thesolutionpathtothegoalisS,C,F,HandGandthestatesconsideredwereinorderS,A,D,E,B,C
,F,H,J,G.
Disadvantages:
1. It works very fine when search graphs are trees or lattices, but can
getstruck in an infinite loop on graphs. This is because depth first search
cantravelaround acycleinthegraphforever.
2. One more problem is that, the state space tree may be of infinite depth,
topreventconsiderationofpathsthataretoolong,amaximumisoftenplacedonthe
depthofnodestobeexpanded,andanynodeatthatdepthistreated asifit had
nosuccessors.
3. Wecannotcomeupwithshortestsolutiontotheproblem.
147
TimeComplexity:
Let n = |V| and e = |E|. Observe that the initialization portion requires (n)
time.Since we never visit a vertex twice, the number of times we go through the loop
is atmost n (exactly n assuming each vertex is reachable from the source).
As,eachvertex is visited at most once. At each vertex visited, we scan its adjacency
list once.Thus, each edge is examined at most twice (once at each endpoint). So the
totalrunningtimeisO(n +e).
Alternatively,
Iftheaveragebranchingfactorisassumedas„b‟andthedepthofthesolutionas„d‟,andmaxim
umdepth m≥d.
SpaceComplexity:
We have to store the nodes from root to current leaf and all the unexpanded
siblingsof each nodeon path.So,We needtostorebmnodes.
Breadthfirstsearch:
Given an graph G = (V, E), breadth-first search starts at some source vertex S
and“discovers" which vertices are reachable from S. Define the distance between a
vertexV and S to be the minimum number of edges on a path from S to V. Breadth-
firstsearch discovers vertices in increasing order of distance, and hence can be used
as analgorithmforcomputingshortestpaths(wherethelengthofapath=numberofedges on
the path). Breadth-first search is named because it visits vertices across
theentirebreadth.
Toillustratethisletusconsiderthefollowing tree:
A
E
START J
S B
H G GOAL
C F
K
Breadth first search finds states level by level. Here we first check all the
immediatesuccessors of the start state. Then all the immediate successors of these,
then all theimmediate successors of these, and so on until we find a goal node.
Suppose S is thestart state and G is the goal state. In the figure, start state S is at
level 0; A, B and Care at level 1; D, e and F at level 2; H and I at level 3; and J, G
and K at level 4. Sobreadth first search, will consider in order S, A, B, C, D, E, F, H, I,
J and G and thenstopbecauseit hasreached thegoalnode.
148
Breadthfirstsearchdoesnothavethedangerofinfiniteloopsasweconsiderstatesinorderofincr
easingnumberofbranches(level)fromthestartstate.
One simple way to implement breadth first search is to use a queue data
structureconsistingofjustastartstate.Anytimeweneedanewstate,wepickitfromthefront of
the queue and any time we find successors, we put them at the end of
thequeue.Thatwayweareguaranteedtonottry(findsuccessorsof)anystatesatlevel
„N‟untilallstatesatlevel„N–1‟havebeentried.
TimeComplexity:
The running time analysis of BFS is similar to the running time analysis of many
graphtraversal algorithms. Let n = |V| and e = |E|. Observe that the initialization
portionrequires (n) time. Since we never visit a vertex twice, the number of times
we gothrough the loop is at most n (exactly n, assuming each vertex is reachable
from thesource). So, Running time is O (n + e) as in DFS. For a directed graph the
analysis isessentiallythesame.
Alternatively,
Iftheaveragebranchingfactorisassumedas„b‟andthedepthofthesolutionas„d‟.
In the average case the last term of the series would be b d/ 2. So, the complexity
isstillO(bd)
SpaceComplexity:
DepthSearch(D-Search):
The exploration of a new node cannot begin until the node currently being explored
isfully explored. D-search like state space search is called LIFO (Last In
FirstOut)search which uses stack data structure. To illustrate the D-search let us
consider thefollowingtree:
A
E
START J
S B
H G GOAL
C F
K
Thesearchorderforgoalnode(G)isasfollows:S,A,B,C,F,H,I,J,G.
149
TimeComplexity:
ThetimecomplexityissameasBreadth firstsearch.
RepresentationofGraphsandDigraphsbyAdjacencyList:
Let G = (V, E) be a digraph with n = |V| and let e = |E|. We will assume that
thevertices ofGare indexed {1,2,,n}.
Av,w
1 ifv,wEotherwise
0
Adjacency List: An array Adj [1 . . . . . . . n] of pointers where for 1 < v < n, Adj
[v]points to a linked list containing the vertices which are adjacent to v (i.e. the
verticesthat can be reached from v by a single edge). If the edges have weights then
theseweightsmay alsobestored in thelinked listelements.
1 2 3
1 1 1 2 3
1 1 1
2 3
2 0 0 1
3 0 1 0 3 2
Adjacencymatrixandadjacencylist
Adjacency matrices allow faster access to edge queries (for example, is (u, v)E)and
adjacency lists allow faster access to enumeration tasks (for example, find all
theverticesadjacent tov).
DepthFirstandBreadthFirstSpanningTrees:
BFSandDFSimposeatree(theBFS/DFStree)alongwithsomeauxiliaryedges(cross edges)
on the structure of graph. So, we can compute a spanning tree in agraph. The
computed spanning tree is not a minimum spanning tree. Trees are
muchmorestructuredobjectsthangraphs.Forexample,treesbreakupnicelyintosubtrees,
upon which subproblems can be solved recursively. For directed graphs
theotheredgesofthegraphcanbe classified asfollows:
150
Forwardedges:(u,v)wherevisaproperdescendentofuinthetree.
Cross edges: (u, v) where u and v are not ancestors or descendents of one
another(infact, theedgemaygobetween different treesoftheforest).
Depth firstsearchandtraversal:
Depth first search of undirected graph proceeds as follows. The start vertex V
isvisited.Nextanunvisitedvertex'W'adjacentto'V'isselectedandadepthfirstsearch from
'W' is initiated. When a vertex 'u' is reached such that all its adjacentvertices have
been visited, we back up to the last vertex visited, which has anunvisited vertex 'W'
adjacent to it and initiate a depth first search from W. The
searchterminateswhennounvisitedvertexcanbereachedfromanyofthevisitedones.
Letus considerthefollowingGraph(G):
2 3
4 5 6 7
Graph
Vertex
2 3
1
1 4 5
3 1 6 7
4 2 8
5 2 8
6 3 8
7 3 8
8 4 5 6 7
If the depth first is initiated from vertex 1, then the vertices of G are visited in
theorder:1,2,4,8,5,6,3,7.Thedepthfirstspanningtreeisasfollows:
151
1
2 3
4 5 6 7
DepthFirstSpanningTree
The spanning trees obtained using depth first searches are called depth first
spanningtrees. The edges rejected in the context of depth first search are called a
back edges.Depthfirstspanning treehasnocrossedges.
Breadthfirstsearchandtraversal:
Starting at vertex 'V' and marking it as visited, BFS differs from DFS in that
allunvisited vertices adjacent to V are visited next. Then unvisited vertices adjacent
tothereverticesarevisitedandsoon.Abreadthfirstsearchbeginningatvertex1ofthegraph
would firstvisit 1andthen 2and3.
2 3
4 5 6 7
BreadthFirstSpanningTree
Next vertices 4, 5, 6 and 7 will be visited and finally 8. The spanning trees
obtainedusing BFS are called Breadth first spanning trees. The edges that were
rejected in thebreadthfirstsearcharecalled crossedges.
ArticulationPointsandBiconnectedComponents:
LetG=(V,E)beaconnectedundirectedgraph.Considerthefollowingdefinitions:
Bridge:Isanedgewhoseremovalresultsinadisconnectedgraph.
Biconnected:Agraphisbiconnectedifitcontainsnoarticulationpoints.Inabiconnectedgrap
h,twodistinctpathsconnecteachpairofvertices.Agraphthatisnotbiconnecteddividesintobic
onnectedcomponents.Thisisillustratedinthefollowingfigure:
152
Biconnected
Components
ArticulationPointBridge
Articulation PointsandBridges
Biconnected graphs and articulation points are of great interest in the design
ofnetwork algorithms, because these are the “critical" points, whose failure will result
inthenetworkbecomingdisconnected.
Let us consider the typical case of vertex v, where v is not a leaf and v is not the
root.Let w1, w2, . . . . . . . wk be the children of v. For each child there is a subtree of
theDFStree rootedatthis child. If for somechild, there is no backedge goingto
aproperancestorofv,thenifweremovev,thissubtreebecomesdisconnectedfromtherestofth
egraph,andhencevisanarticulationpoint.
On the other hand, if every one of the subtree rooted at the children of v have
backedgestoproperancestorsofv,thenifvisremoved,thegraphremainsconnected(theback
edgesholdeverythingtogether).Thisleadstothefollowing:
Observation 1: An internalvertex v of the DFS tree (other than the root) isan
articulation point if and only if there is a subtree rooted at a child of v suchthat
there is no back edge from any vertex in this subtree to a proper ancestorofv.
Thus,afterdeletionofaleaffromatree,therestofthetreeremainsconnected, thus
evenignoring the backedges, the graph is connected afterthedeletion
ofaleaffromtheDFStree.
153
ArticulationPointsbyDepth FirstSearch:
Determiningthearticulationturnsouttobeasimpleextensionofdepthfirstsearch.Consideradepth
first spanning tree forthisgraph.
A H I
B C G
J K
D
E
F L M
Observations1,2,and3provideuswithastructuralcharacterizationofwhichverticesin theDFS
treeare articulationpoints.
A vertex „x‟ is not an articulation point if every child „y‟ has some node lower in
thetreeconnect(viaadottedlink)toanodehigherinthetreethan„x‟,thusprovidinganalternat
e connection from „x‟ to „y‟. This rule will not work for the root node sincethere are
no nodes higher in the tree. The root is an articulation point if it has two
ormorechildren.
DepthFirstSpanningTreefortheabovegraphis:
Byusingtheaboveobservationsthearticulationpointsofthisgraphare:A:
deleted.Biconnectedcomponentsare:{A,C,G,D,E,F},{G,J,L,M},B,H,IandK
154
This observation leads to a simple rule to identify articulation points. For each
isdefine L(u) asfollows:
L (u) = min {DFN (u), min {L (w) w is a child of u}, min {DFN (w) (u,
w)isabackedge}}.
L (u) is the lowest depth first number that can be reached from „u‟ using a path
ofdescendents followed by at most one back edge. It follows that, If „u‟ is not the
rootthen„u‟isanarticulationpointiff„u‟hasachild„w‟suchthat:
L(w)≥DFN(u)
6.6.2. AlgorithmforfindingtheArticulationpoints:
PseudocodetocomputeDFNandL.
AlgorithmArt(u,v)
//uis astartvertexfordepthfirst search. V isits parent ifany inthedepthfirst
// spanning tree. It is assumed that the global array dfn is initialized to zero and that //
theglobalvariablenumisinitializedto1.nisthe numberofverticesinG.
{
dfn[u]:=
num;L[u]:=num;num:=num+1;foreachvertexw
adjacent fromudo
{
if(dfn[w] =0)then
{
Art(w,u); // w is
unvisited.L[u]:=min(L [u], L[w]);
}
elseif(wv)then L[u]:=min(L[u], dfn[w]);
}
}
6.6.1. AlgorithmforfindingtheBiconnectedComponents:
AlgorithmBiComp(u,v)
//uis astart vertexfordepthfirstsearch.V isitsparent ifany inthedepthfirst
//spanning tree.Itis assumed thattheglobal arraydfnisinitiallyzero andthatthe
//global variable numisinitializedto 1.nisthenumberofverticesinG.
{
dfn[u]:= num;L [u]:=num;num
:=num+1;foreachvertexw adjacent fromudo
{
if ((v w) and (dfn [w] < dfn [u]))
thenadd(u,w)tothetopofastacks;
if(dfn[w] =0)then
{
if(L [w]>dfn[u])then
{
write (“New
bicomponent”);repeat
{
Delete an edge from the top of stack
s;Letthisedgebe(x,y);
Write(x,y);
}until(((x,y)=(u,w))or((x,y)=(w,u)));
}
155
BiComp(w,u); // w is
unvisited.L[u]:=min(L [u], L[w]);
}
elseif(wv)thenL[u]: =min(L[u],dfn[w]);
}
}
6.7.1. Example:
ForthefollowinggraphidentifythearticulationpointsandBiconnectedcomponents:
86
11
11 57
24
2 4 62 7 9
33
33 8 10
4 10 5 9 6 2
4 10 95
75
Graph
86 79
8 10
DepthFirstSpanningTree
Toidentifythearticulationpoints,weuse:
L(u) = min {DFN (u), min {L (w) w is a child of u}, min {DFN (w) w is a
vertextowhichthere isback edgefromu}}
L (1) =min{DFN(1),min{L(4)}}=min{1,L(4)}=min{1,1}=1
L (4) =min{DFN(4),min{L(3)}}=min{2,L(3)}=min{2,1}=1
L (3) =min{DFN(3),min{L(10),L(9),L(2)}}=
=min{3,min{L(10),L(9),L(2)}}=min{3,min{4,5,1}}=1
L(10)=min{DFN(10)}=4
L(9)=min{DFN(9)} =5
L (5) =min{DFN(5),min{L(6),L(7)}}=min{7,8,6}=6
L (6) =min{DFN(6)}=8
L (7) =min {DFN(7),min {L(8},min{DFN(2)}}
=min {9,L(8),6}= min {9,6,6}=6
L (8) =min{DFN(8),min{DFN(5),DFN(2)}}
156
=min{10,min(7,6)}=min{10,6}=6
FindingtheArticulationPoints:
Vertex1:Vertex1isnotanarticulationpoint.Itisarootnode.Rootisanarticulationpointifit hastwo or
more childnodes.
Vertex2:isanarticulationpointaschild5hasL(5)=6andDFN(2)=6,So,theconditionL
(5)=DFN(2)istrue.
Vertex3:isanarticulationpointaschild10hasL(10)=4andDFN(3)=3,So,the condition
L(10) >DFN (3) istrue.
Vertex4:isnotanarticulationpointaschild3hasL(3)=1andDFN(4)=2,So,the condition
L(3)>DFN(4) isfalse.
Vertex5:isanarticulationpointaschild6hasL(6)=8,andDFN(5)=7,So,theconditionL
(6)>DFN(5)istrue.
Vertex7:isnotanarticulationpointaschild8hasL(8)=6,andDFN(7)=9,So,the condition
L(8)>DFN(7) isfalse.
Therefore,thearticulationpointsare{2,3,5}.
Example:
ForthefollowinggraphidentifythearticulationpointsandBiconnectedcomponents:
4 1 1
1
2 3 7 8 2 2 3 3
5 6 4 5 5 6 4 6
Graph
7 7
8 8
DFS spanningTree
157
Vertex
1 2
2 1 3
3 2 5 6 4
4 3 7 8
5 3
6 3
7 4 8
8 4 7
Adjacency List
L(u) = min {DFN (u), min {L (w) w is a child of u}, min {DFN (w) w is a
vertextowhichthere isback edgefromu}}
L(1)=min{DFN(1),min{L(2)}}=min{1,L(2)}=min{1,2}=1
L(2)=min{DFN(2),min{L(3)}}=min{2,L(3)}=min{2,3}=2
L(3)=min{DFN(3),min{L(4),L(5),L(6)}}=min{3,min{6,4,5}}=3
L(4)=min{DFN(4),min{L(7)}=min{6,L(7)}=min{6,6}=6
L(5)=min {DFN(5)}=4
L(6)=min {DFN(6)}=5
L(7)=min{DFN(7),min{L(8)}}=min{7,6}=6
L(8)=min{DFN(8),min{DFN(4)}}=min{8,6}=6
Therefore,L(1:8)={1,2,3,6,4,5,6,6}
FindingtheArticulationPoints:
CheckfortheconditionifL(w)>DFN(u)istrue,wherewisanychildofu.Vertex1:
Vertex1isnot an articulationpoint.
Itisarootnode.Rootisanarticulationpointifithastwoormorechildnodes.
Vertex2:isanarticulationpointasL(3)=3andDFN(2)=2.
So,theconditionistrue
Vertex3:isan articulationPointas:
I. L(5)=4and DFN(3)=3
II. L(6)=5andDFN(3)=3and
III. L(4)=6and
DFN(3)=3So,theconditiontrueinabove
cases
158
Vertex4:isanarticulationpointasL(7)=6andDFN(4)=6.
So,theconditionistrue
Vertex7:isnotanarticulationpointasL(8)=6andDFN(7)=7.
So,theconditionisFalse
nodes.Therefore,thearticulationpointsare{2,3,4}.
Example:
ForthefollowinggraphidentifythearticulationpointsandBiconnectedcomponents:
1 1
5
2 2
1
6 3 3
2 4
4 4
8
3
5 5 7 8
7
Graph 6 6 Depth
FirstSpanning
Tree
7 8
DFN(1: 8) ={1,2,3,4,5,6,8,7}
Vertex
2 4 5
1
1 3
3 2 4 7
4 1 3 5 6 7 8
5 1 4 6
6 4 5 8
7 3 4
8 4 6
Adjacency List
L(u) = min {DFN (u), min {L (w) w is a child of u}, min {DFN (w) w is a
vertextowhichthere isback edgefromu}}
L(2)=min{DFN(2),min{L(3)}}=min{2,L(3)}=min{2,1}=11
159
L(3) = min {DFN(3),min{L(4)}}=min{3,L(4)} =min {3,L(4)}
=min {3,1} =1
Therefore,L(1:8)={1,1,1,1,1,4,3,4}
FindingtheArticulationPoints:
CheckfortheconditionifL(w)>DFN(u)istrue,wherewisanychildofu.Vertex1:
isnotanarticulationpoint.
Itisarootnode.Rootisanarticulationpointifithastwoormorechildnodes.
Vertex2:isnotanarticulationpoint.AsL(3)=1andDFN(2)=2.
So,theconditionisFalse.
Vertex3:isnotanarticulationPointasL(4)=1andDFN(3)=3.
So,theconditionisFalse.
Vertex4:isnotanarticulationPointas:
L(3)=1andDFN(2)=2and
L(7)=3and DFN(4)=4
So,theconditionfailsinbothcases.
Vertex5:isnotanArticulationPointasL(6)=4andDFN(5)=6.
So,theconditionisFalse
Vertex6:isnotanArticulationPointasL(8)=4andDFN(6)=7.
So, the condition is
FalseVertex7: isaleafnode.
Vertex8:isaleafnode.
Sothey arenoarticulationpoints.
GAMEPLAYING
Ingame-playingliterature,thetermplayisusedforamove.Thetwomajorcomponentsofgame-
playingprogramareplausiblemovegenerator,andastaticevaluationfunctiongenerator.
160
Inagameofchess,foreverymoveaplayermakes,theaveragebranchingfactoris35,thatistheo
pponentcanmake35differentmoves.Itmaynotbepossibletoexamineallthe states because
the amount of time given for a move is limited and the amount ofcomputational power
available for examining various states is also limited. Hence it isessential that only
very selected moves or paths are examined. For this purpose
only,onehasaplausiblemovegenerator,thatexpandsorgeneratesonlyselectedmoves.
The SEF gives a snapshot of a particular move. More the SEF value, more is
theprobability for a victory. Games can be classified as either a single person playing
ormulti-personplaying.Forsinglepersongames(forexample,Rubik'scube,8-
tilepuzzleetc.)searchstrategiessuchasBest-firstbranchandboundalgorithmcan be used.
Ontheotherhand,inatwo-persongameslikechess,checkersetc.,eachplayertriestooutsmart
the opponent. Each has their own way of evaluating the situation and sinceeach player
tries to obtain the maximum benefits, best first search branch and
boundalgorithmdonotservethepurpose.Thebasicmethodsavailableforgameplayingare:
1. Minimaxsearch.
2. Minimaxsearchwithalphabetacutoffs.
MINIMAXSEARCH
The standard algorithm for two-player games is called minimax search with
staticevaluation. We have to add more knowledge to improve search and to reduce
thecomplexity. Heuristic search adds a small amount of knowledge to a problem
space,giving,surprisingly,afairlydramaticeffectoftheefficiencyofsearchalgorithm.Agoodh
euristic is to select roads that go in the direction of the goal. In this case we call it
asheuristicstaticevaluationfunctionthattakesaboardpositionandreturnsanumberthatindic
ates how favorable that position is to one player or other. We call our players
asMAXandMIN.
The large positive values would correspond to strong positions for one player
whereaslargenegativevalueswouldrepresentadvantageoussituationsfortheopponent.
The player for whom large positive values are advantageous is called the MAX,
andconversely the opponent is referred to as MIN. The value of a node where it is
MAX'sturntomoveismaximumofthevaluesofitschildren,whilethevalueofanodewhereMINis
tomoveistheminimumofthevaluesofitschildren.
MAX represents the player trying to win, or to MAXimize his/her advantage. MIN,
theopponent attempts to MINimize MAX's score. (i.e. we can assume that MIN uses
thesameinformationandalwaysattemptstomovetoastatethatisworstforMAX).
At alternate levels of tree, the minimum and the maximum values of the children
arebackedup. The backingup values is done as follows: The (MAX node) parent of MIN
tipnodesisassignedabackedupvalueequaltothemaximumoftheevaluationsofthetipnodes,
on the other hand, if MIN were to choose among tip nodes, he will choose thathaving
the smallest evaluation (the most negative). Therefore, the (MIN node),
parentofMAXtip nodesisassignedabackedupvalueequaltotheminimumofthe
evaluationofthe tipnodes.
161
After the parents of all tip nodes have been assigned backedup values, we
backupvaluesanotherlevel,assumingthatMAXwouldchoosethatnodewithlargestbackedup
value,whileMINwouldchoosethatnodewithsmallestbackedupvalue.
We continue the procedure level by level, until finally, the successors of the start
nodeare assigned backedup values. The search algorithm then uses these derived
values toselectamongpossiblenextmoves.
A -2 MAX
B -6 C -2 D -4 MIN
E F G H I J K MAX
9 -6 0 0 -2 -4 -3
Thebestfirstmovecanbeextractedfromminimaxprocedureaftersearchterminates.
EXAMPLE
To illustrate these ideas, let us consider a simple game called "Grundy's game".
Therules of the game are as follows: Two players have in front of them a single pile of
7matches. At each move the player must divide a pile of matches into two non-
emptypiles with different numbers of matches in each pile. Thus, 6 matches may be
dividedinto piles of 5 and 1 or 4 and 2, but not 3 and 3. The first player who can no
longermake a move loses the game. The following figure shows the space for a game
with 7matchesandletMINplayfirst:
MIN 7
MIN
3- 1 -1- 1-1 2-2-1- 1 -1
AGAMEGRAPHFORGRUNDYSGAME
Wecanalsousethegametreetoshowthat,nomatterwhatmindoesmaxcanalwayswin. A
winning strategy for max is shown by heavy lines. Max, can always force
thegametoawin,regardless ofmin‟sfirstmove.Mincouldwinonly ifmax playedfoolishly.
162
6.8. ALPHA-BETAPRUNING
The minimax pursues all branches in the space, including many that can be ignored
orprunedbyamoreintelligentalgorithm.Researchersingameplayinghavedevelopedaclasso
fsearchtechniquecalledAlpha-betapruningtoimprovetheefficiencyofsearchintwo-
persongames.
Theideaforalpha-
betasearchissimple:Twovaluescalledalphaandbetaarecreatedduringthesearch.Thealph
avalue,associatedwithMAXnodes,canneverdecrease,andthebetavalue,associatedwithMI
Nnodes,canneverincrease.
Suppose for example, MAX node's alpha value is 6, then MAX need not consider
anybackedup value less than or equal to 6 that is associated with any MIN node below
it.Similarly,ifMINhasabetavalueof6,itneednotconsiderfurtheranyMAXnodebelowitthatha
savalueof6ormore.
Because of these constraints, we can state the following two rules for terminating
thesearch:
1. Search can be stopped below any MIN node having a beta value less than
orequal to the alpha value of any of its MAX node ancestors. The final
backedupvalueofthisMINnodecanthenthesettoitsbetavalue.
2. SearchcanbestoppedbelowanyMAXnodehavinganalphavaluegreaterthanor equal
to the beta value of any of its MIN node ancestors. The final
backedupvalueofthisMAXnodecanthenbesettoitsalphavalue.
Similarly, after statically evaluating nodes J and K to 2 and 1, the backed up value
istheirmaximumor2.ThistellsthatthebackedupvalueofnodeHmustbeless
thanorequalto2,sinceittheminimumof2andtheunknownvalueofnodeX.Sincethevalueofno
deAisthemaximumof6andavaluethatmustbelessthanorequalto2,itmustbe6,andhencewe
haveevaluatedtherootofthetreewithoutgeneratingorevaluatingthenodesX,YorZ.Thisiscal
ledBETACUTOFF.
The whole process of keeping track of alpha and beta values and making cutoff's
whenpossibleiscalledasalpha-betaprocedure.
163
A 6
B6 2 H<=2
C 6 F>=8 8 I 2 X
6 5 8 2 1
D E G W J K Y Z
Alpha-BetaPruning
6.8.1. EXAMPLE2:
Takingthespaceoffigureasshownbelowandwhenalpha-
betapruningappliedisonthisproblem,isasfollows:
3 C Max
3 0 2 3 A D 2 E Min
3 9 7 2 6 2 Max
3 B
0
2 3 7 4 2 1 5 6 2 3 5 0 2 1 Min
5 9
Ahasβ=3(Awillbenolargerthan3).Bis
βpruned,since5>3.
Chasα=3(Cwillbenosmallerthan3).Dis
αpruned,since0 <3.
Eisαpruned,since2<3.Cis3.
AND/ORGRAPH:
A hypergraph consists
of:N,a setofnodes,
164
Hyperarcs also known as K-connectors, where K is the cardinality of the set
ofdecendent nodes. If K = 1, the descendent may be thought of as an OR nodes. If K
>1,theelementsofthesetofdecendentsmaybethoughtofasANDnodes.Inthiscase the
connector is drawn with individual edges from the parent node to each of
thedecendentnodes;theseindividualedgesarethenjoinedwithacurvedlink.
And/orgraphfortheexpressionPandQ->Risfollows:
R
N1
N2
N
P Q Nk
TheK-connectorisrepresentedasafanofarrowswithasingletieisshownabove.
The and/or graphs consists of nodes labelled by global databases. Nodes labelled
bycompound databases have sets of successor nodes. These successor nodes are
calledANDnodes,inordertoprocessthecompounddatabasetotermination,allthecompound
databasesmustbeprocessed totermination.
For example consider, consider a boy who collects stamps (M). He has for the
purposeof exchange a winning conker (C), a bat (B) and a small toy animal (A). In his
classthere are friends who are also keen collectors of different items and will make
thefollowingexchanges.
1. 1winningconker(C)foracomic(D)andabagofsweets(S).
2. 1winningconker(C) forabat(B)andastamp(M).
3. 1bat(B)fortwostamps(M,M).
4. 1smalltoyanimal(A)fortwobats(B,B)andastamp(M).
The problem is how to carry out the exchanges so that all his exchangable items
areconvertedintostamps(M).Thistaskcanbeexpressedmorebrieflyas:
1. Initial state=(C,B,A)
2. Transformationrules:
a. IfCthen(D,S)
b. IfCthen(B,M)
c. IfBthen(M,M)
d. IfAthen(B,B,M)
165
(C,B,A)
(M MM MMMM M MM)GOAL
ExpansionfortheexchangeproblemusingORconnectorsonly
Thefigureshowsthat,alotofextraworkisdonebyredoingmanyofthetransformations. This
repetition can be avoided by decomposing the problem
intosubproblems.Therearetwomajorwaystoorderthecomponents:
Themoreflexiblesystemistoreorderdynamicallyastheprocessingunfolds.Itcanberepresent
edbyand/orgraph.Thesolutiontotheexchangeproblemwillbe:
Swap conker for a bat and a stamp, then exchange this bat for two
stamps.Swap his own bat for two more stamps, and finally swap the small toy
animalfortwobatsandastamp.Thetwobatscanbeexchangedfortwostamps.
(CBA)
(M M) (M M) (M M)
166
Example1:
DrawanAnd/Orgraphforthefollowingprepositions:
1. A
2. B
3. C
4. A^B->D
5. A^C->E
6. B^D->F
7. F->G
8. A^E->H
C A B
E D
H F
167
Chapter
7
BACKTRACKING
GeneralMethod:
The solution is based on finding one or more vectors that maximize, minimize,
orsatisfyacriterionfunctionP(x1, ............ ,xn).Formasolutionandcheck ateverystep
if this has any chance of success. If the solution at any point seems not
promising,ignore it. All solutions requires a set of constraints divided into two
categories: explicitandimplicitconstraints.
Definition 1: Explicit constraints are rules that restrict each x i to take on values
onlyfrom a given set. Explicit constraints depend on the particular
instance Iof problem being solved. All tuples that satisfy the explicit
constraintsdefineapossiblesolution spaceforI.
Definition 2: Implicit constraints are rules that determine which of the tuples in
thesolutionspaceofIsatisfythecriterionfunction.Thus,implicit constraintsdes
cribethewayinwhichthex i‟smustrelatetoeachother.
For8-queensproblem:
Explicitconstraintsusing8-
tupleformation,forthisproblemareS={1,2,3,4,5,6,7,8}.
The implicit constraints for this problem are that no two queens can be
thesame(i.e.,allqueensmustbeondifferentcolumns)andnotwoqueenscanbeon
thesamediagonal.
Backtrackingisamodifieddepthfirstsearchofatree.Backtrackingalgorithmsdetermine
problem solutions by systematically searching the solution space for thegiven problem
instance. This search is facilitated by using a tree organization for thesolutionspace.
Backtracking is the procedure where by, after determining that a node can lead
tonothing but dead end, we go back (backtrack) to the nodes parent and proceed
withthesearchon thenextchild.
Abacktrackingalgorithmneednotactuallycreateatree.Rather,itonlyneedstokeep track of
the values in the current branch being investigated. This is the way
weimplementbacktracking algorithm. We say thatthe state space tree exists
implicitlyinthealgorithmbecauseitisnotactuallyconstructed.
168
Terminology:
Problemstateiseach nodeinthedepthfirstsearchtree.
Solutionstatesaretheproblemstates„S‟forwhichthepathfromtherootnodeto
„S‟definesatupleinthesolutionspace.
Answer states are those solution states for which the path from root node to
sdefinesatuplethatisamemberofthesetofsolutions.
State space is the set of paths from root node to other nodes. State space tree is
thetree organization of the solution space. The state space trees are called static
trees.Thisterminologyfollowsfromtheobservationthatthetreeorganizationsareindepende
ntoftheprobleminstancebeingsolved.Forsomeproblemsitisadvantageoustousedifferenttr
eeorganizationsfordifferentprobleminstance.Inthiscasethetreeorganizationisdetermined
dynamicallyasthesolutionspaceisbeing searched. Tree organizations that are problem
instance dependent are calleddynamictrees.
Live node is a node that has been generated but whose children have not yet
beengenerated.
E-node is a live node whose children are currently being explored. In other words,
anE-nodeisa nodecurrently beingexpanded.
Deadnodeisageneratednodethatisnottobeexpandedorexploredanyfurther.Allchildrenof
adeadnodehavealreadybeenexpanded.
BranchandBoundreferstoallstatespacesearchmethodsinwhichallchildrenofanE-
nodearegeneratedbeforeanyotherlivenodecanbecometheE-node.
PlanarGraphs:
Example:
a
a
e b
the e b
followinggraphcanberedrawnwithoutcrossoversa
d c
sfollows:
d c
169
BipartiteGraph:
Example:
a b c a c e
Thegraph isbipartite.Wecanredrawitas
d e f b d f
The vertex setV = {a, b, c, d, e, f}has been partitioned into V 1 = {a, c, e} andV2 =
{b, d, f}. The complete bipartite graph for which V 1 = n and V2 = m is denotedKn,m.
N-QueensProblem:
TheexplicitconstraintsusingthisformulationareS i={1,2,3,4,5,6,7,8},1<i<
8. Thereforethesolutionspaceconsistsof8 88-tuples.
The implicit constraints for this problem are that no two xi‟s can be the same (i.e.,
allqueens must be on different columns) and no two queens can be on the
samediagonal.
Thisrealizationreducesthesizeofthesolutionspacefrom8 8tuplesto8!Tuples.
The promising function must check whether two queens are in the same column
ordiagonal:
Supposetwoqueensareplacedatpositions(i,j)and(k,l)Then:
Diag45conflict:Twoqueensiandjareonthesame45 0diagonalif:
i–j =k–l.
Thisimplies,j –l=i–k
Diag135conflict:
i+j =k+l.
Thisimplies,j –l=k–i
170
Therefore,twoqueenslieonthesamediagonalifandonlyif:
j- l=i–k
Where,jbethecolumnofobjectinrowiforthei thqueenandlbethecolumnofobjectinrow„k‟forthe
kthqueen.
Tocheckthediagonalclashes,letustakethefollowingtileconfiguration:
*
Inthisexample,wehave:
*
*
i 1 2 3 4 5 6 7 8
*
* xi 2 5 1 8 4 7 3 6
*
Let us consider for
*
thecasewhether thequeenson 3rd rowand
* th
8 rowareconflicting ornot.Inthis
case(i,j)=(3,1)and(k,l)=(8,6).Therefore:
Example:
Supposewestartwiththefeasiblesequence7,5,3,1.
*
*
*
*
Step1:
Add to the sequence the next number in the sequence 1, 2, . . . , 8 not
yetused.
Step2:
If this new sequence is feasible and has length 8 then STOP with a solution.
Ifthenewsequenceisfeasibleandhaslengthlessthen8,repeatStep1.
Step3:
If the sequence is not feasible, then backtrack through the sequence until
wefind the most recent place at which we can exchange a value. Go back to
Step1.
171
Remarks
1 2 3 4 5 6 7 8
7 5 3 1
j- l= 1–2=1
7 5 3 1* 2*
i–k=4–5=1
7 5 3 1 4
j- l= 7–2=5
7* 5 3 1 4 2*
i–k=1–6=5
j- l= 3–6=3
7 5 3* 1 4 6*
i–k=3–6=3
7 5 3 1 4 8
j- l= 4–2=2
7 5 3 1 4* 8 2*
i–k=5–7=2
j- l= 4–6=2
7 5 3 1 4* 8 6*
i–k=5–7=2
7 5 3 1 4 8 Backtrack
7 5 3 1 4 Backtrack
7 5 3 1 6
j- l= 1–2=1
7* 5 3 1 6 2*
i–k=7–6=1
7 5 3 1 6 4
7 5 3 1 6 4 2
j-l=3–8=5
7 5 3* 1 6 4 2 8*
i –k=3–8=5
7 5 3 1 6 4 2 Backtrack
7 5 3 1 6 4 Backtrack
7 5 3 1 6 8
7 5 3 1 6 8 2
7 5 3 1 6 8 2 4 SOLUTION
*indicatesconflictingqueens.
Onachessboard,thesolution willlooklike:
*
*
*
*
*
*
*
*
172
4–QueensProblem:
Let us see how backtracking works on the 4-queens problem. We start with the
rootnode as the only live node. This becomes the E-node. We generate one child. Let
usassume that the children are generated in ascending order. Let us assume that
thechildren are generated in ascending order. Thus node number 2 of figure is
generatedand the path is now (1). This corresponds to placing queen 1 on column 1.
Node 2becomes the E-node. Node 3 is generated and immediately killed. The next
nodegenerated is node 8 and the path becomes (1, 3). Node 8 becomes the E-
node.However, it gets killed as all its children represent board configurations that
cannotlead to an answer node. We backtrack to node 2 and generate another child,
node 13.The path is now (1, 4). The board configurations as backtracking proceeds is
asfollows:
1 1 1 1
. . 2 2 2
. . . . . 3
1 1 1 1
2 . . . 2 2
3 3
. . . . . . 4
(e) (f) (g) (h)
The above figure shows graphically the steps that the backtracking algorithm
goesthrough as it tries to find a solution. The dots indicate placements of a queen,
whichweretriedandrejectedbecauseanotherqueenwasattacking.
In Figure (b) the second queen is placed on columns 1 and 2 and finally settles
oncolumn 3. In figure (c) the algorithm tries all four columns and is unable to place
thenextqueenonasquare. Backtrackingnowtakes place.Infigure (d)the secondqueen is
moved to the next possible column, column 4 and the third queen is placedon column
2. The boards in Figure (e), (f), (g), and (h) show the remaining steps
thatthealgorithmgoesthrough untilasolutionisfound.
173
ComplexityAnalysis:
n1
1nn2n3........... nn n 1
n1
81
Fortheinstanceinwhichn=8,thestatespacetree contains: 8
1=19,173,961nodes
81
ProgramforN-QueensProblem:
# include
<stdio.h># include
<conio.h>#include
<stdlib.h>
place(intk)
{
inti;
for(i=1;i<k;i++)
{
if ((x [i] == x [k]) || (abs (x [i] – x [k]) == abs (i -
k)))return(0);
}
return(1);
}
nqueen(intn)
{
int m, k, i =
0;x[1]=0;
k=1;
while(k>0)
{
x[k]= x[k]+1;
while((x[k]<=n)&&(!place(k)))x[k]
= x[k]+1;
if(x[k]<=n)
{
if(k==n)
{
i++;
printf (“\ncombination;
%d\n”,i);for(m=1;m<=n;m++)
printf(“row = %3d\t column=%3d\n”, m,
x[m]);getch();
}
else
{
k++;
x[k]=0;
}
}
else
k--;
}
174
return(0);
175
}
main()
{
int
n;clrscr();
printf (“enter value for N:
“);scanf(“%d”,&n);
nqueen(n);
}
Output:
EnterthevalueforN:4Co
mbination:1 Combination:2
Row=1 column=2 3
Row = 2 column = 4 1
Row = 3 column = 1 4
Row = 4 column = 3 2
ForN=8,therewillbe92combinations.
SumofSubsets:
Given positive numbers wi, 1 ≤ i ≤ n, and m, this problem requires finding all
subsetsofwiwhosesumsare„m‟.
Allsolutionsarek-
tuples,1≤k≤n.Explicitconstraints:
xiЄ{j|jisanintegerand1≤j≤n}.
Implicitconstraints:
Notwoxicanbethesame.
Thesumofthecorrespondingw i‟sbem.
Abetterformulationoftheproblemiswherethesolutionsubsetisrepresentedbyan n-tuple(x1,..
.. . ,xn)such thatxi Є{0,1}.
Theabovesolutionsarethenrepresentedby(1,1,0,1)and(0,0,1,1).Forboththeab
Forexample,n=4,w=(11,13,24,7)andm=31,thedesiredsubsetsare(11,
13,7)and(24,7).
176
The following figure shows a possible tree organization for two possible
formulationsofthe solution space forthecase n=4.
x1=1 1 x1=4
x1=2 x1=3
2 3 4 5
x2=4
x2=2 x2=3 x2=4
x2=3 x2=4
6 7 8 9 10 11
x3=3 S
x3=4 x3=4 x3=4
12 13 1 4 15
S
x4=4
16
Apossiblesolutionspaceorganisationforthesumofthesubsetsp
roblem.
Graph Coloring(forplanargraphs):
Given any map, if the regions are to be colored in such a way that no two
adjacentregionshavethesamecolor,onlyfourcolorsareneeded.
For many years it was known that five colors were sufficient to color any map, but
nomap that required more than four colors had ever been found. After several
hundredyears, this problem was solved by a group of mathematicians with the help of
acomputer.Theyshowedthatinfactfourcolorsaresufficientforplanar graphs.
The function m-coloring will begin by first assigning the graph to its adjacency
matrix,setting the array x [] to zero. The colors are represented by the integers 1, 2, .
. . , mand the solutions are given by the n-tuple (x1, x2, . . ., xn), where xi is the color
ofnodei.
177
Algorithmmcoloring(k)
//This algorithm was formed usingthe recursivebacktrackingschema.Thegraphis
// represented by its Boolean adjacency matrixG[1:n,1:n]. Allassignmentsof
//1,2, ........... ,mtothevertices ofthegraphsuchthatadjacentverticesareassigned
//distinct integersareprinted.kistheindexofthenext vertextocolor.
{
repeat
{ //Generate alllegalassignments forx[k].
NextValue(k); // Assign to x [k] a legal
color.If(x[k]= 0)thenreturn;
//NonewcolorpossibleIf(k
=n)then //atmostmcolorshavebeen
//usedtocolorthenvertices.
write(x[1:n]);
elsemcoloring(k+1);
}until(false);
}
AlgorithmNextValue(k)
//x[1] , .......... x[k-1]have been assigned integervaluesintherange[1,m]suchthat
//adjacentvertices have distinctintegers.Avalueforx[k]isdeterminedintherange
//[0,m].x[k]isassignedthenexthighestnumberedcolorwhilemaintainingdistinctness
//from the adjacentverticesofvertexk. If no such colorexists,thenx[k]is0.
{
repeat
{
x [k]: = (x[k] +1)mod(m+1) //Nexthighestcolor.
If(x[k]= 0)thenreturn; //Allcolorshavebeenusedforj
:=1to ndo
{ // check if this color is distinct from adjacent
colorsif((G[k,j]0)and(x [k]=x[j]))
// If (k, j) is and edge and if adj. vertices have the same
color.thenbreak;
}
if(j=n+1)thenreturn; //Newcolorfound
}until(false); // Otherwisetrytofindanothercolor.
}
Example:
Color the graph given below with minimum number of colors by backtracking
usingstatespacetree.
x1
1 3
2
1 2 2 3 1 3 1 2 x2
1 3 1 2 2 3 1 3 1 x3
2 2 3
4 3
Graph
x4
2 3 2 2 3 3 1 3 1 3 1 3 1 1 2 2 1 2
A4-nodegraphandallpossible3-colorings
178
HamiltonianCycles:
1 2 3 4 1 2 3
8 7 6 5 5 4
GraphG1 GraphG2
TwographstoillustrateHamiltoniancycle
The traveling salesperson problem using dynamic programming asked for a tour
thathasminimumcost.ThistourisaHamiltoniancycles.Forthesimplecaseofagraphall of
whose edge costs are identical, Hamiltonian will find a minimum-cost tour if
atourexists.
AlgorithmNextValue(k)
//x[1: k-1]isapathofk–1distinctvertices.Ifx[k]=0,thenno vertexhasasyetbeen
//assigned tox[k].Afterexecution,x[k]isassignedto thenext highestnumberedvertex
//whichdoes notalreadyappearinx[1:k –1]andisconnectedbyanedgetox[k–1].
//Otherwisex[k]=0.If k= n, thenin additionx[k]isconnectedto x[1].
{
repeat
{
x[k] := (x[k]+1)mod(n+1); // Next
vertex.If(x[k]= 0)thenreturn;
If(G[x[k –1],x[k]] 0)then
{ //Is thereanedge?
for j:=1 tok– 1 doif(x [j]=x [k])thenbreak;
//checkfordistinctness.
If(j =k)then // If true, then the vertex is
distinct.If((k <n) or((k =n)andG[x[n], x[1]]0))
thenreturn;
}
}until(false);
}
179
AlgorithmHamiltonian(k)
//This algorithm uses therecursive formulationofbacktrackingto findall theHamiltonian
//cyclesofagraph.ThegraphisstoredasanadjacencymatrixG [1:n,1: n]. All cyclesbegin
//atnode1.
{
repeat
{ //Generatevaluesforx[k].
NextValue(k);
//AssignalegalNextvaluetox[k].if(x[
k]= 0)thenreturn;
if(k=n)thenwrite(x[1:n]);elseHa
miltonian(k+1)
}until(false);
}
0/1Knapsack:
Given n positive weights wi, n positive profits pi, and a positive number m that is
theknapsackcapacity,theproblemcallsforchoosingasubsetoftheweightssuchthat:
w i xi mand p i xiismaximized.
1in 1in
Thexi‟sconstituteazero–one-valuedvector.
Bounding functions are needed to killsome live nodes without expanding them. Agood
bounding function for this problem is obtained by using an upper bound on
thevalueofthebestfeasiblesolutionobtainablebyexpandingthegivenlivenodeandany of its
descendants. If this upper bound is not higher than the value of the
bestsolutiondeterminedsofar,thanthatlivenodecanbekilled.
We continue the discussion using the fixed tuple size formulation. If at node Z
thevalues of xi, 1 < i < k, have already been determined, then an upper bound for Z
canbeobtained byrelaxing therequirements xi =0or1.
(Knapsackproblemusingbacktrackingissolvedinbranchandboundchapter)
7.8 TravelingSalePerson(TSP)usingBacktracking:
Considerthegraphshown belowwith4vertices.
30
1 2
5
6 10
4
3 4
20
AgraphforTSP
180
Thesolutionspacetree,similartothen-queensproblemisasfollows:
181
1
2 7 12
3 5 8 10 13 15
4 6 9 11 14 16
Since,thestartingvertexis1,thetreehasarootnodeRandtheremainingnodesare numbered
as depth-first order. As per the tree, from node 1, which is the
livenode,wegenerate3brachesnode2,7and12.Wesimplycomedowntotheleftmost leaf
node 4, which is a valid tour {1, 2, 3, 4, 1} with cost 30 + 5 + 20 + 4 = 59.Currently
this is the best tour found so far and we backtrack to node 3 and to 2,because we do
not have any children from node 3. When node 2 becomes theE-node, we generate
node 5 and then node 6. This forms the tour {1, 2, 4, 3, 1}
withcost30+10+20+6=66andisdiscarded,asthebesttoursofaris59.
Similarly, all the paths from node 1 to every leaf node in the tree is searched in
adepth first manner and the best tour is saved. In our example, the tour costs
areshownadjacenttoeachleafnodes.Theoptimaltourcostistherefore25.
182
Chapter
8
BranchandBound
Generalmethod:
2. It has a bounding function, which goes far beyond the feasibility test as
ameantoprune efficientlythe searchtree.
BranchandBoundreferstoallstatespacesearchmethodsinwhichallchildrenoftheE-
nodearegenerated beforeanyotherlivenodebecomestheE-node
Branch and Bound is the generalisation of both graph search strategies, BFS and D-
search.
A BFS like state space search is called as FIFO (First in first out)
searchasthelistoflivenodesinafirstinfirstoutlist(orqueue).
Definition1:Livenodeisanodethathasbeengeneratedbutwhosechildrenhavenotyetbeeng
enerated.
Definition 2: E-node is a live node whose children are currently being explored.
Inotherwords,anE-nodeisa nodecurrentlybeingexpanded.
173
LeastCost(LC)search:
In both LIFO and FIFO Branch and Bound the selection rule for the next E-node
inrigidandblind.TheselectionruleforthenextE-nodedoesnotgiveanypreferenceto a node
that has a very good chance of getting the search to an answer nodequickly.
Thesearchforananswernodecanbespeededbyusingan“intelligent”ranking
function()cforlivenodes.ThenextE-nodeisselectedonthebasisofthisranking
function.Thenodexisassignedarankusing:
□
c(x)=f(h(x))+g(x)
where,c(x)isthecostofx.
h(x) is the cost of reaching x from the root and f(.) is any non-
decreasingfunction.
g(x)isanestimateoftheadditionaleffortneededtoreachananswernode
fromx.
□
Asearchstrategythatusesacostfunctionc(x)= f(h(x)+g(x)toselectthenext
E-nodewouldalwayschooseforitsnext E-nodealivenodewithleastc(.)iscalledaLC–
search(LeastCostsearch)
BFSandD-searcharespecialcasesofLC-search.Ifg(x)=0andf(h(x))=levelof
nodex,thenanLC searchgeneratesnodesbylevels.Thisiseventuallythesameas
□
aBFS.Iff(h(x))=0andess g(x)>g(y)wheneveryisachildofx,thenthesearchis
entiallyaD-search.
ControlAbstractionforLC-Search:
Aheuristic c
(.)isusedtoestimatec().Thisheuristicshouldbeeasytocomputeand
generallyhasthepropertythat ifx iseitherananswernodeor aleafnode,then
c(x)=(x)c.
LC-searchusesctofindananswernode.ThealgorithmusestwofunctionsLeast()and
Add()todeleteand addalivenodefromortothelistoflivenodes,respectively.
Least() finds a live node with least c(). This node is deleted from the list of live
nodesandreturned.
174
Add(x)addsthenewlivenodextothelistoflivenodes.Thelistoflivenodesbeimplementedasamin
-heap.
AlgorithmLCSearchoutputsthepathfromtheanswernodeitfindstotheroot node
t. This is easy to do if with each node x that becomes live, we associate a field
parentwhich gives the parent of node x. When the answer node g is found, the path
from gto t can be determined by following a sequence of parent values starting from
thecurrentE-node(whichistheparentofg)andendingatnodet.
Listnode=record
{
Listnode*next,*parent;floatcost;
}
AlgorithmLCSearch(t)
{ //Searchtforananswernode
if *t is an answer node then output *t and
return;E:=t; //E-node.
initialize the list of live nodes to be
empty;repeat
{
foreachchildxofEdo
{
if x is an answer node then output the path from x to t and
return;Add(x); //xisanewlivenode.
(xparent):=E; //pointerforpathtoroot
}
iftherearenomorelivenodesthen
{
write (“No answer
node”);return;
}
E:=Least();
}until(false);
}
LC search terminates only when either an answer node is found or the entire
statespacetreehasbeengeneratedandsearched.
Bounding:
Abranchandboundmethodsearchesastatespacetreeusinganysearchmechanism in which
all the children of the E-node are generated before another nodebecomes the E-node.
We assume that each answer node x has a cost c(x) associatedwith it and that a
minimum-cost answer node is to be found. Three common searchstrategies are FIFO,
LIFO, and LC. The three search methods differ only in theselectionruleused to
obtainthenextE-node.
175
A good bounding helps to prune efficiently the tree, leading to a faster exploration
ofthesolutionspace.
□
Acost functionc(.)such thatc( x )<c(x)is usedto provide lower
boundsonsolutionsobtainablefromanynodex.Ifupperisanupperboundonthecostofa
minimum-costsolution,thenalllivenodesxwithc(x)>c(x)>upper.Thestarting
valuefor uppercan beobtainedbysomeheuristicorcanbe setto.
As long as the initial value for upper is not less than the cost of a minimum-
costanswer node, the above rules to kill live nodes will not result in the killing of a
livenode that can reach a minimum-cost answer node. Each time a new answer node
isfound,thevalueofuppercanbeupdated.
Toformulatethesearchforanoptimalsolutionforaleast-costanswernodeinastate space
tree, it is necessary to define the cost function c(.), such that c(x) isminimum for all
nodes representing an optimal solution. The easiest way to do this
istousetheobjectivefunctionitselfforc(.).
Fornodesrepresentinginfeasiblesolutions,c(x)=.
For nodes representing partial solutions, c(x) is the cost of the minimum-
costnodein thesubtree with rootx.
Since,c(x)isgenerallyhardto compute,thebranch-and-boundalgorithmwillusean
□
estimate c(x)suchthatc(x)<c(x)forallx.
The15–PuzzleProblem:
The 15 puzzle is to search the state space for the goal state and use the path
fromthe initial state to the goal state as the answer. There are 16! (16! ≈ 20.9 x
1012)differentarrangementsofthetileson theframe.
As the state space for the problem is very large it would be worthwhile to
determinewhether the goal state is reachable from the initial state. Number the
frame positions1to16.
Position i is the frame position containing title numbered i in the goal arrangement
ofFigure 8.1(b). Position 16 is the empty spot. Let position(i) be the position number
inthe initial state of the title number i. Then position(16) will denote the position of
theemptyspot.
Foranystatelet:
less(i)bethenumberoftilesjsuchthatj<iandposition(j)>position(i).
16
Thegoalstateisreachablefromtheinitialstateiff: less(i)xiseven.
i1
176
Here,x=1ifintheinitialstatetheemptyspotisatoneoftheshadedpositionsoffigure8.1(c)andx=0i
fitisatoneoftheremainingpositions.
1 3 4 15 1 2 3 4
2 5 12 5 6 7 8
7 6 11 14 9 10 11 12
8 9 10 13 13 14 15
(a) Anarrangement (b)Goalarrangement
(c)Figure8.1.15-puzzlearrangement
Example1:
ForthestateofFigure8.1(a)wehaveless(i)valuesasfollows:
16
Therefore, less(i)x(0+0+ 1+1+0+0+1+0+0+ 0+3+6+ 0+
i1
Hence,goalisnotreachable.
Example2:
FortherootstateofFigure8.2wehaveless(i)valuesareasfollows:
16
Therefore, less(i)x(0+0+ 0+0+0+0+0+1+1+ 1+0+0+ 1+
i1
1+1+9)+1=15+1=16.
Hence,goal isreachable.
177
LCSearchfor15PuzzleProblem:
A depth first state space tree generation will result in the subtree of Figure 8.3
whenthe next moves are attempted in the order: move the empty space up, right,
downand left. The searchofthe statespace tree is blind. Itwill take the leftmost
pathfrom the root regardless of the starting configuration. As a result, the answer
nodemayneverbefound.
A breadth first search will always find a goal node nearest to the root. However,
sucha search is also blind in the sense that no matter what the initial configuration,
thealgorithmattemptstomakethesamesequenceofmoves.
Weneedamoreintelligentsearchmethod.Weassociateacostc(x)witheachnodexin
thestate spacetree.Thecost c(x) isthelengthofapath fromtheroot toa
nearestgoalnodeinthesubtreewithrootx.Theeasytocomputeestimate(x)of c
c(x)isasfollows:
□
c(x)=f(x)+g(x)
where,f(x)isthelengthofthepathfromtheroottonodexand
g(x)isanestimateofthelengthofashortestpathfromxtoagoalnodein
thesubtreewithrootx.Here, g (x)isthenumberofnonblanktilesnotin
theirgoalposition.
AnLC-searchofFigure8.2,beginwiththerootastheE-
nodeandgenerateallchildnodes2,3,4and5.ThenextnodetobecometheE-
nodeisalivenodewithleast
c(x).
c(2)=1+4=5
c(3)=1+4=5
c(4)=1+2=3and
c(5)=1+4=5.
Node4becomestheE-
nodeanditschildrenaregenerated.Thelivenodesatthistimeare2,3,5,10,11and 12.So:
c(10)=2+1=3
c(11)=2+3=5and
c(12)=2+3=5.
Thelivenodewithleastcisnode10.ThisbecomesthenextE-node.Nodes22and23
aregeneratednext.Node23isthegoalnode,sosearch terminates.
LC-searchwasalmostasefficientasusingtheexactfunctionc(),withasuitable
choicefor c (),LC-searchwillbefarmoreselectivethananyoftheothersearch
methods.
178
1
1 2 3 4
5 6 8
9 10 7 11
up 13 14 15 12 left
2 down 5
3 right 4
1 2 4 1 2 3 4 1 2 3 4 1 2 3 4
5 6 3 8 5 6 8 5 6 7 8 5 6 8
9 10 7 11 9 10 7 11 9 10 11 9 10 7 11
13 14 15 12 13 14 15 12 13 14 15 12 13 14 15 12
left down right left up left
6 right 7 up 8 9 10 12 13 15
11d own 14
d own
1 2 4 1 2 3 1 2 3 4
1 2 4 1 2 3 4 1 2 3 4 1 2 3 4 1 3 4 1 2 3 4 1 2 3 4
5 6 3 8 5 6 8 4 5 6 7 8
5 6 3 8 5 6 7 8 5 6 7 8 5 6 7 8 5 2 6 8 5 10 6 8 5 6 8
9 10 7 11 9 10 7 11 9 10 11
9 10 7 11 9 10 11 9 10 15 11 9 10 11 9 10 7 11 9 7 11 9 10 7 11
13 14 15 12 13 14 15 12 13 14 15 12 12
13 14 15 12 13 14 15 12 13 14 13 14 15 12 13 14 15 12 13 14 15 12 13 14 15 12
up
own 16 19 left 22 down 23
1 2 4 8 1 2 3 1 2 3 4 1 2 3 4
5 6 3 left 5 6 8 4 5 6 7 5 6 7 8
left
9 10 7 11 9 10 7 11 9 10 11 8 9 10 11 12
down down
13 14 15 12 13 14 15 12 13 14 15 12 13 14 15
17 18 20 21 Goal
1 6 2 4 1 2 4 1 2 3 4 1 2 3 4 Edges are labelled according to the direction in
whichthe emptyspacemoves
5 3 8 5 6 3 8 5 6 8 11 5 6 8 11
9 10 7 11 9 10 7 11 9 10 7 12 9 10 7
13 14 15 12 13 14 15 12 13 14 15 13 14 15 12
Figure8.2.Partofthestatespacetreefor15-puzzleproblem
1 2 3 4 5
1234 12 4 124 1248 1248
56 8 up 5638 right 5638 down 563 down 56311
910711 910711 910711 910711 9107
13141512 13141512 13141512 13141512 13141512
down
10 9 8 7 6
12 8 1248 1248 1248 1248
56411 up 56 11 up 56311 up 56311 left 56311
910312 910312 910 12 910712 910712
1314715 1314715 1314715 1314 15 131415
Jobsequencingwithdeadlines:
We are given n jobs and one processor. Each job i is associated with it a three
tuple(pi, di, ti). Job i requires ti units of processing time. If its processing is not
completedby the deadline di, then a penalty pi is incurred.The objective is to select a
subset Jof the n jobs such that all jobs in J can be completed by their deadlines.
Hence, apenalty can be incurred only on those jobs not in J. The subset J should be
such thatthepenaltyincurredisminimumamongallpossiblesubsetsJ.SuchaJisoptimal.
179
Example:
Consider the following instance with n = 4, (p1, d1, t1) = (5, 1, 1), (p2, d2, t2) =
(10,3,2),(p3,d3,t3)=(6,2,1)and(p4,d4,t4)=(3,1,1).
Thesolutionspaceforthisinstanceconsistsofallpossiblesubsetsofthejobindexset{1,2,3,4}
.Thesolutionspacecanbeorganized intoatree.Figure8.4corresponds to the variable
tuple size formulation. In figure square nodes representinfeasible subsets and all
non-square nodes are answer nodes. Node 9 represents anoptimal solution and is the
only minimum-cost answer node. For this node J={2, 3}and thepenaltyis8.
The cost function c(x) for any circular node x is the minimum penalty
correspondingtoanynodein thesubtreewith rootx.
Thevalueof c(x)=forasquarenode.
LetSxbethesubsetofjobsselectedforJatnodex.
c(x)c(x).
An upper bound u(x) on the cost of a minimum-cost answer node in the subtree x
isu(x)=iSxpi.Theu(x) isthecostofthe solution Sx corresponding to nodex.
180
S(8)={1,4} m=4
c8pip2p310616
i4
is8
CalculationoftheUpper boundu(x)=pi
isx
U(1)=0
U(2)= pip2p3p4106319 eliminatejob1
is2
FIFOBranchandBound:
A FIFO branch-and-bound algorithm for the job sequencing problem can begin
withupper= as an upperboundonthecostofa minimum-costanswernode.
Starting with node 1 as the E-node and using the variable tuple size formulation
ofFigure8.4,nodes2,3,4,and5aregenerated.Thenu(2)=19,u(3)=14,u(4)=
18,andu(5)=21.
Thevariableupperisupdatedto14whennode3isgenerated.Since (4)and c
c(5)aregreaterthanupper,nodes4and5getkilled.Onlynodes2and3remain
alive.
Node2becomesthenextE-node.Its children,nodes 6,7and8are generated.
Thenu(6)=9and soupperisupdatedto9.Thecost
c(7)=10>upperandnode7 getsk
illed.Node8isinfeasibleandsoit iskilled.
Next,node3becomestheE-node.Nodes9 and10arenowgenerated.Thenu(9)=
8andsoupperbecomes8.Thecost c(10)=11>upper,andthisnodeiskilled.
181
ThenextE-
nodeisnode6.Bothitschildrenareinfeasible.Node9‟sonlychildisalsoinfeasible.Theminimu
m-costanswernodeisnode9.Ithasacostof8.
WhenimplementingaFIFObranch-and-boundalgorithm,itisnoteconomicalto kill
livenodeswithc(x)>uppereachtimeupperisupdated.Thisissobecauselive
nodesareinthequeueintheorderinwhichtheyweregenerated.Hence,nodeswith
c(x) >upper aredistributedinsomerandomwayinthequeue. Instead,live nodes
with c(x)>uppercanbekilledwhentheyareabouttobecomeE-nodes.
LCBranchandBound:
AnLCBranch-and-BoundsearchofthetreeofFigure8.4willbeginwithupper=
andnode1asthefirstE-node.
Whennode1isexpanded,nodes2,3,4and5aregeneratedinthatorder.
AsinthecaseofFIFOBB,upperisupdatedto14whennode3isgeneratedand
□
nodes4and5arekilledas c(4)>upperandc(5)>upper.
□
Node2isthenextE-nodeasc(2)=0andc(3)=5.Nodes6,7and8aregenerated
andupperisupdatedto9whennode6isgenerated.So,node7iskilledas c(7)=10
> upper. Node 8 is infeasible and so killed. The only live nodes now are nodes 3
and6.
□
Node6isthenextE-nodeasc(6)=0<c(3).Bothitschildrenareinfeasible.
Node3becomesthenextE-node.Whennode9isgenerated,upperisupdatedto8
asu(9)=8.So,node10with c(10)=11iskilledongeneration.
Node9becomesthenextE-
node.Itsonlychildisinfeasible.Nolivenodesremain.Thesearchterminateswithnode9representin
gtheminimum-costanswernode.
2 3
Thepath=139=5+3=8
TravelingSalePersonProblem:
Byusingdynamicprogrammingalgorithmwecansolvetheproblemwithtimecomplexity of
O(n22n) for worst case. This can be solved by branch and boundtechnique using
efficient bounding function. The time complexity of traveling saleperson problem
using LC branch and bound is O(n22n) which shows that there is
nochangeorreductionofcomplexitythanpreviousmethod.
Westartataparticularnode andvisitallnodesexactlyonceandcomebacktoinitialnodewith
minimumcost.
LetG=(V,E)isaconnectedgraph.LetC(i,J)bethecostofedge<i,j>.cij=if
<i, j> E and let |V| = n, the number of vertices. Every tour starts at vertex 1
182
andendsatthesamevertex.So,thesolutionspaceisgivenbyS={1,,1|isa
183
permutation of (2, 3, . . . , n)} and |S| = (n – 1)!. The size of S can be reduced
byrestrictingSsothat(1,i1,i2,....in-1,1)Siff<ij,ij+1>E,0<j<n-1andi0=in=1.
Procedureforsolvingtravelingsalepersonproblem:
1. Reduce the given cost matrix. A matrix is reduced if every row and column
isreduced. A row (column) is said to be reduced if it contain at least one
zeroandall-remainingentriesarenon-negative.Thiscanbedoneasfollows:
a) Row reduction: Take the minimum element from first row, subtract
itfrom all elements of first row, next take minimum element from
thesecond row and subtract it from second row. Similarly apply the
sameprocedureforallrows.
b) Findthesumofelements,whichweresubtractedfromrows.
c) Applycolumnreductionsforthematrixobtainedafterrowredu ction.
Columnreduction:Taketheminimumelementfromfirstcolumn,subtractitfr
omallelementsoffirstcolumn,nexttakeminimumelement from the second
column and subtract it from second
column.Similarlyapplythesameprocedure forallcolumns.
d) Findthesumofelements,whichweresubtractedfromcolumns.
2. Calculate the reduced cost matrix for every node R. Let A is the reduced
costmatrix for node R. Let S be a child of R such that the tree edge (R,
S)corresponds to including edge <i, j> in the tour. If S is not a leaf node,
thenthereducedcostmatrixforSmaybeobtainedasfollows:
a) Changeallentriesinrowiandcolumn jofAto.
b) SetA(j,1) to.
c) Reduceallrowsandcolumnsintheresultingmatrixexceptforrowsand
column containing only . Let r is the total amount subtracted
toreducethematrix.
□
c) Find cScRAi,jr, where „r‟ is the total
amountsubtractedtoreducethematrix,cRindicatesthe
lowerboundofthe
ithnodein(i,j)pathandcSiscalledthecostfunction.
3. Repeatstep2 untilallnodesarevisited.
184
Example:
Find the LC branch and bound solution for the traveling sale person problem
whosecostmatrixisasfollows:
20 301011
15
35 16 4 2
Thecostmatrixis 2 4
18 3
196
164 7 16
Step 1: Find the reduced cost
matrix.Applyrowreductionmethod:
10 20 0 1
13
14 2 0
Theresultingrowwisereduced costmatrix= 1 3 0 0
3 15 0
16
12 0 3 12
Rowwisereductionsum=10+2+2+3+4=21
Deduct1(whichistheminimum)fromallvaluesinthe1 stcolumn.Deduct3(whichi
stheminimum)fromallvaluesinthe3 rd column.
10 17 0 1
12
11 2 0
Theresultingcolumnwisereduced costmatrix(A)= 0 3 0 2
3 12 0
15
11 0 0 12
Thisisthecostofarooti.e.,node1,becausethisistheinitiallyreducedcostmatrix.Thelowerbound
185
Startingfromnode1,wecannextvisit2,3,4and5vertices.So,considertoexplorethepaths(1,2),(
1,3), (1,4) and (1,5).
Thetreeorganizationuptothispointisas follows:
U=
1 L=25
i=2 i =4 i=5
i=3
2 3 4 5
Variable„i‟indicatesthenextnodetovisit.
Step2:
Considerthepath(1,2):
112
0
0 0 2
12 0
15
11 0 12
Apply row and column reduction for the rows and columns whose rows
andcolumnsare notcompletely.
112 0
Thentheresultantmatrixis 0 0 2
12 0
15
11 0 12
Rowreductionsum= 0 +0+0 +0=0
Columnreductionsum=0+0+0+0=0
Cumulativereduction (r)=0+0=0
□
Therefore,ascScRA1,2r
cS=25+10+0= 35
Considerthepath(1,3):
186
12 2 0
3 0 2
0
15 3
110 12
Apply row and column reduction for the rows and columns whose rows
andcolumnsare notcompletely.
1 2 0
Thentheresultantmatrixis 3 0 2
3 0
4
0 0 12
Considerthepath(1,4):
12
11 0
0 3 2
3 12 0
11 0 0
Apply row and column reduction for the rows and columns whose rows
andcolumnsare notcompletely.
12
11 0
Thentheresultantmatrixis 0 3 2
3 12 0
11 0 0
187
□
Therefore,ascScRA1,4r
cS=25+0+0= 25
Considerthepath(1,5):
12
11 2
03 0
12
15 3
0 0 12
Apply row and column reduction for the rows and columns whose rows
andcolumnsare notcompletely.
10
9 0
Thentheresultantmatrixis 03 0
9
120
0 0 12
i= 2 i =4 i= 5
i= 3
35 2 53 3 25 4 31 5
i =2 i= 5
i= 3
6 7 8
The cost of the paths between(1, 2)= 35, (1, 3) = 53, (1, 4)= 25and (1, 5)= 31.The
cost of the path between (1, 4) is minimum. Hence the matrix obtained for
path(1,4) isconsidered as reducedcostmatrix.
188
12
11 0
A=0 3 2
3 12
0
11 0 0
Thenewpossiblepathsare(4,2),(4,3)and(4,5).
Considerthepath(4,2):
11 0
0 2
11 0
Apply row and column reduction for the rows and columns whose rows
andcolumnsare notcompletely.
11 0
Thentheresultantmatrixis 0 2
11 0
cS=25+3+0= 28
Considerthepath(4,3):
12
0
3 2
11 0
189
Apply row and column reduction for the rows and columns whose rows
andcolumnsare notcompletely.
1 0
Thentheresultantmatrixis 1 0
00
cS=25+12+13=50
Considerthe path(4,5):
12
11
03
0 0
Apply row and column reduction for the rows and columns whose rows
andcolumnsare notcompletely.
1 0
Thentheresultantmatrixis 03
0 0
cS=25+0+11=36
190
Thetreeorganizationuptothispointisas follows:
U=
1 L= 25
i= 2 i =4 i= 5
i= 3
35 2 53 3 25 4 31 5
i =2 i= 5
i= 3
28 6 7 8
36
50
i= 3
i= 5
9 10
The cost of the paths between (4, 2) = 28, (4, 3) = 50 and (4, 5) = 36. The cost
ofthe path between (4, 2) is minimum. Hence the matrix obtained for path (4, 2)
isconsideredasreduced costmatrix.
11 0
A= 0 2
11 0
Thenewpossiblepathsare(2,3)and(2,5).
Considerthepath(2,3):
2
11
Apply row and column reduction for the rows and columns whose rows
andcolumnsare notcompletely.
191
Thentheresultantmatrixis 0
0
cS=28+11+13=52
Considerthepath(2,5):
Apply row and column reduction for the rows and columns whose rows
andcolumnsare notcompletely.
Thentheresultantmatrixis 0
0
Row reduction sum =
0Columnreductionsum=0
Cumulativereduction (r)=0+0=0
□
Therefore,as S R A2,5r
c c
cS=28+0+0= 28
Thetreeorganizationuptothispointisasfollows:
192
U=
1 L=25
i=2 i =4 i=5
i=3
35 2 53 3 25 4 31 5
i =2 i=5
i=3
28 6 7 8
36
50
i=3
i=5
52 9 10 28
i=3
11
The cost of the paths between (2, 3) = 52 and (2, 5) = 28. The cost of the
pathbetween (2, 5) is minimum. Hence the matrix obtained for path (2, 5) is
consideredasreduced costmatrix.
A= 0
0
Thenewpossiblepaths is(5,3).
Considerthepath(5,3):
Change all entries of row 5 and column 3 of A to and also set A(3, 1) to
.Apply row and column reduction for the rows and columns whose rows
andcolumnsare notcompletely.
Thentheresultantmatrixis
Row reduction sum =
0Columnreductionsum=0
Cumulativereduction (r)=0+0=0
□
Therefore,ascScRA5,3r
cS=28+0+0= 28
Theoveralltreeorganizationisas follows:
193
U=
1 L=25
i=2 i =4 i=5
i=3
35 2 53 3 25 4 31 5
i =2 i=5
i=3
28 6 7 8
36
50
i=3
i=5
52 9 10 28
i=3
11 28
Thepathoftravelingsalepersonproblemis:
1 4 2 5 3 1
Theminimumcost ofthepathis:10+6+2+7+3=28.
8.9. 0/1KnapsackProblem
Considertheinstance:M=15,n=4,(P1,P2,P3,P4)=(10,10,12,18)and
(w1,w2, w3,w4) =(2,4,6,9).
0/1 knapsack problem can be solved by using branch and bound technique. In
thisproblemwewillcalculatelowerboundandupperboundforeachnode.
Profit =P1+P2+P3=10+10+12
So,Upper bound=32
To calculate lower bound we can place w4 in knapsack since fractions are allowed
incalculationoflowerbound.
3
Lower bound =10+10+12 + ( X18)=32+6=38
9
Knapsackproblemismaximizationproblembutbranchandboundtechniqueisapplicable for
only minimization problems. In order to convert maximization probleminto
minimization problem we have to take negative sign for upper bound and
lowerbound.
Therefore,Upperbound(U)=-32
Lowerbound(L)=-38
Wechoosethepath,whichhasminimumdifferenceofupperboundandlowerbound.Ifthedifferen
ceisequalthen wechoosethepathby comparingupper boundsandwediscardnodewith
maximumupperbound.
194
U=-32
1 L=-38
x1 =1 x1= 0
U=- U= -
2 3
32L=- 22L=-
38 32
Now we will calculate upper bound and lower bound for nodes 2,
3.Fornode2,x1=1,meansweshouldplacefirstitemintheknapsack.
Fornode3,x1=0,meansweshould notplacefirstitemintheknapsack.
U=10+12=22,makeitas-22
5
L=10+12+ x18=10+12+10 =32,makeit as-32
9
Fornode2,U–L =-32+38 =6
Fornode3,U–L =-22+32=10
U=-32
1 L=-38
x1 =1 x1= 0
U=-32 U= -
2 3
L=-38 22L=-
x2=0 32
=1
x2
U= -22
4 5
U =- L=-36
32L=-38
Now we will calculate lower bound and upper bound of node 4 and 5.
Calculatedifferenceoflowerandupperbound ofnodes4and5.
Fornode4,U –L =-32+38=6
Fornode5,U –L =-22+36=14
Choosenode4, sinceithasminimumdifferencevalueof6.
195
U=-3 2
1 L=-38
x1 =1 x1= 0
U=- U=-22
2 3
32L=- L=-32
38
x2=0
x2 =1
U =- U=-22
4 5
32L=-38 L=-36
x3 =1 x3=0
U= - U=-38
6 7
32L=-3 8 L=-38
Now we will calculate lower bound and upper bound of node 8 and 9.
Calculatedifferenceoflower andupperbound ofnodes8and9.
Fornode6,U –L =-32+38=6
Fornode7,U –L =-38+38=0
Choosenode7,sinceitisminimumdifferencevalueof0.
U=-32
1 L=-38
x1 =1 x1= 0
U=- U= -
2 3
32L=- 22L= -
38 32
x2=0
x2 =1
U=- U=-22
4 5
32 L=-38 L=-36
3 =1 x3=0
x
U=-38
7
U= - 86 L= -38
32L=-3
x4 =1 x4=0
U=- U=-20
8 9
38 L=-38 L= -20
Now we will calculate lower bound and upper bound of node 4 and 5.
Calculatedifferenceoflower andupperboundofnodes4and5.
Fornode8,U –L =-38+38=0
Fornode9,U –L =-20+20=0
Here the difference is same, so compare upper bounds of nodes 8 and 9. Discard
thenode, which has maximum upper bound. Choose node 8, discard node 9 since, it
hasmaximumupperbound.
Considerthepathfrom1247 8
X1=1
X2=1
X3=0
196
X4=1
Thesolutionfor0/1Knapsackproblemis(x 1,x2,x3,x4)=(1,1,0,1)Maximumprofitis:
Pixi=10x1+10x1+12x0+18x1
=10+10+18=38.
197