2 Dynamic Programming: Tuna Trawlers You are managing the dock operations for a fleet of n tuna trawlers. When a trawler arrives at the dock, the tuna fish must be unloaded, processed and flown to various sushi restaurants around the world. Although these restaurants are willing to pay top dollar for fresh tuna, you still need to keep the air freight costs to a minimum in order to turn a profit. There are two companies willing to fly your fish. Company A charges by the pound and will fly your fish to any destination in the world for r dollars per pound. Company B charges a flat rate, if you sign a contract for 4 days. For c dollars, Company B will fly all of your tuna fish anywhere for 4 days. You radio the captains of your fleet and arrange to have one ship arrive each day over the next n days. You also find out from the captains the size of their catch. Thus, you know ahead of time that you will need tofly z1,2, , zn pounds of tuna over the next n days. Your problen is to determine which air freight company to use over these n days to minimize your costs. Erample: Suppose n-10, -5, c 20,000 and the trawlers will bring in 1100, 900, 900, 1200, 1200, 1200, 1200, 900, 900, 1100 pounds of tuna. Then the optimal solution is to use Company A for the first 3 days, Company B for the next 4 days and Company A for the last 3 days. The total cost is 1100.5+900 5+900 5+20000 + 900 . 5 + 900-5+1100-5=49000. Questions: a. Define a function MINCOST, that can be used to solve this dynamic programming problem To do this, you must describe the input parameters to MINCoST and its "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 MINCOST 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 MINCOST 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. State and briefly justify the running time of your dynamic programming algorithm