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 : <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 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

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.