Each problem is given in its own subdirectory, which follow a common structure. In this section we will use the Cargo problem as an example. You should have received the following directory structure:

Cargo/

├── Cargo .java

├── CargoImpl .java

├── CargoTester .java

└── testdata

├── 00_small/ . . .

└── 01_large/ . . .

Cargo.java : Java interface file. Do not modify this file. Your solution ( CargoImpl .java ) must implement this interface.

CargoImpl.java : Template Java class file. Modify this file to implement your solution to the problem.

CargoTester.java : Testing utility. Compile and run to automatically test your code against the provided

testdata .

testdata

: Directory containing test cases used by

CargoTester .

00_small

01_large

contains the "small" test cases.

contains the "large" test cases.

Implementation

You are expected to implement a solution to each problem.

When implementing your solution you should only need to modify  CargoImpl .java . You should not create or modify any other code files.

You may import anything you desire from  java .util or  java .lang . You may not import anything from any other sources, including the  CITS2200 package.

Compiling and Testing

Once you have implemented your solution in  CargoImpl .java , you can compile it and the test utility with:

javac Cargo .java CargoImpl .java CargoTester .java

If this does not successfully compile, then there is an error with your code, if not, you can then run the tests using:

java CargoTester

You should ideally see output something like:

Testing Cargo :

00_small :

00_empty : PASS

01_steps : PASS

. . .

All tests passed

01_large :

. . .

All tests passed

All tests passed

The tester will report the status of each test case:

PASS : Your solution ran and gave the correct answer

FAIL : Your solution ran but gave an incorrect answer

ERROR : Your solution encountered an error and gave no answer

TIME_LIMIT_EXCEEDED : Your solution did not give an answer within the two (2) second time limit

UNKNOWN : The test was not run

By default the tester stops after the first test that does not pass. You can force it to run all tests regardless with

java CargoTester all .

Explanation

You must provide a written explanation of why your solution will give the correct answer and what its time complexity is.

Note that there is no need to describe the step by step process of your algorithm, as the code already does that. Instead you should aim to write a logical argument sufficient to convince a fellow student (or a marker) that your solution will always give the correct answer.

Submission

You must submit exactly two files (for each problem):

CargoExplanation .pdf : A PDF of your explanation of your chosen solution

CargoImpl.java : The Java source code of your completed implementation of your chosen solution Across all four problems you are therefore expected to submit eight files:

CargoExplanation .pdf

CargoImpl.java

FinesExplanation .pdf

FinesImpl.java

ShallowsExplanation .pdf

ShallowsImpl.java

SubsidiariesExplanation .pdf

SubsidiariesImpl.java

Every file you submit as part of your project must include your full name(s) and student number(s). For PDFs, your name(s) and student numbers(s) should appear somewhere on the first page. For  .java code files, the first line   of the file should be of the form:

// Full Name (StudentNum), Full Name (StudentNum)

For example, an individual submission may look like

// Ada Lovelace (21234567)

and a pair pubmission may look like

// Ada Lovelace (21234567), Charles Babbage (22345678)

If your files do not include your name(s) and student number(s), we may not be able to mark your project, as we may not know who submitted it.

If you are working in a pair, only one of you should make a submission.

Marking

Each problem is marked out of a total of 10 possible marks allocated according to the following rubric. Learning

outcomes are as per the Unit Details.

Note that since execution time may vary slightly between runs and between computers, code that passes in one  case may exceed the time limit in another. If in doubt, your code must reliably run within the time limit on a CS lab

computer to receive the marks.

Problem Specifications

Cargo

It is important for a cargo ship crew to be able to predict what total mass of cargo they will have on board at points throughout their voyage. You are tasked with writing a system to keep track of the mass of cargo on board at each point along the route as new jobs come in to transport some cargo from one port to another.

Consider some planned route  p[0], p[1], p[2], . . . where each  p[i] is a port visited along the route. We would like to be able to perform a few different operations:

Add a job carrying some cargo from one port to another (receiving port can not be before sending port)

Remove a previously added job

Find what total mass of cargo we will have at some point along the route

We represent all three of these operations with the

class provided in the

interface:

cargoMass is the mass of cargo being transported (may be negative to delete a previous job)  collect is the index of the port at which we will collect the cargo

deliver is the index of the port to which the cargo must be delivered ( collect <= deliver )

The result of a query is the total mass of cargo expected to be on board when leaving  p[collect] (after any      change caused by the query). The effects of each query are persistent and will impact the results of later queries.

For example:

{cargoMass = 4, collect = 2, deliver = 5} represents adding a job carrying 4 mass units of cargo from p[2] to  p[5]

{cargoMass = -4, collect = 2, deliver = 5} represents deleting the above job

{cargoMass = 0, collect = 3, deliver = 3} represents a query to find the total mass of cargo that will be on board when departing from  p[3]

Implement a function  int[] departureMasses(int stops, Query[] queries) , where  stops is the number of     stops on the route and  queries is a sequence of queries. The function should perform the query operations in the order given, and return an array of the result of each query in the same order.

You may assume  0 < stops <= 10^6 , 0 < queries .length <= 10^6 , collect <= deliver , and no total cargo mass at any point will overflow an int .

Where  N is the number of stops and  Q is the number of queries, a solution with a computational complexity of O(N Q) is not expected to pass the large test cases, but most faster algorithms should.

Example

Consider  departureMasses(8, queries) , with queries of the form  {cargoMass, collect, deliver} as follow:

Total cargo mass when leaving each port is initially  {0, 0, 0, 0, 0, 0, 0, 0}

{4, 2, 5} gives  {0, 0, 4, 4, 4, 0, 0, 0} , result is  4

{3, 3, 8} gives  {0, 0, 4, 7, 7, 3, 3, 3} , result is  7

{0, 4, 4} gives  {0, 0, 4, 7, 7, 3, 3, 3} , result is  7

{-4, 2, 5} gives  {0, 0, 0, 3, 3, 3, 3, 3} , result is  0

Therefore

departureMasses

would return the array

{4, 7, 7, 0} .

It is not uncommon to find choke points or "narrows" in harbours around the world. In busy harbours, a                   harbourmaster will assign ships a priority. Ships with lower priority must gives way to allow ships with higher          priority to pass through the narrows. If a ship fails to give way, the harbourmaster may issue that ship a fine for      each higher priority ship it cut off. Note that multiple ships may be given the same priority, and ships with the same priority are not required to give way to each other.

Implement a function  long countFines(int[] priorities) that counts the total number of fines the           harbourmaster may issue. The array  priorities is a list of the priority of each ship that passed through the narrows in the order they passed through.

Where  N is the number of ships that passed through the narrows, a solution with a computational complexity of O(N^2) is not expected to pass the large test cases, but most faster algorithms should.

Example

Consider  countFines({ 4, 9, 7, 2, 1, 3 }) :

The ship with priority 4 failed to give way to two other ships (9 and 7), 2 fines

The ship with priority 9 did not fail to give way

The ship with priority 7 did not fail to give way

The ship with priority 2 failed to give way to one other ship (3), 1 fine

The ship with priority 1 failed to give way to one other ship (3), 1 fine

The ship with priority 3 did not fail to give way

Therefore  countFines should return the total of  4 fines.