Loading...
Computer Science and Game Theory: A Brief Survey
(see, for example, [Kearns and Reiter 2005; Sandholm and Yakoo 2003]); leading computer scientists are often invited to speak at major game theory conferences, such as the World Congress on Game Theory 2000 and 2004 In this article I survey some of the main themes of work in the area, with a focus on the work in computer science
An Introduction to Computer Science and Problem Solving
Many important topics in computer science can be taught without using computers at all This book unplugs computer science by providing twenty off-line activities, games and puzzles that are suitable for people of all ages and backgrounds, but especially for elementary school chil-dren
Computer Science - Computer Games September Entry
Computer Science - Computer Games Co-op Entry Year Term Course Title Credit Prerequisite Co-requisite Year 1 Fall COMP 232 Mathematics for Computer Science 3 00 MATH 203, 204 COMP 248 Object-Oriented Programming I 3 50 MATH 204 Elective* Winter COMP 228 System Hardware 3 00 COMP 248 MATH 203, 204
Designing educational games for computer programming: A
example, computer programming is a vital knowledge area within computer science with constantly changing curriculum and its teaching remains a difficult endeavour On the other hand, students start from a very early age to interact with computers through games and other entertaining multimedia software
Computer Science - Brown University
the nation's leading computer science programs, the Computer Science Department has continuously produced prominent contributors in the field Computer Science combines the intellectual challenge of a new discipline with the excitement of an innovative and rapidly expanding technology
Searches related to computer science and games filetype:pdf
However, computer science is not an area of study that pertains to IT support, repairing computers, nor installing and configuring networks Nor does it have anything to do with simply using a computer such as doing word-processing, browsing the web or playing games The focus of computer science is on understanding what goes on behind the
60351_3bell98a.pdf ComputerScienceUnplugged...
off-lineactivitiesandgames forallagesTimBell
IanH.Witten
MikeFellows
cJune9,1998
Thisversionofthebookmayonlybeusedbythosewhohavepurchasedashareware licence.Ifyouhaveanindividuallicenceyoumayprintonecopyofthisbookfor yourownuse,orifaninstitutionallicencehasbeenpurchased,acopymaybeprinted foranystaffmemberoftheinstitution,foruseintheinstitution.Copiesoftheblack- linemastersmaybemadeforyourownusewithclasses.Otherwisethisbookmay notbecopiedordistributedwithoutpermission.Seethewebsitebelowfordetails aboutobtainingalicence.Copyright1998.Allrightsreserved. http://unplugged.canterbury.ac.nzAuthors'contactdetails:
TimBell,
DepartmentofComputerScience,
UniversityofCanterbury,
PrivateBag4800,
Christchurch,NewZealand
tim@cosc.canterbury.ac.nz, phone(+643)364-2352IanH.Witten,
DepartmentofComputerScience,
WaikatoUniversity,
Hamilton,NewZealand
ihw@waikato.ac.nz, phone(+647)838-4246MikeFellows,
DepartmentofComputerScience,
UniversityofVictoria,
Victoria,BC,CanadaV8W3P6
mfellows@csr.UVic.ca, phone(604)721-2399Aboutthisbook
Manyimportanttopicsincomputersciencecanbetaughtwithoutusingcomputersatall.This bookunplugscomputersciencebyprovidingtwentyoff-lineactivities,gamesandpuzzlesthat aresuitableforpeopleofallagesandbackgrounds,butespeciallyforelementaryschoolchil- dren.Theactivitiescoverawiderangeoftopics,fromalgorithmstoartificialintelligence,from binarynumberstobooleancircuits,compressiontocryptography,datarepresentationtodead- lock.Byavoidingtheuseofcomputersaltogether,theactivitiesappealtothosewholackready accesstocomputers,andareidealforpeoplewhodon'tfeelcomfortableusingthem.Theonly materialsneededarecards,string,crayonsandotherhouseholditems. Fullinstructionsaregivenforeachactivity,andreproduciblesareprovidedwhereverpos- sibletominimizetheeffortrequiredforclasspreparation.Eachactivityincludesabackground sectionthatexplainsitssignificance,andanswersareprovidedforallproblems.Allyouneed formostoftheseactivitiesarecuriosityandenthusiasm. Theseactivitiesareprimarilyaimedatthefivetotwelveyear-oldagegroup.Theyhavebeen usedintheclassroom,insciencecenterdemonstrations,inthehome,andevenforcommunity fundaysinapark!Buttheyarebynomeansrestrictedtothisagerange:theyhavebeenused toteacholderchildrenandadultstoo. Thisbookisprincipallyforteacherswhowouldliketogivetheirclassessomethingabit differentfromthestandardfare,teachersattheelementary,juniorhigh,andhighschoollevels. Itisalsowrittenforcomputingprofessionalswhowouldliketohelpoutintheirchildren's orgrandchildren'sclassrooms,forparentswhocanusetheseasfamilyactivities,forhome- schoolers,forsciencecenterswhoruneducationalprogramsforchildren,forcomputercamps orclubs,andforcourseinstructors-includinguniversityprofessors-whoarelookingfora motivationalintroductiontoacomputersciencetopic.Itisdesignedforanyonewhowants tointroducepeopletokeyconceptsoftheinformationageofwhichtheyhavenoknowledge themselves. TopicsincludethePoorCartographer(graphcoloring),theMuddyCity(minimalspanning trees),TreasureHunt(finite-statemachines),thePeruvianCoinFlip(cryptographicprotocols), MagicCardFlips(errorcorrectingcodes),theChocolateFactory(human-computerinterac- tion),andmanymore. Sounplugyourcomputer,andgetreadytolearnwhatcomputerscienceisreallyabout!From"ComputerScienceUnplugged"
cBell,Witten,andFellows,1998Pagei
Pageii
Acknowledgments
Manychildrenandteachershavehelpedustore®neourideas.Thechildrenandteachersat SouthParkSchool(Victoria,BC),ShirleyPrimarySchool,andIlamPrimarySchool(Christchurch, NewZealand)wereguineapigsformanyactivities.WeareparticularlygratefultoLindaPic- ciotto,KarenAble,BryonPorteous,PaulCathro,TracyHarrold,SimoneTanoa,LorraineWood- ®eld,andLynnAtkinsonforwelcomingusintotheirclassroomsandmakinghelpfulsugges- tionsforre®nementstotheactivities.GwendaBensemannhastrialedseveraloftheactivities forusandsuggestedmodi®cations.RichardLyndersandSumantMurugeshhavehelpedwith classroomtrials.PartsofthecryptographyactivitiesweredevelopedbyKenNoblitz.Some oftheactivitieswererunundertheumbrellaoftheVictoria"Mathmania"group,withhelp fromKathyBeveridge.ThedelightfulillustrationsweredonebyMalcolmRobinsonandGail Williams,andhavealsobene®tedfromadvicefromHansKnutson.MattPowellhasprovided valuableassistancewiththe"Unplugged"project. SpecialthanksgotoPaulandRuthEllenHoward,whotestedmanyoftheactivitiesand providedanumberofhelpfulsuggestions.PeterHenderson,JoanMitchell,NancyWalker- Mitchell,JaneMcKenzie,GwenStark,TonySmith,TimA.H.Bell1,MikeHallett,andHaroldThimblebyalsoprovidednumeroushelpfulcomments.
Weoweahugedebttoourfamilies:Judith,Pam,andRobertafortheirsupport,andAndrew, Anna,Hannah,Max,Michael,andNikkiwhoinspiredmuchofthiswork,2andwereoftenthe®rstchildrentotestanactivity.
Wewelcomecommentsandsuggestionsabouttheactivities.Detailsaboutcontactingthe authorsaregivenonpage227intheconclusion.1Norelationtothe®rstauthor.
2Infact,thetextcompressionactivitywasinventedbyMichael.
From"ComputerScienceUnplugged"
cBell,Witten,andFellows,1998Pageiii
Pageiv
Contents
Introduction1
IData:therawmaterial-Representinginformation7
1Countthedots-Binarynumbers11
2Colorbynumbers-Imagerepresentation19
3Youcansaythatagain!-Textcompression27
4Cardflipmagic-Errordetectionandcorrection33
5Twentyguesses-Informationtheory41
IIPuttingcomputerstowork-Algorithms49
6Battleships-Searchingalgorithms55
7Lightestandheaviest-Sortingalgorithms73
8Beattheclock-Sortingnetworks83
9Themuddycity-Minimalspanningtrees91
10Theorangegame-Routinganddeadlockinnetworks97
IIITellingcomputerswhattodo-Representingprocedures10311Treasurehunt-Finite-stateautomata107
12Marchingorders-Programminglanguages119
From"ComputerScienceUnplugged"
cBell,Witten,andFellows,1998Pagev
IVReallyhardproblemsÐIntractability125
13ThepoorcartographerÐGraphcoloring129
14TouristtownÐDominatingsets143
15IceroadsÐSteinertrees151
VSharingsecretsandfightingcrimeÐCryptography16316SharingsecretsÐInformationhidingprotocols169
17ThePeruviancoinflipÐCryptographicprotocols173
18KidkryptoÐPublic-keyencryption185
VIThehumanfaceofcomputingÐInteractingwithcomputers19519ThechocolatefactoryÐHumaninterfacedesign199
20ConversationswithcomputersÐTheTuringtest213
Conclusion227
Bibliography229
References229
Index231
Pagevi
Introduction
Computersareeverywhere.Thoughyoumaynotrealizeit,it'sunlikelythatyou'llgetthrough thedaywithoutusingone.Evenifyoudon'thaveoneathome,andyoudon'tuseabank,and youavoidthecheckoutatthesupermarketÐandthecornerstoreÐyou'llprobablyendupusing acomputerdisguisedasaVCR,microwave,orvideogame.Whenyougraduatefromschool, itwillbehardto®ndacareerthatdoesn'tinvolvecomputers.Theyseemtobetakingover! Withcomputersaroundeverycorner,itmakessenseto®ndouthowtheywork,whattheycan doÐandwhattheycan'tdo.Theactivitiesinthisbookwillgiveyouadeeperunderstandingof whatcomputersareabout. Thereasonthisbookisªunpluggedºisthatweareconcernedaboutpresentingtheideas andissuesofcomputerscience,andtheseareofteneasiertoexplainwithpaperandcrayons, ordinarymaterials,andsimpleactivities.Webelieveyouwillbesurprisedanddelighted,as weare,withhowmuchentertainmentcanbehadwithsimplethingsanimatedbytheideas importantinunderstandingcomputers.RatherthantalkingaboutchipsanddisksandROMand RAM,wewanttoconveyafeelingfortherealbuildingblocksofcomputerscience:howto representinformationinacomputer,howtomakecomputersdothingswithinformation,how tomakethemworkef®cientlyandreliably,howtomakethemsothatpeoplecanusethem. Pressingsocialissuesareraisedbycomputingtechnology,likehowinformationcanbekept privateandwhethercomputerswilleverbeasintelligentasus.Thereareperformanceissues: computersaremind-bogglinglyfast,yetpeoplearealwayscomplainingthattheircomputeris tooslow.Andtherearehumanissues:whydopeoplegetsofrustratedusingcomputers?Are computersgettingoutofcontrol?Behindtheseissueslieimportanttechnicalfactors,andthe activitiesinthisbookwillhelpyouunderstandwhattheyare. Wehaveselectedawiderangeoftopicsfromthe®eldofcomputerscience,andpackaged themsothattheycanbelearnedwithoutusingacomputer.Theywillgiveyouagoodideaof whatcomputerscanandcan'tdo,whattheymightbeabletodointhefuture,andsomeofthe problemsandopportunitiesthatcomputerscientistsfacenow. Butthemainreasonthatwewrotethisbookisbecausecomputerscienceisfun.Youdon't believeus?Ðreadon!Thesubjectisburstingwithfascinatingideasjustwaitingtobeexplored, andwewanttosharethemwithpeoplewhomightnotbetunedintocomputers,butwouldbe interestedintheideasincomputerscience.Theseactivitieswillcertainlygiveyousomething tothinkabout.From"ComputerScienceUnplugged"
cBell,Witten,andFellows,1998Page1
INTRODUCTION
Theactivitiesandhowtousethem
Theactivitiesaredividedintosixtopics:data(representinginformation),puttingcomputersto work(algorithms),tellingcomputerswhattodo(representingprocedures),reallyhardprob- lems(intractability),sharingsecretsand®ghtingcrime(cryptography),andthehumanfaceof computing(interactingwithcomputers).Theseareasarerepresentativeofthekindsofthings thatcomputerscientistsstudy,althoughthelistisfarfromexhaustive.Eachtopichasabrief introductionexplainingwhereit®tsintothewiderpicture,followedbyseveralactivities. Alltheactivitiesbeginwithasummaryofmaterialsneeded.Anagegroupisgiven,butit ismerelyindicativeÐtheworkcanbeadaptedforanyonewhohasthebasicskills,andagreat dealdependsonthechildren'sbackground.Thereisnomaximumage.Althoughnearlyallthe activitiesaredesignedforelementaryschoolchildren,manyhavebeenusedwitholderchildren, andeventointroducetopicstouniversitystudents.Atimeisindicatedforeachactivity:this alsoisveryapproximate.Theactivitiesgenerallytakeabout30to40minutestocomplete, althoughtheycanbeadaptedtosuitthetimeavailable.Somecanserveasextendedprojects, andmostcanbecutdowntoa®ve-minutedemonstrationÐperhapsasanillustrationinalecture orseminar.Weindicatewhetherthereisaminimumormaximumnumberofpeoplerequired foranactivity.Althoughtheactivitiesaredescribedforaclassroomsituation,youwill®ndthat mostcanbeundertakenindividuallyorwiththehelpofasecondpersonsuchasaparentor friend. Eachactivitydescriptionhasthesamestructure.Theybeginwithafocussection,which listssomeofthekeyskillsthataredevelopedbytheactivity,andasummarysection,which providessomebackgroundtotheactivity.Thereisalistoftechnicaltermsthatmightseemlike jargon,butwillbeusefulifyouwanttopursuethetopicintotheprimaryscienti®cliterature. Thematerialspartgivesachecklistofwhatisrequiredtoundertaketheactivitywithaclass. Thenexttwosectionstakeyouthroughtheactivity.Whattodoisastep-by-stepexpla- nationofhowtopresentittochildren.Thestepsaretheresultofexperimentingwithseveral approaches,butyoushouldfeelfreetoadaptthemtosuityourgroup.Variationsandextensions suggestalternativewaystopresenttheactivity,andideasforextendingit. What'sitallabout?isintendedto®lltheteacherinonthewidersigni®canceoftheactivity. OlderchildrenmightappreciatehearingaboutsomeofthisÐyoumightevenhavethemreadthe sectionthemselves.Youngerchildrenmaynotbeabletocomprehendthebiggerpicture,andit isoftenbesttoletthemenjoytheactivityinitsownright,perhapswithasimpli®edaccountof itssigni®cance.Thissectionisalsointendedforparents.Somewillbecurious,andotherswill wanttotalkabouttheactivitieswiththeirchildathome.Itmayalsoproveusefulforjustifying theactivitiestoparentsorsupervisorswhoarenotconvincedoftheirvalue. Furtherreadingprovidesreferencestobooksandpapersonthetopic.Manyoftherefer- encesarefairlytechnical,butwehavetriedtoincludeoneswrittenforlaypeoplewherepossible. Ageneralreferencethatprovidesanaccessibleintroductiontomanyofthetopicsintheactiv- itiesisDavidHarel'sbookAlgorithmics:TheSpiritofComputing,whichwaspublishedina slightlylesstechnicalformasTheScienceofComputing.Completebibliographicinformation aboutallmaterialmentionedappearsattheendofthebook. Manyoftheactivitiesdeservearewardforgoodwork.Wehavemadethepictureonpage6 intoastamp,whichwedispensefreelyonworksheetsandthebacksofhandsinreturnfor Page2INTRODUCTION
agoodeffort.Anyrubberstampshopwillbeabletomakeoneforyoufromacopyofthe picture.Anotherreasonforusingthisparticularstampisthatitremindschildrenthatthework isaboutcomputers,whichisimportantbecausethereisnotmuchmentionofcomputersduring theactivities.Fortheteacher
Don'tbeputofffromusingtheseactivitiesjustbecauseyoufeelyoudon'tknowmuchabout computers.Despitethetechnicalnatureofthetopics,thisbookisintendedspeci®callyfor teacherswhohavenobackgroundincomputerscience.We®ndthatsuchpeopleoftenenjoy theactivitiesasmuchasthechildren.Theactivitiesaredesignedtoprovideopportunitiesfor teachersandstudentstolearntogetherabouttheprinciplesofcomputerscience.Toassistyou, everyactivityhasasectionthatexplainsitsbackgroundinnon-technicalterms.Answerstoall theproblemsareprovidedsothatyoucancon®rmthatyouhavethingsright. Mostoftheactivitiescanbeusedtosupplementamathematicsprogram,butsome(particu- larlyActivity19abouthumaninterfacedesignandActivity20aboutarti®cialintelligence)are alsoappropriateforsocialprograms.Thefocussectionidenti®esskillsthatthechildrenwill exercise,rangingfromrepresentingnumbersinbasetwotocoloring,fromlogicalreasoningto interviewing.Topicsandskillscanbelocatedusingtheindexatthebackofthebook.Ifyouaren'texperiencedwithworkinginaclassroom...
Theseactivitiescanbeusedbycomputingprofessionalswhowouldliketocommunicatecom- puterscienceideastochildrenorothergeneralaudiences.Theyareidealforthoseoccasions whenyouareaskedtopresentsomethingaboutyourprofession,butrealizethatthecomputers thatyouworkwithareprobablynotnearlyasimpressiveasthevideogamesthatthechildren useeveryday. Ifyouaregoingtousetheseactivitiesinaclassroomsituation,particularlywithyounger children,gettingsomehelpfromateacheraboutkeepingorderintheclassroomcanmakethe timemoreproductive,andavoidfrustration.Therearesomefairlysafetechniquesthatwill workingeneral(suchasªI'llchoosesomeonesittingquietlywiththeirhandupº),althoughthe bestmethodvariesfromclasstoclass.Someteachershaverewardsystemsthatyoucanuse, oryoucanbringyourownrewardsÐsuchasstickers,orthestamponpage6.Theremaybea signalthattheteacherusestoindicatethateveryonemustbequiet.Thissortofinformationcan beveryvaluable! Forsomewhatexploratoryandopen-endedactivitiessuchasthese,itisnaturaltoexpecta rangeofresponsesfromindividualstudents.Oneeffectivestrategyistoemploythosestudents whorapidlyunderstandwhat'sgoingontoexplainthingstootherswhoarehavingmoredif®- culty.YoungerstudentsmaybecomequiteanimatedÐmoresothantheuniversitystudentsto whomyoumightbeaccustomed!Thegoalistodosomethinginterestingandtohavefun;a certainamountofchaosisnotnecessarilyabadthing. Don'tforgettocheckthelistofmaterialsrequired:it'seasytoforgetanimportantpiece ofequipment.Oftenthematerialswillbeavailablefromtheschool(suchasbalancescales, Page3INTRODUCTION
crayons,andchalk).Ifyouarenotinvolvedintheteachingprofession,youmaynotrealizethat theprobabilityofaphotocopierbreakingdownisparticularlyhighinthe®veminutesbeforea classforwhichyouneedasetofhandouts. Manyoftheactivitiesinvolvesolvingproblems.Inmostcases,theintentionisnottoexplain howtosolvetheproblem,buttoallowthechildrentounderstanditand®ndtheirownmethodof solution.Knowinganalgorithmthatsolvesaproblemhaslittleintrinsicvalue,buttheprocess ofdiscoveringanalgorithm(evenifitisnotthebestone)canbeveryinstructive.Insomecases thereisnogoodalgorithm;rather,theintentionisforthechildrentolearnabouttheinherent complexityoftheproblem.Sometimestherewillbeanopportunitytoexplaintothechildren howaparticularproblemappliestotherealworld,butoftenitwillsuf®ceforchildrentoseethe eleganceofasolution,orappreciatethatsomeproblemsdon'thaveeasysolutions. Aboveall,thereisnosubstituteforenthusiasmandbeingwellprepared.Childrenappreciate bothoftheseandrespondaccordingly.Andifyouarefromoutsidetheclassyouhavethe advantagethatthechildrenmaybemoreattentivebecauseyouareofferingabreakfromthe dailyroutine.Forthetechnically-minded
Aswellasprovidingatasteofcomputerscienceforchildren,wehaveincludedsomematerial forthosewhowouldliketodelvealittledeeperintothesubject.Likethisone,thesesections aremarkedªforthetechnically-minded.º Oneofourgoalsistocommunicatewhatcomputerscienceisreallyabout.Computersci- enceisarichsubjectconcernedwithwhatcomputerscanandcannotdo,howtoapproachprob- lems,andhowtomakecomputersmorevaluabletotheirusers.Verylittlecomputerscienceis taughtinelementaryandhighschool.Moststudentswilldosomesortofªcomputingºwork, butusuallyitisabouthowtousecomputersratherthanhowtodesignthemforotherpeopleto use.Acommonmisconceptionisthatcomputerscienceisaboutprogramming.Programming isafundamentaltool,butitisnottheendinitself.Computerscienceisaboutprogramming inthesamewaythatastronomyisabouttelescopesÐjustaslearningastronomyneednotin- volveunderstandinghowatelescopeisbuilt,learningaboutcomputersciencedoesnotneedto involveprogramming.Infact,muchofcomputersciencewouldexistevenifcomputersdidn't (althoughitwouldprobablyhaveadifferentname!)Noneoftheactivitiesinthisbookrequire acomputer,buttheprinciplesthattheyteacharewidelyusedinmoderncomputers. FewyoungstersÐorevenadultsÐareawareofwhatcomputersreallycanandcan'tdo.For example,manyreal-lifeoptimizationproblems,suchastime-tablingteachersandclasses,or ®ndingtheshortestroutetomakedeliveries,taketoolongtosolveoptimallyoncomputersÐ regardlessofhowfastthecomputeris.Thereareevenproblems,suchassolvingsomeequations (knownasDiophantineequations),thatwecanprovewillneverbesolvedbyacomputer.There arelotsofthingsthatcomputerscan'tdo. Manythingsthatcomputerscandoarealsonotwidelyknown.Forexample,manypeople usedebitcardstopayforgoods,wheremoneyistransferreddirectlyfromtheirbankaccount tothestore's.However,intheprocessthebank®ndsoutwherethepurchaseisbeingmade, andcouldbuildupapro®leoftheperson'sshoppinghabits.Despitethislossofprivacy,debit Page4INTRODUCTION
cardsarewidelyaccepted.Mostpeopleareunawarethatcryptographicprotocolsexistwhich enablethetransactiontobecarriedoutreliablywithoutthebankbeingabletoidentifywhothe moneyisgoingto!ThisseemsincredibleÐliterallyunbelievableÐtopeoplewhohavenever encounteredpublickeycryptosystemsandinformationhidingprotocols.Ifmorepeopleknow aboutsuchthings,theremaywellbeanoutcryforsystemsthatprotectprivacybetter.(Activ- ity16oninformationhidingprotocolsdemonstratesasituationwhereitispossibletoexchange informationwithoutlosinganyprivacy).Understandingthetechnicalissuesinvolvedgoesa longwaytomakinginformeddecisionsonprivacyissues,justasanunderstandingofbiology goesalongwaytomakinginformeddecisionsonenvironmentalissues. Wehopethatthisbookwilltakesomeofthescience®ctionoutofpeople'sunderstandingof computers.Theupcominggenerationofcomputerusersdeservesaclearviewofthetechnical issuesthatunderpinthemyriadofcomputerizedsystemsthatpermeateourlives. To®ndoutmoreabouttheªUnpluggedºproject,visitthewebsiteat http://unplugged.canterbury.ac.nz/. Page5 Instructions:Havethispicturemadeintoarubberstamp(abouthalfthissize)anduseitasarewardforgoodwork.From"ComputerScienceUnplugged"
cBell,Witten,andFellows,1998Page6
PartIData:therawmaterialÐRepresenting
informationFrom"ComputerScienceUnplugged"
cBell,Witten,andFellows,1998Page7
Dataistherawmaterialthatcomputersworkon.Peopleusedtothinkofcomputersasgiant electroniccalculators.Butnowadaysit'sbettertothinkofacomputerasacrossbetweenan electronic®lingcabinet,alibrary,andaTV.Calculatorsworkwithnumbers.Butcomputers workwithdataofanykind:baseballlore,sportsfacts,letters,mailinglists,accounts,pay- rolls,advertisements,magazines,books,encyclopedias,music,movielistingsÐevenmovies themselves.Calculatorsdoarithmeticonnumbers.Computerscandothattoo.Butmoreim- portantly,theycanmanipulateallsortsofdata,lookingforhigh-scoringplayers,predictingthe outcomeofbaseballgames,helpingtowriteletters,addressenvelopes,balanceaccounts,print checks,distributeadvertisements,layoutmagazinepages,®ndinformationinbooksandency- clopedias,playmusic,lookthroughmovielistingsÐtheycanevenshowmovies.Whatisreally amazingisthatallofthiswiderangeoffacts,documentsandimagesarestoredonamachine that,atthelowestlevel,onlyworkswithtwothings:zeroandone! Inthispartofthebookwelookathowdifferentkindsofinformationcanberepresented byacomputer.Internally,allcomputersstoredatainanelectronicformthatisbasedonavery simpleidea:thateverythingcanbecodedasasequenceofthedigitszeroandone.You,theuser, donotnormallyseethesethingsbecausethedataispresentedinahuman-readableformÐwho wantstoseeabunchofnumbersinsteadofamovie?Buttounderstandwhatcomputersdo,you needtoknowwhatitisthattheyworkwith,andhownumbers,letters,words,andpicturescan beconvertedintozerosandones.Forteachers
Representinginformationisabsolutelyfundamentaltocomputing.Althoughthediffer- enceishardtopindownprecisely,data,whichdictionariesde®neasªnumericalinforma- tioninaformsuitableforprocessingbycomputer,ºissubtlydifferentfrominformation, orªknowledgederivedfromstudy,experience,orinstruction.ºWerefertothestuffthatis storedandmanipulatedbycomputersasdata,andthereal-worldentitiesthataresorep- resentedasinformation.Thusdataistherawmaterialofcomputing,whileinformation istherawmaterialofcomputerapplications.3Informationisconvertedintodataforthe computer,anddataispresentedasinformationtotheuser. The®veactivitiesinthissectionprovideabroadintroductiontoinformationrepresenta- tion.The®rstisaboutbinarynumbers,disguisedasagamethatevenveryyoungchildren enjoyplaying.Thesecond,akindofªpaintbynumbersºactivity,showshowpictures canberepresentedasnumbers,andembodiesconventionsusedinfaxmachinesfortrans- mittingimagesoverphonelines.Thenexttwoactivitiesareaboutwaysofrepresenting informationthatareef®cientandreliable.Dataoftenconsumesvastquantitiesofcom- puterdiskspaceÐthisisparticularlytrueofmulti-mediamaterialcontainingsoundand images.Computeruserswilltestifythattheyneverseemtohavequiteenoughdiskspace, andsocomputerscientistsareconcernednotjustwithhowtostoredata,buthowtostore itef®ciently.Activity3showshowordinarytextcanberepresentedasnumbersinan ef®cientway.Thenextactivityisaboutmaintainingtheintegrityofthedata.Themedia3Weusedatainthesingular,becauseitusuallyseemslikealargeÐoftenformidablylargeÐentityinitself,rather
thanacollectionofindividualªdatums.º Page9 onwhichdataisstored(andtransmitted)issusceptibletotheoccasionalerror,anditis importantthattheeffectoferrorsisnegligible.Disguisedasamagictrick,weintroduce awidely-usedtechniquetodetectandcorrectminorerrorsincomputerdata.The®nal activityinthissectionisabouthowinformationcanbequanti®ed.Becausetheideaof informationissocentraltocomputerscience,awholetheoryhasbeendevelopedthat enablesustoquantifyinformationand®ndlimitsonhowef®cientlyitcanbestoredand transmitted. Takentogether,theseactivitieswillhelpchildrenunderstandhowdifferentkindsofinfor- mationcanbestoredonacomputer,withouttakingupmorespacethannecessary,andin awaythatdecreasesthechanceoflossofdataduetodefectsinthestoragemedium.They willalsolearnabouthowtomeasuretheinformationcontentofdata.Theactivitiescan beperformedinanyorder,thoughitishelpfulifActivity1isdone®rst.The®rstthree aresuitableforchildreninearlyelementaryschool,whileforthelasttwothechildren needtobeatthemiddleelementarylevel.However,thesearelowerbounds:evenquite advancedchildrenenjoytheseactivitiesandlearnfromthem,asdoadults.Forthetechnically-minded
Manycomputerprofessionalswillbesurprisedatthecontentoftheseactivities.Pro- gressingfrombinarynumbers,throughpicturerepresentation,totextcompression,error control,andfoundationsofinformationtheory,constitutesaratherunusualintroduction tocomputerscience.Indeed,manystudentsofthesubjectareunfamiliarwithsomeof theseideas. No-onewoulddisagreethatinformationrepresentationisbasictocomputing.Butthe traditionalfareofintegers,floating-pointnumbers,andcharacterstringsconveysanim- poverishedandpedestrianviewofinformation.Picturesandtextarewhatuserssee,and inthissensetheyarethefundamentaldatatypesincomputingtoday.Insteadofwork- ingtowardstructureddataÐsuchaslists,trees,andobjecthierarchiesÐthewaymany computingtechnologyandprogrammingcoursesdo,wepursueauser-orientedtrack.Ef- ®cientstorageofinformation,anditsintegrity,arethemajorissuesofconcern.Afeeling forhowinformationisquanti®edunderpinsourunderstandingofwhatitisthatcomputers workwith.Thesetopicsprovideaviewofcomputingthatyoungchildrencanrelateto, andtheylendthemselvesnaturallytosimplebutintriguingactivities.Page10
Activity1
CountthedotsÐBinarynumbers
AgegroupEarlyelementaryandup.
AbilitiesassumedCountingupto15or31,matching,sequencing.Time10to40minutes.
SizeofgroupFromindividualstothewholeclass.
FocusRepresentingnumbersinbasetwo.
Patternsandrelationshipsinpowersoftwo.
Summary
Alldatainamoderndigitalcomputerisultimatelystoredandtransmittedasaseriesof zerosandones.Thisactivitydemonstrateshownumbersandtextcanberepresentedusing justthesetwosymbols.Technicalterms
Binarynumberrepresentation;binarytodecimalconversion;bitsandbytes;character sets.From"ComputerScienceUnplugged"
cBell,Witten,andFellows,1998Page11
ACTIVITY1.COUNTTHEDOTSÐBINARYNUMBERS
Figure1.1:Initiallayoutofthebinarycards
Figure1.2:Flippingthecardstoshow®vedots
Materials
Eachchildwillneed:
onesetof®vecardsfromtheblacklinemasteronpage17(theblacklinemasterhastwo sets), acopyoftheblacklinemasteronpage18,and apenorpencil.Whattodo
1.Seatthechildrenwheretheycanseeyou,andgiveeachchildasetofcards.
2.Thechildrenshouldlaytheircardsout,asinFigure1.1,withthe16-dotcardtotheirleft.
Somechildrenwillbetemptedtoputthecardsintheoppositeorder,soyoushouldcheck thattheyareindescendingnumericorderfromlefttoright.Foryoungerchildren,donot usethe16-dotcard.Page12
ACTIVITY1.COUNTTHEDOTSÐBINARYNUMBERS
Figure1.3:Solutiontotheworksheetonpage18
3.Havethechildrenworkoutwhichcardstoflipoversothatexactly®vedotsareshowing.
Theonly(correct)waytodothisistohavethe4-dotand1-dotcardsfaceup,andtherest facedown(Figure1.2).Eachcardmustbeeitherfaceuporfacedown,withallornoneof itsdotsshowing.Bepreparedforsomenovelwaysofgetting®vedotsÐitisnotunusual forchildrentoproducetherequisitenumberbyusingsparecardstocoverupthreeofthe dotsontheeightcard!4.Nowgetthechildrentoshowothernumbersofdots,sothattheyexplorewhichnumbers
canberepresented. Askfornumberssuchasthree(requirescards2and1),twelve(8and4),nineteen(16,2 and1)andsoon.Forthosewho®ndthecombinationforanumberquickly,askifthey can®ndanotherwaytogetthenumber(thereisonlyonewaytodisplayeachnumber, andtheyarelikelytodiscoverthiseventually). Discusswhatthebiggestnumberisthatcanbemadewiththecards(itis31for®vecards,15forfourcards).Thesmallest?(Oftenthenumberonewillbeoffered®rst,butthe
correctansweriszero.)Isthereanynumberbetweenthesmallestandlargestthatcan'tbe represented?(NoÐallnumberscanberepresented,andeachhasauniquerepresentation.)5.Forolderchildren,askthemtodisplaythenumbers1,2,3,4,...insequence,andseeif
theycanworkoutaprocedureforincrementingthenumberofdotsdisplayedonthecards byone(thenumberofdotsincreasesbyoneifyouflipallcardsfromrighttoleftuntil youturnonefaceup).Page13
ACTIVITY1.COUNTTHEDOTSÐBINARYNUMBERS
6.Thispartoftheactivityuseszerosandonestorepresentwhetheracardisfaceupornot.
Tellthechildrenthatwewillusea0toshowthatacardishidden,anda1ifitsfaceis showing.Forexample,thepatterninFigure1.2isrepresentedby00101.Givethemsome othernumberstoworkout(e.g.10101represents21,11111represents31).Withsome practicethechildrenwillbeabletoconvertinbothdirections.Youcouldaskchildrento taketurnscallingoutthedayofthemonththattheywerebornonusingzerosandones, andhavetherestoftheclassinterpretthedate. Thisrepresentationiscalledthebinarysystem,alsoknownasbasetwo.7.Usetheworksheetonpage18toextendtheexercise.(Acompletedworksheetisshown
inFigure1.3.) Theworksheetusesalightbulbthatisswitchedontorepresentacardthatisshowing, andalightbulbthatisofftorepresentahiddencard.The®rstfewpatternsshouldbe easytoworkout.Forexample,the®rstpatternhasthe8and1cardsshowing,sothe valuerepresentedis8+1=9.Forthepatternswithfewerthan®velightbulbs,the childrenshoulduseonlythesmallervaluedcards.Forexample,thesecondpatternhas onlythreelightbulbs,whichcorrespond(fromlefttoright)tothe4-,2-,and1-dotcards respectively.Seeifthechildrencanworkthisoutforthemselves. Thesix-bulbquestionsaredesignedtomakethechildrenthinkabouthowmanydots shouldbeonasixthcard.Thenumberofdotsoneachcardisdoublethenumberonthe previousone,sothesequenceis1,2,4,8,16,32,64....Thusa32-dotcardwouldbe added(attheleft)tosolveaproblemthatneedssixcards. Thecodeatthebottomoftheworksheetusesthenumbers1to26torepresenttheletters ofthealphabet.(Azerocanbeusedtorepresentaspace.)Thechildrenmustworkout whateachnumberinthecodeis,andlookupthecorrespondingletterinthetable.This showshowatextualmessagecanbeconvertedtoaseriesofzerosandones.Thechildren canthenwritecodedmessagesforeachother.Variationsandextensions
Insteadofusingcardswithdots,theexercisecanbedonewiththelengthsofrods(asetofrods oflengths1,2,4,8and16unitscanbeusedtocreateanylengthfrom0to31)orwithweights (asetofweightsof1,2,4,8and16unitscanbecombinedtoproduceanyweightfrom0to31). Insteadofcallingoutsequenceslike01101,tryusingbeepsÐcalloutahigh-pitchedbeepfor aoneandalow-pitchedoneforazero.Thisactivityisnoisyintheclassroom,butchildren®nd itmemorable!Modemsandfaxmachinesusetoneslikethistotransmitinformation,although thetonesaresentsoquicklythattheyblendtomakeacontinuousscreechingsound.Ifthe childrenaren'tfamiliarwiththis,theycouldtrycallingafaxmachinenumbertohearwhatit soundslike. Anyobjectsthathavetwostatescanbeusedtorepresentnumbers.Figure1.4showssome differentwaysofrepresentingthenumbernine(01001).Aparticularlychallengingmethodis touseyour®ngers.Ifa®ngerisupitrepresentsaone;downrepresentszero.CountingonyourPage14
ACTIVITY1.COUNTTHEDOTSÐBINARYNUMBERS
Figure1.4:Someunusualwaysofrepresentingthenumbernine(01001inbinary) ®ngersusingthebinarysystemenablesyoutogoupto31ononehand,and1023ontwohands. Itrequiressomedexterity,andyouhavetowatchoutforrudegesturesalongtheway!Forareal challenge,tryusingyourtoesaswellÐthiswillallowyoutocountuptomorethanamillion. (Howmanyexactly?Twohandsgive1024possibilities,0through1023.Handsandtoesgive10241024=1;048;576possibilities,0through1,048,575.)
Olderchildrenwillenjoyextendingthesequence1,2,4,8,16,32...Thesequencecontains aninterestingrelationship:ifyouaddthenumbersfromthebeginningfromlefttoright,thesum willalwaysbeonelessthanthenextnumberinthesequence. Anotherpropertyofbinarynumbersisthatyoucandoublethenumberbyinsertingazero ontheright-handsideofanumber.Forexample,1001(9)doubledis10010(18).Olderchildren shouldbeabletoexplainwhythishappens.(Alloftheplacescontainingaonearenowworth twicetheirpreviousvalue,andsothetotalnumberdoubles.Thesameeffectoccursinbaseten, whereinsertingazeroontherightofanumbermultipliesitbyten.) Binarynumbersarecloselyrelatedtotheguessinggameinwhichonepersonthinksofa numberandsomeoneelsetriestoguessitbyaskingquestionsoftheformªisitgreaterthanor equaltox?ºForexample,supposethenumberisknowntobelessthan32.Asensible®rst questionwouldbeªisitlessthan16?ºTheyes/noanswerstothequestionsaregivenbythe zero/onebitsinthebinaryrepresentationofthenumber.ThisisexploredindetailinActivity5. The®ve-bitcodeusedforlettersdoesnotallowbothupper-andlower-caseletterstobe represented.Youcouldhavethechildrenworkouthowmanydifferentcharactersacomputer hastorepresent(includingdigits,punctuation,andspecialsymbolssuchas$),andconsequently howmanybitsareneededtostoreacharacter.(Withtwolotsof26letters,10digits,andafew punctuationmarks,thereareboundtobemorethan64codesneeded,soatleastsevenbits arenecessary.Sevenbitsallowsfor128characters,andthisismorethansuf®cient.)Most currentcomputersusearepresentationcalledASCII(AmericanStandardCodeforInformation Interchange),whichisbasedonusingsevenbitspercharacter.Longercodesthatallowforthe languagesofnon-Englishspeakingcountriesarenowbecomingcommon.Page15
ACTIVITY1.COUNTTHEDOTSÐBINARYNUMBERS
What'sitallabout?
Moderndigitalcomputersalmostexclusivelyusethesystemdescribedabovetorepresentin- formation.Thesystemiscalledbinarybecauseonlytwodifferentdigitsareused.Itisalso knownasbasetwo(asopposedtobaseten,whichhumansnormallyuse).Eachzeroorone iscalledaªbitº,thetermbeingacontractionofbinarydigit.Abitisusuallyrepresentedina computer'smainmemorybyatransistorthatisswitchedonoroff,oracapacitorthatischarged ordischarged.Onmagneticdisks(¯oppydisksandharddisks),bitsarerepresentedbythedi- rectionofamagnetic®eldonacoatedsurface,eitherNorth-SouthorSouth-North.CD-ROMs storebitsopticallyÐthepartofthesurfacecorrespondingtoabiteitherdoesordoesnotre¯ect light.Whendatamustbetransmittedoveratelephonelineorradiolink,theonesandzerosare commonlyrepresentedbyhigh-andlow-pitchedtones. Onebitonitsowncan'trepresentmuch,sotheyareusuallygroupedtogetherasinthe exerciseabove.Itisverycommontostorebitsingroupsofeight,whichcanrepresentnumbers from0to255.Agroupofeightbitsiscalledabyte. Aswellasrepresentingnumbers,thiscodecanalsorepresentthecharactersinaword- processordocument.AbyteisoftenusedtorepresentasinglecharacterinatextÐthenumbers0 to255aremorethanenoughtoencodealltheupper-andlower-caseletters,digits,punctuation, andmanyothersymbols. Torepresentlargernumbers,severalbytesaregroupedtogether.Twobytes(16bits)can represent65,536differentvalues,andfourbytescanrepresentover4billionvalues.Thespeed ofacomputerisaffectedbythenumberofbitsitcanprocessatonce.Forexample,a32- bitcomputercanperformarithmeticandmanipulationson32-bitnumbers,whereasa16-bit computermustbreaklargenumbersinto16-bitquantities,makingitslower. Normallywedon'tseethebitsandbytesinacomputerdirectlybecausetheyareautomati- callyconvertedtocharactersandnumberswhentheyaredisplayed,butultimatelybitsandbytes areallthatacomputerusestostorenumbers,text,andallotherinformation.Furtherreading
Mostintroductorycomputingtextsdiscussthebinarynumbersystem.MyfriendArnold'sbook ofPersonalComputersbyGarethPowellhasawholechapteronbinarynumbers.Page16
Instructions:Copythispageontocard,andcutouttheboxestomaketwosetsoffivecards.From"ComputerScienceUnplugged"
cBell,Witten,andFellows,1998Page17
Instructions:Workoutthenumbersrepresentedbythelightbulbsatthetopofthepage.Also,thereisamessagecodedinbinaryatthebottomofthepage;workoutthenumbersandlookthemupinthetabletogetthemessage.
From"ComputerScienceUnplugged"
cBell,Witten,andFellows,1998Page18
Activity2
ColorbynumbersÐImage
representationAgegroupEarlyelementaryandup.
AbilitiesassumedElementarycounting,andsomeconcentration.Activ- ity1(CounttheDots)ishelpful,butnotessential, preparation.Experiencewithgraphingisalsouseful.Time20minutesormore.
SizeofgroupFromindividualstothewholeclass.
FocusRepresentation.
Coloring.
Pictures.
Summary
Computersareoftenusedtostoredrawings,photographsandotherpictures.Thisactivity showshowpicturescanberepresentedef®cientlyasnumbersinacomputer.Technicalterms
Rasterimages;pixels;imagecompression;run-lengthcoding;facsimilemachines.From"ComputerScienceUnplugged"
cBell,Witten,andFellows,1998Page19
ACTIVITY2.COLORBYNUMBERSÐIMAGEREPRESENTATION
Figure2.1:Theletterªaºfromacomputerscreen,andamagni®edviewshowingthepixelsthat makeuptheimage.Materials
Eachchildwillneed:
acopyoftheblacklinemasteronpage25,and apencilanderaser.Youwillneed:
anoverheadprojectortransparencyofFigure2.1(ordrawitontheclassroomboard).Whattodo
1.Discusswhatfacsimile(fax)machinesdo(arrangingforthechildrentosendand/orre-
ceivefaxeswouldbeexcellentpreparationforthisactivity).Askforotherplaceswhere computersstorepictures(forexample,adrawingprogram,agamewithgraphicsinit,or amulti-mediasystem). Explainthatcomputerscanreallyonlystorenumbers(iftheyhavedonetheactivityon binarynumbersthentheywillalreadyhavesomeappreciationofthis).Havethechildren suggesthowapicturemightberepresentedusingonlynumbers.2.Demonstratehowimagesaredisplayedonacomputerscreen,asfollows:
Computerscreensaredividedupintoagridofsmalldotscalledpixels.Thewordpixel isacontractionofªpictureelement.ºOnablackandwhitescreen,eachpixeliseither blackorwhite.Figure2.1showsapictureofaletterªaºthathasbeenmagni®edsothat thedotsarevisible.(Thisimageshouldbeshownonanoverheadprojector,ordrawnon theboard.)Whenacomputerstoresapicture,allthatitneedstostoreiswhichdotsare blackandwhicharewhite.3.UsingtheimageofFigure2.1,demonstratehowpicturescanberepresentedbynumbers
ontheblackboard,asfollows: Beginbywritingdownthenumberofconsecutivewhitepixelsinthe®rstlineofthe image(inFigure2.1thereisonlyonewhitepixelatthestartofthe®rstline).ThenwritePage20
ACTIVITY2.COLORBYNUMBERSÐIMAGEREPRESENTATION
Figure2.2:TheimageofFigure2.1codedusingnumbers
downthenumberofconsecutiveblackpixels(three),andsoonuntilthewholelinehas beencoded.Thusthe®rstlineofFigure2.1willberepresentedas1,3,1.Eachrow ofpixelsintheimageistranscribedusingthismethod.Forexample,thesecondlineof Figure2.1isrepresentedby4,1,sinceithasfourwhitepixelsfollowedbyoneblackone. Figure2.2showsthe®nalrepresentationofFigure2.1.Noticethatlinesbeginningwith ablackpixelhaveazeroatthebeginningtoindicatethattherearenowhitepixelsatthe startoftheline. Theremaybesomeconfusionwiththisdemonstrationifyouuseachalkboard,because coloringinapixelmakesitwhiteratherthanblack!4.Havethechildrenªdecodeºthepicturesontheworksheetonpage25.
Handouttheworksheetsandgetthechildrentodeciphertheimagesthere(seeFigure2.3 forthecompletedimages;Figure2.4containsareducedversionwhichmakesthepictures clearer).Theªtestºpictureontherightistheeasiest,andtheªbeingºontheleftisthe mostcomplex.1Thesquaresonthegridshouldbecoloredincompletely,andmadeas darkaspossible.Ifthesquaresontheblacklinemasteraretoosmall,youcanusequad- ruledpaper.Itisimportanttousepencil,asmistakesareeasilymade!Childrenshould markeachlineofnumbersasthey®nishwithit.Somemayprefertocircleallthenumbers thatrepresentblackpixelstohelpthemkeeptrackofwheretheyareuptoÐitisveryeasy togetconfusedaboutwhichnumbersareforblackandwhichareforwhite. Notethateachlinealwaysbeginswiththenumberofwhitepixels.Ifthe®rstpixelis black,thelinewillbeginwithazero.Variationsandextensions
Theimagewillbeclearerifthechildrendrawonasheetoftracingpaperontopofthegrid,so thatthe®nalimagecanbeviewedwithoutthegrid. Insteadofcoloringinthegridtheclasscouldusesquaresofstickypaperonalargergrid,or placeanyobjectsonagrid.Thecodescouldevenbeusedforacross-stitchpattern.1Theimagesaretakenfromtheexcellentchildren'sdrawingprogramKidPix,byBrøderbundSoftware.
Page21
ACTIVITY2.COLORBYNUMBERSÐIMAGEREPRESENTATION
Figure2.3:Thecompletedimages
Figure2.4:Thecompletedimagesreduced
Page22
ACTIVITY2.COLORBYNUMBERSÐIMAGEREPRESENTATION
Childrencantrydrawingtheirownpicturesonagrid(ortrytocopyonefromacomputer screen).Theycancodethepictureasnumbersandgiveittofriendstodecipher. Inpracticethereisusuallyalimittothemaximumlengthofarunofpixelsbecausethe lengthisbeingrepresentedasabinarynumber.Askthechildrenhowtheywouldrepresenta runoftwelveblackpixelsiftheycouldonlyusenumbersuptoseven.(Agoodwayistocodea runofsevenblackpixels,followedbyarunofzerowhite,thenarunof®veblack.) Themethodcanbeextendedtocoloredimagesbyusinganumbertorepresentthecolor (e.g.0isblack,1isred,2isgreenetc.)Twonumbersarenowusedtorepresentarunofpixels: the®rstgivesthelengthoftherunasbefore,andthesecondspeci®esthecolor.What'sitallabout?
Thesimplestwaytorepresentablackandwhitepictureonacomputeristorepresentwhite pixelswithazero(say)andblackwithaone.However,itiscommonforimagestocontain largeblocksofwhitepixels(especiallyinthemargins)andrunsofblackpixels(e.g.ahorizontal line).Facsimiledocumentscommonlyhaveabout100pixelsperinch,soarowofwhitepixels atthetopofa7inchwidepagecouldtake700bitsofstorage. Theªrun-lengthcodingºthatweusedintheactivityaboveismuchmoreef®cient.Itrep- resentstherun-lengthof700usingthebinarysystem(seeActivity1),whichcanbedonein10 bits.Thisexampleisalittleextreme,butneverthelesssigni®cantsavingscanbemade. Savingspaceusingtechniqueslikethisiscalledcompression,anditiscrucialtotheviability ofworkingwithimagesoncomputers.Forexample,faximagesaregenerallycompressedto aboutaseventhoftheiroriginalsize.Withoutcompressiontheywouldtakeseventimesaslong totransmit,whichwouldmakefaxamuchlessattractivemeansofcommunication.Images storedoncomputerdisksareoftencompressedtoatenthorevenahundredthoftheiroriginal size.Withoutcompressiontheremightberoomforjustahandfulofimagesonthedisk,but withcompressionmanymoreimagescanbestored.Theadvantageisevengreaterwhenstoring movingpictures,whichnormallyinvolve25ormoreimageseachsecond.Thecompression methodusedinthisactivityisrelatedtothemethodusedonmostcommonfaxmachines.A hostofothermethodsarealsoavailable.TheonesthatgivethebestcompressionareªlossyºÐ theychangetheimageveryslightlysothatitcanbestoredmuchmoreef®ciently. Isthereadown-side?Ðcanªcompressingºanimageeverexpandit?Well,yes.Achecker- boardimageinwhichpixelsalternateblackandwhitewouldbemuchmoreef®cienttostore usingonebitforeachpixelthanusingonenumberforeachpixel,becauseitwillbenecessary torepresentthenumberasseveralbitstoallowforthepossibilityoflongerruns.Although thisparticularcaseisunlikely,somerealimagesÐsuchashalftoneimages,likeillustrations innewspapers,thataremadeupoflotsoftinydotsÐdonotcompresswellandmayevenex- pand.Itissometimesnecessarytotailortherepresentationmethodtothekindofimagebeing represented.Page23
ACTIVITY2.COLORBYNUMBERSÐIMAGEREPRESENTATION
Furtherreading
RepresentingimagesoncomputersisdiscussedindepthbyNetravaliandHaskellinDigital pictures:representationandcompression.Thestandardmethodforcodingonfaxmachinesis describedbyHunterandRobinsoninapaperpublishedin1978entitledªInternationaldigital facsimilecodingstandards.ºAmorerecentstandardforcodingimagesisdescribedinthebook JPEG:StillImageDataCompressionStandardbyPennebakerandMitchell.Page24
Instructions:Usethenumberstocolorinthesquares.Thereisarowofnumbersforeachlineinthepicture.Forexample,theline4,9,2,1meanstoleave4squaresempty,colorin9,leave2empty,andcolorinthenextone.
From"ComputerScienceUnplugged"
cBell,Witten,andFellows,1998Page25
ACTIVITY2.COLORBYNUMBERSÐIMAGEREPRESENTATION
Page26
Activity3
Youcansaythatagain!ÐText
compressionAgegroupEarlyelementaryandup.
AbilitiesassumedCopyingwrittentext.
Time10minutesormore.
SizeofgroupFromindividualstothewholeclass.
FocusWriting.
Copying.
Repetitioninwrittentext.
Summary
Despitethemassivecapacityofmoderncomputerstoragedevices,thereisstillaneedfor systemstostoredataasef®cientlyaspossible.Bycodingdatabeforeitisstored,and decodingitwhenitisretrieved,thestoragecapacityofacomputercanbeincreasedat theexpenseofslightlysloweraccesstime.Thisactivityshowshowtextcanbecodedto reducethespaceneededtostoreit.From"ComputerScienceUnplugged"
cBell,Witten,andFellows,1998Page27
ACTIVITY3.YOUCANSAYTHATAGAIN!ÐTEXTCOMPRESSION
Technicalterms
Textcompression;Ziv-Lempelcoding.
Materials
Eachchildwillneed:
acopyoftheblacklinemasteronpage32.Youwillalsoneed:
acopyofotherpoemsortextforthechildrentoencode.Whattodo
1.Giveeachchildacopyoftheblacklinemasteronpage32,andhavethemªdecodeºthe
messageby®llinginemptyboxeswiththecontentsoftheboxthattheirarrowpointsto. Forexample,the®rstemptyboxshouldcontainthelettere.The®rstemptyboxonthe secondlinereferstothephrasePeaseporridgeonthe®rstline.Thecompletedworksheet isshowninFigure3.1.2.Nowhavethechildrenwritetheirownrepresentationofsometextusingboxesandarrows.
Thegoalistohaveasfewoftheoriginalcharactersleftaspossible.Thearrowsshould alwayspointtoanearlierpartofthetexttoensurethatitcanbedecodediftheboxes are®lledinfromtoptobottom,lefttoright.Thechildrencaneitherchoosetheirown text,makesomeup,orencodesomethathasbeenprovided.Manynurseryrhymesand poemsforchildrencanbecodedparticularlyeffectivelybecausetheytendtohavealot ofrepetition,atleastintherhymingparts1.BookssuchasDr.Seuss'sªGreeneggsand hamºalsoprovideagoodsourceofcompressibletext.Variationsandextensions
Thearrow-and-boxcoderequiresthatarrowsalwayspointtoanearlierpieceoftext,although itisonlythe®rstletterpointedtothatneedstobeearlier.Forexample,Figure3.2showsa codedversionofthewordªBanana.ºEventhoughthemissingtextpointstopartofitself,it canbedecodedcorrectlyprovidedthelettersarecopiedfromlefttorightÐeachletterbecomes availableforcopyingbeforeitisneeded.Thiskindofself-referentialrepresentationisusefulif thereisalongrunofaparticularcharacterorpattern. Oncomputerstheboxesandarrowsarerepresentedbynumbers.Forexample,thecodein Figure3.2mightberepresentedasªBan(2,3)º,wherethe2meanscountbacktwocharacters1AgoodrhymeisªAdillar,adollar/ateno'clockscholar/whatmakesyoucomesosoon/youusedtocomeat
teno'clock/andnowyoucomeatnoon.ºPage28
ACTIVITY3.YOUCANSAYTHATAGAIN!ÐTEXTCOMPRESSION
Figure3.1:Thecompletedworksheet
Figure3.2:Aself-referentialcode
Page29
ACTIVITY3.YOUCANSAYTHATAGAIN!ÐTEXTCOMPRESSION
to®ndthestartingpointforcopying,andthe3meanscopythreeconsecutivecharacters.On acomputerthepairofnumberstypicallytakeupasimilaramountofspacetotwoletters,so matchesofonlyonecharacterarenotnormallyencoded.Childrencouldtryencodingand decodingtextsusingthenumberrepresentation. Togetafeelforhowthistechniquewouldworkonrealtext,childrencouldbegivena photocopiedpagecontainingaquantityoftext,andstartingabouthalf-waydownthepage, crossoutanytextthatcouldbereplacedbyapointertoanearlieroccurrence.Theearlier occurrencesshouldonlybegroupsoftwoormoreletters,sincethereisnosavingifasingle letterissubstitutedwithtwonumbers.Thegoalistogetasmanyletterscrossedoutaspossible.What'sitallabout?
ThestoragecapacityofcomputersisgrowingatanunbelievablerateÐinthelast25years,the amountofstorageprovidedonatypicalcomputerhasgrownaboutamillionfoldÐbutinstead ofsatisfyingdemand,thegrowthisfuelingit.Theabilityofcomputerstostorewholebooks suggeststhepossibilityofstoringlibrariesofbooksoncomputer;beingabletoshowahigh qualityimageonacomputersuggestsdisplayingmovies;andtheavailabilityofhighcapacity CD-ROMsimpli®esthedistributionofdataandprogramsthathadpreviouslybeenlimitedby thesizeofa¯oppydisk.Anyonewhoownsacomputerwillhaveexperiencedthevariationof Parkinson'slawthatstatesthatthedataalwaysexpandsto®llthestorageavailableforit. Analternativetobuyingmorestoragespaceistocompressthedataonhand.Thisactivity illustratesthecompressionprocess:therepresentationofthedataischangedsothatittakesup lessspace.Theprocessofcompressinganddecompressingthedataisnormallydoneautomati- callybythecomputer,andtheuserneednotevenbeawarethatitisbeingdoneexceptthatthey mightnoticethatthediskholdsmore,andthatittakesalittlemoretimetoget®lesfromthe disk.Essentiallysomecomputingtimeisbeingtradedforstoragespace.Sometimesthesystem canevenbefasterusingcompressionbecausethereislesstoreadfromthedisk,andthismore thancompensatesforthesmallamountoftimeneededtodecompressthematerial. Manymethodsofcompressionhavebeeninvented.Theprincipleofpointingtoearlier occurrencesofchunksoftextisapopulartechnique,oftenreferredtoasªZiv-Lempelcoding,º orLZcoding,aftertwoIsraeliprofessorswhopublishedseveralimportantpapersinthe1970s and1980saboutthiskindofcompression.Itisveryeffectivebecauseitadaptstowhatever sortofdataisbeingcodedÐitisjustassuitableforSpanish,orevenJapanesewhichusesa completelydifferentalphabet,asitisforEnglish.Itevenadaptstothesubjectofthetext,since anywordthatisusedmorethanoncecanbecodedwithapointer.LZcodingwilltypicallyhalve thesizeofthedatabeingcompressed.Itisusedinpopulararchivingprogramswithnameslike ZipandARC,andinªdiskdoublingºsystems.Itisalsousedinhigh-speedmodems,whichare devicesthatallowyoutointeractwithcomputersoverordinarytelephonelines.Hereitreduces theamountofdatathatneedstobetransmittedoverthephoneline,noticeablyincreasingthe apparentspeedoftransmission. Anotherclassofcompressionmethodsisbasedontheideathatfrequentlyoccuringletters shouldhaveshortercodesthanrareones(Morsecodeusesthisidea.)Someofthebestmethods (whichtendtobeslower)usetheideathatyoucanhaveagoodguessatwhatthenextletterwillPage30
ACTIVITY3.YOUCANSAYTHATAGAIN!ÐTEXTCOMPRESSION
beifyouknowthelastfewletters.WewillencounterthisprincipleinActivity5.Furtherreading
AcomprehensiveintroductiontocompressionmethodscanbefoundinthebooksTextcom- pressionbyBell,ClearyandWitten,andManagingGigabytes:Compressingandindexingdoc- umentsandimagesbyWitten,MoffatandBellÐalthoughtheseareaimedatuniversity-level computersciencestudentsratherthanlaypeople.Ifyouareinterestedincomputerprogram- ming,youwillenjoyMarkNelson'sThedatacompressionbook,whichisapractically-oriented guidetothesubject.Dewdney'sTuringOmnibusdiscussesatechniquecalledªHuffmancod- ingºinasectionabouttextcompression.Page31
Instructions:Fillineachblankboxbyfollowingthearrowattachedtotheboxandcopyingthelettersintheboxthatitpointsto.