Question

After all your hard work studying for Algorithms you, Alice and Bob end up stuck in a room full of deadly zombies! Luckily you have a gun with plenty of ammunition and can reliably shoot one zombie dead every second. Each zombie is di feet away and moving at a speed of si feet per second. If a zombie reaches you then you all die. You are arguing about what order to shoot the zombies so you live as long as possible.

1. State this input and output conditions for this optimization problem.
2. Alice suggests shooting the closest zombie first. Give a counterexample that shows this is incorrect.
3. Bob suggests shooting the fastest zombie first. Give a counterexample that shows this is incorrect.
4. What order should you shoot the zombies?
5. Prove your order will let you live the longest. Grading You will be docked points for errors in your math, disorganization, unclarity, or incomplete proofs.

Answer 1

Answer:

The most important quantity to consider in order to answer this question is the arrival time of the zombies from their initial position, which is the quotient between their distance to the visitors, divided the zombie's speed.

See explanation below.

Step-by-step explanation:

Part 1)

What is crucial to know is what is the time at which each zombie would reach Alice and Bob, and that is given by the quotient between the distance away each zombie is, divided by the zombie's speed:

$speed=\frac{distance}{time} \\time=\frac{distance}{seed} \\t_i=\frac{d_i}{s_i}$

Then, it is this quotient for each zombie, that one has to estimate given the input values distance and speed, and it is the output "time" ($t_i$) for each zombie, what we need to analyze so as to prioritize an order regarding which zombie to kill first.

Part 2)

Shooting the closest zombie first is not a good idea, since the speed of that closest zombie may be much slower than another zombie further away, but with much larger speed. Again, the important value to analyze is the time that it would take each zombie to reach Alice and Bob.

Part 3)

Shooting the fastest zombie first is not a good idea either, because that fastest zombie could be located very far away from the visitors, and other zombies closer by may reach them first.

Part 4)

The order that should be used to kill the zombies is given by the value of the time to reach Bob and Alice based on the quotient distance (di) over speed (si) explained in Part 1). The zombie that shows smallest time should be shot first, and then the others in increasing order of time value.

Part 5)

Notice that the individual zombie information is not presented in the question, but the student should be able to calculate the quotients for each zombie, and considering that there could be at most one shot every second, estimate the number of seconds that the time for each zombie in increasing order would allow until the addition of shooting time per second in the appropriate order cannot match the arrival time of the zombies that are left.

One should count number of seconds from the first shot (to the zombie with shortest arrival time), and then increase in one unit (one shot per second), to the following zombie with slightly larger arrival time), and so on, until the addition of seconds (one second per shot and per increasing arrival time of zombie) exceeds the next zombie arrival time.