Problem 15. (10 points) Use the divide and conquer algorithm presented in class to determine the number of inversions in the sequnc (4,8,2,3,6,7,5) Show enough work to convince me that you are using the algorithm. Problem 16. (10 points) The LONGESTINCREASINGSUBSEQUENCE proble (hearafter referred to as LIS) has a sequence of integers as input and asks you to find a subsequence in which the integers are increasing and is as long as possible. For example, if the input was 6,3,2,4,1,5,7 then one solution with length 4 would be [3,4,5,7] (tied with [2,4,5,7]) Give a dynamic programming algorithm to solve LIS and run your algorithm on the sequence [5,7,1,6,4,2,9,3,8 Problem 17. 10 points) Most countries have coins of various denominations ul, va..%) and it is common to Inake c units of change using the minimum number of coins necessary As an example, in the country of Eastern Slobovia there are coins with value1,4,6,9Making change for 12 units requires at least 2 coins (G+6). Making change for 20 units requires at least 4 coins (9+9+1+1) Design a dynamic programming algorithm to determine the minimum number of coins necessary to make change of units