2 CHAPTER1. COMPUTERSANDPROGRAMS
1.2 ProgramPower
Youhave alreadylearnedanimportantlessonofcomputing:Software(programs)rulesthehardware(the
physicalmachine).It is thesoftwarethatdetermineswhatany computercando.Withoutprograms, comput-
erswouldjustbeexpensive paperweights.Theprocessofcreatingsoftwareis calledprogramming, andthat
is themainfocusofthisbook.
Computerprogrammingis a challengingactivity. Goodprogrammingrequiresanabilitytoseethebig
picturewhilepayingattentiontominutedetail.Noteveryonehasthetalenttobecomea first-classprogram-
mer, justasnoteveryonehastheskillstobea professionalathlete.However, virtuallyanyonecanlearnhow
toprogramcomputers. Withsomepatienceandeffortonyourpart,thisbookwillhelpyoutobecomea
programmer.
Therearelotsofgoodreasonstolearnprogramming.Programmingis a fundamentalpartofcomputer
scienceandis,therefore,importantto anyoneinterestedin becominga computerprofessional.Butotherscan
alsobenefitfromtheexperience.Computershave becomea commonplacetoolin oursociety. Understanding
thestrengthsandlimitationsofthistoolrequiresanunderstandingofprogramming.Non-programmersoften
feelthey areslavesoftheircomputers.Programmers,however, aretrulythemasters.If youwanttobecome
a moreintelligentuserofcomputers,thenthisbookis foryou.
Programmingcanalsobeloadsoffun. It isanintellectuallyengagingactivitythatallowspeopleto
expressthemselvesthroughusefulandsometimesremarkablybeautifulcreations. Believe it ornot,many
peopleactuallywritecomputerprogramsasa hobby. Programmingalsodevelopsvaluableproblem-solving
skills,especiallytheabilitytoanalyzecomplex systemsbyreducingthemtointeractionsofunderstandable
subsystems.
Asyouprobablyknow, programmersarein greatdemand.Morethana few liberalartsmajorshave turned
a couplecomputerprogrammingclassesintoa lucrative careeroption.Computersaresocommonplaceinthe
businessworldtodaythattheabilitytounderstandandprogramcomputersmightjustgive youtheedgeover
yourcompetition,regardlessofyouroccupation.
1.3 Whatis ComputerScience?.
Youmightbesurprisedtolearnthatcomputerscienceis notthestudyofcomputers.Afamouscomputer
scientistnamedEdsgarDijkstraoncequippedthatcomputersaretocomputersciencewhattelescopesareto
astronomy. Thecomputeris animportanttoolincomputerscience,butit is notitselftheobjectofstudy.
Sincea computercancarryoutany processthatwecandescribe,therealquestionisWhatprocessescanwe
describe?Putanotherway, thefundamentalquestionofcomputerscienceis simplyWhatcanbecomputed?
Computerscientistsusenumeroustechniquesofinvestigationtoanswerthisquestion.Thethreemainones
aredesign,analysis, andexperimentation.
Onewaytodemonstratethata particularproblemcanbesolvedis toactuallydesigna solution.Thatis,
wedevelopa step-by-stepprocessforachievingthedesiredresult.Computerscientistscallthisanalgorithm.
That’s a fancy wordthatbasicallymeans“recipe.” Thedesignofalgorithmsis oneofthemostimportant
facetsofcomputerscience.Inthisbookyouwillfindtechniquesfordesigningandimplementingalgorithms.
Oneweaknessofdesignis thatit canonlyanswerthequestionWhatis computable?inthepositive.If I
candeviseanalgorithm,thentheproblemis solvable.However, failingtofindanalgorithmdoesnotmean
thata problemis unsolvable.It maymeanthatI’mjustnotsmartenough,orI haven’t hitupontherightidea
yet.Thisis whereanalysiscomesin.
Analysisis theprocessofexaminingalgorithmsandproblemsmathematically. Computerscientistshave
shownthatsomeseeminglysimpleproblemsarenotsolvablebyanyalgorithm. Otherproblemsarein-
tractable. Thealgorithmsthatsolve theseproblemstake toolongorrequiretoomuchmemorytobeof
practicalvalue.Analysisofalgorithmsis animportantpartofcomputerscience;throughoutthisbookwe
willtouchonsomeofthefundamentalprinciples.Chapter 13 hasexamplesofunsolvableandintractable
problems.
Someproblemsaretoocomplex orill-definedtolendthemselvestoanalysis.Insuchcases,computer
scientistsrelyonexperimentation;they actuallyimplementsystemsandthenstudytheresultingbehavior.
Evenwhentheoreticalanalysisisdone,experimentationisoftenneededinordertoverifyandrefinethe