Mark J. Guzdial Visit to download the full and correct content document: https://ebookmass.com/product/introduction-to-computing-and-programming-in-pytho n-global-edition-mark-j-guzdial/
More products digital (pdf, epub, mobi) instant download maybe you interests ...
Introduction To Computing And Problem Solving Using Python 1st Edition E. Balaguruswamy
https://ebookmass.com/product/introduction-to-computing-andproblem-solving-using-python-1st-edition-e-balaguruswamy/
Introduction to Computation and Programming Using Python, Third Edition John V. Guttag
https://ebookmass.com/product/introduction-to-computation-andprogramming-using-python-third-edition-john-v-guttag/
Python Programming for Beginners: 2 Books in 1 - the Ultimate Step-By-Step Guide to Learn Python Programming Quickly With Practical Exercises Mark Reed
https://ebookmass.com/product/python-programming-forbeginners-2-books-in-1-the-ultimate-step-by-step-guide-to-learnpython-programming-quickly-with-practical-exercises-mark-reed/
Introduction to Computing Using Python: An Application Development Focus, 2nd Edition – Ebook PDF Version
https://ebookmass.com/product/introduction-to-computing-usingpython-an-application-development-focus-2nd-edition-ebook-pdfversion/
Quantum Computing by Practice: Python Programming in the Cloud with Qiskit and IBM-Q Vladimir Silva
https://ebookmass.com/product/quantum-computing-by-practicepython-programming-in-the-cloud-with-qiskit-and-ibm-q-vladimirsilva/
Python Programming and SQL: 10 Books in 1 - Supercharge Your Career with Python Programming and SQL Andrew Reed
https://ebookmass.com/product/python-programming-andsql-10-books-in-1-supercharge-your-career-with-pythonprogramming-and-sql-andrew-reed/
Introduction to Quantum Computing (River Publishers Series in Rapids in Computing and Information Science and Technology) 1st Edition Ahmed Banafa
https://ebookmass.com/product/introduction-to-quantum-computingriver-publishers-series-in-rapids-in-computing-and-informationscience-and-technology-1st-edition-ahmed-banafa/
A Beginners Guide to Python 3 Programming 2nd Edition
John Hunt
https://ebookmass.com/product/a-beginners-guide-topython-3-programming-2nd-edition-john-hunt/
Introduction to Computing 1st Edition David A. Joyner
https://ebookmass.com/product/introduction-to-computing-1stedition-david-a-joyner/
Introductionto Computingand Programming inPython TM AMULTIMEDIA APPROACH MarkJ.GuzdialandBarbaraEricson
CollegeofComputing/GVU
GeorgiaInstituteofTechnology
FourthEdition
GlobalEdition
BostonColumbusIndianapolisNewYorkSanFranciscoHoboken AmsterdamCapeTownDubaiLondonMadridMilanMunichParisMontrealToronto DelhiMexicoCitySãoPauloSydneyHongKongSeoulSingaporeTaipeiTokyo
VicePresidentandEditorialDirector,ECS: MarciaJ.Horton
ExecutiveEditor: TracyJohnson
AssistantAcquisitionsEditor,GlobalEdition: AditeeAgarwal
ExecutiveMarketingManager: TimGalligan
MarketingAssistant: JonBryant
SeniorManagingEditor: ScottDisanno
ProductionProjectManager: GregDulles
ProgramManager: CaroleSnyder
ProjectEditor,GlobalEdition: K.K.Neelakantan
SeniorManufacturingController,GlobalEdition: KayHolman
MediaProductionManager,GlobalEdition: VikramKumar
GlobalHEDirectorofVendorSourcingandProcurement: DianeHynes
DirectorofOperations: NickSklitsis
OperationsSpecialist: MauraZaldivar-Garcia
CoverDesigner: LuminaDatamatics
Manager,RightsandPermissions: RachelYoudelman
AssociateProjectManager,RightsandPermissions: TimothyNicholls
Full-ServiceProjectManagement: KalpanaArumugam,SPiGlobal
MICROSOFTAND/ORITSRESPECTIVESUPPLIERSMAKENOREPRESENTATIONSABOUTTHESUITABILITYOFTHEINFORMATION CONTAINEDINTHEDOCUMENTSANDRELATEDGRAPHICSPUBLISHEDASPARTOFTHESERVICESFORANYPURPOSE.ALLSUCH DOCUMENTSANDRELATEDGRAPHICSAREPROVIDED“ASIS”WITHOUTWARRANTYOFANYKIND.MICROSOFTAND/ORITS RESPECTIVESUPPLIERSHEREBYDISCLAIMALLWARRANTIESANDCONDITIONSWITHREGARDTOTHISINFORMATION, INCLUDINGALLWARRANTIESANDCONDITIONSOFMERCHANTABILITY,WHETHEREXPRESS,IMPLIEDORSTATUTORY,FITNESS FORAPARTICULARPURPOSE,TITLEANDNON-INFRINGEMENT.INNOEVENTSHALLMICROSOFTAND/ORITSRESPECTIVE SUPPLIERSBELIABLEFORANYSPECIAL,INDIRECTORCONSEQUENTIALDAMAGESORANYDAMAGESWHATSOEVERRESULTING FROMLOSSOFUSE,DATAORPROFITS,WHETHERINANACTIONOFCONTRACT,NEGLIGENCEOROTHERTORTIOUSACTION, ARISINGOUTOFORINCONNECTIONWITHTHEUSEORPERFORMANCEOFINFORMATIONAVAILABLEFROMTHESERVICES.THE DOCUMENTSANDRELATEDGRAPHICSCONTAINEDHEREINCOULDINCLUDETECHNICALINACCURACIESORTYPOGRAPHICAL ERRORS.CHANGESAREPERIODICALLYADDEDTOTHEINFORMATIONHEREIN.MICROSOFTAND/ORITSRESPECTIVESUPPLIERS MAYMAKEIMPROVEMENTSAND/ORCHANGESINTHEPRODUCT(S)AND/ORTHEPROGRAM(S)DESCRIBEDHEREINATANYTIME. PARTIALSCREENSHOTSMAYBEVIEWEDINFULLWITHINTHESOFTWAREVERSIONSPECIFIED.
PearsonEducationLimited
EdinburghGate Harlow EssexCM202JE
England
andAssociatedCompaniesthroughouttheworld
VisitusontheWorldWideWebat: www.pearsonglobaleditions.com
© PearsonEducationLimited2016
TherightsofMarkJ.GuzdialandBarbaraEricsontobeidentifiedastheauthorsofthisworkhavebeenassertedbytheminaccordancewiththe Copyright,DesignsandPatentsAct1988.
AuthorizedadaptationfromtheUnitedStatesedition,entitledIntroductiontoComputingandProgramminginPython™ :AMultimediaApproach,Fourth Edition,ISBN9780134025544,byMarkJ.GuzdialandBarbaraEricsonpublishedbyPearsonEducation © 2016.
Allrightsreserved.Nopartofthispublicationmaybereproduced,storedinaretrievalsystem,ortransmittedinanyformorbyanymeans,electronic, mechanical,photocopying,recordingorotherwise,withouteitherthepriorwrittenpermissionofthepublisheroralicensepermittingrestrictedcopyingin theUnitedKingdomissuedbytheCopyrightLicensingAgencyLtd,SaffronHouse,6 10KirbyStreet,LondonEC1N8TS.
Alltrademarksusedhereinarethepropertyoftheirrespectiveowners.Theuseofanytrademarkinthistextdoesnotvestintheauthororpublisherany trademarkownershiprightsinsuchtrademarks,nordoestheuseofsuchtrademarksimplyanyaffiliationwithorendorsementofthisbookbysuchowners
BritishLibraryCataloguing-in-PublicationData
AcataloguerecordforthisbookisavailablefromtheBritishLibrary 10987654321
ISBN10:1-292-10986-6
ISBN13:978-1-292-10986-2
Typesetin10.5/13TimesbySPiGlobal PrintedandboundinMalaysia.
Dedicatedtoourfirstteachers,ourparents: Janet,Charles,Gene,andNancy
This page intentionally left blank
PrefacefortheFourthEdition13
PrefacetotheFirstEdition18
AbouttheAuthors24
1 INTRODUCTION 25
1 IntroductiontoComputerScienceandMedia Computation 27
1.1WhatIsComputerScienceAbout?27
1.2ProgrammingLanguages30
1.3WhatComputersUnderstand33
1.4MediaComputation:WhyDigitizeMedia?35
1.5ComputerScienceforEveryone37
1.5.1It’sAboutCommunication37
1.5.2It’sAboutProcess37
1.5.3YouWillProbablyNeedIt38
2 IntroductiontoProgramming 42
2.1ProgrammingIsAboutNaming42
2.1.1FilesandTheirNames44
2.2ProgramminginPython45
2.3ProgramminginJES46
2.4MediaComputationinJES47
2.4.1ShowingaPicture51
2.4.2PlayingaSound54
2.4.3NamingValues54
2.5MakingaProgram57
2.5.1Functions:RealMath-LikeFunctionsThatTake Input61
3 CreatingandModifyingText 68 3.1Strings:MakingHumanTextinaComputer68
3.1.1MakingStringsfromStrings:TellingStories70
3.2TakingStringsApartwith For 73
3.2.1TestingthePieces75
3.2.2TakingStringApart,andPuttingStringsTogether78
3.2.3TakingStringsApartwithIndices81
3.2.4Mirroring,Reversing,andSeparatingStringswithIndex83
3.2.5EncodingandDecodingStringsUsingaKeywordCipher85
3.3TakingStringsApartbyWords87
3.4What’sInsideaString90
3.5WhataComputerCanDo91
4 ModifyingPicturesUsingLoops 98 4.1HowPicturesAreEncoded99
4.2ManipulatingPictures104
4.2.1ExploringPictures108
4.3ChangingColorValues110
4.3.1UsingLoopsinPictures110
4.3.2Increasing/DecreasingRed(Green,Blue)112
4.3.3TestingtheProgram:DidThatReallyWork?117
4.3.4ChangingOneColorataTime118
4.4CreatingaSunset119
4.4.1MakingSenseofFunctions119
4.5LighteningandDarkening124
4.6CreatingaNegative125
4.7ConvertingtoGrayscale126
4.8SpecifyingPixelsbyIndex128
5 PictureTechniqueswithSelection 138 5.1ReplacingColors:Red-Eye,SepiaTones,andPosterizing138
5.1.1ReducingRed-Eye142
5.1.2Sepia-TonedandPosterizedPictures:Using ConditionalstoChoosetheColor144
5.2ComparingPixels:EdgeDetection150
5.3BackgroundSubtraction153
5.4Chromakey156
5.5Coloringinranges161
5.5.1AddingaBorder161
5.5.2LighteningtheRightHalfofaPicture162
5.6SelectingwithoutRetesting163
6 ModifyingPixelsbyPosition 169 6.1ProcessingPixelsFaster169
6.1.1LoopingacrossthePixelswith Range 171
6.1.2WritingFasterPixelLoops173
6.2MirroringaPicture175
6.3CopyingandTransformingPictures182
6.3.1Copying183
6.3.2CopyingSmallerandModifying189
6.3.3CopyingandReferencing191
6.3.4CreatingaCollage193
6.3.5GeneralCopying196
6.3.6Rotation197
6.3.7Scaling200
6.4CombiningPixels:Blurring205
6.5BlendingPictures208
6.6DrawingonImages210
6.6.1DrawingwithDrawingCommands212
6.6.2VectorandBitmapRepresentations213
6.7ProgramsasSpecifyingDrawingProcess215
6.7.1WhyDoWeWritePrograms?216
2 SOUND 225 7 ModifyingSoundsUsingLoops 227 7.1HowSoundIsEncoded227
7.1.1ThePhysicsofSound227
7.1.2InvestigatingDifferentSounds230
7.1.3EncodingtheSound235
7.1.4BinaryNumbersandTwo’sComplement236
7.1.5StoringDigitizedSounds237
7.2ManipulatingSounds239
7.2.1OpenSoundsandManipulatingSamples239
7.2.2UsingtheJESMediaTools242
7.2.3Looping243
7.3ChangingtheVolumeofSounds244
7.3.1IncreasingVolume244
7.3.2DidThatReallyWork?245
7.3.3DecreasingVolume249
7.3.4UsingArrayIndexNotation250
7.3.5MakingSenseofFunctionsinSounds251
7.4NormalizingSounds251
7.4.1GeneratingClipping253
8 ModifyingSamplesinaRange 259
8.1ManipulatingDifferentSectionsoftheSoundDifferently259
8.1.1RevisitingIndexArrayNotation260
8.2SplicingSounds262
8.3GeneralClipandCopy269
8.4ReversingSounds271
8.5Mirroring273
8.6OnFunctionsandScope273
9 MakingSoundsbyCombiningPieces 279
9.1ComposingSoundsThroughAddition279
9.2BlendingSounds280
9.3CreatinganEcho282
9.3.1CreatingMultipleEchoes284
9.3.2CreatingChords284
9.4HowSamplingKeyboardsWork285
9.4.1SamplingasanAlgorithm289
9.5AdditiveSynthesis289
9.5.1MakingSineWaves289
9.5.2AddingSineWavesTogether291
9.5.3CheckingOurResult292
9.5.4SquareWaves293
9.5.5TriangularWaves295
9.6ModernMusicSynthesis297
9.6.1MP3297
9.6.2MIDI298
10 BuildingBiggerPrograms 302
10.1DesigningProgramsTop-Down303
10.1.1ATop-DownDesignExample304
10.1.2DesigningtheTop-LevelFunction305
10.1.3WritingtheSubfunctions307
10.2DesigningProgramsBottom-Up311
10.2.1AnExampleBottom-UpProcess312
10.3TestingYourProgram312
10.3.1TestingtheEdgeConditions314
10.4TipsonDebugging315
10.4.1FindingWhichStatementtoWorryAbout316
10.4.2SeeingtheVariables316
10.4.3DebuggingtheAdventureGame318
10.5AlgorithmsandDesign321
10.6ConnectingtoDataOutsideaFunction322
10.7RunningProgramsOutsideofJES326
3 TEXT,FILES,NETWORKS,DATABASES, ANDUNIMEDIA 333 11 ManipulatingTextwithMethodsandFiles 335
11.1TextasUnimedia335
11.2ManipulatingPartsofStrings336
11.2.1StringMethods:IntroducingObjectsandDotNotation337
11.2.2Lists:Powerful,StructuredText339
11.2.3StringsHaveNoFont341
11.3Files:PlacestoPutYourStringsandOtherStuff341
11.3.1OpeningandManipulatingFiles343
11.3.2GeneratingFormLetters344
11.3.3ReadingandManipulatingDatafromtheInternet345
11.3.4ScrapingInformationfromaWebPage348
11.3.5ReadingCSVData349
11.3.6WritingOutPrograms351
11.4ThePythonStandardLibrary352
11.4.1MoreonImportandYourOwnModules353
11.4.2AddingUnpredictablytoYourProgramwithRandom354
11.4.3ReadingCSVFileswithaLibrary356
11.4.4ASamplingofPythonStandardLibraries356
12
AdvancedTextTechniques:Web andInformation 361
12.1Networks:GettingOurTextfromtheWeb361
12.1.1AutomatingAccesstoCSVData365
12.1.2AccessingFTP367
13 12.2UsingTexttoShiftBetweenMedia368
12.3MovingInformationBetweenMedia371
12.4UsingListsasStructuredTextforMediaRepresentations374
12.5HidingInformationinaPicture375
12.5.1HidingaSoundInsideaPicture377
MakingTextfortheWeb 383 13.1HTML:TheNotationoftheWeb383
13.2WritingProgramstoGenerateHTML388
13.2.1MakingHomePages390
13.3Databases:APlacetoStoreOurText393
13.3.1RelationalDatabases395
13.3.2AnExampleRelationalDatabaseUsingHashTables396
13.3.3WorkingwithSQL399
13.3.4UsingaDatabasetoBuildWebPages401
4 MOVIES 407 14 CreatingandModifyingMovies 409
14.1GeneratingAnimations410
14.2WorkingwithVideoSource419
14.2.1VideoManipulatingExamples419
14.3BuildingaVideoEffectBottom-Up423
15 Speed 430
15.1FocusingonComputerScience430
15.2WhatMakesProgramsFast?430
15.2.1WhatComputersReallyUnderstand431
15.2.2CompilersandInterpreters432
15.2.3WhatLimitsComputerSpeed?436
15.2.4DoesItReallyMakeaDifference?438
15.2.5MakingSearchingFaster441
15.2.6AlgorithmsThatNeverFinishorCan’tBeWritten443
15.2.7WhyIsPhotoshopFasterthanJES?444
15.3WhatMakesaComputerFast?444
15.3.1ClockRatesandActualComputation445
15.3.2Storage:WhatMakesaComputerSlow?446
15.3.3Display447
16 FunctionalProgramming 450 16.1UsingFunctionstoMakeProgrammingEasier450
16.2FunctionalProgrammingwithMapandReduce454
16.3FunctionalProgrammingforMedia457
16.3.1MediaManipulationwithoutChangingState458
16.4Recursion:APowerfulIdea459
16.4.1RecursiveDirectoryTraversals464
16.4.2RecursiveMediaFunctions466
17 Object-OrientedProgramming 471 17.1HistoryofObjects471
17.2WorkingwithTurtles473
17.2.1ClassesandObjects473
17.2.2SendingMessagestoObjects474
17.2.3ObjectsControlTheirState476
17.3TeachingTurtlesNewTricks478
17.3.1OverridinganExistingTurtleMethod480
17.3.2WorkingwithMultipleTurtlesatOnce481
17.3.3TurtleswithPictures483
17.3.4DancingTurtles484
17.3.5RecursionandTurtles487
17.4AnObject-OrientedSlideShow488
17.4.1MakingtheSlideClassMoreObject-Oriented491
17.5Object-OrientedMedia493
17.6JoetheBox498
17.7WhyObjects?499
APPENDIX 506
A QuickReferencetoPython 506
A.1Variables506
A.2FunctionCreation507
A.3LoopsandConditionals507
A.4OperatorsandRepresentationFunctions508
A.5NumericFunctions509
A.6SequenceOperations509
A.7StringEscapes509
A.8UsefulStringMethods509
A.9Files510
A.10Lists510
A.11Dictionaries,HashTables,orAssociativeArrays510
A.12ExternalModules510
A.13Classes511
A.14FunctionalMethods511
Bibliography512
Index515
Prefaceforthe FourthEdition WestartedMediaComputationintheofSummer2002,andtaughtitforthefirsttime inSpring2003.It’snowovertenyearslater,whichisagoodtimetosummarizethe changesacrossthesecond,third,andfourtheditions.
MediaComputationhasbeenusedsuccessfullyinanundergraduatecourseatGeorgiaTechforthelastdozenyears.Thecoursecontinuestohavehighretentionrates(over 85%ofstudentscompletetheclasswithapassinggrade),andismajorityfemale.Both studentsandteachersreport enjoying thecourse,whichisanimportantrecommendation forit.
ResearchershavefoundthatMediaComputationworksinavarietyofcontexts. TheUniversityofIllinois-ChicagohadthefirstMediaComputationpaperoutsideof Georgia,andtheyshowedhowswitchingtoMediaCompimprovedtheirretention ratesinclassesthatweremuchmorediversethanthoseatGeorgiaTech[41].The UniversityofCalifornia-SanDiegoadoptedMediaComputationaspartofabigchange intheirintroductorycourse,wheretheyalsostartedusingpair-programmingandpeer instruction.Theirpaperatthe2013SIGCSESymposiumshowedhowthesechanges ledtodramaticimprovementsinstudentretention,evenmeasuredayearlaterinthe Sophomoreyear.ThepaperalsowontheBestPaperawardattheconference[27]. It’sbeenparticularlydelightfultoseeMediaComputationadoptedandadaptedfor newsettings,likeCynthiaBaileyLee’screationofaMATLABMediaComputation curriculum[12].
Markwroteapaperin2013,summarizingtenyearsofMediaComputationresearch. MediaComputationdoesoftenimproveretention.Ourdetailedinterviewstudieswith femalestudentssupportstheclaimthattheyfindtheapproachtobecreativeandengaging,andthat’swhatkeepsthestudentsintheclass.ThatpaperwontheBestPaperaward atthe2013InternationalComputingEducationResearch(ICER)Conference[33].
HOWTOTEACHMEDIACOMPUTATION Overthelast10years,wehavelearnedsomeoftheapproachesthatworkbestfor teachingMediaComputation.
• Letthestudentsbecreative. ThemostsuccessfulMediaComputationclasses useopen-endedassignmentsthatletthestudentschoosewhatmediatheyuse. Forexample,acollageassignmentmightspecifytheuseofparticularfiltersand compositions,butallowforthestudenttochooseexactlywhatpicturesareused. Theseassignmentsoftenleadtothestudentsputtinginalotmoretimetoget just thelookthattheywanted,andthatextratimecanleadtoimprovedlearning.
• Letthestudentssharewhattheyproduce. Studentscanproducesomebeautiful pictures,sounds,andmoviesusingMediaComputation.Thoseproductsaremore motivatingforthestudentswhentheygettosharethemwithothers.Someschools provideonlinespaceswherestudentscanpostandsharetheirproducts.Other schoolshaveevenprintedstudentworkandheldanartgallery.
• Codeliveinfrontoftheclass. Thebestpartoftheteacheractuallytypingincode infrontoftheclassisthat nobody cancodeforlonginfrontofanaudienceand not makeamistake.Whentheteachermakesamistakeandfixesit,thestudents see(a)thaterrorsareexpectedand(b)thereisaprocessforfixingthem.Coding livewhenyouareproducingimagesandsoundsisfun,andcanleadtounexpected resultsandtheopportunitytoexplore,“Howdid that happen?”
• Pairprogrammingleadstobetterlearningandretention. Theresearchresultson pairprogrammingaretremendous.Classesthatusepairprogramminghavebetter retentionresults,andthestudentslearnmore.
• Peerinstructionisgreat. Notonlydoespeerinstructionleadtobetterlearning andretentionoutcomes,butitalsogivestheteacherbetterfeedbackonwhatthe studentsarelearningandwhattheyarestrugglingwith.Westronglyencourage theuseofpeerinstructionincomputingclasses.
• Workedexampleshelpwithcreativitylearning. Mostcomputerscienceclasses donotprovideanywherenearlyenoughworked-outexamplesforstudentsto learnfrom.Studentsliketolearnfromexamples.OneofthebenefitsofMedia Computationisthatweprovidealotofexamples(we’venevertriedtocountthe numberof for and if statementsinthebook!), and it’seasytoproducemore ofthem.Inclass,wedoanactivitywherewehandoutexampleprograms,then showaparticulareffect.Weaskpairsorgroupsofstudentstofigureoutwhich programgeneratedthateffect.Thestudentstalkaboutcode,andstudyabunchof examples.
APCSPRINCIPLES TheAdvancedPlacementexaminCSPrinciples1 hasnowbeendefined.Wehave explicitlywrittenthefourtheditionwithCSPrinciplesinmind.Forexample,weshow howtomeasurethespeedofaprogramempiricallyinordertocontrasttwoalgorithms (LearningObjective4.2.4),andweexploremultiplewaysofanalyzingCSVdatafrom theInternet(LearningObjectives3.1.1,3.2.1,and3.2.2).
Overall,weaddresstheCSPrincipleslearningobjectivesexplicitlyinthisbookas shownbelow:
• In BigIdeaI:Creativity :
• LO1.1.1: usecomputingtoolsandtechniquestocreateartifacts.
• LO1.2.1: usecomputingtoolsandtechniquesforcreativeexpression.
1 http://apcsprinciples.org
• LO1.2.2: ... createacomputationalartifactusingcomputingtoolsandtechniques tosolveaproblem.
• LO1.2.3: createanewcomputationalartifactbycombiningormodifying existingartifacts.
• LO1.2.5: ... analyzethecorrectness,usability,functionality,andsuitabilityof computationalartifacts.
• LO1.3.1: ... useprogrammingasacreativetool.
• In BigIdeaII:Abstraction:
• LO2.1.1: ... describethevarietyofabstractionsusedtorepresentdata.
• LO2.1.2: ... explainhowbinarysequencesareusedtorepresentdigitaldata.
• LO2.2.2: ... usemultiplelevelsofabstractionincomputation.
• LO2.2.3: ... identifymultiplelevelsofabstractionsbeingusedwhenwriting programs.
• In BigIdeaIII:Dataandinformation:
• LO3.1.1: ... usecomputerstoprocessinformation,findpatterns,andtest hypothesesaboutdigitallyprocessedinformationtogaininsightandknowledge.
• LO3.2.1: ... extractinformationfromdatatodiscoverandexplainconnections, patterns,ortrends.
• LO3.2.2: ... uselargedatasetstoexploreanddiscoverinformationandknowledge.
• LO3.3.1: analyzehowdatarepresentation,storage,security,andtransmission ofdatainvolvecomputationalmanipulationofinformation.
• In BigIdeaIV:Algorithms:
• LO4.1.1: ... developanalgorithmdesignedtobeimplementedtorunona computer.
• LO4.1.2: ... expressanalgorithminalanguage.
• LO4.2.1: ... explainthedifferencebetweenalgorithmsthatruninareasonable timeandthosethatdonotruninareasonabletime.
• LO4.2.2: explainthedifferencebetweensolvableandunsolvableproblems incomputerscience.
• LO4.2.4: ... evaluatealgorithmsanalyticallyandempiricallyforefficiency, correctness,andclarity.
• In BigIdeaV:Programming:
• LO5.1.1: ... developaprogramforcreativeexpression,tosatisfypersonal curiosityortocreatenewknowledge.
• LO5.1.2: developacorrectprogramtosolveproblems.
• LO5.2.1: explainhowprogramsimplementalgorithms.
• LO5.3.1: ... useabstractiontomanagecomplexityinprograms.
• LO5.5.1: ... employappropriatemathematicalandlogicalconceptsinprogramming.
• In BigIdeaVI:TheInternet :
• LO6.1.1: explaintheabstractionsintheInternetandhowtheInternetfunctions.
CHANGESINTHEFOURTHEDITION 1. Wefixedlotsofbugsthatourcrackbug-findersidentifiedinthethirdedition.
2. Wechangedmostofthepicturesinthebook–theyweregettingstale,andourkids wantedustonotuseasmanypicturesofthem.
3. Weaddedmoreend-of-chapterquestions.
4. Weaddedawholenewchapter,ontextasamediumandmanipulatingstrings (tomakesentences,koans,andcodes).Thisisn’ta necessary chapter(e.g.,we introduce for and if statements,butwedidn’tremovetheintroductionslaterin thebook).Forsomeofourteachers,playingwithtextwithshorterloops(iterating overallthecharactersinasentenceistypicallysmallerthanthethousandsofpixels inapicture)isamorecomfortablewaytostart.
5. WegaveupfightingthebattleofinventingaWebscraperthatcouldbeatoutthe changesthatFacebookmade,whichkeptbreakingtheoneweputinthe3rdedition andthenkeptupdatingontheteacher’swebsite2 .Instead,wewroteexamplesin thisbookforprocessingCSV(Comma-SeparatedValues),acommonformatfor sharingdataontheInternet.WeparsetheCSVfromafileusingstringprocessing, thenusingtheCSVlibraryinPython,andthenaccessingthedatabyURL.
6. Weaddedsomenewedgedetectioncodewhichisshorterandsimplertounderstand.
7. Weaddedmorewithturtles:creatingdancingturtles(using sleep fromthe time moduletopauseexecution)andrecursivepatterns.
8. WeupdatedthebooktousethelatestfeaturesinJES,whichincludethosethat reducetheneedtousefullpathnames(aproblemidentifiedbyStephenEdwards andhisstudentsintheirSIGCSE2014paper[43]).
ACKNOWLEDGMENTS Oursincerethanksgoouttoallourreviewersandbug-finders:
• AtthetopofthelistisSusanSchwarzoftheUSMilitaryAcademyatWestPoint. Susanrunsalargecoursewithmanyinstructors,andpayscarefulattentionto what’sgoinginallofthesectionsofthecourse.Sheturnedthatattentionon thethirdeditionofthisbook.Shecaughtmanybugs,andgaveuslotsofuseful feedback.Thanks,Susan!
2 http://home.cc.gatech.edu/mediaComp and http://www.mediacomputation.org
• OurotherbugfindersforthebookwereJohnRutkiewicz,U.Massachusetts–Dartmouth;BrianDorn,U.Nebraska–Omaha;DaveLargent,BallStateUniversity;Simon,UniversityofNewcastle;EvaHeinrich,MasseyUniversity;Peter J.DePasquale,TheCollegeofNewJersey,andBillLeahy,GeorgiaInstituteof Technology.
• MatthewFrazier,NorthCarolinaStateUniversity,workedwithusinthesummer of2014tocreateanewversionofJES–fixingmanybugs,andimprovingJES considerably.
• Wearegratefulforthefeedbackfromourbookreviewersforthe4thedition: AndrewCencini,BenningtonCollege;SusanFox,MacalesterCollege;Kristin Lamberty,UniversityofMinnesota-Morris;JeanSmith,TechnicalCollegeofthe Lowcountry;andWilliamT.Verts,UniversityofMassachusetts-Amherst.
• Wearegratefulfortheinputfromourbookreviewersforthe3rdedition,too: JosephOldham,CentreCollege;LukaszZiarek,PurdueUniversity;Joseph O’Rourke,SmithCollege;AtulPrakash,UniversityofMichigan;NoahD.Barnette,VirginiaTech;AdelaidaA.Medlock,DrexelUniversity;SusanE.Fox, MacalesterCollege;DanielG.Brown,UniversityofWaterloo;BrianA.Malloy, ClemsonUniversity;ReneeRenner,CaliforniaStateUniversity,Chico.
MarkGuzdialandBarbaraEricson GeorgiaInstituteofTechnology
PrefacetotheFirstEdition Researchincomputingeducationmakesitclearthatonedoesn’tjust“learntoprogram.” Onelearnstoprogram something [8,19],andthemotivationtodothatsomethingcan makethedifferencebetweenlearningandnotlearningtoprogram[5].Thechallenge foranyteacheristopicka something thatisapowerfulenoughmotivator.
Peoplewanttocommunicate.Wearesocialcreaturesandthedesiretocommunicate isoneofourprimalmotivations.Increasingly,thecomputerisusedasatoolforcommunicationevenmorethanatoolforcalculation.Virtuallyallpublishedtext,images, sounds,music,andmoviestodayarepreparedusingcomputingtechnology.
Thisbookisaboutteachingpeopletoprograminordertocommunicatewithdigital media.Thebookfocusesonhowtomanipulateimages,sounds,text,andmoviesas professionalsmight,butwithprogramswrittenbystudents.Weknowthatmostpeople willuseprofessional-gradeapplicationstoperformthesetypeofmanipulations.But, knowing how towriteyourownprogramsmeansthatyou can domorethanwhatyour currentapplicationallowsyoutodo.Yourpowerofexpressionisnotlimitedbyyour applicationsoftware.
Itmayalsobetruethatknowinghowthealgorithmsinamediaapplicationswork allowsyoutousethembetterortomovefromoneapplicationtothenextmoreeasily. Ifyourfocusinanapplicationisonwhatmenuitemdoeswhat,everyapplicationis different.Butifyourfocusisonmovingorcoloringthepixelsinthewayyouwant, thenmaybeit’seasiertogetpastthemenuitemsandfocusonwhatyouwanttosay.
Thisbookisnotjustaboutprogramminginmedia.Media-manipulationprograms canbehardtowriteormaybehaveinunexpectedways.Naturalquestionsarise,like “WhyisthesameimagefilterfasterinPhotoshop?”and“Thatwashardtodebug—Are therewaysofwritingprogramsthatare easier todebug?”Answeringquestionslike theseiswhatcomputerscientistsdo.Thereareseveralchaptersattheendofthebook thatareabout computing,notjustprogramming.Thefinalchaptersgobeyondmedia manipulationtomoregeneraltopics.
Thecomputeristhemostamazinglycreativedevicethathumanshaveeverconceived. Itiscompletelymadeupofmind-stuff.Thenotion“Don’tjustdreamit,beit”isreally possibleonacomputer.Ifyoucanimagineit,youcanmakeit“real”onthecomputer. Playingwithprogrammingcanbeand should beenormousfun.
OBJECTIVES,APPROACHANDORGANIZATION Thecurricularcontentofthisbookmeetstherequirementsofthe“imperative-first” approachdescribedintheACM/IEEE ComputingCurriculum2001 standardsdocument [2].Thebookstartswithafocusonfundamentalprogrammingconstructs:assignments, sequentialoperations,iteration,conditionals,anddefiningfunctions.Abstractions
(e.g.,algorithmiccomplexity,programefficiency,computerorganization,hierarchicaldecomposition,recursion,andobject-orientedprogramming)areemphasizedlater, afterthestudentshaveacontextforunderstandingthem.
Thisunusualorderingisbasedonthefindingsofresearchinthelearningsciences. Memoryisassociative.Weremembernewthingsbasedonwhatweassociatethemwith. Peoplecanlearnconceptsandskillsonthepremisethattheywillbeusefulsomedaybut theconceptsandskillswillberelatedonlytothepremises.Theresulthasbeendescribed as“brittleknowledge”[25]—thekindofknowledgethatgetsyouthroughtheexam butispromptlyforgottenbecauseitdoesn’trelatetoanythingbutbeinginthatclass.
Conceptsandskillsarebestrememberediftheycanberelatedtomanydifferent ideasortoideasthatcomeupinone’severydaylife.Ifwewantstudentstogain transferable knowledge(knowledgethatcanbeappliedinnewsituations),wehaveto helpthemtorelatenewknowledgetomoregeneralproblems,sothatthememoriesget indexedinwaysthatassociatewiththosekindsofproblems[22].Inthisbook,weteach withconcreteexperiencesthatstudentscanexploreandrelateto(e.g.,conditionalsfor removingred-eyeinpictures)andlaterlayabstractionsontopofthem(e.g.,achieving thesamegoalusingrecursionorfunctionalfiltersandmaps).
Weknowthatstartingfromtheabstractionsdoesn’treallyworkforcomputing students.AnnFleuryhasshownthatstudentsinintroductorycomputingcoursesjust don’tbuywhatwetellthemaboutencapsulationandreuse(e.g.,[7]).Studentsprefer simplercodethattheycantraceeasilyandtheyactuallythinkthatsuchcodeis better. Ittakestimeandexperienceforstudentstorealizethatthereisvalueinwell-designed systems.Withoutexperience,it’sverydifficultforstudentstolearntheabstractions.
The mediacomputation approachusedinthisbookstartsfromwhatmanypeople usecomputersfor:imagemanipulation,exploringdigitalmusic,viewingandcreating Webpages,andmakingvideos.Wethenexplainprogrammingandcomputinginterms oftheseactivities.WewantstudentstovisitAmazon(forexample)andthink,“Here’s acatalogWebsite—andIknowthattheseareimplementedwithadatabaseanda setofprogramsthatformatthedatabaseentriesasWebpages.”Wewantstudentsto useAdobePhotoshopandGIMPandthinkabouthowtheirimagefiltersareactually manipulatingred,green,andbluecomponentsofpixels.Startingfromarelevantcontext makestransferofknowledgeandskillsmorelikely.Italsomakestheexamplesmore interestingandmotivating,whichhelpswithkeepingstudentsintheclass.
Themediacomputationapproachspendsabouttwo-thirdsofthetimeongiving studentsexperienceswithavarietyofmediaincontextsthattheyfindmotivating.After thattwo-thirds,though,theynaturallystarttoaskquestionsabout computing.“Whyis itthatPhotoshopisfasterthanmyprogram?”and“Moviecodeisslow—Howslowdo programsget?”aretypical.Atthatpoint,weintroducetheabstractionsandthevaluable insightsfromcomputersciencethatanswer their questions.That’swhatthelastpart ofthisbookisabout.
Adifferentbodyofresearchincomputingeducationexploreswhywithdrawalor failureratesinintroductorycomputingaresohigh.Onecommonthemeisthatcomputingcoursesseem“irrelevant”andunnecessarilyfocuson“tediousdetails”such asefficiency[21,1].Acommunicationscontextisperceivedasrelevantbystudents
(astheytellusinsurveysandinterviews[6,18]).Therelevantcontextispartofthe explanationforthesuccesswehavehadwithretentionintheGeorgiaTechcoursefor whichthisbookwaswritten.
Thelateentranceofabstractionisn’ttheonlyunusualorderinginthisapproach.We startusingarraysandmatricesinChapter3,inourfirstsignificantprograms.Typically, introductorycomputingcoursespusharraysoffuntillater,becausetheyareobviously morecomplicatedthanvariableswithsimplevalues.Arelevantandconcretecontext isverypowerful[19].Wefindthatstudentshavenoproblemmanipulatingmatricesof pixelsinapicture.
Therateofstudentswithdrawingfromintroductorycomputingcoursesorreceiving aDorFgrade(commonlycalledthe WDFrate)isreportedinthe30–50%rangeor evenhigher.Arecentinternationalsurveyoffailureratesinintroductorycomputing coursesreportedthattheaveragefailurerateamong54U.S.institutionswas33%and among17internationalinstitutionswas17%[24].AtGeorgiaTech,from2000to2002, wehadanaverageWDFrateof28%intheintroductorycourserequiredforallmajors. Weusedthefirsteditionofthistextinourcourse IntroductiontoMediaComputation. Ourfirstpilotofferingofthecoursehad121students,nocomputingorengineering majors,andtwo-thirdsofthestudentswerefemale.OurWDFratewas11.5%.
Overthenexttwoyears(Spring2003toFall2005),theaverageWDFrateatGeorgia Tech(acrossmultipleinstructors,andliterallythousandsofstudents)was15%[29]. Actually,the28%priorWDFrateand15%currentWDFrateareincomparable,since allmajorstookthefirstcourseandonlyliberalarts,architecture,andmanagement majorstookthenewcourse.Individualmajorshavemuchmoredramaticchanges. Managementmajors,forexample,hada51.5%WDFratefrom1999to2003withthe earliercourse,andhada11.2%failurerateinthefirsttwoyearsofthenewcourse[29]. Sincethefirsteditionofthisbookwaspublished,severalotherschoolshaveadopted andadaptedthisapproachandevaluatedtheirresult.Allofthemhavereportedsimilar, dramaticimprovementsinsuccessrates[4,42].
WaystoUseThisBook ThisbookrepresentswhatweteachatGeorgiaTechinprettymuchthesameorder. Individualteachersmayskipsomesections(e.g.,thesectiononadditivesynthesis, MIDI,andMP3),butallofthecontentherehasbeentestedwithourstudents. However,thismaterialhasbeenusedinmanyotherways.
• AshortintroductiontocomputingcouldbetaughtwithjustChapters2(introductiontoprogramming)and3(introductiontoimageprocessing),perhapswith somematerialfromChapters4and5.Wehavetaughtevensingle-dayworkshops onmediacomputationusingjustthismaterial.
• Chapters6through8basicallyreplicatethecomputerscienceconceptsfrom Chapters3through5butinthecontextofsoundsratherthanimages.Wefind thereplicationuseful—somestudentsseemtorelatebettertotheconceptsof iterationandconditionalswhenworkingwithonemediumthanwiththeother.
Further,itgivesustheopportunitytopointoutthatthesame algorithm canhave similareffectsindifferentmedia(e.g.,scalingapictureupordownandshiftinga soundhigherorlowerinpitcharethesamealgorithm).Butitcouldcertainlybe skippedtosavetime.
• Chapter12(onmovies)introducesnonewprogrammingorcomputingconcepts. Whilemotivational,movieprocessingcouldbeskippedtosavetime.
• Werecommendgettingtoatleastsomeofthechaptersinthelastunit,inorderto leadstudentsintothinkingaboutcomputingandprogramminginamoreabstract manner,butclearlynot all ofthechaptershavetobecovered.
PythonandJython TheprogramminglanguageusedinthisbookisPython.Pythonhasbeendescribedas “executablepseudo-code.”Wehavefoundthatbothcomputersciencemajorsandnon majorscanlearnPython.SincePythonisactuallyusedforcommunicationstasks(e.g., Websitedevelopment),it’sarelevantlanguageforanintroductorycomputingcourse. Forexample,jobadvertisementspostedtothePythonWebsite(http://www.python. org)showthatcompanieslikeGoogleandIndustrialLight&MagichirePythonprogrammers.
ThespecificdialectofPythonusedinthisbookis Jython (http://www.jython. org).Jython is Python.ThedifferencesbetweenPython(normallyimplementedinC) andJython(whichisimplementedinJava)areakintothedifferencesbetweenany twolanguageimplementations(e.g.,Microsoftvs.GNUC++ implementations)—the basiclanguageis exactly thesame,withsomelibraryanddetailsdifferencesthatmost studentswillnevernotice.
TYPOGRAPHICALNOTATIONS ExamplesofPythoncodelooklikethis: x=x+1.Longerexampleslooklikethis: defhelloWorld(): print "Hello,world!"
WhenshowingsomethingthattheusertypesinwithPython’sresponse,itwillhave asimilarfontandstyle,buttheuser’stypingwillappearafteraPythonprompt(>>>): >>> print 3+4
7
UserinterfacecomponentsofJES(JythonEnvironmentforStudents)willbespecifiedusingasmallcapsfont,like Save menuitemandthe Load button. Thereareseveralspecialkindsofsidebarsthatyou’llfindinthebook.
ComputerScienceIdea: AnExampleIdea Keycomputerscienceconceptsappearlikethis.
CommonBug: AnExampleCommonBug
Commonthingsthatcancauseyourprogramtofailappearlikethis.
DebuggingTip: AnExampleDebuggingTip
Ifthere’sagoodwaytokeepabugfromcreepingintoyourprogramsinthefirstplace, it’shighlightedhere.
MakingItWorkTip: AnExampleHowtoMakeItWork Bestpracticesortechniquesthatreallyhelparehighlightedlikethis.
INSTRUCTORRESOURCES TheinstructorresourcesareavailableonthePearsonEducation’sInstructorResource Centerat www.pearsonglobaleditions.com/guzdial:
• PowerPoint Presentationslides
ACKNOWLEDGMENTS Oursincerethanksgoouttothefollowing:
• JasonErgle,ClaireBailey,DavidRaines,andJoshuaSklare,whomadetheinitial versionofJESwithsurprisingqualityinanamazinglyshortamountoftime.Over theyears,AdamWilson,LarryOlson,YuCheung(Toby)Ho,EricMickley,Keith McDermott,EllieHarmon,TimmyDouglas,AlexRudnick,BrianO’Neill,and WilliamFredrick(Buck)ScharfnorthIIIhavemadeJESintotheusefulandstill understandabletoolthatitistoday.
• AdamWilsonbuilttheMediaToolsthataresousefulforexploringsoundsand imagesandprocessingvideo.
• AndreaForte,MarkRichman,MattWallace,AlisaBandlow,DerekChambless, LarryOlson,andDavidRenniehelpedbuildcoursematerials.Derek,Mark,and Mattcreatedmanyexampleprograms.
• TherewereseveralpeoplewhoreallymadetheeffortcometogetheratGeorgia Tech.BobMcMath,Vice-ProvostatGeorgiaTech,andJimFoley,AssociateDean forEducationintheCollegeofComputing,investedinthiseffortearlyon.Kurt Eiseltworkedhardtomakethiseffortreal,convincingotherstotakeitseriously. JanetKolodnerandAaronBobickwereexcitedandencouragingabouttheidea ofmediacomputationforstudentsnewtocomputerscience.JeffPiercereviewed
andadvisedusonthedesignofthemediafunctionsusedinthebook.Aaron Lantermangavemelotsofadviceonhowtoconveythedigitalmaterialcontent accurately.JoanMorton,ChrissyHendricks,DavidWhite,andallthestaffofthe GVUCentermadesurethatwehadwhatweneededandthatthedetailswere handledtomakethiseffortcometogether.AmyBruckmanandEugeneGuzdial boughtMarktimetogetthefinalversioncompleted.
• WearegratefultoColinPottsandMonicaSweatwhohavetaughtthisclassat GeorgiaTechandgivenusmanyinsightsaboutthecourse.
• CharlesFowlerwasthefirstpersonoutsideofGeorgiaTechwillingtotakethe gambleandtrialthecourseinhisowninstitution(GainesvilleCollege),forwhich we’reverygrateful.
• ThepilotcourseofferedinSpring2003atGeorgiaTechwasveryimportantin helpingusimprovethecourse.AndreaForte,RachelFithian,andLaurenRichdid theassessmentofthepilotofferingofthecourse,whichwasincrediblyvaluablein helpingusunderstandwhatworkedandwhatdidn’t.Thefirstteachingassistants (JimGruen,AngelaLiang,LarryOlson,MattWallace,AdamWilson,andJose Zagal)didalottohelpcreatethisapproach.BlairMacIntyre,ColinPotts,and MonicaSweathelpedmakethematerialseasierforotherstoadopt.JochenRick madetheCoWeb/SwikiagreatplaceforCS1315studentstohangout.
• Manystudentspointedouterrorsandmadesuggestionstoimprovethebook. ThankstoCatherineBilliris,JenniferBlake,KarinBowman,MaryamDoroudi, SuzannahGill,BaillieHomire,JonathanLaing,MireilleMurad,MichaelShaw, SummarShoaib,andespeciallyJonathanLonghitano,whohasarealflairfor copyediting.
• Thankstoformer MediaComputation studentsConstantinoKombosch,Joseph Clark,andShannonJoinerforpermissiontousetheirsnapshotsfromclassin examples.
• TheresearchworkthatledtothistextwassupportedbygrantsfromtheNational ScienceFoundation—fromtheDivisionofUndergraduateEducation,CCLIprogram,andfromtheCISEEducationalInnovationsprogram.Thankyouforthe support.
• ThankstocomputingstudentsAnthonyThomas,CelinesRivera,andCarolina Gomezforallowingustousetheirpictures.
• Finallybutmostimportant,thankstoourchildrenMatthew,Katherine,andJennifer Guzdial,whoallowedthemselvestobephotographedandrecordedforMommy andDaddy’smediaprojectandwhoweresupportiveandexcitedabouttheclass.
MarkGuzdialandBarbaraEricson GeorgiaInstituteofTechnology PearsonwouldliketothankandacknowledgeDheerajD.,REVAInstituteofTechnologyandManagementKattigenahalli,SomitraSanadhya,IndianInstituteofTechnology Delhi,andSimon,UniversityofNewcastle,forcontributingtotheGlobalEdition,and ShaligramPrajapat,DeviAhilyaUniversityIndore,NgHu,MultimediaUniversity, RohitTahiliani,RenjithS.,andShivaniPandit,forreviewingtheGlobalEdition.
AbouttheAuthors MarkGuzdial isaprofessorintheSchoolofInteractiveComputingintheCollege ofComputingatGeorgiaInstituteofTechnology.Heisoneofthefoundersofthe ACM’sInternationalComputingEducationResearchworkshopseries.Dr.Guzdial’s researchfocusesonlearningsciencesandtechnology,specifically,computingeducation research.HisfirstbookswereontheprogramminglanguageSqueakanditsusein education.Hewastheoriginaldeveloperof“Swiki”(SqueakWiki),thefirstwiki developedexplicitlyforuseinschools.HeisaFellowandaDistinguishedEducator oftheACM.Heisontheeditorialboardsofthe JournaloftheLearningSciences and CommunicationsoftheACM. Hewasarecipientofthe2012IEEEComputerSociety UndergraduateTeachingAward.
BarbaraEricson isaresearchscientistandthedirectorofComputingOutreachfor theCollegeofComputingatGeorgiaTech.Shehasbeenworkingonimprovingintroductorycomputingeducationsince2004.
ShehasservedastheteachereducationrepresentativeontheComputerScience TeachersAssociationboard,theco-chairoftheK-12AlliancefortheNationalCenter forWomeninInformationTechnology,andasareaderfortheAdvancedPlacement ComputerScienceexams.Sheenjoysthediversityofthetypesofproblemsshehas workedonovertheyearsincomputingincludingcomputergraphics,artificialintelligence,medicine,andobject-orientedprogramming.
MarkandBarbarareceivedthe2010ACMKarlV.KarlstromAwardforOutstanding ComputerEducatorfortheirworkonMediaComputationincludingthisbook.Theyled aprojectcalled“GeorgiaComputes!”forsixyears,whichhadasignificantimpactin improvingcomputingeducationintheUSstateofGeorgia[31].Together,theyMark andBarbaraareleadersinthe ExpandingComputingEducationPathways (ECEP) alliance3
3 http://www.ecepalliance.org
PART 1 INTRODUCTION Chapter1IntroductiontoComputerScience andMediaComputation
Chapter2IntroductiontoProgramming
Chapter3CreatingandModifyingText
Chapter4ModifyingPicturesUsingLoops
Chapter5PictureTechniqueswithSelection
Chapter6ModifyingPixelsbyPosition
This page intentionally left blank
1 1 Introduction toComputerScience andMediaComputation ChapterLearningObjectives • Toexplainwhatcomputerscienceisaboutandwhatcomputerscientistsare concernedwith.
• Toexplainwhywedigitizemedia.
• Toexplainwhyit’svaluabletostudycomputing.
• Toexplaintheconceptofan encoding.
• Toexplainthebasiccomponentsofacomputer.
1.1 WHATISCOMPUTERSCIENCEABOUT? Computerscienceisthestudyof process:howweorcomputersdothings,howwe specifywhatwedo,andhowwespecifywhatthestuffisthatwe’reprocessing.That’s aprettydrydefinition.Let’stryametaphoricalone.
ComputerScienceIdea: ComputerScienceIstheStudyofRecipes
‘‘Recipes’’hereareaspecialkind—onethatcanbeexecutedbyacomputationaldevice, butthispointisonlyofimportancetocomputerscientists.Theimportantpointoverallis thatacomputersciencerecipedefines exactly whathastobedone.
Moreformally,computerscientistsstudy algorithms whicharestep-by-stepprocedurestoaccomplishatask.Eachstepinanalgorithmissomethingthatacomputer alreadyknowshowtodo(e.g.,addtwosmallintegernumbers)orcanbetaughthowto do(e.g.,addinglargernumbersincludingthosewithadecimalpoint).Arecipethatcan runonacomputeriscalleda program.Aprogramisawaytocommunicateanalgorithm inarepresentationthatacomputercanexecute.
Touseourmetaphorabitmore—thinkofanalgorithmasthestep-by-stepwaythat yourgrandmothermadehersecretrecipe.Shealwaysdiditthesameway,andhada
reliablygreatresult.Writingitdownsothatyoucanreaditanddoitlaterisliketurning heralgorithmintoaprogramforyou.You execute therecipeby doing it—following therecipestep-by-stepinordertocreatesomethingthewaythatyourgrandmotherdid. Ifyougivetherecipetosomeoneelsewhocanreadthelanguageoftherecipe(maybe EnglishorFrench),thenyouhavecommunicatedthatprocesstothatotherperson,and theotherpersoncansimilarlyexecutetherecipetomakesomethingthewaythatyour grandmotherdid.
Ifyou’reabiologistwhowantstodescribehowmigrationworksorhowDNA replicates,thenbeingabletowritearecipethatspecifies exactly whathappens,in termsthatcanbecompletelydefinedandunderstood,is very useful.Thesameistrue ifyou’reachemistwhowantstoexplainhowequilibriumisreachedinareaction. Afactorymanagercandefineamachine-and-beltlayoutandeventesthowitworks— beforephysicallymovingheavythingsintoposition—usingcomputer programs.Being abletoexactlydefinetasksand/orsimulateeventsisamajorreasonwhycomputers haveradicallychangedsomuchofhowscienceisdoneandunderstood.
Infact,ifyou can’t writearecipeforsomeprocess,maybeyoudon’treallyunderstandtheprocess,ormaybetheprocesscan’tactuallyworkthewaythatyouarethinking aboutit.Sometimes,tryingtowritetherecipeisatestinitself.Now,sometimesyou can’twritetherecipebecausetheprocessisoneofthefewthatcannotbeexecutedby acomputer.WewilltalkmoreaboutthoseinChapter14.
Itmaysoundfunnytocall programs arecipe,buttheanalogygoesalongway.Much ofwhatcomputerscientistsstudycanbedefinedintermsofrecipes.
• Somecomputerscientistsstudyhowrecipesarewritten:Aretherebetterorworse waysofdoingsomething?Ifyou’veeverhadtoseparateeggwhitesfromyolks,you realizethatknowingtherightwaytodoitmakesaworldofdifference.Computer sciencetheoreticiansthinkaboutthefastestandshortestrecipes,andtheonesthat takeuptheleastamountofspace(youcanthinkaboutitascounterspace—the analogyworks),orevenusetheleastamountofenergy(whichisimportantwhen runningonlow-powerdeviceslikecellphones). How arecipeworks,completely apartfromhowit’swritten(e.g.,inaprogram),iscalledthestudyofalgorithms. Softwareengineersthinkabouthowlargegroupscanputtogetherrecipesthatstill work.(Someprograms,liketheonesthatkeeptrackofcreditcardtransactions, haveliterallymillionsofsteps!)Theterm software meansacollectionofcomputer programs(recipes)thataccomplishatask.
• Othercomputerscientistsstudytheunitsusedinrecipes.Doesitmatterwhether arecipeusesmetricorEnglishmeasurements?Therecipemayworkineither case,butifyoudon’tknowwhatapoundoracupis,therecipeisalotless understandabletoyou.Therearealsounitsthatmakesenseforsometasksand notothers,butifyoucanfittheunitstothetasks,youcanexplainyourselfmore easilyandgetthingsdonefaster—andavoiderrors.Everwonderwhyshipsat seameasuretheirspeedin knots?Whynotusesomethinglikemeterspersecond? Sometimes,incertainspecialsituations—onashipatsea,forinstance—themore commontermsaren’tappropriateordon’tworkaswell.Orwemayinventnew kindsofunits,likeaunitthatrepresentsawholeotherprogramoracomputer,or
anetworklikeyourfriendsandyourfriends’friendsinFacebook.Thestudyof computerscienceunitsisreferredtoas datastructures.Computerscientistswho studywaysofkeepingtrackoflotsofdata(inlotsofdifferentkindsofunits)and figuringouthowtoaccessthedataquicklyarestudying databases.
• Canrecipesbewrittenforanything?Aretheresomerecipesthat can’t bewritten? Computerscientistsknowthattherearerecipesthatcan’tbewritten.Forexample, youcan’twritearecipethatcanabsolutelytellwhethersomeotherrecipewill actuallywork.Howabout intelligence?Canwewritearecipesuchthatacomputer followingitwouldactuallybe thinking (andhowwouldyoutellifyougotitright)?
Computerscientistsin theory, intelligentsystems, artificialintelligence,and systems worryaboutthingslikethis.
• Thereareevencomputerscientistswhofocusonwhetherpeople like whatthe recipesproduce,almostlikerestaurantcriticsforanewspaper.Someofthese are human–computerinterface specialistswhoworryaboutwhetherpeoplecan understandandmakeuseoftherecipes(“recipes”thatproducean interface that peopleuse,likewindows,buttons,scrollbars,andotherelementsofwhatwethink aboutasarunningprogram).
• Justassomechefsspecializeincertainkindsofrecipes,likecrepesorbarbecue, computerscientistsalsospecializeincertainkindsofrecipes.Computerscientists whoworkin graphics aremostlyconcernedwithrecipesthatproducepictures, animations,andevenmovies.Computerscientistswhoworkin computermusic aremostlyconcernedwithrecipesthatproducesounds(oftenmelodicones,but notalways).
• Stillothercomputerscientistsstudythe emergentproperties ofrecipes.Think abouttheWorldWideWeb.It’sreallyacollectionof millions ofrecipes(programs) talkingtooneanother.WhywouldonesectionoftheWebgetsloweratsome point?It’saphenomenonthatemergesfromthesemillionsofprograms,certainly notsomethingthatwasplanned.That’ssomethingthat networking computer scientistsstudy.What’sreallyamazingisthattheseemergentproperties(that thingsjuststarttohappenwhenyouhavemany,manyrecipesinteractingatonce) canalsobeusedtoexplainnoncomputationalthings.Forexample,howantsforage forfoodorhowtermitesmakemoundscanalsobedescribedassomethingthat justhappenswhenyouhavelotsoflittleprogramsdoingsomethingsimpleand interacting.TherearecomputerscientiststodaywhostudyhowtheWeballowsfor newkindsofinteractions,particularlyinlargegroups(likeFacebookorTwitter). Computerscientistswhostudy socialcomputing areinterestedinhowthesenew kindsofinteractionsworkandthecharacteristicsofthesoftwarethataremost successfulforpromotingusefulsocialinteractions.
Therecipemetaphoralsoworksonanotherlevel.Everyoneknowsthatsomethings inarecipecanbechangedwithoutchangingtheresultdramatically.Youcanalways increasealltheunitsbyamultiplier(say,double)tomakemore.Youcanalwaysadd moregarlicororeganotothespaghettisauce.Buttherearesomethingsthatyoucannot changeinarecipe.Iftherecipecallsforbakingpowder,youmaynotsubstitutebaking
