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
equired filename. The PDF file could be generated using LATEX(recommended), Microsoft Word (saved as PDF, not the
.docx file), or other edito
tools. The submission must be typed. Handwritten submissions are not accepted.
Due Fe
uary 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
co
ectness, but also on clarity. Answers that are technically co
ect that are hard to understand will not receive full marks.
Mark values for each question are contained in the [square
ackets]. Your submitted file does not need to include
epeat
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
iefly 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 you
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 intege
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
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 bette
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
e
ors 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 co
ect 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 co
ectness of the code in A2Q2.java (passed test cases in
auto-testing), and 50% based on the written answers provided in the PDF file.