Answer Happy

Part (B): Dynamic Programming Problem (B1) (30 points): Coin-row Problem There is a row of n coins whose values are some positive integers C1, C2, ..., Cn, not necessarily distinct. The goal is to pick up the maximum amount of money subject to the constraint that no two coins adjacent in the initial row can be picked up. Let F(n) be the maximum amount that can be picked up from the row of n coins. If we choose to pick up Cn, then the largest amount we can get from the group that includes C, is equal to Cr + F(n − 2), i.e. the value of the nth coin plus the maximum amount we can pick up from the first n – 2 coins. If we do not pick up Cn, then the maximum amount we can get from the group that does not include C, is equal to Fin – 1) by the definition of F(n). Thus, we have the following recurrence: F(n) = max{C,+ F(n − 2), F(n − 1)} for n >1, subject to the obvious initial conditions: F(0) = 0, F(1) = C. Consider the cost T(n) to be that of finding max(a,b), then we obtain the recurrence relation: T(n) = T(n-2) +T(n-1) +1 for n> 1 with T(0) = T(1) = 0 Hence, the above D&Q approach leads to this Fibonacci-like recurrence. You are required to: • Prove mathematically that the above recurrence leads to an exponential complexity. (10 points) • Write a pseudo code for a Dynamic Programming algorithm to solve this problem. (10 points) • Provide a complexity analysis of your algorithm (5 points) • Show the result of testing your algorithm on the coin row of denominations: 4, 20, 15, 10, 5, 9,6 (5 points) .