Greedy Algorithms, Assignments, and Drone Attacks

Part A (Individual, 30 marks)

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 /= 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 AJ of animals from A so that the animals in AJ can be safely put together, and that the number of animals in AJ is as large as possible.

Algorithm: Initialise AJ 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 AJ  if it can be put safely together with all other animals already in AJ.    [10 marks]
 
(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.

Part B (Group, 70 marks)

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, refills its ammunition (“ammo” for short), and goes 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 w2 units of damage to the vehicle (i.e. reduces its value by w2), 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, 32) = 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, 22) = 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, 32) = 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 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