You are given some data to analyze. You can spend D dollars to perform the analysis. You have organized the process of analyzing the data so that it consists of n tasks that have to be performed sequentially by using dedicated hardware: you will use a processor P; to perform task i, for every i. Each processor is relatively cheap but may fail to complete its task with some probability, independently of the other processors. Specifically, P; costs ci dollars and succeeds to complete its task with probability si, while it fails with probability 1 - si.

(a) (3 points) What is the probability that the process of analyzing the data will be com- pleted successfully?

(b) Note that you can improve this success probability by using Pi identical processors Pi for task i instead of just one.

i. (8 points) What is the probability that task i will be completed successfully now?

ii. (4 points) What is the probability that the process of analyzing the data will be completed successfully?

iii. (25 points) Given 81,..., Sn, integers c1, ..., Cn and integer D, give an algorithm to compute p1, ...,Pn such that the success probability of the entire process is maxi- mized while you do not spend more than D dollars. Your algorithm should run in time polynomial in n and D.