VIEW CODING Solution for CS6515 Dynamic Programming Homework 2
Chapter 2
[DPV] Problem 2.1 (Practice Fast Multiplication)
Graded Problem
You have been invited to participate in a new game created by Head TA Jamie.
Jamie gives you a list of tasks that you may choose to attempt or skip.
- The ith task has a point value of P[i]
- The ith task has a success rate of S[i] where 0 <= S[i] <= 1.0
- You start with a multiplier value x and an increment value y
Starting from task 1, you may choose to attempt or skip a task. This will affect your final score.
- If you succeed, your score will be increased by the point value times the current multiplier.
- If you fail, your score will be deducted by half the point value, ignoring the multiplier.
- To add a bit of strategy to the game, every task you skip increments the multiplier by y.
- Each time you attempt a task, the multiplier is reset to x after the attempt.
To play the game, you are given the following:
- A list of point values P for n tasks, with non-negative values.
- A list of success rates S for n tasks, with non-negative values.
- A non-negative x as the initial multiplier.
- A non-negative y as the multiplier increment.
Develop an efficient dynamic programming algorithm to determine the maximum expected value
and which tasks you should attempt to achieve it.
Notes:
- You start with zero points.
- The list of attempted tasks must be in the same order that you received them.
Please answer the following parts, only in terms of the value optimization portion of the problem:
- Define the entries of your table in words. E.g. T(i) or T(i, j) is …
- State a recurrence for the entries of your table in terms of smaller subproblems. Don’t forget your base case(s).
