Computers and Technology

The residents of the underground city of Zion defend themselves through a combination of kung fu, heavy artillery, and efficient algorithms. Recently they have become interested in automated methods that can help fend off attacks by swarms of robots. Here is what one of these robot attacks looks like.
• A swarm of robots arrives over the course of n seconds; in the i-th second, xi robots arrive. Based on remote sensing data, you know this sequence x1, x2, . . . , xn in advance.
• You have at your disposal an electromagnetic pulse (EMP), which can destroy some of the robots as they arrive; the EMP’s power depends on how long it has been allowed to charge up. To make it precise, there is a function f(·) so that if j seconds have passed since the EMP was last used, then it is capable of destroying up to f(j) robots.
• So specifically, if it is used in the k-th second, and it has been j seconds since it was previously used, then it destroys min(xk, f(j)) robots. (After this use, it will be completely drained.)
• We will also assume that EMP starts off completely drained, so if it is used for the first time in the j-th second, then it is capable of destroying up to f(j) robots.
The problem is: Given the data on robot arrivals x1, x2, . . . , xn, and given the recharging function f(·), choose the points in time at which you are going to activate the EMP so as to destroy as many robots as possible.
(a) Show that the following algorithm does not correctly solve this problem, by giving an instance on which it does not return the correct answer.
Schedule-EMP(x1, . . . , xn)
Let j be the smallest number for which f(j) ≥ xj
(If no such j exists then set j = n)
Activate the EMP in the j-th second
If n − j ≥ 1 then
Continue recursively on the input xj+1, . . . , xn
(i. e. invoke Schedule-EMP(xj+1, . . . , xn)
In your example, say, what the correct answer is and also what the algorithm above finds.
(b) Give an efficient algorithm that takes the data on robot arrivals x1, . . . , xn, and the recharging function f(·), and returns the maximum number of robots that can be destroyed by a sequence of EMP activations.

answer
Answers: 2

Other questions on the subject: Computers and Technology

image
Computers and Technology, 21.06.2019 20:20, ab847150
Wireless communications is likely to be viewed as an essential part of an enterprise network infrastructure when: select one: a. mobile communication is needed b. communication facilities must be installed at low initial cost c. communication must take place in a hostile or difficult terrain that makes wired communication difficult or impossible d. the same information must be broadcast to many locations
Answers: 1
image
Computers and Technology, 23.06.2019 16:00, cravens511peeelg
An english teacher would like to divide 8 boys and 10 girls into groups, each with the same combination of boys and girls and nobody left out. what is the greatest number of groups that can be formed?
Answers: 2
image
Computers and Technology, 23.06.2019 17:00, kyleemarie2003
Companies that implement and apply an information system effectively can create
Answers: 1
image
Computers and Technology, 24.06.2019 13:00, pineapplepizaaaaa
If you add the following to the query grid in an access query, what is it called? salestaxamt: [salestaxrate]*[totalsale] formula calculated field total calculation
Answers: 2
Do you know the correct answer?
The residents of the underground city of Zion defend themselves through a combination of kung fu, he...

Questions in other subjects:

Konu
History, 15.04.2021 18:10
Konu
Mathematics, 15.04.2021 18:10
Konu
Mathematics, 15.04.2021 18:10