# Assignment

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 L
ATEX(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
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 : <lst > 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 ) { if ( lst [p1] == ’C ’) {

7 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
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
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 2
n 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 nk 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:
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
(c) Perform experiments to demonstrate that the number of moves taken by the 3-peg TOH solution is 2
n 1. Report
(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

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.