CPS420 Assignment

CPS420	W2024 Assignment
Worth: 6%	Hamiltonian Circuits	Due: March 24

Team Work

This assignment can be done in teams of one or two people. A third person can be added to the team for a 20% penalty (i.e. the final grade for the work will be 80% of the original grade). This third member must be declared in writing in the D2L component of the submission when the assignment is submitted.

You do not have to be in the same teams as for Lab6!

Assignment Summary

In this assignment you will implement a brute force backtracking algorithm to find a Hamiltonian circuit in an undirected graph when this is possible.

Just like for lab 6, your code will be automatically tested and graded on the moons, with a manual verification of the algorithm. You are also provided grading functionality in the main class of the program, but it is partial: Running it will show what the first 25 marks out of 30 will be for your assignment assuming that the algorithm is implemented reasonably. The remaining 5 marks will be determined by running your work on a few other large examples.

Your code will only be graded on the moons and not on any other platforms, and it must pass the grading tests on the moons in order to receive a grade.

For this reason, you are encouraged to do your entire development on the moons: like for lab6, you will not be writing large quantities of code (our solution adds 30 lines of code to the Hamilton class, in addition to the lab6 code that added about 15 lines to the Graph class) A sophisticated development environment is not required for this amount of coding. Also the testing infrastructure is already set up on the moons.

However, the coding in this assignment is more challenging than in lab6 and this is why the assignment is worth more, and you are given more time to do it.

Assignment Description

Introduction

In this assignment you will need to make a few modifications to one class in an existing set of java classes described in their javadoc.

Be sure to finish Lab6 before starting this assignment to familiarize yourselves with the Graph API, java development process on the moons, and the provided testing infrastructure and process which are all used in both.

Preparation on the moons

The preparation is very similar to the one for Lab6:

Create a directory where you will do your development (e.g. cps420A) and copy all the files handed out into it:
```
  mkdir cps420A
  cp ~cps420/public_html/doc/Now/A/Handouts/* cps420A
  cd cps420A
  chmod u+x test
```
Replace Graph.java in that directory by the one you developed in Lab6 to implement the isConnected method. This method will be needed to implement your assignment.

You are now ready code and test your work on the moons. You will only need to edit Hamilton.java for this assignment. You can also edit Test.java if you want to do more extensive testing, but you should not modify Walk.java.

Handouts

Here is an explanation of the handouts:

Test.java is the main program you can use to test your code. Just as for lab6, this is the java file that you will run in java. Also, like lab6, this is a grading program, but only partially: It calculates the first 25 out of 30 grades but the remainder of the grading will be done on larger random data. If you wish, you can modify this program during your development to support your own testing, but be aware that the grading will be performed using our own Test.java which simply has a few more tests than the ones in the handout.
Graph.java is the same file handed out in lab 6 that defines the clas Graph. You should use your modified version where you have implemented the isConnected method. However, we will be testing your assignment with our own solution for this class, and you do not need to resubmit this class.
Walk.java defines a class of Walk objects that you will use to store the walks you are building. The testing functionality assumes that when a Hamiltonian circuit is found, it is returned as a Walk object. You should not change anything in this class.
Hamilton.java is the only java file that you will work on. This is the file that you will submit for your assignment and the only work that will be graded.
makefile and test are used to compile and test your work as explained in the Compiling and Testing section of Lab6. The assignment has its own Tests folder.

Programming

As mentioned above, the only java file that you will work on is Hamilton.java. The class Hamilton is a static class i.e. a class that is not meant to be instantiated: all its methods and variables are static.

The only public interface of the Hamilton class is the class method getHamiltonian which is defined as:
```
public static Walk getHamiltonian(Graph graph)
```
This method is used by the Test program, and its signature and return type should not be modified.
As you can see in the code, the class has three static variables that are accessible to all static methods in the class:
- The graph passed as a parameter to getHamiltonian is stored in a static Graph variable called g
- The number of vertices in g is stored in a static int variable called totalV
- The Hamiltonian circuit being built is stored in the static Walk variable called hamiltonian
Making these variables static avoids repeatedly passing them as parameters in the recursive function calls.
For the assignment, you should implement getHamiltonian using a brute force macktracking algorithm. A brute force algorithm to find a Hamiltonian circuit in a graph G tries all possible walks in a methodical way to see if one yields a Hamilton circuit, and returns the first one it finds or null if none can be found.
Backtracking is implemented with a recursive helper function. The algorithm is summarized as:
1. Visit the first vertex
2. For each newly visited vertex, visit every one of its unvisited adjacent vertices one by one, each time trying to complete the Hamiltonian circuit, until you find one that works.
3. Do this recursively (you will need a recursive helper function).
The handout proposes a foundHamiltonian helper function for that purpose, but because the helper function is a private method, you do not need to implement your recursive helper function as suggested if you prefer a different approach.

Compiling and Testing

The processes for compiling and testing your code are the same as for lab6: Your assignment will be graded on the one platform that you all have access to, the Computer Science Linux moons, and therefore you should make sure that your assignment is compiling and running smoothly on that platform. To that effect, you will find a makefile to compile your code and a testing script to run the tests in the Handouts directory.

To compile your code, simply type
```
  make
```
To test your code, simply type
```
  ./test
```

The test script simply runs the main program which is located in the Test class. This Test class provides all the testing facilities that you will need to test your work. The main function uses test cases that are stored in the tests folder to calculate the first 25 grades (out of 30) for your assignment, assuming the algorithm is implemented reasonably.

If you are struggling to pass the provided tests, you are encouraged to supplement this testing with your own files, and you can certainly modify Test.java to do so, but keep in mind that we will be using our own Test.java for grading, and not yours.

The additional testing we will perform when grading your assignment will load test your program, so if you are finding that your program is slowing down on larger graphs, you should try to make your algorithm more efficient.

March 14 update: because there are different definitions of Hamiltonian circuits for very small numbers of vertices,when we grade the assignment we will remove the test cases "toosmall" and "small", which are for graphs of 2 of fewer vertices, and we will redistribute their 2 grades in the other tests.

Once your code is running smoothly, you are ready to submit the assignment as explained in the Submission section below.

Do not wait until the last minute to start this assignment and test it on the moons as you may run into unexpected last minute problems! As mentioned above, your program must work on the moons in order to get a grade.

As for lab6, do not wait until the last minute to test your code on the moons as you may run into unexpected last minute problems! As mentioned above, your program must work on the moons in order to get a grade.

References and links

Lecture section 2.2A for paths and circuits, 2.2C for Hamiltonian circuits, and 2.3 for the adjacency matrix representation of graphs..
Textbook chapter 10.1 and 10.2
javadoc is the javadoc documentation for the assignment.
Handouts contains the java classes used in this assignment, makefile to compile your program and test script to test it.
Tests folder contains the tests used to grade your assignment on the moons.
A recording of the March 6 Zoom assignment demonstration session is posted in the D2L path: Content > 2 - Graph Theory > Assignment: Graph Theory

Assignment Submission

The submission process for this assignment is similar to the one for Lab6. There are 2 parts to this submission:

One member of your team should submit the work electronically on the scs moons as follows:
```
submit-cps420 Hamilton.java
```
Do not change the names of this file as this could make the automated grading fail, resulting in a grade of 0.
You will also need to declare your teams on D2L and tell us where to find your assignment on the moons so that we can grade it and provide you with feedback on your grade in D2L. To so so, please follow the instructions for D2L Submissions.
The two submission folders are called "Assignment - Individual submissions" and "Assignment - Group submissions". The relevant self enrolment groups if you are submitting as a team all have "A" as a prefix.

This page is maintained by Sophie Quigley (cps420@cs.torontomu.ca)
Last modified Thursday, 14-Mar-2024 14:41:26 EDT

CPS420

W2024 Assignment

Worth: 6%

Hamiltonian Circuits

Due: March 24