Undergraduate Topics in Computer Science Edwin F. Meyer III Nickolas Falkner · Raja Sooriamurthi Zbigniew Michalewicz Guide to Teaching Puzzle-based Learning Undergraduate Topics in Computer Science Undergraduate Topics in Computer Science (UTiCS) delivers high-quality instructional content for undergraduatesstudyinginallareasofcomputingandinformationscience.Fromcorefoundationaland theoreticalmaterialtofinal-yeartopicsandapplications,UTiCSbookstakeafresh,concise,andmodern approachandareidealforself-studyorforaone-ortwo-semestercourse.Thetextsareallauthoredby established experts in their fields, reviewed by an international advisory board, and contain numerous examplesandproblems.Manyincludefullyworkedsolutions. Forfurthervolumes: http://www.springer.com/series/7592 Edwin F. Meyer III (cid:129) Nickolas Falkner (cid:129) Raja Sooriamurthi (cid:129) Zbigniew Michalewicz Guide to Teaching Puzzle-based Learning EdwinF.MeyerIII NickolasFalkner BaldwinWallaceUniversity UniversityofAdelaide Berea,Ohio,USA SouthAustralia,Australia RajaSooriamurthi ZbigniewMichalewicz CarnegieMellonUniversity UniversityofAdelaide Pittsburgh,Pennsylvania,USA SouthAustralia,Australia SeriesEditor IanMackie AdvisoryBoard SamsonAbramsky,UniversityofOxford,Oxford,UK KarinBreitman,PontificalCatholicUniversityofRiodeJaneiro,RiodeJaneiro,Brazil ChrisHankin,ImperialCollegeLondon,London,UK DexterKozen,CornellUniversity,Ithaca,USA AndrewPitts,UniversityofCambridge,Cambridge,UK HanneRiisNielson,TechnicalUniversityofDenmark,KongensLyngby,Denmark StevenSkiena,StonyBrookUniversity,StonyBrook,USA IainStewart,UniversityofDurham,Durham,UK ISSN1863-7310 ISSN2197-1781(electronic) UndergraduateTopicsinComputerScience ISBN978-1-4471-6475-3 ISBN978-1-4471-6476-0(eBook) DOI10.1007/978-1-4471-6476-0 SpringerLondonHeidelbergNewYorkDordrecht LibraryofCongressControlNumber:2014941623 #Springer-VerlagLondon2014 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpart of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionor informationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodologynowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerpts inconnectionwithreviewsorscholarlyanalysisormaterialsuppliedspecificallyforthepurposeofbeing enteredandexecutedonacomputersystem,forexclusiveusebythepurchaserofthework.Duplication ofthispublicationorpartsthereofispermittedonlyundertheprovisionsoftheCopyrightLawofthe Publisher’s location, in its current version, and permission for use must always be obtained from Springer.PermissionsforusemaybeobtainedthroughRightsLinkattheCopyrightClearanceCenter. ViolationsareliabletoprosecutionundertherespectiveCopyrightLaw. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexempt fromtherelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) To my Parents: Both PhDs who raised six children, each of whom has earned a PhD. Thanks for continually holding us to such high standards. E. F. M. To my wife, Katrina, and my friend, Marita, bothofwhombelievedthattherewasmoreto me. N. F. To my sons, Anand and Santosh, who are each other’s puzzle and solution. R. S. To my friend, Paweł Kerntopf, who, during my high-school years, introduced me to the world of mathematical puzzles. Z. M. ThiSisaFMBlankPage Introduction to Teaching Puzzle-based Learning: What Is It and What Is This Book About? Nowmorethanever,aneducationthatemphasizesgeneral problemsolvingskillswillbeimportant.–BillGates Whatismissinginmostcurricula–fromelementaryschoolallthewaythroughto university education – is coursework focused on the development of problem- solving skills. Most students never learn how to think about solving problems. Usuallytheyarejusttrainedtoapplyparticularformulaetoaproblemandmostof theireffortisrelatedto“calculatingtheanswer.” Students are not prepared for framing and solving problemsthat are given ina descriptive form: they have serious difficulties in extracting relevant information, eliminatingnoise (that is always present indescriptive-type problems), building a model ofthe problem,andreasoning aboutthesolution.Further, throughouttheir education,theyareconstrained toconcentrateonspecific questionsatthe backof chapters. So,withoutmuchthinking,theyapplythematerialfromeachchaptertosolvea fewproblemsgivenattheendofeachchapter(whyelsewouldaproblembeatthe end of the chapter?). One of our favourite examples to illustrate this point is a puzzleonbreakingachocolatebar: Arectangularchocolatebarconsistsofm(cid:1)nsmallrectanglesandyouwishtobreakitinto itsconstituentparts.Ateachstep,youcanonlypickuponepieceandbreakitalonganyof itsverticalorhorizontallines.Howshouldyoubreakthechocolatebarusingtheminimum numberofsteps(breaks)? If you do not know the answer, which textbook would you search to discover the solution? Textbooks on optimization? Simulation? Strategies? Games? Other textbooks? Or it might be that someone wrote a book on chocolates where in Chapter 7 there is a full discussion on efficient breaking strategies of a chocolate bar?Veryunlikely.Thesameappliestosolvingmanyreal-worldproblems:which textbook should you search to find an approach that would lead to the solution? Some individuals (including the authors of this book), when interviewing job candidates, would ask them to solve problems during the interview. When a candidate responds, “I didn’t have that in school,” they would reply, “Yeah, I knowyoudidn’t;that’swhyI’maskingit.” vii viii IntroductiontoTeachingPuzzle-basedLearning:WhatIsItandWhatIsThisBookAbout? In the introduction of Heard on the Street, Quantitative Questions from Wall StreetJobInterviews,1theauthorwrites:“Thisbookbridgestheconsiderablegap between the typical education and the knowledge required to successfully answer job interview questions. The considerable gap arises because interviewers must separate the wolves from the sheep. The sheep are confined by the boundaries of their education. The wolves are not. Of course, most interviewers are wolves. Unfortunately, most interviewees are sheep. The ‘butchering’ that can take place intheseinterviewsishorrific.” Clearly, it is not surprising that most students are ill prepared for framing and addressing real-world problems. When they finally enter the real world, they sud- denly find that problems do not come with associated formulas, instructions, or textbooks. Although many educators are interested in teaching “thinking skills” rather than “teaching information and content,” the fact remains that young people often have serious difficulties in independent thinking (or problem-solving skills) regardless of the nature of a problem. As Alex Fisher wrote in his book, Critical Thinking2: “... though many teachers would claim to teach their students ‘how to think’, most would say that they do this indirectly or implicitly in the course of teachingthecontentwhichbelongstotheirspecialsubject.Increasingly,educators havecometodoubttheeffectivenessofteaching‘thinkingskills’inthisway,because most students simply do not pick up the thinking skills in question.” The curricular approach of emphasizing “remembering” over “reasoning” has dominated the edu- cationalarena–whetherinhistory,physics,geography,oranyothersubject–almost ensuringthatstudentsneverlearnhowtothinkaboutsolvingproblemsingeneral. Overthepastfewdecades,variouspeopleandorganizationshaveattemptedto addressthiseducationalgapbyteaching“thinkingskills”basedonsomestructure (e.g. critical thinking, constructive thinking, creative thinking, parallel thinking, verticalthinking,lateralthinking,confrontationalandadversarialthinking).How- ever, all these approaches are characterized by a departure from mathematics as theyconcentratemoreon“talkingaboutproblems”ratherthan“solvingproblems.” Itisourviewthatthelackofproblem-solvingskillsingeneralistheconsequenceof adecreasinglevelofmathematicalsophisticationinmodernsocieties. Itseems thatadifferentapproach isneeded.Manyindividualsandeducational organizationshaverecognizedthisneedsometimeago.Manyinstructorshavebeen introducing puzzles and various problem-solving activities in more or less formal way over the last twenty years. For example, in How to Solve It: Modern Heuristics3 the authors introduced a variety of puzzles to support a course on modernheuristicmethods.A.LevitinandM.Levitinhavebeenbasingtheircourses onpuzzles.4TimBellfromUniversityofCanterbury(NewZealand)incorporated 1CrackTF(2008)Heardonthestreet,quantitativequestionsfromWallStreetjobinterviews,11th edn.Typesetbytheauthor,USA. 2FisherA(2001)Criticalthinking:anintroduction.CambridgeUniversityPress,Cambridge. 3MichalewiczZ,FogelDB(2000)Howtosolveit:modernheuristics.Springer,Berlin/NewYork. 4LevitinA,LevitinM(2011)Algorithmicpuzzles.OxfordUniversityPress,Oxford/NewYork. IntroductiontoTeachingPuzzle-basedLearning:WhatIsItandWhatIsThisBookAbout? ix puzzlesintotheirComputerSciencecurriculum.HisCSUnplugged5isacollection offreelearningactivitiesthatteachComputerSciencethroughengaginggamesand puzzles.Puzzle-basedproblemsolvinghasbeenofferedasafor-creditcoursesince 2002attheBaldwinWallaceUniversity(Ohio,USA)–andnowtherearetwosuch problem-solving courses that Ed Meyer teaches in the graduate business program (not to mention his teaching of problem solving during the summer at Gedanken Institute for problem solving for many years now). His Naked Physics6 contains 64problems(fromphysicsandmathematics)todevelopstudents’problem-solving skills.AtCarnegieMellonUniversity,Puzzle-basedLearninghasbeenofferedasa very popular freshmen seminar since 2009. Abbreviated versions of this course have been offered to range of audiences from middle school, to high-school outreach programs, to graduate school, to managers and engineers in industry workshops,andtoretiredprofessionalsincontinuingeducationprograms. Clearly,manyindividualsallovertheworldexperimentedwithsuchapproaches over many years; however, the term Puzzle-based Learning emerged just a few yearsago.7Asitwasthecasewithallearlierattempts,itfocusesongettingstudents to think about framing and solving unstructured problems (those that are not encountered at the end of some textbook chapter). The idea is to increase the student’smathematical awareness andproblem-solvingskillsby solvingavariety ofpuzzlesandreflectingontheirsolutionprocesses. SowhatisPuzzle-basedLearning? Puzzle-based Learning is a foundational approach to develop thinking skills, mental stamina and perseverance at solving problems. We focus on unstructured, generallycontext-free(i.e.,doesnotrequiredomainknowledge)andalmostalways entertainingproblems,betterknownaspuzzles. Overtheyears,researchershavedevelopedsetsofrulesforsolvingpuzzlesand problemsanditislefttothereadertoidentifyonethatworksforhisorherteaching situation. However, there are a couple of places to start looking. Gyorgy Po´lya8 presentedfourfundamentalstepstoproblemsolving: 1. Understandingtheproblem(Recognizingwhatisaskedfor) 2. Devisingaplan(Respondingtowhatisaskedfor) 3. Carryingouttheplan(Developingtheresultoftheresponse) 4. Lookingback(Checkingwhatdoestheresulttellme) andalsoprovideda(large)listofdifferentproblemsolvingapproaches(heuristics) that would give the puzzler a starting point or a way to rearrange the problem to 5Seecsunplugged.org. 6MeyerEF(2011)Nakedphysics.GedankenPublishing. 7MichalewiczZ,MichalewiczM(2008)Puzzle-basedlearning:anintroductiontocriticalthink- ing,mathematics,andproblemsolving.HybridPublishers,Melbourne. 8GyorgyPo´lyawasborninBudapeston13December1887.FormostofhiscareerintheUnited States,hewasaprofessorofmathematicsatStanfordUniversity.Heworkedonagreatvarietyof mathematicaltopics,includingseries,numbertheory,combinatorics,andprobability.Inhislater days,GyorgyPo´lyaspentconsiderableeffortontryingtocharacterizethegeneralmethodsthat peopleusetosolveproblems,andtodescribehowproblemsolvingshouldbetaughtandlearned.