2. (3 pts) Describe a dynamic programming algorithm to find the longest monotonically increasing subsequence of a sequence of n integers. 3. (3 pts) Design a dynamic programming algorithm to find the change of n cents using the fewest number of coins given any set of k different coin denominations. For example, coins in America are in denominations of 1, 5, 10, and 25 cents. However, this question does not have any specific denomination. It only assumes that each coin's value is an integer and one of the coins is a penny. 4. (2 pts) Gas stations optimization. There are n gas station S, ..., S, along I-80 from San Francisco to New York. On a full tank of gas your car goes for D miles. Gas station S is in San Francisco, each gas station Si, for 2in, is diD miles after the previous gas station Si- 1, and gas S, is in New York. Compute the minimum number of gas stops you must make when driving from San Francisco to New York. Give the pseudo-code for a greedy algorithm that solves the above optimization problem. Briefly justify why your algorithm finds the optimum solution. What is the asymptotic running time of your algorithm in term of n?