EECS 2011 Z, Winter 2023 – Assignment 2Remember to write your full name and student number prominently on your submission. To avoid suspicions of plagiarism:at the beginning of your submission,...

can you help me with this question please


EECS 2011 Z, Winter 2023 – Assignment 2 Remember to write your full name and student number prominently on your submission. To avoid suspicions of plagiarism: at the beginning of your submission, clearly state any resources (people, print, electronic) outside of the course materials, and the course staff, that you consulted. You must submit a PDF file and Java files (if any) with the required filename. The PDF file could be generated using LATEX(recommended), Microsoft Word (saved as PDF, not the .docx file), or other editor/tools. The submission must be typed. Handwritten submissions are not accepted. Due February 17, 2023, 10:00 PM (on eClass); required file(s): a2sol.pdf, A2Q2.java Answer each question completely, always justifying your claims and reasoning. Your solution will be graded not only on correctness, but also on clarity. Answers that are technically correct that are hard to understand will not receive full marks. Mark values for each question are contained in the [square brackets]. Your submitted file does not need to include/repeat the questions — just write your solutions. The assignment must be completed individually. 1. [10] For each of the two programs below, complete the following three tasks: • State the proper postcondition. The postcondition should be a short sentence with fewer than 10 words. • State a loop invariant that can be used to prove the postcondition. You may briefly explain why the invariant is true; however, a formal proof for the invariant is not required. • Assuming the stated loop invariant as well as the negation of the loop guard, prove the postcondition. Keep your arguments clear, complete, and concise. (a) Program A 1 // Precondition: is non -empty and contains only ’C’, or ’S’. 2 // Postcondition: ??? 3 void ProgramA(char[] lst) { 4 int p1 = 0; 5 int p2 = 0; 6 while (p1 < lst.length)="" {="" 7="" if="" (lst[p1]="=" ’c’)="" {="" 8="" swap="" lst[p1]="" and="" lst[p2];="" 9="" p2="p2" +="" 1;="" 10="" }="" 11="" p1="p1" +="" 1;="" 12="" }="" 13="" }="" (b)="" program="" b="" 1="" precondition:="" n="">= 1 is a positive integer 2 // Postcondition: ??? 3 float ProgramB(int n) { 4 float r = 1.0; 5 int k = 1; 6 while (k < n) { 7 r = r * k / (k + 1); 8 k = k + 1; 9 } 10 return r 11 } programming question the best way to learn a data structure or an algorithm is to code it up. in this assignment, we have a programming exercise for which you will be asked to write some code and submit it. you may also be asked to include a write-up about your code in the pdf file that you submit. make sure to maintain your academic integrity carefully, and protect your own work. all code submissions will be checked for plagiarism at the end of the term. it is much better to take the hit on a lower mark than risking much worse consequences by committing an academic offence. 2. [10] in this programming question, we will explore a variation of the tower of hanoi (toh) problem. below is the wikipedia page of this famous problem. please read it first to get an understanding of what the problem is about. https://en.wikipedia.org/wiki/tower_of_hanoi by reading the above page, you’ll notice that the number of moves needed to solve a toh puzzle with n disks and 3 pegs is 2n − 1. in this assignment, we would like to explore how we can solve the puzzle faster with an additional peg, i.e., 4 pegs in total. specifically, we would like to apply the following strategy, which is still a high-level idea for now and not 100% precisely defined: • to move a stack of n disks from some origin peg to some destination peg, we could think of some number k between 1 and n (you decide if it should be inclusive or not), and then: – move n− k disks to an intermediate peg using all four pegs. – move what’s left on the origin peg to the destination peg, using as many pegs as possible. (you’ll need to decide whether to use 3 or 4 pegs here.) – move the n−k smallest disks from the intermediate peg to the destination peg, using as many pegs as possible. (you’ll need to decide whether to use 3 or 4 pegs here.) your job is to implement the 4-peg toh solution with the above strategy, as well as conducting experiments measuring the number of moves taken by the solution and reporting the results. specifically, complete the following tasks: (a) download and read the starter code a2q2.java carefully and understand the requirements and specifications of the methods to be implemented. read all instructions in the starter code carefully. in particular, make sure to not modify the parts of the starter code that says “do not modify” in the comments, e.g., the package declaration “package a2” and the import lines. (b) implement the threepegtoh method, which returns the sequence of moves that solves the 3-peg toh problem. the solution to this problem is well-known and easily found online. however, you should complete it independently for your own learning benefits. (c) perform experiments to demonstrate that the number of moves taken by the 3-peg toh solution is 2n−1. report your experiments and their results in your pdf submission. (d) implement the fourpegtoh method. (e) in the pdf file, describe your strategy on how to choose the value of k. you are not required to come up with the optimal strategy. what’s important is that you come up with something original that is better than the 3-peg solution, and that you can use experiments to evaluate the strategy you choose. (f) perform experiments to demonstrate the number of steps taken by your 4-peg toh solution as a function of n, and show that it is consistently faster than the 3-peg solution. compare different ways of choosing k and show how it affects the number of steps taken. report your experiments and their results in your pdf submission. along with the starter code, we have also provided a tester file a2tester.java that contains some junit test cases as well as the related testing methods. this tester file works essentially the same way as the auto-tester that we will use when marking this question (except that there will be more test cases). please read the tester code to understand how errors are detected, e.g., when an invalid move exception is thrown and when the check result method returns false. feel free to modify this tester file, and you should add more test cases to test your code thoroughly. however, do not submit the tester file in your submission. as usual, you may setup the java project using any programming ide of your choice such as intellij, eclipse, vscode, or notepad — it doesn’t matter as long as the a2q2.java file is correct and you are fully responsible for using the ide you choose properly. be careful: sometimes the ide automatically inserts lines of code such as the package declaration https://en.wikipedia.org/wiki/tower_of_hanoi and imports. make sure to double-check your code before submission to remove any unnecessary those extra lines since they may cause all test cases to fail in auto-testing. summary: what to include in your submission: • in the pdf file a2sol.pdf, provide the reports of your experiments according to the above task descriptions (a) to (f). • your a2q2.java file with the complete implementation your solution. this is the only java file you submit. do not submit a2tester.java. the marking of this question will be 50% based on the correctness of the code in a2q2.java (passed test cases in auto-testing), and 50% based on the written answers provided in the pdf file. n)="" {="" 7="" r="r" *="" k="" (k="" +="" 1);="" 8="" k="k" +="" 1;="" 9="" }="" 10="" return="" r="" 11="" }="" programming="" question="" the="" best="" way="" to="" learn="" a="" data="" structure="" or="" an="" algorithm="" is="" to="" code="" it="" up.="" in="" this="" assignment,="" we="" have="" a="" programming="" exercise="" for="" which="" you="" will="" be="" asked="" to="" write="" some="" code="" and="" submit="" it.="" you="" may="" also="" be="" asked="" to="" include="" a="" write-up="" about="" your="" code="" in="" the="" pdf="" file="" that="" you="" submit.="" make="" sure="" to="" maintain="" your="" academic="" integrity="" carefully,="" and="" protect="" your="" own="" work.="" all="" code="" submissions="" will="" be="" checked="" for="" plagiarism="" at="" the="" end="" of="" the="" term.="" it="" is="" much="" better="" to="" take="" the="" hit="" on="" a="" lower="" mark="" than="" risking="" much="" worse="" consequences="" by="" committing="" an="" academic="" offence.="" 2.="" [10]="" in="" this="" programming="" question,="" we="" will="" explore="" a="" variation="" of="" the="" tower="" of="" hanoi="" (toh)="" problem.="" below="" is="" the="" wikipedia="" page="" of="" this="" famous="" problem.="" please="" read="" it="" first="" to="" get="" an="" understanding="" of="" what="" the="" problem="" is="" about.="" https://en.wikipedia.org/wiki/tower_of_hanoi="" by="" reading="" the="" above="" page,="" you’ll="" notice="" that="" the="" number="" of="" moves="" needed="" to="" solve="" a="" toh="" puzzle="" with="" n="" disks="" and="" 3="" pegs="" is="" 2n="" −="" 1.="" in="" this="" assignment,="" we="" would="" like="" to="" explore="" how="" we="" can="" solve="" the="" puzzle="" faster="" with="" an="" additional="" peg,="" i.e.,="" 4="" pegs="" in="" total.="" specifically,="" we="" would="" like="" to="" apply="" the="" following="" strategy,="" which="" is="" still="" a="" high-level="" idea="" for="" now="" and="" not="" 100%="" precisely="" defined:="" •="" to="" move="" a="" stack="" of="" n="" disks="" from="" some="" origin="" peg="" to="" some="" destination="" peg,="" we="" could="" think="" of="" some="" number="" k="" between="" 1="" and="" n="" (you="" decide="" if="" it="" should="" be="" inclusive="" or="" not),="" and="" then:="" –="" move="" n−="" k="" disks="" to="" an="" intermediate="" peg="" using="" all="" four="" pegs.="" –="" move="" what’s="" left="" on="" the="" origin="" peg="" to="" the="" destination="" peg,="" using="" as="" many="" pegs="" as="" possible.="" (you’ll="" need="" to="" decide="" whether="" to="" use="" 3="" or="" 4="" pegs="" here.)="" –="" move="" the="" n−k="" smallest="" disks="" from="" the="" intermediate="" peg="" to="" the="" destination="" peg,="" using="" as="" many="" pegs="" as="" possible.="" (you’ll="" need="" to="" decide="" whether="" to="" use="" 3="" or="" 4="" pegs="" here.)="" your="" job="" is="" to="" implement="" the="" 4-peg="" toh="" solution="" with="" the="" above="" strategy,="" as="" well="" as="" conducting="" experiments="" measuring="" the="" number="" of="" moves="" taken="" by="" the="" solution="" and="" reporting="" the="" results.="" specifically,="" complete="" the="" following="" tasks:="" (a)="" download="" and="" read="" the="" starter="" code="" a2q2.java="" carefully="" and="" understand="" the="" requirements="" and="" specifications="" of="" the="" methods="" to="" be="" implemented.="" read="" all="" instructions="" in="" the="" starter="" code="" carefully.="" in="" particular,="" make="" sure="" to="" not="" modify="" the="" parts="" of="" the="" starter="" code="" that="" says="" “do="" not="" modify”="" in="" the="" comments,="" e.g.,="" the="" package="" declaration="" “package="" a2”="" and="" the="" import="" lines.="" (b)="" implement="" the="" threepegtoh="" method,="" which="" returns="" the="" sequence="" of="" moves="" that="" solves="" the="" 3-peg="" toh="" problem.="" the="" solution="" to="" this="" problem="" is="" well-known="" and="" easily="" found="" online.="" however,="" you="" should="" complete="" it="" independently="" for="" your="" own="" learning="" benefits.="" (c)="" perform="" experiments="" to="" demonstrate="" that="" the="" number="" of="" moves="" taken="" by="" the="" 3-peg="" toh="" solution="" is="" 2n−1.="" report="" your="" experiments="" and="" their="" results="" in="" your="" pdf="" submission.="" (d)="" implement="" the="" fourpegtoh="" method.="" (e)="" in="" the="" pdf="" file,="" describe="" your="" strategy="" on="" how="" to="" choose="" the="" value="" of="" k.="" you="" are="" not="" required="" to="" come="" up="" with="" the="" optimal="" strategy.="" what’s="" important="" is="" that="" you="" come="" up="" with="" something="" original="" that="" is="" better="" than="" the="" 3-peg="" solution,="" and="" that="" you="" can="" use="" experiments="" to="" evaluate="" the="" strategy="" you="" choose.="" (f)="" perform="" experiments="" to="" demonstrate="" the="" number="" of="" steps="" taken="" by="" your="" 4-peg="" toh="" solution="" as="" a="" function="" of="" n,="" and="" show="" that="" it="" is="" consistently="" faster="" than="" the="" 3-peg="" solution.="" compare="" different="" ways="" of="" choosing="" k="" and="" show="" how="" it="" affects="" the="" number="" of="" steps="" taken.="" report="" your="" experiments="" and="" their="" results="" in="" your="" pdf="" submission.="" along="" with="" the="" starter="" code,="" we="" have="" also="" provided="" a="" tester="" file="" a2tester.java="" that="" contains="" some="" junit="" test="" cases="" as="" well="" as="" the="" related="" testing="" methods.="" this="" tester="" file="" works="" essentially="" the="" same="" way="" as="" the="" auto-tester="" that="" we="" will="" use="" when="" marking="" this="" question="" (except="" that="" there="" will="" be="" more="" test="" cases).="" please="" read="" the="" tester="" code="" to="" understand="" how="" errors="" are="" detected,="" e.g.,="" when="" an="" invalid="" move="" exception="" is="" thrown="" and="" when="" the="" check="" result="" method="" returns="" false.="" feel="" free="" to="" modify="" this="" tester="" file,="" and="" you="" should="" add="" more="" test="" cases="" to="" test="" your="" code="" thoroughly.="" however,="" do="" not="" submit="" the="" tester="" file="" in="" your="" submission.="" as="" usual,="" you="" may="" setup="" the="" java="" project="" using="" any="" programming="" ide="" of="" your="" choice="" such="" as="" intellij,="" eclipse,="" vscode,="" or="" notepad="" —="" it="" doesn’t="" matter="" as="" long="" as="" the="" a2q2.java="" file="" is="" correct="" and="" you="" are="" fully="" responsible="" for="" using="" the="" ide="" you="" choose="" properly.="" be="" careful:="" sometimes="" the="" ide="" automatically="" inserts="" lines="" of="" code="" such="" as="" the="" package="" declaration="" https://en.wikipedia.org/wiki/tower_of_hanoi="" and="" imports.="" make="" sure="" to="" double-check="" your="" code="" before="" submission="" to="" remove="" any="" unnecessary="" those="" extra="" lines="" since="" they="" may="" cause="" all="" test="" cases="" to="" fail="" in="" auto-testing.="" summary:="" what="" to="" include="" in="" your="" submission:="" •="" in="" the="" pdf="" file="" a2sol.pdf,="" provide="" the="" reports="" of="" your="" experiments="" according="" to="" the="" above="" task="" descriptions="" (a)="" to="" (f).="" •="" your="" a2q2.java="" file="" with="" the="" complete="" implementation="" your="" solution.="" this="" is="" the="" only="" java="" file="" you="" submit.="" do="" not="" submit="" a2tester.java.="" the="" marking="" of="" this="" question="" will="" be="" 50%="" based="" on="" the="" correctness="" of="" the="" code="" in="" a2q2.java="" (passed="" test="" cases="" in="" auto-testing),="" and="" 50%="" based="" on="" the="" written="" answers="" provided="" in="" the="" pdf="">