Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Algorithm Design and Analysis

Milestone 2: Software Assignment and Mid-Semester Assessment

Submission Instructions

Create a single .zip archive containing the following components:

● For Software Assignment tasks 1–3, please include .java files in the cor-rect folder format. Please ensure code files do not contain any non-English characters (such as comments in Chinese) because my AUT computer can-not 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 brute-force 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 approx-imate approach to solving the delivery truck problem, and which improves 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)