代写EECS 2011、代写Java设计程序

日期：2022-08-04 10:36

EECS 2011: Assignment 4

Due: as set in eClass.

May be done in groups of up to three students

TL;DR: implement one static method in one class. Submit that class. Cheating not

allowed but some external code use is officially permitted.

Motivation

The purpose of this assignment is to implement a commonly used graph algorithm and

use it to solve a related problem.

Introduction

Graph theory is the study of graphs, which are mathematical structures used to model

pairwise relations between objects. A graph in this context is made up of vertices (also

called nodes or points) which are connected by edges (also called links or lines).

The included skeleton implementation provides several methods to build a graph data

structure from a file, etc. It also provides an iterator that visits the elements. Note that not

all of the functionality is implemented.

You are encouraged to review the textbook chapters on graphs. You may also use the

Java examples from the Algorithms textbook1

(please cite them if you do). A starter code

is also supplied.

Description

In this assignment, you will have to write two implementations of graph algorithms. For

your convenience, some starting code is provided. Note that the starter code may either

not implement some of the required features, or might implement them improperly – e.g.,

via stubs. Note that the speed of your algorithms may strongly depend on the

implementation of the missing methods and on the choice of auxiliary data structures you

choose to utilize for your algorithms. You are permitted to use any java.util classes:

ArrayList, PriorityQueue, HashMap, etc.

The graph is implemented a class called Graph, implementing loading of the graph

content from a file. Take a look at the associated classed to confirm you understand the

overall structure of the classes.

Part 1

Finish the implementation of the following method in the Graphs class (note the -s

ending of the class name):

public static Set<String> nearby(Graph graph, String origin, int hops)

1 https://algs4.cs.princeton.edu/40graphs/

2

The method allows one to determine which cities are nearby a specified city, within a

specified number of edges, and returns a set of such cities as Strings, with the

corresponding distances (edge counts) appended to them after a comma. E.g., calling the

method with Oshawa as origin, and 2 as the number of edges should produce a set with

the following items:

"Port Perry, 1", "Ajax, 1", "Bowmanville, 1", "Uxbridge, 2", and "Ajax, 2".

You will notice that the graph files contain the actual distances and possible travel times.

For your algorithm, these will merely indicate that there is an edge present between a pair

of vertices.

As usual, you are free to implement any private or protected methods and classes as you

see fit. However, you should not modify the signatures of the existing methods in the

classes supplied if you choose to modify the method bodies. The main method in the

A4demo class should be able to print the mock results of your algorithm, to illustrate the

API.

Part 2

Nothing needs to be submitted for this part.

Explore your implementation, by redesigning some methods or by modifying the input, to

see if the graphs based on distances and those based on times can produce different

outputs. Three csv files are supplied with this assignment, one based on an Ontario map,

and two more resembling graph examples in the SW textbook.

NOTES:

1. Do not use package-s in your project. Using packages will cost you a 10 %

deduction from the assignment mark.

2. Some aspects of your code will be marked automatically (e.g., how it handles

boundary cases and error conditions), using a custom tester class and/or custom

unit tests. It is also imperative you test your classes. If any of the java files that

you submit do not compile, the whole submission will be given a grade of zero,

regardless of how trivial the compiler error is. The code you submit should

compile using

javac *.java

command in either Windows, Linux, or macOS.

3. Your code should include Javadoc comments.

Submission

Find all the java files in your project and submit them electronically via eClass (do not

zip, tar, rar, or 7z them). Submit only the file(s) you modified; you are expected to

change only the Graphs class. You may create other classes if you deem them necessary.

If working in a group, make only one submission per group and include a group.txt

file containing the names and the student numbers of the group members. The deadline is

3

firm. Contact your instructor in advance if you cannot meet the deadline explaining your

circumstances. The extension may or may not be granted, at instructor’s discretion.

Grading

The assignment will be graded using the Common Grading Scheme for Undergraduate

Faculties2

. We look at whether the code passes the unit tests, satisfies the requirements of

this document, and whether it conforms to the code style rules.

Academic Honesty

Academic honesty will be strictly enforced in this course. Specifically, direct

collaboration (e.g., sharing code or answers) is not permitted, and plagiarism detection

software will be employed. You are, however, allowed to discuss the questions, ideas, or

approaches you take.

Cite all sources you use (online sources – including web sites, old solutions, books, etc.)

in your code comments; using textbook examples is allowed, but these must be cited as

well.

E.g.,

1) /**

* Constructs an empty list with the specified initial capacity.

*

* @param initialCapacity the initial capacity of the list

* @exception IllegalArgumentException if the specified initial

capacity

* is negative

* uses code from www.xxx.yyy.edu/123.html for initialization

*

*/

2) //formula based on Jane Smart’s thesis, page XX, available at

https://...

a = b + c;

Although using outside sources is allowed – with proper citing, if the amount of nonoriginal

work is excessive, your grade may be reduced. You might find the following

article useful to have an idea what kind of collaboration is appropriate:

https://en.wikipedia.org/wiki/Clean_room_design

2 https://secretariat-policies.info.yorku.ca/policies/common-grading-scheme-for-undergraduate-faculties/

4

You may not post the contents of this assignment, nor solicit solutions on any

external resources.