CPS420 Lab 6

CPS420	W2024 Lab 6
Worth: 4%	Graph Connectedness	Due: March 13

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.

Lab Summary

In the assignment, you will implement an algorithm in java to decide whether a graph is connected. This implementation will take place on the Computer Science Department's UNIX servers called the moons. This lab is intended to prepare you to work on the assignment. You are provided a few java files to which you will need to add code to decide whether a graph is connected. All the facilities needed to test your code are also provided on the moons.

The coding in this lab is minimal: around 15 lines of straightforward java code. The challenge in this lab is not the coding, but making sure that you can work in java in a UNIX environment, and understanding the Graph API provided to you for the assignment and this lab.

Your code in this lab will be automatically tested and graded on the moons. It will not be tested on any other platform, and it must pass the tests on the moons in order to receive a grade. For this reason, you are encouraged to do your entire development on the moons: You will not be writing large quantities of code requiring a sophisticated development environment, and the testing infrastructure is already set up on the moons.

Lab Description

Introduction

In this assignment you will need to make a few modifications to an existing set of two java classes described in a javadoc. Before you start coding you should familiarize yourselves with these modules and their APIs:

Test is the main program which tests your code and assigns it a grade. This is the one that you will run in java.
Graph is a generic class that implements undirected graphs using adjacency matrices: Graph has been designed to be a fairly generic class with many methods. You will probably not need to use all the attributes and methods provided, but you may find many of them quite useful.

You will be modifying a section at the end of Graph.java containing two method stubs and submitting this file to be graded. The grading script will use its own Test.java exactly as handed out, and therefore you should not modify this file, or any code in Graph.java other than the two methods you are modifying.

Preparation on the moons

First, if you do not remember how to login to the moons, please review the "Getting started with the moons" section of the CPS420 References and Technical Information page

Once you've logged in, create a directory where you will do your development (e.g. cps420L6) and copy the four files handed out into it:

  mkdir cps420L6
  cp ~cps420/public_html/doc/Now/Lab6/Handouts/* cps420L6
  cd cps420L6
  chmod u+x test

You are now ready to edit the file Graph.java and test it on the moons.

Programming

Implement the following Graph methods described in the javadoc:

  public boolean isConnected()
  private void DFSvisit(int vertex)

Do not change the method signature and return value of the isConnected method, and do not modify anything else in the java files handed out. DFSvisit is a helper function for isConnected and you can therefore change its structure if you wish. The reason for these restrictions is that the scripts that will be grading your code automatically will assume that the classes follow the provided javadoc specs. If you change the code or specs, you run the risk of having the script give you a grade of 0, which would be a shame.

Hint: If you perform a depth-first (or breadth-first) traversal of your graph starting at any vertex, and this traversal visits all the vertices of your graph, then you can be sure that the graph is connected.

Compiling and Testing

Your lab 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 it 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 your lab grade (which is out of 40).

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 grade that you get when you run the tests on the moons should end up being your lab grade. Hopefully you will get a score of 40 out of 40. If you don't, you should debug your code on the moons until you do. 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.

References and links

The adjacency matrix representation of graphs is explained in slides 2.3 and section 10.2 of the textbook.
javadoc is the javadoc documentation for the lab.
Handouts contains the java classes used in this lab, makefile to compile your program and test script to test it.
Tests folder contains the tests used to grade your lab on the moons.

Lab Submission

Because this is a programming lab, the submission process for this lab is different from the other labs in this course. There are 2 parts to this submission:

One member of your team should submit the work electronically on the scs moons by typing:
```
submit-cps420 Graph.java
```
Do not change the name 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 "Lab6 - Individual submissions" and "Lab6 - Group submissions". The relevant self enrolment groups if you are submitting as a team all have "L6" as a prefix.

This page is maintained by Sophie Quigley (cps420@cs.torontomu.ca)
Last modified Tuesday, 12-Mar-2024 23:58:53 EDT

CPS420

W2024 Lab 6

Worth: 4%

Graph Connectedness

Due: March 13