这次作业是用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.

(c) Prove an upper bound on the time complexity of your algorithm.