01_introduction_problems

Module:Introduction(Week2outof5)Course:AlgorithmicToolbox(Course1outof6)Specialization:DataStructuresandAlgorithmsProgrammingAssignment1:IntroductionRevision:September10,2016IntroductionWelcometoyourfirstprogrammingassignmentoftheAlgorithmicToolboxclass!Itconsistsofsevenalgorithmicproblems.Thefirstthreeproblemsrequireyoujusttoimplementcarefullythealgorithmscoveredinthelectures.Theremainingfourproblemswillrequireyoutofirstdesignanalgorithmandthentoimplementit.Foralltheproblems,weprovidestartersolutionsinC++,Java,andPython3.Thesesolutionsimplementstraightforwardnaivealgorithmsthatusuallyworkonlyforsmallinputs.Toverifythis,youmaywanttosubmitthesesolutionstothegrader.Thiswillusuallygiveyoua“timelimitexceeded”messageforPythonstarterfilesandeither“timelimitexceeded”or“wronganswer”messageforC++andJavasolutions(thereasonforwronganswerbeinganintegeroverflowissue).Yourgoalistoreplaceanaivealgorithmwithanefficientone.Inparticular,youmaywanttousethenaiveimplementationforstresstestingyourefficientimplementation.Inthisprogrammingassignment,thegraderwillshowyoutheinputdataifyoursolutionfailsonanyofthetests.Thisisdonetohelpyoutogetusedtothealgorithmicproblemsingeneralandgetsomeexperiencedebuggingyourprogramswhileknowingexactlyonwhichteststheyfail.However,forallthefollowingprogrammingassignments,thegraderwillshowtheinputdataonlyincaseyoursolutionfailsononeofthefirstfewtests(pleasereviewthequestions9.4and9.5intheFAQsectionforamoredetailedexplanationofthisbehaviorofthegrader).1LearningOutcomesUponcompletingthisprogrammingassignmentyouwillbeableto:1.Seethehugedifferencebetweenaslowalgorithmandafastone.2.Playwithexampleswhereknowingsomethinginterestingaboutaproblemhelpstodesignanalgorithmthatismuchfasterthananaiveone.3.Implementsolutionsthatworkmuchmorefasterthanstraightforwardsolutionsforthefollowingcom-putationalproblems:(a)computeasmallFibonaccinumber;(b)computethelastdigitofalargeFibonaccinumber;(c)computeahugeFibonaccinumbermodulo𝑚;(d)computethelastdigitofasumofFibonaccinumbers;(e)computethelastdigitofapartialsumofFibonaccinumbers;(f)computethegreatestcommondivisoroftwointegers;(g)computetheleastcommonmultipleoftwointegers.4.Implementthealgorithmscoveredinthelectures,designnewalgorithms.5.Practiceimplementing,testing,anddebuggingyoursolution.Inparticular,youwillfindouthowinpractice,whenyouimplementanalgorithm,youbumpintounexpectedquestionsandproblemsnotcoveredbythegeneraldescriptionofthealgorithm.Youwillalsocheckyourunderstandingofthealgorithmitselfandmostprobablyseethattherearesomeaspectsyoudidnotthinkofbeforeyouhadtoactuallyimplementit.Youwillovercomeallthosecomplexities,implementthealgorithms,testthem,debug,andsubmittothesystem.Remembertheadvice(link)wegaveyouinthefirstmoduleabouttestingyourprogramsandfeelfreetoreturntothosevideosorpartsofthemagainwhileworkingonyourassignment.Intheendofthisdocumentyouwillfindalsogeneralrecommendationsonsolvingalgorithmicproblems.PassingCriteria:3outof7Passingthisprogrammingassignmentrequirespassingatleast3outof7codeproblemsfromthisassignment.Inturn,passingacodeproblemrequiresimplementingasolutionthatpassesallthetestsforthisprobleminthegraderanddoessounderthetimeandmemorylimitsspecifiedintheproblemstatement.2Contents1Problem:SmallFibonacciNumber42Problem:LastDigitofaLargeFibonacciNumber63Problem:GreatestCommonDivisor84Problem:LeastCommonMultiple105AdvancedProblem:HugeFibonacciNumbermodulom126AdvancedProblem:SumofFibonacciNumbers147AdvancedProblem:PartialSumofFibonacciNumbers168GeneralInstructionsandRecommendationsonSolvingAlgorithmicProblems188.1ReadingtheProblemStatement..................................188.2DesigninganAlgorithm.......................................188.3ImplementingYourAlgorithm....................................188.4CompilingYourProgram......................................188.5TestingYourProgram........................................208.6SubmittingYourProgramtotheGradingSystem.........................208.7DebuggingandStressTestingYourProgram...........................209FrequentlyAskedQuestions219.1Isubmittheprogram,butnothinghappens.Why?........................219.2Isubmitthesolutiononlyforoneproblem,butalltheproblemsintheassignmentaregraded.Why?.................................................219.3Whatarethepossiblegradingoutcomes,andhowtoreadthem?................219.4Howtounderstandwhymyprogramfailsandtofixit?.....................229.5Whydoyouhidethetestonwhichmyprogramfails?......................229.6Mysolutiondoesnotpassthetests?MayIpostitintheforumandaskforahelp?.....239.7Myimplementationalwaysfailsinthegrader,thoughIalreadytestedandstresstesteditalot.Wouldnotitbebetterifyougivemeasolutiontothisproblemoratleastthetestcasesthatyouuse?Iwillthenbeabletofixmycodeandwilllearnhowtoavoidmakingmistakes.Otherwise,IdonotfeelthatIlearnanythingfromsolvingthisproblem.Iamjuststuck...2331Problem:SmallFibonacciNumberProblemIntroductionRecallthedefinitionofFibonaccisequence:𝐹0=0,𝐹1=1,and𝐹𝑖=𝐹𝑖−1+𝐹𝑖−2for𝑖≥2.Yourgoalinthisproblemistoimplementanefficientalgorithmforcomp