8. (13 points) Greedy Algorithms Alice, Bob and yourself have been trapped in a

Question

8. (13 points) Greedy Algorithms Alice, Bob and yourself have been trapped in a room with many hideous zombies. You have a gun that you can fire at a rate of one second per shot (no reloading and you always hit your targeted zombie). Each zombie i is di feet away and is walking towards you at a speed of si (in feet per second). Ifa zombie reaches 0 feet away it will eat you. You all are arguing over which order to shoot the zombies so you can live as long as possible (i.e. kill the maximum number of zombies) a) (2 point) Alice thinks you should shoot the closest zombie first. Describe a set of zombies for which this is not correct. (Give a distance and speed for each zombie.) b) (2 points) Bob thinks you should shoot the fastest zombie first. Describe a set of zombies for which this not correct. (Give a distance and speed for each zombie.) c) (2 points) Which zombie should you shoot first? d) (2 points) What order would you target these zombies? Assume each pair is a zombie zi -(di, si)

Explanation / Answer

(a) Consider the distance speed pair of zombies as follows: {(2,1),(6,6)}.

If we choose closest zombie first then we can shoot only zombie (2,1) before die, but if we choose (6,6) first then (2,1) we can shoot both zombie.

(b) Consider the distance speed pair of zombies as follows: {(2,2),(9,3)}.

Here also if we choose fastest zombie first then we can shoot only (9,3) zombie.

But if wechoose (2,2) first then (9,3) then we can shoot both zombie,

(c) Zombie having smallest distance/speed ratio should shoot first.

(d) Consider the distance speed pairs Z={(4,0.5),(6,2),(3,3),(8,4),(2,0.1),(9,4),(7,2)}.

Let us find the distance speed ratio:{8,3,1,2,20,2.25,3.5}

Now shoot in smallest ratio first: So the sequence of shooting will be {(3,3),(8,4),(9,4),(6,2),(7,2),(4,0.5),(2,0.1)}.

(e) As we shoot smallest ratio first, so the zombie which will reach us first will shoot first. then the next which will reach us first will shoot. In this way we can continue shooting until two zombie having same ratio and we need to shoot them at same time to escape.

So our algorithm always gives corrrect output.

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.