Mastering Greedy Algorithms: Optimizing Solutions for Efficiency"

Greedy algorithms are fundamental techniques used in computer science and optimization problems. They belong to a class of algorithms that make decisions based on the current best option without considering the overall future consequences. Despite their simplicity and intuitive appeal, greedy algorithms can provide efficient solutions to a wide range of problems across various domains.

At the core of greedy algorithms lies a simple principle: at each step, choose the locally optimal solution that seems best at the moment, with the hope that it will lead to a globally optimal solution. This principle makes greedy algorithms easy to understand and implement, as they typically involve iterating through a set of choices and making decisions based on some criteria.

One of the key characteristics of greedy algorithms is their greedy choice property, which states that at each step, the locally optimal choice leads to an optimal solution overall. This property allows greedy algorithms to make decisions without needing to backtrack or reconsider previous choices, resulting in efficient solutions for many problems.

Greedy algorithms are commonly used in problems involving optimization, scheduling, and combinatorial optimization. Examples include finding the minimum spanning tree in a graph (Prim's and Kruskal's algorithms), finding the shortest path in a weighted graph (Dijkstra's algorithm), and scheduling tasks to minimize completion time (interval scheduling).

Despite their effectiveness in many situations, greedy algorithms may not always produce the optimal solution for a given problem. In some cases, a greedy approach can lead to suboptimal solutions that are not globally optimal. This occurs when the greedy choice property does not guarantee an optimal solution at each step, or when there are conflicting objectives that cannot be resolved by a greedy strategy alone.

To mitigate these limitations, it is essential to carefully analyze the problem at hand and determine whether a greedy approach is appropriate. In some cases, greedy algorithms can be augmented with additional techniques or heuristics to improve their performance or guarantee optimality. Alternatively, other algorithmic paradigms such as dynamic programming or divide and conquer may be better suited for certain problems.

Overall, greedy algorithms offer a powerful and versatile tool for solving optimization problems efficiently. By understanding their principles and characteristics, programmers and researchers can leverage greedy algorithms to tackle a wide range of computational challenges and design elegant solutions that balance simplicity and effectiveness.

1. Greedy Algorithm

2. Greedyalgorithmisgenerallyusedtosolveoptimizationproblems.
Optimizationproblems
Aproblemthatmayhavemanyfeasiblesolutions.
Eachsolutionhasavalue.
Optimizationproblemcanbeeithermaximizationorminimizationproblems,
whereinmaximizationproblem,wewishtofindasolutiontomaximizethe
valueandintheminimizationproblem,wewishtofindasolutiontominimize
thevalue.
Thereareanumberofapproachestosolveoptimizationproblems.Someof
themaregivenbelow-
•Branch and Bound
•Greedy Method
•Dynamic Programming
Greedy Algorithm

3. Greedy Algorithm
AlgorithmGreedy(a,n)
{
Solution:=0;
fori=0tondo
{
x:=select(a);
iffeasible(solution,x)
{
Solution:=union(solution,x)
}
returnsolution;
}
}

4. GreedyMethodfindsoutofmanyoptions,butyouhavetochoosethebest
option.
GreedyAlgorithmsolvesproblemsbymakingthebestchoicethatseemsbest
attheparticularmoment.
Agreedyalgorithmworksinphases.Ateachphase:
Youtakethebestyoucangetrightnow,withoutregardforfutureconsequences
Youhopethatbychoosingalocaloptimumateachstep,youwillendupata
globaloptimum
Greedyalgorithmsaresimpleandstraightforward,andtheytakedecisionson
thebasisofinformationathandwithoutworryingabouttheeffectthese
decisionsmayhaveinthefuture.
Theyareeasytoinvent,easytoimplementandmostofthetimequite
efficient.
Greedy Algorithm

5. Onlyafewoptimizationproblemscanbesolvedbythegreedymethod.Someof
themaregivenbelow-
Machinescheduling
FractionalKnapsackProblem
MinimumSpanningTree
HuffmanCode
JobSequencing
ActivitySelectionProblem
StepsforachievingaGreedyAlgorithmare:
Feasible:Herewecheckwhetheritsatisfiesallpossibleconstraintsornot,toobtain
atleastonesolutiontoourproblems.
LocalOptimalChoice:Inthis,thechoiceshouldbetheoptimumwhichisselected
fromthecurrentlyavailable
Unalterable:Oncethedecisionismade,atanysubsequencestepthatoptionisnot
altered.
Greedy Algorithm

6. Knapsack Problem using Greedy
method
Two main kinds of Knapsack Problems
0-1 Knapsack:
N items (can be the same or different)
Haveonly oneof each
Mustleave or take(i.e., 0-1) each item (ingots of gold)
DP works, greedy does not since items cannot be broken
Fractional Knapsack:
N items (can be the same or different)
Can takefractional partof each item (bags of gold dust)
Greedy works and DP algorithms work
6
Knapsack Problem using Greedy method

7. Greedy approach for Fractional
Knapsack Problem
StepstosolvetheFractionalProblem:
•Calculatetheratio(value/weight)foreachitem.
•Sortalltheitemsindecreasingorderoftheratio.
•Initializeres=0,curr_cap=given_cap.
•Dothefollowingforeveryiteminthesortedorder:
•Iftheweightofthecurrentitemislessthanorequaltotheremainingcapacity,
thenaddthevalueofthatitemintotheresult
•Elseaddthecurrentitemasmuchaswecan(fraction)andbreakoutoftheloop.
•Returnres.
7
Fractional Knapsack Problem
Givenasetofitems,eachwithaweightandavalue/profit,determineasubsetof
itemstoincludeinacollectionsothatthetotalweightislessthanorequaltoagiven
limitandthetotalvalue/profitisaslargeaspossible.

8. Greedy approach for Fractional
Knapsack Problem
Example:Consider5itemsalongtheirrespectiveweightsandvalues:-
I=(I
1,I
2,I
3,I
4,I
5)
w=(5,10,20,30,40)
v=(30,20,100,90,160)
ThecapacityofknapsackW=60
8
Thegreedyalgorithm:
Step1:Sortv
i/w
iintonon-increasingorder.
Step2:Puttheobjectsintotheknapsackaccordingtothesortedsequenceas
possibleaswecan.
Fractional Knapsack Problem

9. Greedy approach for Fractional
Knapsack Problem
Example:Consider5itemsalongtheirrespectiveweightsandvalues:-
ThecapacityofknapsackW=60
First, we choose the item I
iwhose weight is 5.
Then choose item I
3whose weight is 20.
Now, the total weight of knapsack is 20 + 5 = 25
NowthenextitemisI
5,anditsweightis40,but
wewantonly35,sowechosethefractionalpartofit,
So,wearrangethevalueofV/Windecreasingorderasgivenintableandthiswillbethe
solutionofgivenproblem.
ThealgorithmusessortingtosorttheitemswhichtakesO(n×logn)timecomplexityandthen
loopsthrougheachitemwhichtakesO(n).Hencesumminguptoatimecomplexityof
O(n×logn+n)=O(n×logn).Iftheitemsarealreadysorted,thenittakesO(n)timecomplexity.
9
I I1 I2 I3 I4 I5
W 5 10 20 30 40
V 30 20 100 90 160
V/W 6 2 5 3 4
I I1 I3 I5 I4 I2
W 5 20 40 30 10
V 30 100 160 90 20
V/W 6 5 4 3 2
Fractional Knapsack Problem

10. Find Minimum number of Coins
SupposewewantachangeforMRs.andwehaveaninfinitesupplyofeachofthe
denominationsinIndiancurrency,i.e.,wehaveaninfinitesupplyof{1,2,5,10,20,
50,100,500,1000}valuedcoins/notes,whatistheminimumnumberofcoins
and/ornotesneededtomakethechange?
Input:M=70
Output:2
Weneeda50Rsnoteanda20Rsnote.
Input:V=121
Output:3
Weneeda100Rsnote,a20Rsnoteanda1Rscoin.
10
Solution:Greedy Approach.

11. Find Minimum number of Coins
SupposewewantachangeforMRs.andwehaveaninfinitesupplyofeachofthe
denominationsinIndiancurrency,i.e.,wehaveaninfinitesupplyof{1,2,5,10,20,50,
100,500,1000}valuedcoins/notes,whatistheminimumnumberofcoinsand/ornotes
neededtomakethechange?
Input:M=70
Output:2
Weneeda50Rsnoteanda20Rsnote.
Input:V=121
Output:3
Weneeda100Rsnote,a20Rsnoteanda1Rscoin.
11
Algorithm:
1.Sortthearrayofcoinsindecreasingorder.
2.Initializeresultasempty.
3.Findthelargestdenominationthatissmallerthancurrent
amount.
4.Addfounddenominationtoresult.Subtractvalueoffound
denominationfromamount.
5.Ifamountbecomes0,thenprintresult.
6.Elserepeatsteps3and4fornewvalueofV

12. Find Minimum number of Coins
Input:M=11,Denominations={9,6,5,1}
Thegreedyapproachwillreturndenomination9,1,and1
Output-3
Butwecansolvebytaking5and6.So,outputwillbe2.
12
Note:Thisapproachmaynotworkforalldenominations.Forexample,it
doesn’tworkfordenominations{9,6,5,1}andM=11.Theaboveapproach
wouldprint9,1and1.Butwecanuse2denominations5and6.Forgeneral
input,dynamicprogrammingapproachcanbeused:

13. Minimum Spanning Tree
GivenanundirectedandconnectedgraphG(V,E),aspanningtreeofthegraphG
isatreethatspansGandisasubgraphofG.
•Thecostofthespanningtreeisthesumoftheweightsofalltheedgesinthe
tree.Therecanbemanyspanningtrees.Minimumspanningtree(MST)isthe
spanningtreewherethecostisminimumamongallthespanningtrees.There
alsocanbemanyminimumspanningtrees.
•Minimumspanningtreehasdirectapplicationinthedesignofnetworks.Itis
usedinapproximatingthetravellingsalesmanproblem.Otherpractical
applicationsare:
•ClusterAnalysis
•Handwritingrecognition
•Imagesegmentation

14. Howmanyspanningtreewillbepossibleforabovegraph?
Totalnumberofvertices(V)=4
Totalnumberofedges(e)=4,Spanningtreecanbecreatedbytakingv-1edgesout
ofeedges.
So,therewillbe
4
C
3spanningtrees.
1 2
4 3
Suppose the above graph contain one more edge b/w 1 and 3. Then, above formula
will be modified as follows.
5
C
3 –a
Where, ais the number of cycles formed. For the above graph, a=2.
1 2
4 3
Minimum Spanning Tree

15. Minimum Spanning Tree
Howmanyspanningtreewillbepossibleforabovegraph?
TherearetwofamousalgorithmsforfindingtheMinimumSpanningTree:
•Kruskal’sAlgorithm
•PrimsAlgorithm

16. Minimum Spanning Tree
Kruskal’sAlgorithm
▪Kruskal’sAlgorithmbuildsthespanningtreebyaddingedgesoneby
oneintoagrowingspanningtree.Kruskal'salgorithmfollowsgreedy
approachasineachiterationitfindsanedgewhichhasleastweight
andaddittothegrowingspanningtree.
AlgorithmSteps:
▪Sortthegraphedgesinincreasingorderwithrespecttotheir
weights.
▪StartaddingedgestotheMSTfromtheedgewiththesmallest
weight.
▪Onlyaddedgeswhichdoesn'tformacycle,until(n-1)edges
areused.
▪Stop

17. Minimum Spanning Tree
Kruskal’sAlgorithm
Minimum spanning tree with total cost=
11
( = 1 + 2 + 3 + 5)

18. Minimum Spanning Tree
Kruskal’sAlgorithm
TimeComplexity:
Aswehavetoselectmincostedgefromthegraph,sowecanuseminheap
asitgivesminvalues.So,ifalltheedgesarekeptintheminheap,then
afterdeletingeverytimewegetthesmallestvalue.Thetimetakento
deleteanelementfromminheapisO(logn).So,timetocreatespanning
treefornedgewillbe-
O(nlogn)

19. Minimum Spanning Tree
Prims’sAlgorithm
▪Prim’sAlgorithmalsouseGreedyapproachtofindtheminimumspanning
tree.InPrim’sAlgorithmwegrowthespanningtreefromastartingposition.
UnlikeanedgeinKruskal's,weaddvertextothegrowingspanningtreein
Prim's.
GeneralSteps:
1.First,wehavetoinitializeanMSTwiththerandomlychosenvertex.
2.Now,wehavetofindalltheedgeswhichareconnectedtothe
vertex(ces).Fromtheedgesfound,selecttheminimumedgeand
addittothetree.
3.Repeatstep2untiltheminimumspanningtreeisformed.

20. Minimum Spanning Tree
Prims’sAlgorithm
AlgorithmSteps:
▪CreateasetmstSetthatkeepstrackofverticesalreadyincludedin
MST.
▪Assignakeyvaluetoallverticesintheinputgraph.Initializeallkey
valuesasINFINITE.Assignkeyvalueas0forthefirstvertexsothat
itispickedfirst.
▪WhilemstSetdoesn’tincludeallvertices
▪PickavertexuwhichisnotthereinmstSetandhasminimumkey
value.
▪IncludeutomstSet.
▪Updatethekeyvalueofalladjacentverticesofu.Toupdatethekey
values,iteratethroughalladjacentvertices.Foreveryadjacent
vertexv,iftheweightofedgeu-vislessthanthepreviouskeyvalue
ofv,updateitelsekeepitasitis

21. Minimum Spanning Tree
MST-PRIM(G,w,r)
1.foreachu∈G.V
2. u.key←∞
3. u.π←NIL
4.r.key←0
5.Q←G.V------(Build_Heap)
6.whileQ≠Ø
7. u←EXTRACT-MIN(Q)
8. foreachv∈G.Adjacent[u]
9. ifv∈Qandw(u,v)<v.key
10. v.π←u
11. v.key←w(u,v)

22. Minimum Spanning Tree
Use Prim’s algorithm to find an MST in the following graph.
The state at the start of the algorithm:
Intheabovediagram,theredtextisthekey
valuesofthevertices(i.e.,v.key)andthegreen
textisthepredecessorvertex.

23. Minimum Spanning Tree
The state at the start of the algorithm:
Intheabovediagram,theredtextis
thekeyvaluesofthevertices(i.e.,
v.key)andthegreentextisthe
predecessorvertex.
Firstthealgorithmpicksanarbitrarystarting
vertexandupdatesitskeyvalueto0.
HerewearbitrarilychooseAasourstarting
vertex.
Vertex A B C D E F
Key 0 ∞ ∞ ∞ ∞ ∞
PredecessorNIL NIL NIL NIL NIL NIL

24. Minimum Spanning Tree
Firstthealgorithmpicksanarbitrarystarting
vertexandupdatesitskeyvalueto0.
HerewearbitrarilychooseAasourstarting
vertex.
ThenAisextractedfromthequeue,andthe
keysofitsneighboursareupdated:
Vertexcolours:Blue:currentvertex,
green:verticesaddedtotree.
Vertex A B C D E F
Key 0 1 1 ∞ ∞ ∞
PredecessorNIL A A NIL NIL NIL

25. Minimum Spanning Tree
Then D is extracted from the queue Finally,Fisextractedfromthequeueandthe
algorithmiscomplete

26. Minimum Spanning Tree
MST-PRIM(G,w,r)
1.foreachu∈G.V
2. u.key←∞
3. u.π←NIL
4.r.key←0
5.Q←G.V
6.whileQ≠Ø
7. u←EXTRACT-MIN(Q)
8. foreachv∈G.Adjacent[u]
9. ifv∈Qandw(u,v)<v.key
10. v.π←u
11. v.key←w(u,v)
i.Thetimecomplexityrequiredforonecallto
EXTRACT-MIN(Q)isO(logV)usingamin
priorityqueue.Thewhileloopatline6is
executingtotalVtimes.EXTRACT-MIN(Q)is
calledVtimes.So,thecomplexityofEXTRACT-
MIN(Q)isO(VlogV).
ii.Theforloopatline8isexecutingtotalVtimes
asavertexmaybeconnectedtoremaining|V-1|
verticesincompletegraph.Thetimerequiredto
executeline11isO(logv)byusingthe
DECREASE_KEY operationontheminheap.
Line11alsoexecutestotalV-1times.
So,thetotaltimerequiredtoexecuteline11is
O(|V|*|V-1|*logV)=O(V
2
logV).
TotaltimecomplexityofMST-PRIMisthesumofalltimecomplexitiesi.e.,O((VlogV)+(V
2
logV)
+(V)+V).
TheDECREASE_KEY operationwillexecutefornumberofedgeswhichareconnectedtothe
selectedvertex.So,wecanreplaceV
2
byE.Where,E=V*(V-1)/2inworstcase.
O((VlogV)+(ElogV)+(V)+V)=O((V+E)logV)=>O((V+E)logV),since|E|>=|V|.
V times

27. Minimum Spanning Tree
Construct the minimum spanning tree for the following graphs.
i
ii
iii

28. Dijkstra Algorithm
▪Dijkstraalgorithmisasingle-sourceshortestpathalgorithm.Here,
single-sourcemeansthatonlyonesourceisgiven,andwehavetofind
theshortestpathfromthesourcetoallthevertices.
▪Itisminimizationproblemandcanbesolvedbygreedymethod.Itonly
worksonweightedgraphswithpositiveweights.
▪Dijkstra'salgorithmallowsustofindtheshortestpathbetweenanytwo
verticesofagraph.
▪Itdiffersfromtheminimumspanningtreebecausetheshortestdistance
betweentwoverticesmightnotincludealltheverticesofthegraph.

29. Dijkstra Algorithm
▪InDijkstra,firstselectthestartingvertexandsetitscost=0.Thecostof
remainingverticeswillbesetto∞.
▪Usetherelaxationformulatoupdatethecostofeachvertex.The
relaxationformulais-
▪If(d[u]+c[u,v]<d[v]then
▪d[v]=d[u]+c[u,v]
▪Else
▪Nochange

30. Dijkstra Algorithm
Algorithm
1.Markthesourcenodewithacurrentdistanceof0andtherestwith
infinity.
2.Setthenon-visitednodewiththesmallestcurrentdistanceasthe
currentnode,letssayC.
3.ForeachneighbourNofthecurrentnodeC:addthecurrentdistance
ofCwiththeweightoftheedgeconnectingC-N.Ifitissmallerthanthe
currentdistanceofN,setitasthenewcurrentdistanceofN.
4.MarkthecurrentnodeCasvisited.
5.Gotostep2ifthereareanynodesareunvisited.

31. Dijkstra Algorithm
Pseudo-code
Dijkstra(G,W,s) //usespriorityqueueQ
Initialize(G,s)
S←φ
Q←V[G] //InsertintoQ(MinHeap)
whileQ!=φ
dou←EXTRACT-MIN(Q)//deletesufromQ
S=S∪{u}
foreachvertexvinAdj[u]
doRELAX(u,v,w)←thisisanimplicitDECREASEKEYoperation

32. Dijkstra Algorithm
DijkstraAlgorithm
Start with a weighted graph
Chooseastartingvertexandassigninfinity
pathvaluestoallothervertices
Gotoeachvertexandupdateits
pathlength
Ifthepathlengthoftheadjacentvertexis
lesserthannewpathlength,don'tupdateit

33. Dijkstra Algorithm
DijkstraAlgorithm
Avoidupdatingpathlengthsof
alreadyvisitedvertices
After each iteration, we pick the unvisited
vertex with the least path length. So, we
choose 5 before 7
Notice how the rightmost vertex has its
path length updated twice
Repeat until all the vertices have been visited

34. Dijkstra Algorithm
Pseudo-code
Dijkstra(G,W,s) //usespriorityqueueQ
Initialize(G,s)
S←φ
Q←V[G] //InsertintoQ -----
whileQ!=φ
dou←EXTRACT-MIN(Q)//deletesufromQ------
S=S∪{u}
foreachvertexvinAdj[u]
doRELAX(u,v,w)←DECREASEKEYoperation
V times
V log V times
V log V times
-----V
2
log V times

35. Dijkstra Algorithm
DijkstraAlgorithmTimeComplexity-
ThetimecomplexityofDijkstra'salgorithmcanbereducedtoO((V+E)logV)
usingadjacencylistrepresentationofthegraphandamin-heaptostore
theunvisitedvertices,whereEisthenumberofedgesinthegraphandVis
thenumberofverticesinthegraph.
Timecomplexity=O((V+E)logV)

36. Dijkstra Algorithm
i
ii
ii

37. ProblemStatement
Injobsequencingproblem,theobjectiveistofindasequenceof
jobs,whichiscompletedwithintheirdeadlinesandgivesmaximum
profit.
Job Sequencing with Deadlines
Thesimpleandbrute-forcesolutionforthisproblemistogenerateall
thesequencesofthegivensetofjobsandfindthemostoptimal
sequencethatmaximizestheprofit.
TimecomplexityofthissolutionwouldbeO(2^n)
Tooptimizethisalgorithm,wecanmakeuseofagreedyapproachthat
producesanoptimalresult,whichworksbyselectingthebestandthe
mostprofitableoptionavailableatthemoment.

38. Job Sequencing with Deadlines: Algorithm
•Sort the jobs based on decreasing order of profit and find the largest
deadline
•Create a Gantt chart of maximum deadline size
•Iterate through the jobs and perform the following:
•Choose aSlot iif:
•Slot iisn’t previously selected.
•Slot ishould be closest to its deadline
•imust be asmaximum as possible
•If no such slot exists, ignore the job and continue.
Greedy approach

39. Job Sequencing with Deadlines: Example
JOBS DEADLINES PROFITS
Job 1 5 200
Job 2 3 180
Job 3 3 190
Job 4 2 300
Job 5 4 120
Job 6 2 100
Inthetablebelow,jobswiththeirprofitsanddeadlinesaregiven.What
wouldbetheoptimalsequencingofjobswhichwillgivemaximumprofit?

40. Job Sequencing with Deadlines: Example
JOBS DEADLINES PROFITS
Job 1 5 200
Job 2 3 180
Job 3 3 190
Job 4 2 300
Job 5 4 120
Job 6 2 100
Inthetablebelow,jobswiththeirprofits
anddeadlinesaregiven.Whatwouldbe
theoptimalsequencingofjobswhichwill
givemaximumprofit?
JOBS DEADLINES PROFITS
Job 4 2 300
Job 1 5 200
Job 3 3 190
Job 2 3 180
Job 5 4 120
Job 6 2 100
Step1:
Sortthejobsindecreasingorderoftheir
profit.
Here we can see that value of the maximum
deadline is5.

41. Job Sequencing with Deadlines: Example
Step 2:
As maximum deadline is 5, so create a Gantt chart
of size 5
Step3:
Now,pickthejobsonebyoneaspresentedin
step,1,andplacethemontheGanttchartasfar
aspossiblefrom0andclosesttoitsdeadline.
WewillpickJob4.Itsdeadlineis2.So,placing
thejobintheemptyslotavailablejustbeforethe
deadline.
JOBS DEADLINES PROFITS
Job 4 2 300
Job 1 5 200
Job 3 3 190
Job 2 3 180
Job 5 4 120
Job 6 2 100

42. Job Sequencing with Deadlines: Example
Step4:
WewillnowpickJob1.Itsdeadlineis5.So,
placingthejobintheemptyslotavailablejust
beforethedeadline.
Step5:
WewillnowpickJob3.Itsdeadlineis3.So,
placingthejobintheemptyslotavailablejust
beforethedeadline.
Step6:
WewillnowpickJob2.Itsdeadlineis3.Here
secondandthirdslotsarealreadyfilled.So,
placejob2onthenextavailablefreesloti.e.,
firstslot.
JOBS DEADLINES PROFITS
Job 4 2 300
Job 1 5 200
Job 3 3 190
Job 2 3 180
Job 5 4 120
Job 6 2 100

43. Job Sequencing with Deadlines: Example
Step7:
WewillnowpickJob5.Itsdeadlineis4.Placethe
jobinthefirstemptyslotbeforethedeadline,i.e.,
fourthslot.
WewillnowpickJob6.Itsdeadlineis2.Nowwe
needtoplacethejobinthefirstemptyslot
beforethedeadline.Since,nosuchslotis
available,henceJob6cannotbecompleted.
So,themostoptimalsequenceofjobsto
maximizeprofitisJob2,Job4,Job3,Job5,
andJob1.
Andthemaximumprofitearnedcanbe
calculatedas:
ProfitofJob2+ProfitofJob4+ProfitofJob3+
profitofJob5+profitofJob1
180+300+190+120+200=990
JOBS DEADLINES PROFITS
Job 4 2 300
Job 1 5 200
Job 3 3 190
Job 2 3 180
Job 5 4 120
Job 6 2 100

44. Job Sequencing with Deadlines: Analysis
•Sort the jobs based on decreasing order of profit and find the largest deadline---nlogn
•Create a Gantt chart of maximum deadline size --------------K
•Iterate through the jobs and perform the following: -------------n
•Choose aSlot iif:
•Slot iisn’t previously selected. ------------nxm
•Slot ishould be closest to its deadline
•imust be asmaximum as possible
•If no such slot exists, ignore the job and continue.
Since,sizeoftheGantt
chartarraywillbemand
maxcomparisontoplace
anitemmaybemand
fornjobsitwillnxm
Time complexity= nlogn+ n+ nxm+k
= nxm=O(n
2
) if n==m

45. Problem Statement
Givennnumberofsortedfilesofdifferentlengths,thetaskistofind
theminimumcomputationsdonetoreachtheOptimalMergePattern.
Optimal Merge Pattern
Optimalmergepatternisapatternthatrelatestothemergingoftwoor
moresortedfilesinasinglesortedfile.Thistypeofmergingcanbedone
bythetwo-waymergingmethod.
Ifwehavetwosortedfilescontainingnandmrecordsrespectivelythen
theycouldbemergedtogether,toobtainonesortedfileintimeO(n+m).

46. Letusconsiderthegivenfiles,f1,f2,f3,f4andf5with20,30,10,5and30number
ofelements,respectively.
Optimal Merge Pattern
If merge operations are performed according to the provided sequence, then
M1 = merge f1 and f2 => 20 + 30 = 50
M2 = merge M1 and f3 => 50 + 10 = 60
M3 = merge M2 and f4 => 60 + 5 = 65
M4 = merge M3 and f5 => 65 + 30 = 95
Hence, the total number of operations is
50 + 60 + 65 + 95 = 270
Now, the question arises is there any better solution?

47. Letusconsiderthegivenfiles,f1,f2,f3,f4andf5with20,30,10,5and30number
ofelements,respectively.
Optimal Merge Pattern
Sortingthenumbersaccordingtotheirsizeinanascendingorder,wegetthefollowing
sequence−
f4,f3,f1,f2,f5
Hence,mergeoperationscanbeperformedonthissequence
M1=mergef4andf3=>5+10=15
M2=mergeM1andf1=>15+20=35
M3=mergeM2andf2=>35+30=65
M4=mergeM3andf5=>65+30=95
Therefore,thetotalnumberofoperationsis15+35+65+95=210,whichislessthan
firstone.
So, we need to find a merge pattern that can merge elements in the least number
of comparison.

48. Algorithm OPTIMAL_MERGE_PATTERNS(S) // S is set of sequences
Create min heap H from S
while H.length> 1 do
min1 ← minDel(H) // returns minimum element from H & delete it
min2 ← minDel(H)
NewNode.Data← min1 + min2
NewNoode.LeftChild ← min1
NewNode.RightChild ← min2
Insert(NewNode, H)// Insert node NewNodein Heap
end
Optimal Merge Pattern: Greedy approach

49. Optimal Merge Pattern: Greedy approach

50. Optimal Merge Pattern: Greedy approach
Hence, the solution takes 15 + 35 + 60 + 95 = 205 number of comparisons.

51. AlgorithmOPTIMAL_MERGE_PATTERNS(S) // S is set of sequences
Create min heap H from S
while H.length> 1 do
min1 ← minDel(H)
min2 ← minDel(H)
NewNode.Data← min1 + min2
NewNoode.LeftChild ← min1
NewNode.RightChild ← min2
Insert(NewNode, H)
Optimal Merge Pattern: Greedy approach
ComplexityAnalysis
Themainloopinthisalgorithmisexecutedinn-1times.Ineveryiteration,
twodeleteminimum,andoneinsertoperationisperformed.Constructionof
heaptakesO(logn)time.ThetotalrunningtimeofthisalgorithmisO(nlogn).
T(n)=(n–1)*max(O(findmin),O(insert))

52. Optimal Merge Pattern: Greedy approach
ComplexityAnalysis-
T(n)=(n–1)*max(O(findmin),O(insert))
Case1:Iflistissortedandstoredinanarray
O(findmin)=O(1)andO(insert)=O(n)
So,T(n)=(n–1)*n=O(n
2
)
O(findmin)=O(1)andO(insert)=O(logn)
So,T(n)=(n–1)*logn=O(nlogn)
Case2:Listisrepresentedasmin-heap

53. Problem Statement
HuffmanCodingisatechniqueofcompressingdatatoreduceitssize
withoutlosinganyofthedetails.ItwasfirstdevelopedbyDavidHuffman.
HuffmanCodingisgenerallyusefultocompressthedatainwhichthereare
frequentlyoccurringcharacters.
Huffman Coding
Supposethestringbelowistobesentoveranetwork.
AscharactersincomputersarerepresentedusingASCIIcode,whichis
denotedby8bitsinbinary.Thereareatotalof15charactersinthe
abovestring.Thus,atotalof8*15=120bitsarerequiredtosendthis
string.
Toreducethesize(compress)withoutlosinganyinformation,Huffman
codingisused.Huffmancodingassignvariable-lengthcodestoinput
characters.

54. Steps to build Huffman Tree-
1.Calculatethefrequencyofeachcharacterinthestring.
2.Sortthecharactersinincreasingorderofthefrequency.Thesearestoredina
priorityqueueQusingheap.
3.Makeeachuniquecharacterasaleafnode.
4.Createanemptynodez.Assigntheminimumfrequencytotheleftchildofz
andassignthesecondminimumfrequencytotherightchildofz.Setthevalue
ofthezasthesumoftheabovetwominimumfrequencies.
5.RemovethesetwominimumfrequenciesfromQandaddthesumintothelist
offrequencies(*denotetheinternalnodesinthefigureabove).
6.Insertnodezintothetree.
7.Repeatsteps3to5forallthecharacters.
8.Foreachnon-leafnode,assign0totheleftedgeand1totherightedge.
Huffman Coding

55. Steps to build Huffman Tree-
Calculatethefrequencyofeachcharacterinthestring.
Sortthecharactersinincreasingorderofthefrequency.Thesearestoredin
apriorityqueueQ.
Huffman Coding

56. Steps to build Huffman Tree-
Createanemptynodez.Assigntheminimumfrequencytotheleftchildof
zandassignthesecondminimumfrequencytotherightchildofz.Setthe
valueofthezasthesumoftheabovetwominimumfrequencies.
RemovethesetwominimumfrequenciesfromQandaddthesumintothe
listoffrequencies(*denotetheinternalnodesinthefigureabove).
Huffman Coding

57. Steps to build Huffman Tree-
SelecttwominimumelementsfromQandaddthemintreeusingthestep
3.
Huffman Coding
For each non-leaf node, assign 0 to the left edge and 1 to the right edge

58. Steps to build Huffman Tree-
Assign0totheleftedgeand1totherightedge
Huffman Coding

59. Forsendingthestringoveranetwork,wehavetosendthetreeaswellasthe
compressed-code.Thetotalsizeisgivenbythetablebelow.
Huffman Coding
Character Frequency Code Size
A 5 11 5*2 = 10
B 1 100 1*3 = 3
C 6 0 6*1 = 6
D 3 101 3*3 = 9
4 * 8 = 32 bits15 bits 28 bits
Without encoding, the total size of the string was 120 bits. After encoding the
size is reduced to 32 + 15 + 28 = 75

60. createapriorityqueueQusingheapconsistingofeachuniquecharacterandits
frequencymeansaminheapisconstructedforthefrequencies.
foralltheuniquecharacters:
createanewNode
extractminimumvaluefromQandassignittoleftChildofnewNode
extractnextminimumvaluefromQandassignittorightChildofnewNode
calculatethesumofthesetwominimumvaluesandassignittothevalueof
newNode
insertthisnewNodeintothetreeandaddthesumintothelistoffrequencies
returnrootNode
Timecomplexity
TimeComplexityisO(nlogn)becauseweareextractingminimumnodes2*(n-1)times
andeachtimewheneveranodeisbeingextractedfromtheheapthenafunction
calledheapify()isbeingcalledtorearrangetheelementaccordingtotheirpriority.
Thisfunctionheapify()takesO(logn)time.
So,overalltime=2*(n-1)*logn=O(nlogn)
Huffman Coding Complexity

61. Travelling Sales Person Problem
Thetravellingsalesmanproblemsabidebyasalesmanandasetofcities.Thesalesmanhas
tovisiteveryoneofthecitiesstartingfromacertainone(e.g.,thehometown)andtoreturn
tothesamecity.Thechallengeoftheproblemisthatthetravellingsalesmanneedsto
minimizethetotallengthofthetrip.
Example:Anewspaperagentdailydropsthenewspapertotheareaassignedinsucha
mannerthathehastocoverallthehousesintherespectiveareawithminimumtravel
cost.Computetheminimumtravelcost.
Theareaassignedtotheagentwherehehastodropthenewspaperisshowninfig:
61

62. Travelling Sales Person Problem
TheTSPdescribesascenariowhereasalesmanisrequiredtotravelbetween
ncities.Hewishestotraveltoalllocationsexactlyonceandhemustfinishat
hisstartingpoint.Theorderinwhichthecitiesarevisitedisnotimportant,
buthewishestominimizethedistancetraveled.
Thegreedyalgorithmgoesasfollows:
1.Sortalloftheedgesinthenetwork.
2.Selecttheshortestedgeandaddittoourtourifitdoesnotviolateanyof
thefollowingconditions:therearenocyclesinourtourwithlessthann
edgesorincreasethedegreeofanynode(city)tomorethan2.
3.Ifwehavenedgesinourtourstop,ifnotrepeatstep2.
62

63. 63
Travelling Sales Person Problem
Findtheoptimalpathforthefollowinggraph.
The weights of the edges of the graph is as
follows-
A <-> B = 2.4,
A <-> D =4.7,
A <-> C =6.8,
B <-> D = 5.1,
C <-> B =6,
C <-> D =5.9,

64. 64
Travelling Sales Person Problem
Findtheoptimalpathforthefollowinggraph.

65. 65
Travelling Sales Person Problem
Findtheoptimalpathforthefollowinggraph.

66. 66
Travelling Sales Person Problem
Findtheoptimalpathforthefollowinggraph.

67. 67
Travelling Sales Person Problem
Findtheoptimalpathforthefollowinggraph.
The Final answer is A -> B -> D -> C -> A = 2.4 + 5.1 +
5.9 + 6.8 =20.2

68. 68
Travelling Sales Person Problem
Findtheoptimalpathforthefollowinggraph.
Usealgorithmandfindthepath
WecanaddtheroutesB<->D,B<->Aand
C<->Dtoourtourwithoutproblem
Path weight in ascending order
B <-> D = 2,
A <-> B = 4,
C <-> D =5,
A <-> D =6,
A <-> C =7,
C <-> B =8

69. 69
Travelling Sales Person Problem
Findtheoptimalpathforthefollowinggraph.
Usealgorithmandfindthepath
WecanaddtheroutesB<->D,A<->
BandC<->Dtoourtourwithout
problem
Path weight in ascending order
B <-> D = 2,
A <-> B = 4,
C <-> D =5,
A <-> D =6,
A <-> C =7,
C <-> B =8
WecannotaddA<->Dtoourtourasit
wouldcreateacyclebetweenthenodesA,
BandDandincreasetheorderofnodeDto
3.
Wethereforeskipthisedgeandultimately
addedgeA<->Ctothetour.

70. 70
Travelling Sales Person Problem
Complexity:Thisalgorithmsearchesforthelocaloptimaandoptimizesthe
localbestsolutiontofindtheglobaloptima.
•Itbeginsbysortingalltheedgesandthenselectstheedgewiththe
minimumcost.
•Itcontinuouslyselectsthebestnextchoicesgivenaconditionthatno
loopsareformed.
ThecomputationalcomplexityofthegreedyalgorithmisO(N
2
log2(N))and
thereisnoguaranteethataglobaloptimumsolutionisfound.