首页 > > 详细

辅导Algorithm语言、讲解Java编程设计、辅导Java程序 辅导Python程序|讲解R语言编程

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

联系我们
  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp
热点标签

联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!