For this dynamic programming problem, be sure to

(a) describe the subproblem

(b) give a recurrence for the subproblem

(c) provide pseudo-code showing how a table for the subproblems is filled

(d) give the time and space requirements of your method

(Exercise 6.23, p 196, from DPV) A mission-critical production system has n stages that have to be performed sequentially; stage i is performed by machine Mi. Each machine M has a probability ri of functioning reliably and a probability 1 ri of failing (and the failures are independent). Therefore, if we implement each stage with a single machine, the probability that the whole system works is r1.r2...In. To improve this probability we add redundancy by having mi copies of the machine M that performs stage i. The probability that all mi copies fail simultaneously is only (1 ri)Mi, so the probability that stage i is completed correctly is 1- (1 ri)Mi and the probability that the whole system works is II1 [1 (1 ri)mi]. Each machine M has a cost Ci, and there is a total budget B to buy machines. (Assume that B and the C are positive integers.) Given the probabilities ri, r2, ..., In, the costs C1, C2, ..., Cn, and the budget B, find the maximum reliability that can be achieved within budget B. (10 points) (Exercise 6.23, p 196, from DPV) A mission-critical production system has n stages that have to be performed sequentially; stage i is performed by machine Mi. Each machine M has a probability ri of functioning reliably and a probability 1 ri of failing (and the failures are independent). Therefore, if we implement each stage with a single machine, the probability that the whole system works is r1.r2...In. To improve this probability we add redundancy by having mi copies of the machine M that performs stage i. The probability that all mi copies fail simultaneously is only (1 ri)Mi, so the probability that stage i is completed correctly is 1- (1 ri)Mi and the probability that the whole system works is II1 [1 (1 ri)mi]. Each machine M has a cost Ci, and there is a total budget B to buy machines. (Assume that B and the C are positive integers.) Given the probabilities ri, r2, ..., In, the costs C1, C2, ..., Cn, and the budget B, find the maximum reliability that can be achieved within budget B. (10 points)