# 编程代写 | Algorithms and Data Structures 2021: First Practical Assignment

1 Instructions

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.

The deadline for the rst practical assignment is Wednesday November 17, 15:30. You should submit your code and report via Brightspace. You are allowed to work on the assignment in pairs. Then you must be enrolled in the same practical group on Brightspace. Only one team member has to submit the assignment.

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.

1We will check this using MOSS. Note that MOSS results can be viewed without logging in. Therefore we will not require you to put your name or student number in your code.

3 Bridging the Grand Canyon

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?