any 2 questions

any 2 questions


CCPS 209 Labs CCPS 209 Computer Science II Labs Ilkka Kokkarinen Chang School of Continuing Education Ryerson University Version of March 17, 2022
 DramatisPersonae Lab0(A):PlainOldIntegers 9 Lab0(B):Dublications 12 Lab0(C):ReverseVerse 14 Lab0(D):ListsOfIntegers 16 Lab0(E):AllIntegersGreatAndSmall 18 Lab0(F):TwoBranchingRecursions 20 Lab0(G):...OrWeShallAllCrashSeparately 23 Lab0(H):MoreIntegersGreatAndSmall 27 Lab0(I):SquaringOff 29 Lab0(J):SimilarMeasuresOfDissimilarity 31 Lab0(K):SufYixArrays 33 Lab0(L):ICan,ThereforeIMust 35 Lab0(M):TowerBlocks 36 Lab0(N):SubstringParts 37 Lab0(O):CharsToTheLeftOfMe,IntegersToTheRight... 40 Lab0(P):TwoPointers 42 Lab0(Q):AboutturnIsPlayfair 46 Lab0(R):FrogsOnABox 49 Lab0(S):HammingCenter 51 Lab0(T):CliqueMentality 54 Lab1:PolynomialI:Basics 57 Lab2:PolynomialII:Arithmetic 60 Lab3:PolynomialIII:Comparisons 61 Lab4:ExtendingAnExistingClass 63 Lab5:It'sAllInYourHead 64 Lab6:TextFilesI:WordCount 66 Lab7:TextFilesII:Tail 68 Lab8:ConcurrencyInAnimation 69 Lab9:LissajousCurves 72 Lab10:ComputationStreams 74 Lab11:AndYouWillFindMe,PrimeAfterPrime 75 Lab12:TheSecondHandUnwinds 77 Lab13:RecursiveMondrianArt 79 Lab14:H-TreeFractal 82 Lab15:ZeckendorfEncoding 85 Lab16:EgyptianFractions 87 Lab17:DiamondSequence 90 Lab18:WorkingScale 93 Lab19:SymbolicDistancesI:Representation 97 Lab20:SymbolicDistancesII:Arithmetic 101 Lab21:SymbolicDistancesIII:Comparisons 102 Lab22:TruchetTiles 104 Lab23:Ulam-WarburtonCrystals 106 Lab24:ChipsOnFire 110 Lab25:ManhattanSkyline 113 Lab26:FilterWriter 115 Lab27:StackingImages 117 Lab28:AllThePrettyHues 119 Lab29:InTimelyManner 122 Lab30:MarkAndRewind 125 Lab31:RegionQuadtrees 127 Lab32:TriplefreeSequences 130 Lab33:SardineArray 132 Lab34:PreferentialVoting 134 Lab35:MultipleWinnerElection 136 Lab36:RationalRoots 137 Lab37:BigTen-Four 139 Lab38:Euclid'sOrchard 141 Lab39:HotPotato 144 Lab40:SeamCarving 146 Lab41:GeometryI:Segments 149 Lab42:GeometryII:Polygons 153 Lab43:GeometryIII:PointsInPolygons 156 Lab44:GeometryIV:ConvexHull 160 Lab45:PermutationsI:AlgebraicOperations 164 Lab46:PermutationsII:Cycles 166 Lab47:PermutationsIII:LehmerCodes 169 Lab48:TheCurseOfTheClumpino 173 Lab49:NoBitsLost 176 Lab50:TheWeightOfPower 181 Lab51:Miller-RabinPrimalityTesting 186 Lab52:LinusSequence 192 Lab53:Tchoukaillon 194 Lab54:AllHailTheMightyXor 198 Lab55:AccumulatedWisdom 201 Lab56:Yind()MeAFind,catchMeACatch 205 Lab57:FloodFill 208 Lab58:BlockCellularAutomata 211 Lab59:HitomezashiGolygons 214 Lab60:BitDeque 216 Lab61:SaveTheDate 221 Lab62:WorleyNoise 226 Lab63:RecursiveSubdivisionOfImplicitShapes 231 Lab64:LearningTheRopesI:Composition 235 Lab65:LearningTheRopesII:Comparisons 239 Lab66:Slater-VélezSequence 241 Lab67:LemireDynamicFrequencySampling 243 Lab68:IntervalSetsI:DynamicSetOperations 246 Lab69:IntervalSetsII:Iteration 251 Lab70:CupTournamentSurvival 254 Lab71:TheGammaAndTheOmega 257 Lab72:LazyGenerationOfPermutations 260 Lab73:Newton-RaphsonFractals 263 Lab74:BetweenTheLines 266 Lab75:SquareCoral 269 Lab76:Sultan'sDaughter 271 Lab77:GeneralizedChaosGame 273 This document contains the lab speciYications for the course CCPS 209 Computer Science II, as compiled and taught over the years by Ilkka Kokkarinen for the Chang School of Continuing Education,Toronto,Canada.Itcurrentlyoffersaveritablebuffetof97problemspeci/icationsfor studentstofreelypicktheirbattlesfrom,withnewandexcitingproblemsaddedonasemi-regular basisastheauthorkeepscomingupwiththem.Theseproblemsvarygreatlyinthemesothatthey promisesomethingforeveryone,inspiritofTheLoveBoat.Studentswhohavepreviouslytakenthis author'scourseCCPS109ComputerScienceIinPythonshouldalsonotethatunlikeintheproblem setusedinthatcourse,theseproblemsarenotlistedintheirorderofdif/icultybutintheorder inwhichtheywerecreated.Havenofeartotakealookaroundalloverthisdocumenttoseewhich topicsinterestyouenoughtoraisetheurgetohitthekeyboard! TheseproblemsdrillinvariousaspectsoftheJavalanguageanditsstandardlibrary,andintroduce (althoughoccasionallybetweenthelines)manyclassicideas,concepts,techniquesandalgorithms thatwill surelycomehandy inyour futurecoding tasks inbothschoolandworking life.The Yirst half of these labs mostly contains problems about the straightforward application of basic data types such integers, arrays and lists, whereas the problems in the second half are inspired by discretemath,combinatoricsandcomputationalgeometry.Occasionallytheseproblemsevenreach outintomoreremoteareassuchasfractalart,gametheoryandpoliticalscience.(Thislasttopicis coveredseveralproblemsaboutimplementingandanalyzingvariousvotingsystems.) ToworkontheselabsusingIntelliJIDEA,startbycreatingyourselfnewprojectnamed“209Labs” inwhichallyoursourcecodefortheselabsshouldgo.Intothatproject,youwillthenmanuallycopy theautomatedJUnittestsfromtheinstructor'sGitHubrepositoryCCPS209Labs foreachlabthat youattempttosolve.Firstdownloadthisentirefoldersomewhereinyourcomputer,andwhenever you embark on a new lab problem, copy the corresponding JUnit test class in your labs project folder.Onceyouhave implementedall themethodsof the labsso that theycompile, IntelliJ IDEA will allow you to run either one test or all the tests for that particular lab, for you to determine whetheryourworkpassesthemuster. When IntelliJ IDEA initially complains about the import statements in the JUnit test class, you should correct theproblemonceand forallby clicking the red lightbulb symbol toopenadrop- downmenufromwhereyouaddJUnit4inyourclasspath.ThatisenoughforIDEAtoknowtouse JUnit 4 for all the tests in the same project. Note that these tests are written in JUnit 4 framework,insteadofJUnit5,sobesuretoaddthecorrectframeworkinyourclasspath! ThefuzzacceptancetestsintheJUnittestclasseswilltryoutyourmethodswithalargenumberof pseudorandomlygeneratedtestcases.Thesetestcasesareguaranteedtobeexactlythesamefor everyone working on the Java language and its standard libraries, regardless of the particular computer environment they currently happen to be working on. Each pseudorandom fuzz test computesachecksumfromtheresultsthatyourmethodreturnsforthetestcasesthatweregiven to it. Once this checksum equals the expected checksum computed and hardcoded into the test methodfromtheinstructor'sprivatemodelsolution,TheManfromDelMontesaysyesandgrants you thegreencheckmark tocelebrateyourbeating this levelwithaniceglassofpineapple juice. Your method is now correct and accepted as being black box equal to the instructor's private solution,withouthavingtohavethisprivatemodelsolutionavailableforcomparison. https://github.com/ikokkari/JavaExamples http://www.scs.ryerson.ca/~ikokkari/ https://continuing.ryerson.ca https://continuing.ryerson.ca https://github.com/ikokkari/PythonProblems https://www.jetbrains.com/idea/ https://github.com/ikokkari/CCPS209Labs https://www.youtube.com/watch?v=YqmpVWzH4FM Anydiscrepancy in the checksumreveals that yourmethod returnedadifferent answer than the instructor’sprivatesolutionforatleastforonetestcase.Unfortunately,suchpseudorandomfuzzing schememakesitimpossibletopinpointanyoneactualtestcaseforwhichyourmethodisfailing,or determine for how many test cases your method disagrees with the instructor’s private model solution.Toalleviatethismechanismthatmaysometimesfeelatadbitpassiveaggressive,theJUnit test classes also feature conventional tests with explicit test cases aimed to Ylush out the most commonbugsandedgecasesituationsthatseemtorepeatinstudentsolutions. To test your code, you should also usually write your own main method in your classes and hardcodeyourown test cases there. (No lawof eithernatureormanpreventsyour classes from havingadditionalutilitymethodsthanmerelythosethatourJUnittestsexplicitlytryout.) AlltheseJUnitfuzztestsaredesignedtoruntocompletionwithinacoupleofsecondsatmostper each green checkmark,when executed on amodern off-the-shelf desktop computer atmost Yive years old.None of these automated tests should ever requireminutes, let alone hours, to complete. Ifany JUnit testgets stuck thatway, thatmeansyourmethodsaredoingsomething algorithmicallyveryinef/icient,eitherintimeorinspace.Youshouldmercilesslyrootoutallsuch inefYicientdesignsfromyourmethod,andreplacethemwithbetteralgorithmsthatgettothesame endresultatleastanorderofmagnitudefaster! Inalltheselabs,silenceisgolden.Whenitcomestoyourmethodstalkingoutofschoolalloverthe textconsole,therulesforomertàareasstrictastheyareinthethornybadlandsofSicily.Sincethese JUnit testswillpummelyour codewitha largenumberofpseudo-randomlygenerated test cases harder than an old time detective giving a suspect the third degree under the hot lights, all requiredmethodsmustbeabsolutelysilentandprintabsolutelynothingontheconsoleduring theirexecution.AnylabsolutionthatprintsanythingatallontheconsoleduringitsJUnittest will be rejected and receive a zeromark. Make sure to comment out all your console output statementsyouusedfordebuggingbeforesubmittingyourproject. Onceyouhavecompletedallthelabsthatyouthinkyouaregoingtocompletebeforethedeadline, youwillandmustsubmitallyourcompletedlabsinoneswoopastheentire“209Labs”project folderthatcontainsallthesourceYilesalongwiththeprovidedJUnittestsandanynecessarytextor imagedataYiles,compressedintoazipYilethatyouthenuploadintotheassignmenttabonD2L.As there isnopartial credit given for these labs,pleasedonot includeanysolutions thatdonot passthetestswith/lyingcoloursintoyoursubmission.Tomakeiteasierforthe instructorto tally up your working labs, you shouldmake it clear in the projectREADME Yile howmany lab problemsyouareclaimingtohavesuccessfullysolved. Studentsshouldworkontosolvetheseproblemsindependently.Discussionofproblemsbetween studentsisacceptable,aslongasthisdiscussiontakesplacesolelyatthelevelofideasandnoactual solutioncodeispassedbetweenthestudents.ThisproblemcollectionalsohasanofYicialsubreddit r/ccps209tofacilitatesuchdiscussion.Notethatthissubredditisintendedonlyforthediscussion of theseproblems, andany coursemanagement issues shouldbehandledelsewhere through the appropriatechannels. http://www.linfo.org/rule_of_silence.html https://www.reddit.com/r/ccps209/ Lab 0(A): Plain Old Integers JUnit:P2J1Test.java The transition labsnumbered0(X) translateyourexistingPythonknowledge intoequivalent Java knowledgeall thewaybetweenyourbrainandyour Yingertips.Youmayalreadybe familiarwith someoftheseproblemsfromthisauthor'sothercourseCCPS109ComputerScienceI.Evenifyou are coming to this second course via some other route, these problems are self-contained and requirenospeciYicbackgroundknowledge.Each0(X) labconsistsofup to fourrequiredstatic methodsthatareeffectivelyfunctionsthatinvolvenoobjectorientedthinking,designorcoding. Insideyourfreshnewproject,createtheYirstclassthatmustbenamedexactlyP2J1.Ifyouname yourclassesandmethodsanythingother thanhowtheyarespeciYied in thisdocument, the JUnit testsusedtoautomaticallycheckandgradetheselabswillnotbeabletoevenYindyourmethods. Insidethenewclass,theYirstmethodtowriteis public static long fallingPower(int n, int k) Pythonhastheintegerexponentiationoperator**convenientlybuiltinthelanguage,whereasJava unfortunatelydoesnotofferthat.Exponentiationwouldbebasicallyuselessanywayinalanguage thatusesYixedsizeintegersthatsilentlyhidetheoverYlowsthattheintegerexponentiationwillbe producing in spades. (You should also note that in both Python and Java, the caret character^ denotesthebitwiseexclusiveoroperationthathasnothingtodowithintegerexponentiation.) Insteadofintegerexponentiation,yourtaskistoimplementtherelatedoperationoffallingpower that isuseful inmanycombinatorial formulas.Denotedsyntacticallybyunderliningtheexponent, each term that gets multiplied into the product is always one less than the previous term. For example,thefallingpower83iscomputedas8*7*6=336.Similarly,thefallingpower105equals 10*9*8*7*6=30240.Nothingessentialchangeshereevenforanegativebase;thefallingpower (-4)5 iscomputedwiththesameformulaas -4* -5* -6* -7* -8 = -6720.Analogoustoordinary exponentiation,n0=1foranyintegern. Thismethod should return the falling powernkwhere the basen can be any integer, positive or negative or zero, and the exponent k can be any nonnegative integer. The JUnit fuzz tests are designedsothatyourmethoddoesnothavetoworryaboutpotentialintegeroverYlow…provided thatyouperformyourarithmeticcalculationswiththelongkindof64-bitintegers!Ifyouusethe bare 32-bit int type anywhere, a silent integer over/low will make your method occasionally returnincorrectresultsandfailtheJUnittests,evenifthatmethodworkedcorrectlywhenyoutried itwithyourownsmallvaluesofnandk. public static int[] everyOther(int[] arr) Givenanintegerarrayarr,createandreturnanewarraythatcontainspreciselytheelementsin theeven-numberedpositionsinthearrayarr.Forexample,giventhearray{5, 2, 3, 10, 2}, thismethodwouldcreateandreturnanewarrayobject{5, 3, 2}thatcontainstheelementsin https://github.com/ikokkari/CCPS209Labs/blob/master/P2J1Test.java https://github.com/ikokkari/PythonProblems theeven-numberedpositions0,2and4of theoriginalarray.Makesure thatyourmethodworks correctlyforarraysofbothoddandevenlengths,andforemptyarraysandsingletonarrayswith justoneelement.The lengthof theresultarraythatyoureturnmustalsobeexactlyrightsothat therearenoextrazeroshangingaroundattheendofthearray. public static int[][] createZigZag(int rows, int cols, int start) Thismethodcreatesandreturnsanewtwo-dimensionalintegerarray,whichinJavaisreallyjusta one-dimensional arraywhose elements are one-dimensional arrays of typeint[]. The returned arraymusthavethecorrectnumberofrowsthateachhaveexactlycolscolumns.Thisarraymust containthenumbersstart,start+1,… ,start+(rows*cols-1) in itsrowsinsortedorder, exceptthattheelementsineachodd-numberedrowmustbelistedindescendingorder. For example,when calledwithrows=4,cols=5 andstart=4, thismethod should create and returnthetwo-dimensionalarraywhosecontentsshowupas 4 5 6 7 8 13 12 11 10 9 14 15 16 17 18 23 22 21 20 19 whendisplayed in the standardmatrix form that ismore readable than themore truthful form {{4,5,6,7,8},{13,12,11,10,9},{14,15,16,17,18},{23,22,21,20,19}},inrealitya one-dimensionalarraywhosefourelementsarethemselvesone-dimensionalarraysofintegersthat serveasrowsofthistwo-dimensionalarray.Inadditiontorectangulargridsofvalues,thisscheme canrepresentarbitraryraggedarrayswhoserowsdon'tneedtoallbeofthesamelength. public static int countInversions(int[] arr) Inside an arrayarr, an inversion is a pair of two positionsiarr[j]. In combinatorics,theinversioncountinsideanarrayisaroughmeasureofhowmuch“outoforder” thatarrayis.Ifanarrayissortedinascendingorder,ithaszeroinversions,whereasann-element array sorted in reverse order has n(n-1)/2 inversions, the largest number possible. (You will encounter inversions again in this course, if youwork through the labs 45 to 47 that deal with permutations and their operations.) This method should count the inversions inside the given arrayarr, and return that count.Asalwayswhenwritingmethods thatoperateonarrays,make sure that yourmethodworks correctly for arrays of any length, including the important special casesofzeroandone. Once you havewritten all fourmethods, add the above JUnit test class P2J1Test.java inside the same project. Unlike in Python with its more dynamic nature, the JUnit test class cannot be compileduntilyourclasscontainsallfourmethodsexactlyastheyarespeci/ied.Ifyouwant totestonemethodwithouthavingtoYirstwritealsotheotherthree,youmustimplementtheother threemethodsasdo-nothingmethodstubsthatonlycontainsomeplaceholderreturnstatement https://github.com/ikokkari/CCPS209Labs/blob/master/P2J1Test.java that returns zero or some other convenient do-nothing value. Even better way to handle this situationwouldbetohavethemethodconsistsoftheone-linerbody throw new UnsupportedOperationException(); that tells the caller in a controlled fashion that the method does not even pretend to achieve anythingatall,butgivesuprightaway.Ofcourseallsuchmethodstubswillimmediatelyfailtheir respective tests, as they properly should. However, their existence allows the JUnit test class to compile and run cleanly so that you can start testing each one method the moment you have properlyreplacedtheabovestatementinitsbodywiththeactualJavacodethatsolvesthespeciYied problem. IntelliJ IDEA conveniently allows you to run all tests for that problem, or just one individualtest,justbyclickingthegreenPlaybuttonnexttoeachindividualtestinitssourcecode. Lab 0(B): Dublications JUnit:P2J2Test.java CreateanewclassnamedP2J2insidetheverysameprojectasyouplacedyourP2J1classinthe previouslab.InsidethisnewclassP2J2,writethefollowingfourmethods. public static String removeDuplicates(String text) Given atext string, create and return a brand new string that is otherwise the same astext except thateveryrunofequalconsecutivecharactershasbeenturned intoasinglecharacter.For example, given the arguments "Kokkarinen" and "aaaabbxxxxaaxa", this method would return"Kokarinen" and"abxaxa",respectively.Onlyconsecutiveduplicateoccurrencesofthe samecharacterareeliminated,butthelateroccurrencesofthesamecharacterremainintheresult as long as therewas some other character between these occurrences. For the purposes of this problem,theupper-andlowercaseversionsofthesamecharacterareconsidereddifferent,sothat removingduplicatesfrom"AaabbBBBCc"shouldreturntheresult"AabBCc". public static String uniqueCharacters(String text) Create and return a new string that contains each character oftext only once regardless of its appearancecountthere,thesecharacterslistedinorderthattheyappearintheoriginalstring.For example, given the argument strings "Kokkarinen" and "aaaabbxxAxxaaxa", this method shouldreturn"Kokarine"and"abxA",respectively.Sameasinthepreviousproblem,theupper- andlowercaseversionsofthesamecharacteraretreatedasdifferentcharacters. Youcouldsolvethisproblemwithtwonestedloops,theouterloopiteratingthroughthepositions of the text, and the inner loop iterating through all previous positions to look for a previous occurrenceof thatcharacter.ButyoucanbemoreefYicientanduseaHashSet to rememberwhichcharactersyouhavealreadyseen,and let thatdatastructurehelpyoudecide in constanttimewhetherthenextcharacterisappendedintotheresult. public static int countSafeSquaresRooks(int n, boolean[][] rooks) Somenumberofchessrookshavebeenplacedonsomesquaresofageneralizedn-by-nchessboard. Thetwo-dimensionalarrayrooksofbooleantruthvaluestellsyouwhichsquarescontainarook. (This array is guaranteed tobe exactlyn-by-n in itsdimensions.)Thismethod should return the countofhowmany remaining squares are safe from the rollingwrathof these rampaging rooks, thatis,donotcontainanyrooksinthesameroworcolumn. Probably the best way to do this is to create and Yill in two one-dimensional boolean arrays safeRows andsafeCols withn elements each. These arrays keep track of which rows and columnsof the chessboard areunsafe. Initially all rows and columns are safe as far asweknow, sincebotharraysareinitiallyallfalse.However,togetcountoftheactualsituationinthegiven https://github.com/ikokkari/CCPS209Labs/blob/master/P2J2Test.java https://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html chessboard, loop through all the squares of the chessboard.Whenever you Yind a rook in some position(row,col),mark that entirerow andcol as beingunsafe in those respective arrays. After you have done this for all the squares throughout the entire chessboard, loop through the safeRows andsafeCols arraysseparatelytocounthowmanyrowsandcolumnsarestillsafe. ReturntheproductofthosetwonumbersasyourYinalanswer. public static int recaman(int n) Computeandreturnn:thtermintheRecamán'ssequence,startingthecountfromterma1=1.See thedeYinitionofthiscurioussequenceonthelinkedWolframMathworldpage,orreadmorefrom thepage “AsymptoticsofRecaman’s sequence”.Forexample,whencalledwithn=7, thismethod wouldreturn20,andwhencalledwithn=19,return62.(Morevaluesfordebuggingpurposesare listedatOEISsequenceA005132.) To make your function fast and efYicient even when computing the sequence element for large valuesofn,youshoulduseasufYicientlylargeboolean[]tokeeptrackofwhichintegervaluesare already part of the generated sequence, so that you can generate each element in constant time insteadof having to loop through the entire previously generated sequence like some "Shlemiel" tiring himself by running back and forth across the same positions. The size 10*n should be enough, and yet this scheme uses roughly ten bits of heapmemory for each number generated. (Storing theencounterednumbers intosomeHashSet instance insteadwouldburn upmemoryatleastanorderofmagnitudeharder.) http://mathworld.wolfram.com/RecamansSequence.html https://11011110.github.io/blog/2019/12/20/asymptotics-recamans-sequence.html http://oeis.org/A005132 http://wiki.c2.com/?ShlemielThePainter Lab 0(C): Reverse Verse JUnit:P2J3Test.java One lastbatchof transitionalproblemsadapted fromthe instructor'scollectionofPythongraded labs. Only three methods to write this time, though. The JUnit test for these labs uses the warandpeace.txttextYileassourceofdata,sopleaseensurethatthistextYilehasbeenproperly copiedintoyourcourselabsprojectfolder. public static void reverseAscendingSubarrays(int[] items) Rearrangetheelementsofthegivenarrayofintegersinplace(thatis,donotcreateandreturna newarray)sothattheelementsofeverymaximalstrictlyascendingsubarrayarereversed.For example,giventhearray{5, 7, 10, 4, 2, 7, 8, 1, 3}(theprettycoloursindicatethe ascending subarrays and are not actually part of the argument), after executing thismethod, the elementsofthearraywouldbe{10, 7, 5, 4, 8, 7, 2, 3, 1}.Givenanotherargument array{5, 4, 3, 2, 1},thecontentsofthatarraywouldstayas{5, 4, 3, 2, 1}seeing thatitseachelementisamaximalascendingsubarrayoflengthone. public static String pancakeScramble(String text) ThisniftylittleproblemistakenfromtheexcellentWolframChallengesproblemsitewhereyoucan also see examples of what the result should be for various arguments. Given a text string, constructanewstringbyreversingitsYirsttwocharacters,thenreversingtheYirstthreecharacters ofthat,andsoon,untilthelastroundwhereyoureverseyourentirecurrentstring. Thisproblemisanexercise in Javastringmanipulation.Forsomemysteriousreason,even in this day and age the Java String type still does not come with a reverse method built in. The canonical way to reverse a Java string str is to Yirst convert it
May 23, 2022
SOLUTION.PDF

Get Answer To This Question

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here