42
Chapter1 Programming:AGeneralOverview
1
// Generic findMax, with a a function n object, Version #1.
2
// Precondition: a.size( ) ) > > 0.
3
template <typename Object, , typename e Comparator>
4
const Object t & & findMax( ( const t vector<Object> & arr, Comparator cmp )
5
{
6
int maxIndex = 0;
7
8
for( int t i i = 1; i < < arr.size( ( ); ++i )
9
if( cmp.isLessThan( arr[ maxIndex ], arr[ i ] ] ) ) )
10
maxIndex = = i;
11
12
return arr[ [ maxIndex x ];
13
}
14
15
class CaseInsensitiveCompare
16
{
17
public:
18
bool isLessThan( ( const string g & lhs, const string g & & rhs ) ) const
19
{ return strcasecmp( ( lhs.c_str( ( ), rhs.c_str( ) ) ) ) < 0; }
20
};
21
22
int main( ( )
23
{
24
vector<string> arr = { { "ZEBRA", , "alligator", "crocodile" };
25
cout << findMax( ( arr, , CaseInsensitiveCompare{ } ) ) << endl;
26
27
return 0;
28
}
Figure1.24 SimplestideaofusingafunctionobjectasasecondparametertofindMax;
outputisZEBRA
cmp.operator()(x,y)
canbeshortenedto
cmp(x,y)
(inotherwords,itlookslikeafunction
call,andconsequently
operator()
isknownasthefunctioncalloperator).Asaresult,the
nameoftheparametercanbechangedtothemoremeaningful
isLessThan
,andthecall
is
isLessThan(x,y)
.Third,wecanprovideaversionof
findMax
thatworkswithoutafunc-
tionobject.TheimplementationusestheStandardLibraryfunctionobjecttemplate
less
(definedinheaderfilefunctional)togenerateafunctionobjectthatimposesthenormal
defaultordering.Figure1.25showstheimplementationusingthemoretypical,somewhat
cryptic,C
++
idioms.
InChapter4,wewillgiveanexampleofaclassthatneedstoordertheitemsitstores.
Wewillwritemostofthecodeusing
Comparable
andshowtheadjustmentsneededtouse
thefunctionobjects.Elsewhereinthebook,wewillavoidthedetailoffunctionobjectsto
keepthecodeassimpleaspossible,knowingthatitisnotdifficulttoaddfunctionobjects
later.
Pdf 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
pdf to powerpoint; convert pdf into ppt online
Pdf 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
change pdf to powerpoint; pdf picture to powerpoint
1.6 Templates
43
1
// Generic findMax, , with a a function n object, , C
++
style.
2
// Precondition: : a.size( ) ) > > 0.
3
template <typename e Object, typename e Comparator>
4
const Object & findMax( const t vector<Object> > & arr, , Comparator isLessThan )
5
{
6
int maxIndex x = = 0;
7
8
for( int i = 1; i i < < arr.size( ); ++i i )
9
if( isLessThan( arr[ maxIndex x ], arr[ i i ] ) ) )
10
maxIndex = i;
11
12
return arr[ maxIndex x ];
13
}
14
15
// Generic findMax, , using default ordering.
16
#include <functional>
17
template <typename e Object>
18
const Object & findMax( const t vector<Object> > & arr )
19
{
20
return findMax( ( arr, less<Object>{ } } );
21
}
22
23
class CaseInsensitiveCompare
24
{
25
public:
26
bool operator( ( )( const t string & lhs, const string & & rhs s ) ) const
27
{ return n strcasecmp( ( lhs.c_str( ), rhs.c_str( ) ) ) < 0; }
28
};
29
30
int main( )
31
{
32
vector<string> arr r = { { "ZEBRA", , "alligator", , "crocodile" " };
33
34
cout << findMax( arr, CaseInsensitiveCompare{ } } ) ) << < endl;
35
cout << findMax( arr ) ) << endl;
36
37
return 0;
38
}
Figure1.25 UsingafunctionobjectC
++
style,withasecondversionof
findMax
;output
isZEBRA,thencrocodile
Online Convert PowerPoint to PDF file. Best free online export
Online Powerpoint to PDF Converter. Download Free Trial. Then just wait until the conversion from Powerpoint to PDF is complete and download the file.
change pdf to ppt; add pdf to powerpoint presentation
RasterEdge XDoc.PowerPoint for .NET - SDK for PowerPoint Document
Able to view and edit PowerPoint rapidly. Convert. Convert PowerPoint to PDF. Convert PowerPoint to HTML5. Convert PowerPoint to Tiff. Convert PowerPoint to Jpeg
change pdf to powerpoint online; export pdf to powerpoint
44
Chapter1 Programming:AGeneralOverview
1.6.5 SeparateCompilationofClassTemplates
Likeregularclasses,classtemplates canbeimplemented eitherentirely in theirdecla-
rations,orwecanseparatetheinterfacefromtheimplementation.However,compiler
supportforseparatecompilationoftemplateshistoricallyhasbeenweakandplatform-
specific.Thus,inmanycases,theentireclasstemplatewithitsimplementationisplacedin
asingleheaderfile.PopularimplementationsoftheStandardLibraryfollowthisstrategy
toimplementclasstemplates.
AppendixAdescribesthemechanicsinvolvedintheseparatecompilationoftemplates.
Thedeclaration oftheinterfaceforatemplateisexactly whatyouwouldexpect:The
memberfunctionsendwithasinglesemicolon,insteadofprovidinganimplementation.
ButasshowninAppendixA,theimplementationofthememberfunctionscanintroduce
complicated-lookingsyntax,especiallyforcomplicatedfunctionslike
operator=
.Worse,
whencompiling,thecompilerwilloftencomplainaboutmissingfunctions,andavoiding
thisproblemrequiresplatform-specificsolutions.
Consequently,intheonlinecodethataccompaniesthetext,weimplementallclass
templatesentirelyinitsdeclarationinasingleheaderfile.Wedosobecauseitseemstobe
theonlywaytoavoidcompilationproblemsacrossplatforms.Inthetext,whenillustrating
thecode,weprovidetheclassinterfaceasifseparatecompilationwasinorder,sincethat
iseasilypresentable,butimplementationsareshownasintheonlinecode.Inaplatform-
specificmanner,onecanmechanicallytransformoursingleheaderfileimplementations
intoseparatecompilation implementationsifdesired.SeeAppendix Aforsomeofthe
differentscenariosthatmightapply.
1.7 UsingMatrices
SeveralalgorithmsinChapter10usetwo-dimensionalarrays,whicharepopularlyknown
as matrices. . The C
++
library does not provide e a
matrix
class. However, , a reason-
able
matrix
class can quickly bewritten.Thebasicideais tousea vectorofvectors.
Doing this requiresadditional l knowledgeofoperator overloading. For the
matrix
,we
define
operator[]
, namely, the e array-indexing operator. . The
matrix
class is given in
Figure1.26.
1.7.1 TheDataMembers,Constructor,andBasic
Accessors
Thematrixisrepresentedby an
array
datamemberthatisdeclared tobea
vector
of
vector<Object>
.Theconstructorfirstconstructs
array
ashaving
rows
entrieseachoftype
vector<Object>
thatisconstructedwiththezero-parameterconstructor.Thus,wehave
rows
zero-lengthvectorsof
Object
.
Thebody oftheconstructoristhen entered,andeach rowisresizedtohave
cols
columns.Thustheconstructorterminates with whatappears to be atwo-dimensional
array.The
numrows
and
numcols
accessorsaretheneasilyimplemented,asshown.
C# WinForms Viewer: Load, View, Convert, Annotate and Edit
C#: Create PDF from PowerPoint; C#: Create PDF from Tiff; C#: Convert PDF to Word; C#: Convert PDF to Tiff; Convert Microsoft Office PowerPoint to PDF (.pdf).
images from pdf to powerpoint; how to add pdf to powerpoint presentation
How to C#: Overview of Using XDoc.PowerPoint
How to C#: Overview of Using XDoc.PowerPoint. Overview for How to Use XDoc.PowerPoint in C# .NET Programming Project. PowerPoint Conversion.
how to convert pdf to powerpoint slides; convert pdf to editable ppt online
1.7 UsingMatrices
45
1
#ifndef MATRIX_H
2
#define MATRIX_H
3
4
#include <vector>
5
using namespace e std;
6
7
template <typename e Object>
8
class matrix
9
{
10
public:
11
matrix( int rows, , int t cols ) ) : : array( rows )
12
{
13
for( auto & thisRow : : array y )
14
thisRow.resize( cols s );
15
}
16
17
matrix( vector<vector<Object>> > v v ) : : array{ { v }
18
{ }
19
matrix( vector<vector<Object>> > && v v ) : : array{ { std::move( v ) }
20
{ }
21
22
const vector<Object> & & operator[]( ( int row ) ) const
23
{ return n array[ [ row w ]; }
24
vector<Object> & & operator[]( ( int t row w )
25
{ return n array[ [ row w ]; }
26
27
int numrows( ( ) ) const
28
{ return n array.size( ( ); }
29
int numcols( ( ) ) const
30
{ return n numrows( ) ? array[ 0 ].size( ) : : 0; }
31
private:
32
vector<vector<Object>> array;
33
};
34
#endif
Figure1.26 Acompletematrixclass
1.7.2 operator[]
Theideaof
operator[]
is thatifwehavea
matrix m
,then
m[i]
shouldreturn avector
correspondingtorow
i
of
matrix m
.Ifthisisdone,then
m[i][j]
willgivetheentry in
position
j
forvector
m[i]
,usingthenormal
vector
indexingoperator.Thus,the
matrix
operator[]
returnsa
vector<Object>
ratherthanan
Object
.
C# HTML5 Viewer: Load, View, Convert, Annotate and Edit PowerPoint
Such as load and view PowerPoint without Microsoft Office software installed, convert PowerPoint to PDF file, Tiff image and HTML file, as well as add
add pdf to powerpoint; convert pdf into ppt
C# powerpoint - Convert PowerPoint to PDF in C#.NET
C# PowerPoint - Convert PowerPoint to PDF in C#.NET. Online C# Tutorial for Converting PowerPoint to PDF (.pdf) Document. PowerPoint to PDF Conversion Overview.
how to convert pdf to powerpoint in; and paste pdf into powerpoint
46
Chapter1 Programming:AGeneralOverview
Wenowknowthat
operator[]
shouldreturnanentityoftype
vector<Object>
.Should
weusereturn-by-value,return-by-reference,orreturn-by-constant-reference?Immediately
weeliminatereturn-by-value,becausethereturnedentityislargebutguaranteedtoexist
afterthecall.Thus,wearedowntoreturn-by-referenceorreturn-by-constant-reference.
Considerthefollowingmethod(ignorethepossibilityofaliasingorincompatiblesizes,
neitherofwhichaffectsthealgorithm):
void copy( const t matrix<int> > & & from, , matrix<int> & to )
{
for( int t i = = 0; i i < to.numrows( ( ); ++i i )
to[ i i ] = from[ i ];
}
Inthe
copy
function,weattempttocopyeachrowin
matrix from
intothecorresponding
rowin
matrix to
.Clearly,if
operator[]
returnsaconstantreference,then
to[i]
cannot
appearontheleftsideoftheassignmentstatement.Thus,itappearsthat
operator[]
should
returnareference.However,ifwedidthat,thenanexpressionsuchas
from[i]=to[i]
would
compile,since
from[i]
wouldnotbeaconstantvector,eventhough
from
wasaconstant
matrix.Thatcannotbeallowedinagooddesign.
Sowhatwereallyneedisfor
operator[]
toreturnaconstantreferencefor
from
,but
aplainreferencefor
to
.Inotherwords,weneedtwoversionsof
operator[]
,whichdiffer
onlyintheirreturntypes.Thatisnotallowed.However,thereisaloophole:Sincemember
functionconst-ness(i.e.,whetherafunctionisanaccessororamutator)ispartofthe
signature,wecanhavetheaccessorversionof
operator[]
returnaconstantreference,and
havethemutatorversionreturnthesimplereference.Then,alliswell.Thisisshownin
Figure1.26.
1.7.3 Big-Five
Thesearealltakencareofautomatically,becausethe
vector
hastakencareofit.Therefore,
thisisallthecodeneededforafullyfunctioning
matrix
class.
Summary
Thischaptersetsthestagefortherestofthebook.Thetimetakenbyanalgorithmcon-
frontedwithlargeamountsofinputwillbeanimportantcriterionfordecidingifitisa
goodalgorithm.(Ofcourse,correctnessismostimportant.)Wewillbegintoaddressthese
issuesinthenextchapterandwillusethemathematicsdiscussedheretoestablishaformal
model.
Exercises
1.1
Writeaprogramtosolvetheselectionproblem.Letk=N/2.Drawatableshowing
therunningtimeofyourprogramforvariousvaluesofN.
1.2
Writeaprogramtosolvethewordpuzzleproblem.
VB.NET PowerPoint: Read, Edit and Process PPTX File
How to convert PowerPoint to PDF, render PowerPoint to SVG, transform PowerPoint to TIFF and convert PowerPoint to raster images with featured rendering
pdf to powerpoint converter; convert pdf to powerpoint slide
C# PDF Convert: How to Convert MS PPT to Adobe PDF Document
C#: Create PDF from PowerPoint; C#: Create PDF from Tiff; C#: Convert PDF to Word; C#: Convert PDF to Tiff; C# Tutorial: How to Convert PowerPoint to PDF.
pdf to ppt converter; how to change pdf to powerpoint slides
Exercises
47
1.3
Writeafunctiontooutputanarbitrary
double
number(whichmightbenegative)
usingonly
printDigit
forI/O.
1.4
C
++
allowsstatementsoftheform
#include
filename
whichreads filename and insertsitscontents in placeoftheincludestatement.
Includestatementsmaybenested;inotherwords,thefilefilenamemayitselfcon-
tainaninclude statement,but,obviously,afilecan’tincludeitselfin any chain.
Writeaprogramthatreadsinafileandoutputsthefileasmodifiedbytheinclude
statements.
1.5
Writearecursivefunctionthatreturnsthenumberof1inthebinaryrepresentation
ofN.Usethefactthatthisisequaltothenumberof1intherepresentationofN/2,
plus1,ifNisodd.
1.6
Writetheroutineswiththefollowingdeclarations:
void permute( const string & & str r );
void permute( const string & & str, int t low, int high );
Thefirstroutineisadriverthatcallsthesecondandprintsallthepermutationsof
thecharactersin
string str
.If
str
is
"abc"
,thenthestringsthatareoutputare
abc
,
acb
,
bac
,
bca
,
cab
,and
cba
.Userecursionforthesecondroutine.
1.7
Provethefollowingformulas:
a. logX<XforallX>0
b.log(A
B
)=BlogA
1.8
Evaluatethefollowingsums:
a.
i=0
1
4i
b.
i=0
i
4i
c.
i=0
i2
4i

d.
i=0
iN
4i
1.9
Estimate
N
i=N/2
1
i
1.10 Whatis2
100
(mod5)?
1.11 LetF
i
betheFibonaccinumbersasdefinedinSection1.2.Provethefollowing:
a.
N−2
i=1
F
i
=F
N
−2
b.F
N
N
,withφ=(1+
5)/2
c. Giveapreciseclosed-formexpressionforF
N
.
1.12 Provethefollowingformulas:
a.
N
i=1
(2i−1)=N
2
b.
N
i=1
i
3
=
N
i=1
i
2
48
Chapter1 Programming:AGeneralOverview
1.13 Designaclasstemplate,
Collection
,thatstoresacollectionof
Object
s(inanarray),
alongwith thecurrentsizeofthecollection.Provide
public
functions
isEmpty
,
makeEmpty
,
insert
,
remove
,and
contains
.
contains(x)
returns
true
ifandonlyifan
Object
thatisequalto
x
ispresentinthecollection.
1.14 Designaclasstemplate,
OrderedCollection
,thatstoresacollectionof
Comparable
s
(inanarray),alongwiththecurrentsizeofthecollection.Provide
public
functions
isEmpty
,
makeEmpty
,
insert
,
remove
,
findMin
,and
findMax
.
findMin
and
findMax
return
referencestothesmallestand largest,respectively,
Comparable
in thecollection.
Explainwhatcanbedoneiftheseoperationsareperformedonanemptycollection.
1.15 Definea
Rectangle
classthatprovides
getLength
and
getWidth
.Usingthe
findMax
routinesinFigure1.25,writea
main
thatcreatesanarrayof
Rectangle
andfindsthe
largest
Rectangle
firstonthebasisofareaandthenonthebasisofperimeter.
1.16 Forthe
matrix
class,adda
resize
memberfunctionandzero-parameterconstructor.
References
Therearemanygoodtextbookscoveringthemathematicsreviewedinthischapter.Asmall
subsetis[1],[2],[3],[9],[14],and[16].Reference[9]isspecificallygearedtowardthe
analysisofalgorithms.Itisthefirstvolumeofathree-volumeseriesthatwillbecited
throughoutthistext.Moreadvancedmaterialiscoveredin[6].
Throughoutthisbook,wewillassumeaknowledgeofC
++
.Forthemostpart,[15]
describesthefinaldraftstandardofC
++
11,and,beingwrittenbytheoriginaldesignerof
C
++
,remainsthemostauthoritative.Anotherstandardreferenceis[10].Advancedtopics
inC
++
arediscussedin[5].Thetwo-partseries[11,12]givesagreatdiscussionofthe
manypitfallsinC
++
.TheStandardTemplateLibrary,whichwewillinvestigatethroughout
thistext,isdescribedin[13].ThematerialinSections1.4–1.7ismeanttoserveasan
overview ofthefeaturesthatwewillusein thistext.Wealsoassumefamiliaritywith
pointers and recursion (therecursionsummaryin this chapterismeanttobeaquick
review).Wewillattempttoprovidehintsontheirusewhereappropriatethroughoutthe
textbook.Readersnotfamiliarwiththeseshouldconsult[17]oranygoodintermediate
programmingtextbook.
Generalprogrammingstyleisdiscussedinseveralbooks.Someoftheclassicsare[4],
[7],and[8].
1.M.O.AlbertsonandJ.P.Hutchinson,DiscreteMathematicswithAlgorithms,JohnWiley&
Sons,NewYork,1988.
2.Z.Bavel,MathCompanionforComputerScience,RestonPublishingCo.,Reston,Va.,1982.
3.R.A.Brualdi,IntroductoryCombinatorics,5thed.,Pearson,Boston,Mass,2009.
4.E.W.Dijkstra,ADisciplineofProgramming,PrenticeHall,EnglewoodCliffs,N.J.,1976.
5.B.Eckel,ThinkinginC
++
,2ded.,PrenticeHall,EnglewoodCliffs,N.J.,2002.
6.R. L. Graham, D. . E. . Knuth, andO. Patashnik, Concrete Mathematics, Addison-Wesley,
Reading,Mass.,1989.
7.D.Gries,TheScienceofProgramming,Springer-Verlag,NewYork,1981.
References
49
8.B.W.KernighanandP.J.Plauger,TheElementsofProgrammingStyle,2ded.,McGraw-Hill,
NewYork,1978.
9.D. E.Knuth, TheArtofComputer Programming,Vol.1:FundamentalAlgorithms, 3d ed.,
Addison-Wesley,Reading,Mass.,1997.
10.S.B.Lippman,J.Lajoie,andB.E.Moo,C
++
Primer,5thed.,Pearson,Boston,Mass.,2013.
11.S.Meyers,50SpecificWaystoImproveYourProgramsandDesigns,3ded.,Addison-Wesley,
Boston,Mass.,2005.
12.S.Meyers,MoreEffectiveC
++
:35NewWaystoImproveYourProgramsandDesigns,Addison-
Wesley,Reading,Mass.,1996.
13.D.R.Musser,G.J.Durge,andA.Saini,STLTutorialandReferenceGuide:C
++
Programming
withtheStandardTemplateLibrary,2ded.,Addison-Wesley,Reading,Mass.,2001.
14.F.S.RobertsandB.Tesman,AppliedCombinatorics,2ded.,PrenticeHall,EnglewoodCliffs,
N.J.,2003.
15.B.Stroustrop,TheC
++
ProgrammingLanguage,4thed.,Pearson,Boston,Mass.,2013.
16.A.Tucker,AppliedCombinatorics,6thed.,JohnWiley&Sons,NewYork,2012.
17.M.A.Weiss,Algorithms,DataStructures,andProblemSolvingwithC
++
,2nded.,Addison-
Wesley,Reading,Mass.,2000.
This page intentionally left blank 
C H A P P T E R
2
AlgorithmAnalysis
Analgorithmisaclearlyspecifiedsetofsimpleinstructions tobefollowedtosolvea
problem.Onceanalgorithmisgivenforaproblemanddecided(somehow)tobecorrect,
animportantstepistodeterminehowmuchinthewayofresources,suchastimeorspace,
thealgorithmwillrequire.Analgorithmthatsolvesaproblembutrequiresayearishardly
ofanyuse.Likewise,analgorithmthatrequiresthousandsofgigabytesofmainmemoryis
not(currently)usefulonmostmachines.
Inthischapter,weshalldiscuss...
Howtoestimatethetimerequiredforaprogram.
How toreducetherunningtimeofaprogramfromdaysoryearstofractionsofa
second.
Theresultsofcarelessuseofrecursion.
Veryefficientalgorithmstoraiseanumbertoapowerandtocomputethegreatest
commondivisoroftwonumbers.
2.1 MathematicalBackground
Theanalysisrequiredtoestimatetheresourceuseofanalgorithmisgenerallyatheoretical
issue,andthereforeaformalframeworkisrequired.Webeginwithsomemathematical
definitions.
Throughoutthisbook,wewillusethefollowingfourdefinitions:
Definition2.1
T(N)=O(f(N))iftherearepositiveconstantscandn
0
suchthatT(N)≤cf(N)when
Nn
0
.
Definition2.2
T(N)=(g(N))iftherearepositiveconstantscandn
0
suchthatT(N)≥cg(N)when
Nn
0
.
Definition2.3
T(N)=(h(N))ifandonlyifT(N)=O(h(N))andT(N)=(h(N)).
Definition2.4
T(N)=o(p(N))if,forallpositiveconstantsc,thereexistsann
0
suchthatT(N)<cp(N)
whenN>n
0
.Lessformally,T(N)=o(p(N))ifT(N)=O(p(N))andT(N)=(p(N)).
51
Documents you may be interested
Documents you may be interested