代写Algorithm语言、代做Java编程设计、代写Java程序

日期：2020-11-02 11:31

Algorithm Design and Analysis

Milestone 2: Software Assignment and Mid-Semester Assessment

Due 6 November 2020

Submission Instructions

Create a single .zip archive containing the following components:

? For Software Assignment tasks 1–3, please include .java files in the correct

folder format. Please ensure code files do not contain any non-English

characters (such as comments in Chinese) because my AUT computer cannot

display these characters. Worse, these code files do not compile for

me.

? For Software Assignment task 4, please include a video file, in .mp4 format,

of no more than 30 MB in size.

? For Mid-Semester Assessment tasks 1–2, submit a single .pdf file.

Please submit the .zip file on Blackboard→Assessment→Milestone 2.

1 Software Assignment (15%)

Consider a delivery truck that travels from a start town to a destination town

passing by multiple towns en route. At each of the n towns along the route

there is the option for the truck to either pick up a new load at cost ci specific

for town i, or else drop off its existing load at a value vi ≤ ci specific for town

i. The truck can only transport one load at a time and can only stop at most

2k ≤ n times to pick up or drop off a load.

The purpose of this assignment is to develop algorithms that can indicate to

a truck driver at which towns it is best to pick up or drop off in order for the

truck to get the best overall profit.

The assignment should include the following components:

1. Brute-force Approach which is a program that implements a basic bruteforce

approach to solving the delivery truck problem that simply checks

all possible solutions (eg finding them by using recursion). (15 marks)

2. Approximate Approach which is a program that demonstrates a approximate

approach to solving the delivery truck problem, and which improves

1

on the performance of the brute-force approach. Please include comments

in your program that clearly explain the approach you have taken and

good test cases. (15 marks)

3. Exact Approach which is a program that demonstrates an approach that

correctly and efficiently solves the delivery truck problem. Please include

comments in your program that clearly explain the approach you have

taken, particularly why it works, and include good test cases that illustrate

its correctness. (15 marks)

4. Demonstration and explanation of the programs with sufficient test cases

should be provided as a video recording (screen-cast) of no longer than 3

minutes. (5 marks)

2 Mid-Semester Assessment (10%)

Submit a single pdf file containing the following sections:

1. Design patterns: identify and describe at least 2 design patterns used in

your software assignment. For each design pattern, provide the following

information:

? Name the design pattern.

? Justify the use of this design pattern and the problem it solves in

your code.

? Provide a comparison of the strengths and weaknesses of this design

pattern with another design pattern you could have used.

(20 marks)

2. Analysis of algorithms: For the brute-force, approximate and exact

approaches, provide a theoretical analysis of the time complexity. You

may utilise either the Master Theorem or the counting technique covered

in lectures for this analysis. (20 marks)

2