2. Another classic problem regarding dynamic problem is 'Coin Change'. In this problem, there are n types of coins of value A1, A2,..., Am. You have to find if it is possible to make a total of Sum value using these coins. You can take each coin as many times as you want. a) One way to think about this problem is to notice that to make a total of Sum value using using coins of value Aj, A2, ..., An, there are 2 scenarios: Not using the coin A, even once. In that case, the total Sum now has to be constructed using coins of value A1, A2,...,A(n-1). Using the coin An at least once. In that case, the total Sum - Ar now has to be constructed using coins of value A1, A2,..., An i. Can this way of thinking be used to engineer a dynamic-programming solution to solve this problem? If so, please come up with an equation to solve the problem using sub-problems. Show how sub-sub-problems may overlap. ii. If you had to make a DP table, what would the rows and columns of that table correspond to? iii. Imagine, the coins you are provided are of values 2, 5, 10, 50, 100, 200, 501, 997. Can you make a DP table to find out if the value 252 can be constructed using these coins or not? You can write code in your computer to generate this DP table. iv. Using the same sets of coins (2, 5, 10, 50, 100, 200, 501, 997), can the value 10 be con- structed? Use the DP table you already constructed in the previous answer. v. What is the asymptotic run-time (big-O) of this approach? vi. Construct another DP table using these sets of coin values (1,2,5,10,50, 100, 200, 500, 1000). Now try to construct these total values: 37,72,101,7. vii. Does the greedy approach of taking the biggest valued coin as many times as possible work for problem (vi)? Does it work for problem (iii)? What could be the reason behind this difference? b) Let's change the coin change problem to increase the complexity a bit more. You now want to count the number of ways a specific 'total value can be generated given a set of coin values A1, A2,... An. You can use each coin as many times as you want. For example: given coins 1, 2, 5, if you want to construct a total of 5, 3 possible ways to accomplish this would be: . (1,1,1,2) . (1,2,2) (5) i. Analyse this new formulation of the problem to find optimal substructure show that the problem can define terms of sub-problems, and those sub-problems can sub-problems, and often these sub-sub-problems overlap. ii. What would the DP table look like? What would the row and column correspond to? For coins of values 1, 2, 3, 4, and a total of 9, construct the DP table. iii. What is the asymptotic-runtime of this aproach? What about the space this algorithm con- sumes? Can you find the big-0 of the space required to store the DP table in terms of the input size (number of coins and total)? iv. Now, assume the complexity of the problem is increased further by limiting how many times you can use each coin. Assume this limit is k. How will you adapt your algorithm? What will the DP table look like this time? V. Again, imagine the limit on coin usage is unique to that coin. How will you adapt your engineered solution this time? For example: Coins of values 1, 2, 3, 4 are available. The limits of usage of each of these coins in order are 8, 4, 2, 1. Imagine you need to construct a total of 20. For this specific example, create and populate a DP table and highlight the path to the