Job
Time
j
1
3
j
2
5
j
3
6
j
4
10
j
5
11
j
6
14
j
7
15
j
8
18
j
9
20
Figure10.4 Jobsandtimes
j
1
j
4
j
7
j
2
j
5
j
8
j
3
j
6
j
9
0
3 56
13 16
20
28
34
40
Figure10.5 Anoptimalsolutionforthemultiprocessorcase
j
1
j
5
j
9
j
2
j
4
j
7
j
3
j
6
j
8
0
3 56
14 15
20
30
34
38
Figure10.6 Asecondoptimalsolutionforthemultiprocessorcase
Convert pdf back to powerpoint - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
convert pdf to editable powerpoint online; convert pdf to powerpoint online no email
Convert pdf back to powerpoint - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
convert pdf into ppt online; pdf to powerpoint converter online
10.1 GreedyAlgorithms
453
MinimizingtheFinalCompletionTime
Weclosethissectionbyconsideringaverysimilarproblem.Supposeweareonlycon-
cernedwithwhenthelastjobfinishes.Inourtwoexamplesabove,thesecompletiontimes
are40and38,respectively.Figure10.7showsthattheminimumfinalcompletiontimeis
34,andthisclearlycannotbeimproved,becauseeveryprocessorisalwaysbusy.
Althoughthisscheduledoesnothaveminimummeancompletiontime,ithasmeritin
thatthecompletiontimeoftheentiresequenceisearlier.Ifthesameuserownsallthese
jobs,thenthisisthepreferablemethodofscheduling.Althoughtheseproblemsarevery
similar,thisnewproblemturnsouttobeNP-complete;itisjustanotherwayofphrasing
theknapsackorbinpackingproblems,whichwewillencounterlaterinthissection.Thus,
minimizingthefinalcompletiontimeisapparentlymuchharderthanminimizingthemean
completiontime.
10.1.2 HuffmanCodes
In this section,weconsider asecond applicationofgreedy algorithms,knownas file
compression.
Thenormal
ASCII
charactersetconsistsofroughly100“printable”characters.Inorder
todistinguishthesecharacters,log100=7bitsarerequired.Sevenbitsallowtherep-
resentationof128characters,sothe
ASCII
charactersetaddssomeother“nonprintable”
characters.Aneighthbitisaddedasaparitycheck.Theimportantpoint,however,isthat
ifthesizeofthecharactersetisC,thenlogCbitsareneededinastandardencoding.
Supposewehaveafilethatcontainsonlythecharactersa,e,i,s,t,plusblankspaces
andnewlines.Supposefurther,thatthefilehastena’s,fifteene’s,twelvei’s,threes’s,fourt’s,
thirteenblanks,andonenewline.AsthetableinFigure10.8shows,thisfilerequires174
bitstorepresent,sincethereare58charactersandeachcharacterrequiresthreebits.
Inreallife,filescanbequitelarge.Manyoftheverylargefilesareoutputofsome
programandthereisusuallyabigdisparitybetweenthemostfrequentandleastfrequent
characters.Forinstance,manylargedatafileshaveaninordinatelylargeamountofdigits,
blanks,andnewlines,butfewq’sandx’s.Wemightbeinterestedinreducingthefilesizein
j
2
j
5
j
8
j
6
j
9
j
1
j
3
j
4
j
7
0
3 5
9
14 16 6 19
34
Figure10.7 Minimizingthefinalcompletiontime
How to C#: Set Image Thumbnail in C#.NET
PDF, C#.NET convert PDF to svg, C#.NET convert PDF to text, C#.NET convert PDF to images VB.NET How-to, VB.NET PDF, VB.NET Word, VB.NET Excel, VB.NET Back Color.
how to convert pdf to powerpoint on; how to convert pdf to powerpoint
VB.NET Word: Word Conversion SDK for Changing Word Document into
completed. To convert PDF back to Word document in VB.NET, please refer to this page: VB.NET Imaging - Convert PDF to Word Using VB.
convert pdf to powerpoint with; convert pdf to powerpoint using
454
Chapter10 AlgorithmDesignTechniques
Character
Code
Frequency
TotalBits
a
000
10
30
e
001
15
45
i
010
12
36
s
011
3
9
t
100
4
12
space
101
13
39
newline
110
1
3
Total
174
Figure10.8 Usingastandardcodingscheme
thecasewherewearetransmittingitoveraslowphoneline.Also,sinceonvirtuallyevery
machine,diskspaceisprecious,onemightwonderifitwouldbepossibletoprovidea
bettercodeandreducethetotalnumberofbitsrequired.
Theansweristhatthisispossible,andasimplestrategyachieves25percentsavings
ontypicallargefilesandasmuchas50to60percentsavingsonmanylargedatafiles.
Thegeneralstrategyistoallowthecodelengthtovaryfromcharactertocharacterand
toensurethatthefrequentlyoccurringcharactershaveshortcodes.Noticethatifallthe
charactersoccurwiththesamefrequency,thentherearenotlikelytobeanysavings.
Thebinarycodethatrepresentsthealphabetcanberepresentedbythebinarytree
showninFigure10.9.
ThetreeinFigure10.9hasdataonlyattheleaves.Therepresentationofeachcharacter
canbefoundbystartingattherootandrecordingthepath,usinga0toindicatetheleft
branchanda1toindicatetherightbranch.Forinstance,sisreachedbygoingleft,then
right,andfinallyright.Thisisencodedas011.Thisdatastructureissometimesreferredto
asatrie.Ifcharacterc
i
isatdepthd
i
andoccursf
i
times,thenthecostofthecodeisequal
to
d
i
f
i
.
AbettercodethantheonegiveninFigure10.9canbeobtainedbynoticingthatthe
newlineisanonlychild.Byplacingthenewlinesymbolonelevelhigheratitsparent,we
obtainthenewtreeinFigure10.10.Thisnewtreehascostof173,butisstillfarfrom
optimal.
a
e
i
s
t
sp
nl
Figure10.9 Representationoftheoriginalcodeinatree
C# PDF Page Rotate Library: rotate PDF page permanently in C#.net
control, RasterEdge XDoc.PDF, is a 100% clean .NET solution for C# developers to permanently rotate PDF document page and save rotated PDF document back or as
pdf to powerpoint converter; how to convert pdf slides to powerpoint
C# Image: Tutorial for Collaborating, Marking & Annotating
Besides, more annotations can be drawn and saved back to the database We are dedicated to provide powerful & profession imaging controls, PDF document, image to
convert pdf to powerpoint slides; how to change pdf to powerpoint on
10.1 GreedyAlgorithms
455
a
e
i
s
t
sp
nl
Figure10.10 Aslightlybettertree
NoticethatthetreeinFigure10.10isafulltree:Allnodeseitherareleavesorhave
twochildren.Anoptimalcodewillalwayshavethisproperty,sinceotherwise,aswehave
alreadyseen,nodeswithonlyonechildcouldmoveupalevel.
Ifthecharactersareplacedonlyattheleaves,anysequenceofbitscanalways be
decoded unambiguously. . For instance,suppose 0100111100010110001000111 is the
encodedstring.0isnotacharactercode,01isnotacharactercode,but010representsi,
sothefirstcharacterisi.Then011follows,givingans.Then11follows,whichisanewline.
Theremainderofthecodeisa,space,t,i,e,andnewline.Thus,itdoesnotmatterifthe
charactercodesaredifferentlengths,aslongasnocharactercodeisaprefixofanother
charactercode.Suchanencodingisknownasaprefixcode.Conversely,ifacharacteris
containedinanonleafnode,itisnolongerpossibletoguaranteethatthedecodingwillbe
unambiguous.
Puttingthesefactstogether,weseethatourbasicproblemistofindthefullbinarytree
ofminimumtotalcost(asdefinedabove),whereallcharactersarecontainedintheleaves.
ThetreeinFigure10.11showstheoptimaltreeforoursamplealphabet.Ascanbeseenin
Figure10.12,thiscodeusesonly146bits.
Noticethattherearemanyoptimalcodes.Thesecanbeobtainedbyswappingchil-
drenintheencodingtree.Themainunresolvedquestion,then,ishowthecodingtreeis
constructed.ThealgorithmtodothiswasgivenbyHuffmanin1952.Thus,thiscoding
systemiscommonlyreferredtoasaHuffmancode.
s
nl
t
a
e
i
sp
Figure10.11 Optimalprefixcode
C# TIFF: Merge and Split TIFF File(s) with C# Programming
C#.NET Demo Code for Merging & Splitting TIFF File(s). // split TIFF document into 2 parts and save them back to disk TIFFDocument.SplitDocument(sourceFilePath
convert pdf into ppt; convert pdf to powerpoint using
RasterEdge Product Refund Policy
the first step for you is to sign and send back RasterEdge Software We are dedicated to provide powerful & profession imaging controls, PDF document, image to
how to convert pdf to ppt using; pdf picture to powerpoint
456
Chapter10 AlgorithmDesignTechniques
Character
Code
Frequency
TotalBits
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
Figure10.12 Optimalprefixcode
Huffman’sAlgorithm
ThroughoutthissectionwewillassumethatthenumberofcharactersisC.Huffman’s
algorithmcanbedescribedasfollows:Wemaintainaforestoftrees.Theweightofatreeis
equaltothesumofthefrequenciesofitsleaves.C−1times,selectthetwotrees,T
1
andT
2
,
ofsmallestweight,breakingtiesarbitrarily,andformanewtreewithsubtreesT
1
andT
2
.
Atthebeginningofthealgorithm,thereareCsingle-nodetrees—oneforeachcharacter.
Attheendofthealgorithmthereisonetree,andthisistheoptimalHuffmancodingtree.
Aworkedexamplewillmaketheoperationofthealgorithmclear.Figure10.13shows
theinitialforest;theweightofeachtreeisshowninsmalltypeattheroot.Thetwotrees
oflowestweightaremergedtogether,creatingtheforestshowninFigure10.14.Wewill
namethenewrootT1,sothatfuturemergescanbestatedunambiguously.Wehavemade
stheleftchildarbitrarily;anytiebreakingprocedurecanbeused.Thetotalweightofthe
newtreeisjustthesumoftheweightsoftheoldtrees,andcanthusbeeasilycomputed.
Itisalsoasimplemattertocreatethenewtree,sincewemerelyneedtogetanewnode,
settheleftandrightpointers,andrecordtheweight.
Nowtherearesixtrees,andweagainselectthetwotreesofsmallestweight.These
happentobeT1andt,whicharethenmergedintoanewtreewithrootT2andweight8.
a
e
i
s
t
sp
nl
10
15
12
3
4
13
1
Figure10.13 InitialstageofHuffman’salgorithm
a
e
i
t
sp
s
T1
nl
10
15
12
4
13
4
Figure10.14 Huffman’salgorithmafterthefirstmerge
C# PDF: Start to Create, Load and Save PDF Document
can use PDFDocument object to do bulk operations like load, save, convert images/document to page in the document), you can save it back to a PDF file or
how to add pdf to powerpoint; how to convert pdf slides to powerpoint
C# Imaging - Linear ITF-14 Barcode Generator
Y to control barcode image area on PDF, TIFF, Word 14 barcode image fore and back colors in BarcodeHeight = 200; barcode.AutoResize = true; //convert barcode to
converter pdf to powerpoint; convert pdf into powerpoint online
10.1 GreedyAlgorithms
457
a
e
i
sp
s
T1
nl
T2
t
10
15
12
13
8
Figure10.15 Huffman’salgorithmafterthesecondmerge
e
i
sp
s
T1
nl
T2
t
T3
a
15
12
13
18
Figure10.16 Huffman’salgorithmafterthethirdmerge
ThisisshowninFigure10.15.ThethirdstepmergesT2anda,creatingT3,withweight
10+8=18.Figure10.16showstheresultofthisoperation.
Afterthethirdmergeiscompleted,thetwotreesoflowestweightarethesingle-node
treesrepresentingiandtheblankspace.Figure10.17showshowthesetreesaremerged
intothenewtreewithrootT4.ThefifthstepistomergethetreeswithrootseandT3,since
thesetreeshavethetwosmallestweights.TheresultofthisstepisshowninFigure10.18.
Finally,theoptimaltree,whichwasshowninFigure10.11,isobtainedbymergingthe
tworemainingtrees.Figure10.19showsthisoptimaltree,withrootT6.
WewillsketchtheideasinvolvedinprovingthatHuffman’salgorithmyieldsanoptimal
code;wewillleavethedetailsasanexercise.First,itisnothardtoshowbycontradiction
thatthetreemustbefull,sincewehavealreadyseenhowatreethatisnotfullisimproved.
e
i
T4
sp
s
T1
nl
T2
t
T3
a
15
25
18
Figure10.17 Huffman’salgorithmafterthefourthmerge
How to C#: Create a Winforms Control
pages, VB.NET comment annotate PDF, VB.NET delete PDF pages, VB.NET convert PDF to SVG. VB.NET How-to, VB.NET PDF, VB.NET Word, VB.NET Excel, VB.NET Back Color.
pdf to ppt converter; add pdf to powerpoint
VB.NET Image: VB.NET Codes to Add Antique Effect to Image with .
a touch of history to the image which can help bring back the sweet We are dedicated to provide powerful & profession imaging controls, PDF document, image to
add pdf to powerpoint slide; how to convert pdf into powerpoint presentation
458
Chapter10 AlgorithmDesignTechniques
i
T4
sp
s
T1
nl
T2
t
T3
a
T5
e
25
33
Figure10.18 Huffman’salgorithmafterthefifthmerge
Next,wemustshowthatthetwoleastfrequentcharactersαandβmustbethetwo
deepestnodes(although othernodesmay beas deep).Again,thisiseasy toshow by
contradiction,sinceifeitherαorβisnotadeepestnode,thentheremustbesomeγthat
is(recallthatthetreeisfull).Ifαislessfrequentthanγ,thenwecanimprovethecostby
swappingtheminthetree.
Wecan thenarguethatthecharactersinanytwonodesatthesamedepthcanbe
swappedwithoutaffectingoptimality.Thisshowsthatanoptimaltreecanalwaysbefound
thatcontainsthetwoleastfrequentsymbolsassiblings;thus,thefirststepisnotamistake.
Theproofcanbecompletedbyusinganinductionargument.Astreesaremerged,we
considerthenewcharactersettobethecharactersintheroots.Thus,inourexample,after
fourmerges,wecanviewthecharactersetasconsistingofeandthemetacharactersT3
andT4.Thisisprobablythetrickiestpartoftheproof;youareurgedtofillinallofthe
details.
Thereasonthatthisisagreedyalgorithmisthatateachstageweperformamerge
withoutregardtoglobalconsiderations.Wemerelyselectthetwosmallesttrees.
Ifwemaintainthetreesinapriorityqueue,orderedbyweight,thentherunningtime
isO(ClogC),sincetherewillbeone
buildHeap
,2C−2
deleteMin
s,andC−2
insert
s,
s
T1
nl
T2
t
T3
a
T5
e
T6
i
T4
sp
58
Figure10.19 Huffman’salgorithmafterthefinalmerge
10.1 GreedyAlgorithms
459
onapriorityqueuethatneverhasmorethanCelements.Asimpleimplementationofthe
priorityqueue,usingalist,wouldgiveanO(C
2
)algorithm.Thechoiceofpriorityqueue
implementationdependsonhowlargeCis.Inthetypicalcaseofan
ASCII
characterset,
Cissmallenoughthatthequadraticrunningtimeisacceptable.Insuchanapplication,
virtuallyalltherunningtimewillbespentonthediskI/Orequiredtoreadtheinputfile
andwriteoutthecompressedversion.
Therearetwodetailsthatmustbeconsidered.First,theencodinginformationmust
betransmittedatthestartofthecompressedfile,sinceotherwiseitwillbeimpossibleto
decode.Thereareseveralwaysofdoingthis;seeExercise10.4.Forsmallfiles,thecost
oftransmittingthistablewilloverrideanypossiblesavingsincompression,andtheresult
willprobablybefileexpansion.Ofcourse,thiscanbedetectedandtheoriginalleftintact.
Forlargefiles,thesizeofthetableisnotsignificant.
Thesecondproblemisthat,asdescribed,thisisatwo-passalgorithm.Thefirstpass
collectsthefrequencydata,andthesecondpassdoestheencoding.Thisisobviouslynot
adesirablepropertyforaprogramdealingwithlargefiles.Somealternativesaredescribed
inthereferences.
10.1.3 ApproximateBinPacking
Inthissection,wewillconsidersomealgorithmstosolvethebin-packingproblem.These
algorithmswillrunquicklybutwillnotnecessarilyproduceoptimalsolutions.Wewill
prove,however,thatthesolutionsthatareproducedarenottoofarfromoptimal.
WearegivenNitemsofsizess
1
,s
2
,...,s
N
.Allsizessatisfy0<s
i
≤1.Theproblem
istopacktheseitemsinthefewestnumberofbins,giventhateachbinhasunitcapacity.
Asanexample,Figure10.20showsanoptimalpackingforanitemlistwithsizes0.2,0.5,
0.4,0.7,0.1,0.3,0.8.
There are two versions of the e binpacking g problem. The first version is online
binpacking.Inthisversion,eachitemmustbeplacedinabinbeforethenextitemcanbe
processed.Thesecondversionistheofflinebinpackingproblem.Inanofflinealgorithm,
wedonotneedtodoanythinguntilalltheinputhasbeenread.Thedistinctionbetween
onlineandofflinealgorithmswasdiscussedinSection8.2.
B
1
0.2
0.8
B
2
0.7
0.3
B
3
0.4
0.1
0.5
Figure10.20 Optimalpackingfor0.2,0.5,0.4,0.7,0.1,0.3,0.8
460
Chapter10 AlgorithmDesignTechniques
OnlineAlgorithms
Thefirstissueto consider is whetherornot an online algorithmcan actually y always
giveanoptimalanswer,evenifitisallowedunlimitedcomputation.Rememberthateven
thoughunlimitedcomputationisallowed,anonlinealgorithmmustplaceanitembefore
processingthenextitemandcannotchangeitsdecision.
Toshowthatanonlinealgorithmcannotalwaysgiveanoptimalsolution,wewillgive
itparticularlydifficultdatatoworkon.Consideraninputsequence,I
1
,ofMsmallitems
ofweight
1
2
−followedbyMlargeitemsofweight
1
2
+,0<<0.01.Itisclearthat
theseitemscanbepackedinMbinsifweplaceonesmallitemandonelargeitemineach
bin.Supposetherewereanoptimalonlinealgorithm,A,thatcouldperformthispacking.
ConsidertheoperationofalgorithmAonthesequenceI
2
,consistingofonlyMsmallitems
ofweight
1
2
−.I
2
canbepackedinM/2bins.However,Awillplaceeachitemina
separatebin,sinceAmustyieldthesameresultsonI
2
asitdoesforthefirsthalfofI
1
,and
thefirsthalfofI
1
isexactlythesameinputasI
2
.ThismeansthatAwillusetwiceasmany
binsasisoptimalforI
2
.Whatwehaveprovedisthatthereisnooptimalalgorithmfor
onlinebinpacking.
Whattheargumentaboveshowsisthatanonlinealgorithmneverknowswhenthe
inputmightend,soanyperformanceguaranteesitprovidesmustholdateveryinstant
throughoutthealgorithm.Ifwefollowtheforegoingstrategy,wecanprovethefollowing.
Theorem10.1
Thereareinputsthatforceanyonlinebin packingalgorithmtouseat least
4
3
the
optimalnumberofbins.
Proof
Supposeotherwise,andsupposeforsimplicity,thatMiseven.Consideranyonline
algorithmArunningontheinputsequenceI
1
,above.Recallthatthissequenceconsists
ofMsmallitemsfollowedbyMlargeitems.LetusconsiderwhatthealgorithmAhas
doneafterprocessingtheMthitem.SupposeAhasalreadyusedbbins.Atthispointin
thealgorithm,theoptimalnumberofbinsisM/2,becausewecanplacetwoelements
ineachbin.Thusweknow that2b/<
4
3
,by ourassumptionofabetter-than-
4
3
performanceguarantee.
NowconsidertheperformanceofalgorithmAafterallitemshavebeenpacked.
Allbinscreatedafterthebthbinmustcontainexactlyoneitem,sinceallsmallitems
areplacedinthefirstbbins,andtwolargeitemswillnotfitinabin.Sincethefirst
bbinscanhaveatmosttwoitemseach,andtheremainingbinshaveoneitemeach,
weseethatpacking2Mitemswillrequireatleast2Mbbins.Sincethe2Mitems
can beoptimallypacked using Mbins,ourperformanceguaranteeassuresusthat
(2Mb)/M<
4
3
.
Thefirstinequalityimpliesthatb/M<
2
3
,andthesecondinequalityimpliesthat
b/M>
2
3
,whichisacontradiction.Thus,noonlinealgorithmcanguaranteethatit
willproduceapackingwithlessthan
4
3
theoptimalnumberofbins.
Therearethreesimplealgorithmsthatguaranteethatthenumberofbinsusedisno
morethantwiceoptimal.Therearealsoquiteafewmorecomplicatedalgorithmswith
betterguarantees.
10.1 GreedyAlgorithms
461
NextFit
Probablythesimplestalgorithmisnextfit.Whenprocessinganyitem,wechecktosee
whetheritfitsinthesamebinasthelastitem.Ifitdoes,itisplacedthere;otherwise,anew
biniscreated.Thisalgorithmisincrediblysimpletoimplementandrunsinlineartime.
Figure10.21showsthepackingproducedforthesameinputasFigure10.20.
Notonlyisnextfitsimpletoprogram,itsworst-casebehaviorisalsoeasytoanalyze.
Theorem10.2
LetMbetheoptimalnumberofbinsrequiredtopackalistIofitems.Thennextfit
neverusesmorethan2Mbins.Thereexistsequencessuchthatnextfituses2M−2
bins.
Proof
ConsideranyadjacentbinsB
j
andB
j+1
.ThesumofthesizesofallitemsinB
j
andB
j+1
mustbelargerthan1,sinceotherwisealloftheseitemswouldhavebeenplacedinB
j
.
Ifweapplythisresulttoallpairsofadjacentbins,weseethatatmosthalfofthespace
iswasted.Thusnextfitusesatmosttwicetheoptimalnumberofbins.
Toseethatthisratio,2,istight,supposethattheNitemshavesizes
i
=0.5ifiis
oddands
i
=2/Nifiiseven.AssumeNisdivisibleby4.Theoptimalpacking,shown
inFigure10.22,consistsofN/4bins,eachcontaining2elementsofsize0.5,andone
bincontainingtheN/2elementsofsize2/N,foratotalof(N/4)+1.Figure10.23
showsthatnextfitusesN/2bins.Thus,nextfitcanbeforcedtousealmosttwiceas
manybinsasoptimal.
FirstFit
Althoughnextfithasareasonableperformanceguarantee,itperformspoorlyinpractice,
becauseitcreatesnewbinswhenitdoesnotneedto.Inthesamplerun,itcouldhave
placedtheitemofsize0.3ineitherB
1
orB
2
,ratherthancreateanewbin.
Thefirstfitstrategyistoscanthebinsinorderandplacethenewiteminthefirstbin
thatislargeenoughtoholdit.Thus,anewbiniscreatedonlywhentheresultsofprevious
placementshaveleftnootheralternative.Figure10.24showsthepackingthatresultsfrom
firstfitonourstandardinput.
B
1
0.2
0.5
empty
B
2
0.4
empty
B
3
0.7
0.1
empty
B
4
0.3
empty
B
5
0.8
empty
Figure10.21 Nextfitfor0.2,0.5,0.4,0.7,0.1,0.3,0.8
Documents you may be interested
Documents you may be interested