算法代写｜Algorithms and Data Structures First Practical Assignment

本次澳洲代写是一个算法和数据结构相关的assignment

The practical assignment consists of two parts, a program and a report.

The program must be written in Java, C++, C or Python 3. You can only use
libraries that come with a minimal installation of the language. You must write all code
yourself, copying code from fellow students or the internet is considered plagiarism.1.
The report must contain an explanation of your algorithm, an analysis of it’s correct
ness and an analysis of it’s runtime complexity. The report must have at least 2 and
at most 10 pages. Write your names on the rst page of the report.

Grades will be determined as follows. You may earn up to 100 points for your solution:
ˆ 20 points for the explanation of your algorithm.
ˆ 10 points for the correctness analysis.
ˆ 10 points for the complexity analysis.
ˆ 50 points for the test results. See the subsection on test results for more (important)
information.
ˆ 10 points for the quality of the code.

The Grand Canyon is one of the natural wonders of the world and receives close to 5
millon visitors per year. Visitors may either see the Grand Canyon from the South Rim
or from the North Rim. Although the South Rim and North Rim are only 10 miles apart
as the raven ies, they are separated by more than 215 miles of road. It is possible to
hike from one rim to the other through the canyon, but this is a really strenuous hike
that takes 12-15 hours.

An eccentric American billionaire, who recently adopted the name Z-Æ-M, hired you
as a consultant. Z-Æ-M wants to construct a spectacular bridge that will allow tourists to
cross the Grand Canyon more easily. Think of the canyon as an innitely long straight line
with width W. To be more specic, the canyon is a set of the all points with 0 < y < W
in xy-plane. Z-Æ-M’s idea is to build N huge pillars at specic places scattered across the
canyon. The location of the k-th pillar is (Xk; Yk). On top of these pillars, Z-Æ-M wants
to place huge disks. Both pillars and disks will be made from kryptonite, an extremely
strong and fully transparent new material. There are M dierent types of disks. The
i-th type of disks has radius Ri, and its price is Ci per disk. Z-Æ-M can buy as many
disks as needed. For each disk, its center must be at the location (Xk; Yk) of the k-th
pillar, for some k. Tourists can walk from one disk to another if they overlap or touch
each other.2 Disks may extend past the South Rim (y = 0) and the North Rim (y = W),
or rest on other pillars. Tourists can only move on the rims and the disks. What is the
minimum cost of all the disks needed to make it possible to walk from the South Rim to
the North Rim?