Transcription of COMPUTATIONAL AND ALGORITHMIC THINKING …
1 DAVID I CLARKCOMPUTATIONAL AND ALGORITHMIC THINKING 2011 2015 BOOK 2 Published byAustralian Mathematics TrustUniversity of Canberra Locked Bag 1 Canberra GPO ACT 2601 AUSTRALIAC opyright 2016 AMT PublishingTelephone: +61 2 6201 Limited ACN 083 950 341 National Library of Australia Card Number and ISSNA ustralian Mathematics Trust Informatics Series ISSN 1838-8086 COMPUTATIONAL and ALGORITHMIC THINKING 2011-2015 Book2 ISBN 978-1-876420-76-5 ContentsIntroductionvComputationalandAlg orithmicThinkingvAlgorithmicThinkingandt heAustralianCurriculumviAcknowledgmentsv iQuestions1 ApplyingRules3 Logic9 Analysis19 Searching19 Sorting19 Patterns21 NumberofRoutes23 HowManyWays?26 AnalysetheProblem31 Algorithms35 Breadth-firstSearch35 ShortestPath48 MaximumFlow51 SinglePassAlgorithms51 DynamicProgramming54 TwoPersonGames57 GreedyAlgorithm62 Lists64 WorkingBackwards66 Chains67 AdHocAlgorithms68iiiSolutions81 ApplyingRules83 Logic87 Analysis93 Searching93 Sorting94 Patterns96 NumberofRoutes98 HowManyWays?
2 101 AnalysetheProblem105 Algorithms109 Breadth-firstSearch109 ShortestPath121 MaximumFlow125 SinglePassAlgorithms126 DynamicProgramming128 TwoPersonGames132 GreedyAlgorithm139 Lists144 WorkingBackwards146 Chains148 AdHocAlgorithms150 DevelopmentofAlgorithms161 Statistics173 HighDistinctionStudents1752011 Competition1752012 Competition1762013 Competition1772014 Competition1792015 Competition181ivIntroductionComputationa landAlgorithmicThinkingTheComputationala ndAlgorithmicThinking(CAT)competition,fo rmerlyknownastheAustralianInformaticsCom petition(AIC),isapre-programmingcompetit iontakenannuallybymorethan7000schoolstud entsfromAustralia, (AIOC) ,itintroducesstudentsandtheirteacherstoa lgorithmicthinking,nowarequiredcomponent oftheAustralianCurriculum, ,itidentifiesstudentswiththecapacitytopr ogramandpointsthemtowardsresourcesthroug hwhichtheycanpursuethis, ,itisthefirstinaseriesofeventsthatidenti fystudentswhowillrepresentAustraliaatthe annualInternationalOlympiadinInformatics (IOI).
3 (TheterminformaticsisusedinEuropeasasyno nymforcomputerscience.)TheCAThastraditio nallybeenapenandpapercompetition, ,afurtherdivisionofthecompetitionwasintr oducedforUpperPrimarystudents(Years5and6 ).ThequestionsintheCATaredesignedtobequi cktosolveandhighlyapproachable, ,andincorporatesunique three-stagetasks :applyingtherulesquestions,thataskstuden tstoapplyawell-definedsetofrulestogivend atalogicquestions,thatusenon- ALGORITHMIC puzzlestoencouragerigorousreasoningandca seanalysisanalysisquestions,wherestudent sareaskedtounderstandthebehaviourofanalg o-rithmthatsolvesagivenproblemalgorithmq uestions, Solutions , (algorithmquestions)andsearchingalgorith ms(analysisquestions), Questions sectionofthebookpresentsthequestions, Solutions , , ,therearetwodistinctbutrelatedsubjects, ,thecontentofthissubjectwillpresentquite achallenge, ,thishasbeenthepreserveofasmallnumberofc oursesinthesenioryearsofthecurriculum,bu tthereisaworldwidedemandforgreatercoding skillsasapartofcoreeducation.
4 , , ,butratherasapedagogicalapproachtoproble msolvingingeneral, (AMT), ,theformationoftheAIOCin1999wasaninitiat iveofProfessorPeterTaylor, , , , :BenBurton,BernardBlackham,DavidClark,Da vidKennedy,AndrewGray,KatherineKavanagh, DavidAnanian-Cooper,DmitryKamenetsky,Rob ertNewey,ChristopherChen, ,TerryMcClelland, ,andofalloftheCATproblemsbeforetheygotop rint, , , ,thedominantcarnivore,thezab, (positive) :If7zabswerebornlastyearand5theyearbefor e, , (A)2009(B)2011(C)2013(D)2015(E) :?representsasingleletter*representsanyn umberofletters, , ,b* *ingmatch?blastingblusteringboastingboos tingbootstrappingbowstringsbristlingbust ing(A)2(B)4(C)5(D)6(E)73
