CO3002/7002代写、代写Python，Java编程

日期：2022-03-27 08:30

CO3002/7002 Assignment 2

Released Mar 9, 2022 Deadline Mar 30, 2022 5:00 pm

This assignment consists of two parts. The first part is to be completed individually. The

second part can be completed in groups of size up to three. Further instructions about group

work will be provided separately.

You should prepare your answers electronically, in a Word document or pdf file. Where

mathematical formulas, diagrams etc are needed you can use handwriting and insert them

into the document as pictures, but any substantial amount of text should be typeset and not

handwritten. You should have the individual and group parts in different files; there are separate

submission points for the two parts on Blackboard.

In line with university policy, marking will be done anonymously. Please do not include

your name or other personally identifiable information in your submission.

Part A (Individual, 30 marks)

In each of the following, a greedy algorithm is proposed for the given problem. Give a simple

counterexample for each of them to show that the proposed greedy algorithm does not always

return the optimal solution. You should (1) give an example input, (2) state the solution

returned by the greedy algorithm on that input, and (3) state the optimal solution (or indeed

any better solution than the greedy one) for that input.

(a) Input: An undirected graph G(V, E).

Problem: Find a minimum spanning tree T of G.

Algorithm:

Choose an arbitrary vertex s in G

Initialise S := {s}, T := {} (empty set), and u := s

while S 6= V do

Find the minimum-weight edge e among all edges (u, v) where v is not in S

Add v to S, add e to T, and set u := v

end while

(Note: this is not Prim’s algorithm.) [10 marks]

(b) Input: A set A of animals, and a set of pairs (ai

, aj ) indicating animal ai cannot be put

together with animal aj (because for example ai attacks or eats aj ).

Problem: Choose a subset A0 of animals from A so that the animals in A0

can be safely

put together, and that the number of animals in A0

is as large as possible.

Algorithm: Initialise A0

to be empty. For each animal in A, count the number of other

animals it can be safely put together. In decreasing order of this count, consider each

animal in turn and add it to A0

if it can be put safely together with all other animals

already in A0

. [10 marks]

1

(c) Input: A set of n tasks, each with a required “amount” of “work”; a set of m workers all

of whom can work on any of the tasks.

Problem: Assign the tasks to the workers so that the work is “distributed as evenly

as possible among the workers”, or more precisely, the amount of work assigned to the

busiest worker (the one with the largest amount of work) is as small as possible.

Algorithm: Sort the tasks in decreasing order of amount of work. For each task in this

sorted order, assign it to the worker who currently (i.e., based on the assignment made so

far) has the least amount of work assigned. [10 marks]

Part B (Group, 70 marks)

Your country is being invaded. As part of the invasion, a long line of enemy armoured vehicles

are moving along a road towards you. You can launch some drone attacks to damage or destroy

some of those vehicles. Unfortunately you only have one drone, so you have to plan your attacks

carefully to maximise the damage you cause to the enemy.

The line of n vehicles is moving at a constant speed past the point where you are stationed

(and where you launch your attack). For simplicity, we assume they move one unit of distance

per unit of time, and that the vehicles are spaced one unit of distance apart from each other.

Each enemy vehicle has a certain “value” (how much it is worth to destroy it). So, we can assume

there is a sequence of vehicles x1, x2, . . . , xn with values v1, v2, . . . , vn. At time i = 1, 2, . . .,

vehicle xi

is directly under your drone and is the only one you can attack. Based on satellite

imaging, you have all the information about these vehicles in advance.

Your drone can only perform one attack at a time. After it fired, it needs to return to base,

refill its ammunition (“ammo” for short), and go up in the air again. The more ammo it carries,

the more powerful the strike is, but it also takes more time to be loaded up. To be precise, it

needs one unit of time for returning to base, w units of time to refill it with w units of ammo,

and another unit of time to go up in air. Thus in total it needs w + 2 units of time between two

strikes, if it is to be loaded with w units of ammo. You can assume you have unlimited ammo,

but the drone can carry at most W units of ammo each time. Assume w and W are all integers.

A strike at an enemy vehicle may not completely destroy it; we assume that with w units of

ammo, one strike causes w

2 units of damage to the vehicle (i.e. reduces its value by w

2

), and if

the value goes down to 0 it is completely destroyed. Note that each strike uses up all the ammo

the drone carries, and you only get at most the value of that vehicle. For example if the drone

carries 5 units of ammo and fires it at an vehicle with value only 7, you only caused 7 units of

damage (reduced its value from 7 to 0), not 25.

You can have the drone loaded and up in the air already before the enemy arrives (so the

first strike does not require loading time and it can carry maximum ammo). Your task is to

determine the timing of the strike(s) and how much ammo to carry in each strike, so as to

maximise the total damage to the vehicles.

The following is an example. Suppose n = 13, v1..v13 = [2, 3, 0, 1, 4, 4, 1, 0, 4, 0, 1, 6, 4],

W = 3. Suppose the drone initially carries 3 units of ammo and first strikes at time t = 2,

causing min(v2, 3

2

) = 3 units of damage to x2. Then it returns to base and fills up 2 units of

ammo, so it is only ready at time t = 6. Then it strikes at t = 6, causing min(v6, 2

2

) = 4 units

of damage to x6. Then it returns to base and refill with 3 units of ammo, so it will only be

ready to fire again at time t = 11, and it waits until t = 12 to fire and causes min(6, 3

2

) = 6

units of damage to x12. In total the damage done is 3 + 4 + 6 = 13 units. Alternatively, if the

drone strikes at times t = 1, 5, 9, 13, with 2 units of ammo each time, it causes a damage of

2 + 4 + 4 + 4 = 14 (why?) There are many other possible strategies. Your task is to find the

2

best one.

(a) Design an efficient algorithm for this problem. You should: (the following is described

in terms of the design of a dynamic programming algorithm, since you almost certainly

should use it)

• In plain English or using some mathematical notation, give a recursive formulation

of the problem.

• Give the pseudocode of the algorithm that is based on this formulation.

• Analyse the time and space complexity of your algorithm.

• Illustrate how your algorithm works when given the 13-vehicle example above as

input. You only need to show the contents of the completed dynamic programming

tables.

[50 marks]

Hint: One possible approach is to define V (i) to be the optimal total damage where the

input consists of only the vehicles x1, . . . , xi

. At time i, either the drone doesn’t strike,

or it does with w units of ammo on board for some w. In the latter case, the previous

strike (if there is one) can only happen at time i − w − 2 or earlier, and we have to find

the optimal solution of the problem where xi−w−2 is the last vehicle. Consider all these

possible scenarios and use recursion for the subproblems. Note that if i − w − 2 ≤ 0 then

there cannot be a previous strike (i.e. this is the first strike) so it can carry maximum

ammo with no loading time; you need to handle this correctly.

There are other correct approaches; the above is just one possible formulation.

(b) Unfortunately, as it turns out, you don’t have unlimited ammo; you only have M units of

ammo, so all the strikes together can use at most M units of ammo. Again assume M is

an integer.

Design an efficient algorithm for the same problem in this limited-ammo case. You only

need to give a recursive formulation and/or pseudocode and explain the time complexity.

Hint: one possible approach is to define V (i, k) to be the optimal total damage where the

input consists of only the vehicles x1, . . . , xi and with k units of ammo available. Consider

all possibilities on what happens at time i as in (a).)

[20 marks]

3

Marking criteria

Marks are given roughly according to these tables:

Part A:

0 Not giving any counterexample at all. E.g. giving some algorithm, pseudocode, actual

program code, copying pages and pages of explanation of the given problem (or

even some unrelated problem) from some websites, textbooks or “research papers”.

(Yes, some of you did that.)

2-3 Wrong understanding of the problem, and wrong counterexample for it. But at least

it is some kind of an example (some input instance and some alleged greedy/optimal

solution).

5 A correct counterexample for a misunderstood version of the problem; or correct

understanding of the problem but two of input/greedy solution/optimal solution

wrong.

7-8 Correct understanding of the problem but one of input/greedy solution/optimal

solution wrong.

10 Correct counterexample (input) and correct explanation (greedy solution and optimal

solution).

Part B: (The mark you get within each range depends on how many of the required elements

(pseudocode, analysis, example execution) is present/correct.)

(a) (b)

0 0 Completely irrelevant answers; copying from some textbook general explanations

about dynamic programming; copying from some websites /

textbooks / “research papers” the solution of some other problem. (Again,

some of you actually did that.)

≥ 10 ≥ 4 Any genuine attempt at the question, no matter how wrong it is.

10-20 4-8 Not any ideas towards a correct algorithm (e.g. gave some greedy-type

algorithms); or gave an inefficient, brute-force type algorithm.

15-25 6-10 There are some ideas towards a recursive formulation, but not a DP algorithm

(did not use dynamic programming tables).

20-40 8-16 Some correct ideas DP-based algorithm but with major problems in formulation/pseudocode/analysis/example

execution (where required).

30-45 12-20 Broadly correct ideas of a DP-based algorithm, but with some minor

problems in formulation/pseudocode/analysis/example execution (where

required).

45-50 Everything is mostly correct, maybe with some small mistakes. Traceback

is included.

4