墨爾本代寫-線上編程學術專家

墨尔本代写assignment,加拿大美国论文代写,北美essay代写-Panda ScholarBest代寫-最專業靠譜代寫IT | CS | 留學生作業 | 編程代寫Java | Python |C/C++ | PHP | Matlab | Assignment Project Homework代寫

C語言代寫 | Algorithms 3027/3927 Assignment 1 v2

C語言代寫 | Algorithms 3027/3927 Assignment 1 v2

墨尔本代写assignment,加拿大美国论文代写,北美essay代写-Panda Scholar這次作業是用C語言完成星球大戰的程序

Algorithms 3027/3927 Assignment 1 v2
Introduction
Commander! We are under attack by alien flying saucers!
Each alien flying saucer shows up on the Earth Defence Grid as a y-coordinate (its height off the
ground), an `-coordinate (the leftmost side) and an r-coordinate (the rightmost side). All flying saucers
are 1 grid square high, but can be any number of grid squares wide.
0 1 2 3 4 5 6 7 98
Figure 1: Six flying saucers given by the data [ { `:0, r:2, y:0 }, { `:3, r:7, y:1 }, { `:2, r:3, y:2 }, { `:7,
r:9, y:2 }, { `:0, r:3, y:3 }, { `:8, r:9, y:4 } ]
To defend ourselves we can use our Earth Defence Laser Cannons. Each laser cannon can be positioned
at any x-coordinate and fires directly upwards. The laser beam is so powerful it will pierce through any
number of flying saucers, and destroy anything with which it comes into contact.
0 1 2 3 4 5 6 7 98
Figure 2: Three laser cannons positioned at 1, 3 and 8 are sufficient to destroy all six flying saucers. It is
not possible to destroy all the flying saucers with only two laser cannons. Notice there are multiple ways
to position three lasers to destroy all the flying saucers.
However, the Earth Defence Laser Cannons are extremely expensive and cannot be moved once put
in place. Your job as Earth Defence Commander is to determine where to position the cannons such that
every flying saucer is destroyed, while using as few cannons as possible. The flying saucers will not be
able to move before the cannons are set up and fired.
Specification
An instance of the Earth Defence problem consists of a list of n rectangles R1, . . . , Rn. For 1 ≤ i ≤ n,
the rectangle Ri represents the i-th saucer and is specified by a left coordinate `i
, a right coordinate
ri and an altitude yi
. Each rectangle has a height of 1. The coordinates and altitudes will always be
non-negative integers.
1
The Laser Cannons can only be placed at integer coordinates. A Laser Cannon placed at coordinate
x destroys a saucer represented by the rectangle Ri
if `i ≤ x ≤ ri
, i.e. the infinite vertical line drawn
through x intersects Ri
. For brevity, we say that x destroys Ri
. Note that the rectangles include their
boundary, so a line at x = 3 will intersect the rectangle { `: 0, r: 3, y: 5 }.
The goal is to determine the minimum number k of Laser Cannons needed to destroy all flying saucers
and the integer coordinates of the Laser Cannons.
Task 1: Find a counter-example to a bad greedy algorithm [20
marks]
A friend of yours (name redacted to preserve anonymity) claims that the following greedy algorithm solves
the problem:
1. Initalize C to be the empty list and S to be the list of saucers represented by rectangles R1, . . . , Rn
2. While S is not empty:
(a) Let x be the integer coordinate that destroys the most number of saucers in S
(b) Add x to C
(c) Remove from S the saucers destroyed by x
3. Return |C| and C as the solution
Your friend says that the algorithm is correct because “it destroys the most number of remaining saucers
at each step, so it is locally optimal and thus globally optimal.”
Your task is to find an input to the Earth Defence problem such that the above algorithm does not
return an optimal solution.
(a) Give a list of rectangles in the format as used in the above figures. You are encouraged to include
a diagram or picture of the rectangles. (Just rectangles, no need to draw actual saucers or aliens.)
(b) Give the coordinates of C in the order that they were added to C.
(c) Give an optimal solution to the problem.
Task 2: Design a correct greedy algorithm [60 marks]
In this task, you will design a greedy algorithm that correctly solves the Earth Defence problem.
(a) Description of how your algorithm works (“in plain English”).
(b) Prove that your algorithm returns an optimal solution.
墨尔本代写assignment,加拿大美国论文代写,北美essay代写-Panda Scholar (c) Prove an upper bound on the time complexity of your algorithm.

在線客服

售前咨詢
售后咨詢
微信號
Essay_Cheery
微信
北美代写,论文Essay代写,留学作业代写,-北美最专业的代写专家 堪培拉代写assignment,论文代写,留学作业代写-peaking代写 essay代写,assignment代写,留学生作业代写网课代做-锐 泽 代写 阿德莱德代写assignment,北美网课代修领导者,留学生网课代修代考 珀斯代写assignment,CS代写,留学生CS程序代写-Custom Writing代写 新西兰代写,math代写,新西兰Assignment代写-美 伦 代写 怎么样? 留学生CS代写,Java编程代写,网课代上代修-ezace留学生代写 达尔文代写assignment,留学生作业代写,留学代写-菠萝 菠萝蜜 代写 代写assignment,网课代上代考,考试代考论文代写-全球最好的华人代写机构 留学生代写,经济代写,代写作业-【靠谱】服务澳洲加拿大英国美国等地区