Car ownership. In this question, we consider a problem in car ownership. As a car gets older, the maintenance costs (fuel costs, repair costs, insurance costs, etc) for the car may increase to the extent that it would be advantageous to sell the current car and buy a new car. The difficulty in this problem is that the prices of new cars change from year to year, the maintenance costs of cars purchased in different years may be different and the resale value of a car can change from year to year as well.

For this question, you are given the following information:

p(i) = the price of a new car in year i , for 1 i n.

v(i, k) = The resale value of a car purchased in year i and sold in year k, for 1 i k n.

m( i, k) = the maintenance cost during year k of a car purchased in year i, for 1 i k n.

The problem is to determine the years y₁, y₂, . . . , y_r, when you would purchase new cars such that the total cost of car ownership from years 1 through n is minimized. The total cost is the sum of the maintenance costs for years 1 through n plus the price of each car purchased minus the resale value of each car sold.

For example, if n = 10, y₁ = 1, y₂ = 5, y₃ = 7, then this solution states that you should purchase a new car in year 1, buy the second car in year 5 and buy the third car in year 7. (You would also sell the first car in year 5, the second car in year 7 and the third car at the beginning of year 11.)

In addition, you should make the following assumptions:

You buy and sell cars at the beginning of the year.

You don't have a car before year 1. (Since you have to buy a new car in year 1, y₁ = 1 .)

You only want to purchase new cars.

At the end of n years, you sell your last car for v(y_r , n + 1) dollars.

Additional Instructions: When you are asked to provide a dynamic programming algorithm. You must provide the following:

a. Define a function OPT that can be used to solve this dynamic programming problem. To do this, you must describe the input parameters to OPT and the "return value" using English sentences. (Note: you are specifying the input-output relation of the function. You should not describe how to compute the function.)

b. Give a mathematical formula that shows how OPT can be computed recursively. Then, explain all the major parts of the formula using English sentences. Remember to include the base cases.

c. Describe how OPT can be computed bottom up using a dynamic programming table. Be sure to include a description of the dimensions of the table and the order that the entries of the table are to be filled. Draw a diagram. Which entry has the solution to the original problem?

d. Analyze and justify the running time of your dynamic programming algorithm.