CO2226 Software engineering, algorithm design and analysisCoursework assignment 2 2021–2022 Java

Updated: Mar 16

University of London

Computing and Information Systems/Creative Computing

CO2226 Software engineering, algorithm design and analysis

Coursework assignment 2 2021–2022

Submission details

Marks will be awarded for correct code, i.e. for code that produces results; if your code does not produce the correct result, no marks will be awarded for that part of the question.

You must submit one Java file called: Ass2226<StudentID>.java. For example, if your student number ID is 101031722, your file will be named: Ass2226101031722.java.

When this file is compiled, it must produce a file: Ass2226<StudentID>.class, e.g. Ass226101031722.class. When run, this must produce the answers to the coursework assignment questions by implementing the appropriate algorithms.

Your java file may contain other classes, but they must all be included in the single java file; please do not submit multiple Java files as you will get a mark of zero – we need just one file. You must write your code assuming all data files are in the same directory as the program (and only use their names as arguments as shown in the example below).

Failure to do this will lead to a mark of zero. If you cannot complete a particular question, the answer should be ‘NOT DONE’. Your program should take the text files described below as command-line arguments.

To run your program, the examiners will type:

java Ass2226101031722 pubs pubs_lon_lat randomGraph

It is important to note that the filenames are referenced without the file extension.

Your output should look like this:

Name: Joe Doe

Student ID: 101031722

Question 1: 2

Question 2: 200 205

Question 3: 4

Question 4: 15

Question 5: [350, 352]

Question 6: 5.12

Question 7: 29.47

Execution Time: 32094 milliseconds

These are just sample answers to show the output format required from your program. The examiners will change the data files to test your programs so make sure your program works with files containing fewer/more pubs or the existing pubs with different ids. Try deleting some lines from the files and see if your program gives different answers. You should use the code provided and adapt it to answer the questions – no changes or alternative approaches the logic of the code are allowed.

Efficiency of your program

You will be penalised if your program runs too slowly (5 marks for every minute over 5 minutes on a machine with Intel Core i7 vPro processor with 12 gigabytes of RAM).

Try to speed up your program by avoiding re-computing values that you have already computed. Instead, store them (rather than re-computing) and identify opportunities and questions that will allow you to do so – then these values will be readily available to your program.

Use System.nanoTime(); to time your program. Read the value at the beginning and end of your program and subtract and divide by a billion to get the result expressed in seconds.

IF YOU DO NOT INCLUDE THE EXECUTION TIME OF YOUR PROGRAM YOU WILL SCORE ZERO.

IF YOU DO NOT USE THE DATA PROVIDED YOU WILL SCORE ZERO.

ALL SOLUTIONS SHOULD INVOLVE CALLS TO YOUR GRAPH INSTANCE METHODS; DO NOT TRY TO FIND ANSWERS ELSEWHERE.

Coursework assignment 2 – preparation and pre-assignment tasks

Finding the shortest paths in unweighted graphs (breadth-first search)

Research Adjacency matrices for representing graphs. Here is a program to help you become familiar with them:

import java.util.HashSet;

import java.util.ArrayList;

public class graph

{

double [] [] adj;

graph (double [] [] a)

{

adj= new double [a.length][a.length];

for (int i=0;i<a.length;i++)

for (int j=0;j<a.length;j++) adj[i][j]=a[i][j];

}

public HashSet <Integer> neighbours(int v)

{

HashSet <Integer> h = new HashSet <Integer> ();

for (int i=0;i<adj.length;i++)

if (adj[v][i]!=0)

h.add(i);

return h;

}

public HashSet <Integer> vertices()

{

HashSet <Integer> h = new HashSet <Integer>();

for (int i=0;i<adj.length;i++)

h.add(i);

return h;

}

ArrayList <Integer> addToEnd (int i, ArrayList <Integer> path)

// returns a new path with i at the end of path

{

ArrayList <Integer> k; k=(ArrayList<Integer>)path.clone(); k.add(i);

return k;

}

public HashSet <ArrayList <Integer>> shortestPaths1(HashSet

<ArrayList <Integer>> sofar, HashSet <Integer> visited, int end)

{

HashSet <ArrayList <Integer>> more = new HashSet <ArrayList