Python Programming: An Introduction to Computer Science

1 , ,storedin a retrieval system,ortransmitted,inany formorbyany means,electronic,mechanical,photocopying ,recording,orotherwise, 2 andreproducedbyWartburg .. ComputerScience?.. PythonProgram.. :TemperatureConverter.. :FutureValue.. :Factorial.. :LongInts.. Decoder.. :BatchUsernames.. :Objects.. Graphics.. ,Informally.. Function.. :TheGoryDetails..977 ControlStructures, .. :TemperatureWarnings.. :ConditionalProgramExecution.. :MaxofThree.. :CompareEachtoAll.. :DecisionTree.. :SequentialProcessing.. :UsePython..116 CONTENTSiii8 ControlStructures, :A QuickReview.. Loops.. Half.. SimulationProblem.. Design.. Design.. Design.. ofObjects.. :Cannonball.. Classes.. :Multi-SidedDice.. :TheProjectileClass.. :DiceRoller.. :SimpleStatistics.. :PythonCalculator.. CalculatorasanObject.. :WordFrequency .. :RacquetballSimulation.

2 :DicePoker.. Text-BasedUI.. GUI.. SimpleSearchingProblem.. :LinearSearch.. :BinarySearch.. Problem-Solving.. Definitions.. Functions.. Search.. Sorting:SelectionSort.. :MergeSort..241viCONTENTSC hapter1 ComputersandProgramsAlmosteveryonehasuse da computeratonetimeoranother. Perhapsyouhave playedcomputergamesoruseda computertowritea ,designairplanes,make movies,runbusinesses,performfinancialtra nsactions, youeverstoppedtowonderwhatexactlya computeris?Howcanonedeviceperformsomanyd ifferenttasks? moderncomputermightbedefinedas amachinethatstoresandmanipulatesinformat ionunderthecon-trolofa changeableprogram. Therearetwo key Computer , anditcantransformtheinformationintonew, usefulforms, simplecalculatortoaddupa columnofnumbers,youareenteringinformatio n(thenumbers)andthecalculatoris processingtheinformationtocomputea runningsumwhichis a ,thepumpusescertaininputs:thecurrentpric eofgaspergallonandsignalsfroma sensorthatreadstherateofgasflowingintoyo urcar.

3 Thepumptransformsthisinputintoinformatio nabouthowmuchgasyoutookandhow muchmoney wouldnotconsidereitherthecalculatororthe gaspumpasfull-fledgedcomputers, aredifferentfromcomputersinthatthey arebuiltto performa single, wherethesecondpartofourdefinitioncomesin tothepicture:computersoperateunderthecon trolofa a detailed,step-by-stepsetofinstructionste llinga wechangetheprogram,thenthecomputerperfor msa differentsequenceofactions,andhence,perf ormsa is thisflexibilitythatallowsyourPCtobeatone momenta wordprocessor, atthenextmomenta financialplanner, andlateron, , justa machineforexecuting(carryingout) , thesamepower;withsuitableprogramming,eac hcomputercanbasicallydoallthethingsthata ny ,thePCthatyoumighthave sittingonyourdeskis reallya candoanythingyouwantit to, that s a powerfulmachine! alreadylearnedanimportantlessonofcomputi ng:Software(programs)rulesthehardware(th ephysicalmachine).

4 It is thesoftwarethatdetermineswhatany , comput-erswouldjustbeexpensive calledprogramming, andthatis a challengingactivity. first-classprogram-mer, justasnoteveryonehastheskillstobea , , a fundamentalpartofcomputerscienceandis,th erefore,importantto anyoneinterestedin becominga becomea commonplacetoolin oursociety. ,however, youwanttobecomea moreintelligentuserofcomputers,thenthisb ookis it ornot,manypeopleactuallywritecomputerpro gramsasa hobby. Programmingalsodevelopsvaluableproblem-s olvingskills,especiallytheabilitytoanaly zecomplex , programmersarein few liberalartsmajorshave turneda couplecomputerprogrammingclassesintoa lucrative youtheedgeoveryourcompetition, ComputerScience?Youmightbesurprisedtolea rnthatcomputerscienceis Thecomputeris animportanttoolincomputerscience,butit is computercancarryoutany processthatwecandescribe,therealquestion isWhatprocessescanwedescribe?

5 Putanotherway, thefundamentalquestionofcomputersciencei s simplyWhatcanbecomputed? ,analysis, particularproblemcanbesolvedis toactuallydesigna ,wedevelopa s a fancy wordthatbasicallymeans recipe. Thedesignofalgorithmsis thatit canonlyanswerthequestionWhatis computable? Icandeviseanalgorithm,thentheproblemis , failingtofindanalgorithmdoesnotmeanthata problemis maymeanthatI mjustnotsmartenough,orI haven t theprocessofexaminingalgorithmsandproble msmathematically. Thealgorithmsthatsolve theseproblemstake animportantpartofcomputerscience; ,computerscientistsrelyonexperimentation ;they , DevicesCPUS econdaryMemoryMain MemoryOutput :FunctionalView ofa ,thebottom-lineis whethera working, ,youwillgetplentyofopportunitiestoobserv e BasicsYoudon t have toknow allthedetailsofhow a computerworkstobea successfulprogrammer, s a bitlike drivinga car.

6 Knowinga littleaboutinternalcombustionengineshelp stoexplainwhyyouhave todothingslike fillthegastank,starttheengine,steponthea ccelerator, byjustmemorizingwhattodo,buta s take a momentto lookunderthehood ,at a higherlevel allmoderndigitalcomputersareremarkablysi milar. functionalview ofa Computer . Thecentralprocessingunit(CPU)is the brain addingtwo numbersandcanalsodologicaloperationslike testingtoseeif two storedinmainmemory(calledRAMforRandomAcc essMemory). Mainmemoryis fast,but it is ,whenthepoweris turnedoff, theinformationin thememoryis , modernpersonalcomputer, thisis usuallysomesortofmagneticmediumsuchasa harddisk(alsocalleda harddrive) keyboard,mouse,andmonitor(videoscreen).I nformationfrominputdevicesisprocessedbyt heCPUandmaybeshuffledoff to themainorsecondarymemory. Similarly, wheninformationneedstobedisplayed,theCPU sendsit ,theinstructionsthatcomprisetheprogramar ecopiedfromthe(more)permanentsecondaryme moryintothemainmemoryofthecomputer.

7 Oncetheinstructionsareloaded, processcalledthefetch executecycle. Thefirstinstructionis retrievedfrommemory, decodedtofigureoutwhatit represents, fetched, , reallyallthecomputerdoesfromthetimethaty outurnit onuntilyouturnit off again:fetch,decode, t seemveryexciting,doesit?Butthecomputerca nexecutethisstreamofsimpleinstructionswi thblazingspeed, , programis justa sequenceofinstructionstellinga , weneedtoprovidethoseinstructionsina languagethata wouldbeniceif wecouldjusttella computerwhattodousingournative language,like they doinsciencefictionmovies.( Computer ,how longwillit take toreachplanetAlphalphaatmaximumwarp? )Unfortunately, despitethecontinuingeffortsofmany top-flightcomputerscientists(includingyo urauthor),designinga computertounderstandhumanlanguageis computerscouldunderstandus, ,if I say: Isawthemanintheparkwiththetelescope, didI have thetelescope,ordidtheman?

8 Andwhowasinthepark?Weunderstandeachother mostofthetimeonlybecauseallhumanssharea ,miscommunicationis gottenaroundthisproblembydesigningnotati onsforexpressingcomputa-tionsinanexact,a ndunambiguousway. Thesespecialnotationsarecalledprogrammin glanguages. Everystructureina programminglanguagehasa preciseform(itssyntax) anda precisemeaning(itssemantics). Aprogramminglanguageis somethinglike a codeforwritingdowntheinstructionsthata ,programmersoftenrefertotheirprogramsasc omputercode, andtheprocessofwritinganalgorithmina programminglanguageis oneexampleofa is heardofsomeotherlanguages,suchasC++,Java , Perl,Scheme, many details,they allsharethepropertyofhavingwell-defined, areprecise,they ,computerhardwarecanonlyunderstandverylo w-level numberfrommemorylocation2001intothe CPUloadthe numberfrommemorylocation2002intothe CPUAdd thetwo numbersin the CPUstorethe resultintolocation2003 Thisseemslike a lotofworktoaddtwo numbers,doesn t it?

9 Actually, it s evenmorecomplicatedthanthisbecausetheins tructionsandnumbersarerepresentedinbinar ynotation(assequencesof0sand1s).Ina high-level languagelike Python ,theadditionoftwo numberscanbeexpressedmorenaturally:c =a + b. That s a loteasierforustounderstand,butweneedsome waytotranslatethehigh-level waysto dothis:a high-level a complex computerprogramthattakesanotherprogramwr ittenina high-level languageandtranslatesit intoanequivalentprograminthemachinelangu ageofsomecomputer. programis calledsourcecode, andtheresultingmachinecodeis a a programthatsimulatesa computerthatunderstandsa high-level machinelanguageequivalent,theinterpreter analyzesandexecutesthesourcecodeinstruct ionbyinstructionasnecessary. one-shottranslation;onceaprogramis compiled,it , , sincethetranslationisdoneonceandforall,b utinterpretedlanguageslendthemselvestoa overmachinelan-guage:portability.

10 Themachinelanguageofa computeris (Program)CompilerMachine :Compilinga High-Level LanguageCodeComputerInputsOutputsSource( Program)Running :Interpretinga High-Level programfora PentiumCPUwon t runona Mac-intoshthatsportsa ,a programwrittenina high-level languagecanberunonmany differentkindsofcomputersaslongasthereis a suitablecompilerorinterpreter(whichis justanotherprogram).Forexample,if I designa new Computer , I canalsoprograma Pythoninterpreterforit,andthenany programwritteninPythoncanberunonmynew Computer , allthetechnicaldetails,it s thisend, alreadyseenthatthereis nomagicinthisprocess,butinsomewaysprogra mmingfeelslike , thosespiritsonlyunderstanda veryarcanelanguagethatwedonotknow. Whatweneedis a a Pythoninterpreter. Wecangive instructionstothePythoninterpreter, andit communicatewiththeGeniethrougha speciallanguageofspellsandincantations( , Python ).