Additional Homework 7 ProblemCompSci 161—Fall, 2022—Dillencourt1. Your friend owns a business with a client base in two different cities, Detroit andSeattle. In any given month, the business can be operated out of either city. Basedon projections of rental costs and storage costs for the necessary equipment, yourfriend has estimate the cost for a given month operating out of either city for thenext n months: if th e business operates out of Detroit in month i the cost for themonth will be Di, and if the business operates out of Seattle in month i it will be Si.If the bu siness operates out of on e city in month i and out of th e other one in monthi + 1, there is an additional cost of T for the transition.For a given sequence of n months, a schedule is a sequence of n locations, where eachentry in the sequence is either Detroit or Seattle and the ith entry in the sequence isthe operating location for the ith month.Give a dynamic programming algorithm that takes as input the transition cost T andthe values Di, . . . , Dnand S1, . . . , Sn, and produces a schedule that minimizes thetotal cost.As an example, suppose n = 5 and T = 10 with the following profit estimates:City month 1 month 2 month 3 month 4 month 5Detroit 5 7 30 30 15Seattle 30 40 4 6 20The optimum schedule would be [Detroit,Detroit,Seattle,Seattle,Seattle]with a total profit of 5 + 7 + 4 + 4 + 20 + 10 = 50In your solution provide the following:(a) The specification of the solution for computing the cost of the optimum schedule,as prescribed on slide 6-15: subproblem d omain, function/memoization tabledefinition, goal, initial condition(s), and recurr ence equation.(b) A verbal (English) description of additional information that can be u sed toderive the optimal schedule (analogous to the keep array in the weighted intervalscheduling problem and the truck-loading and knapsack problems).(c) Pseudocode to compu te the memoization table and the additional information.(d) Pseudocode to compute the optimal schedule from the memoization table andthe additional inf ormation.12. Suppose you are a consultant for a company that manufactures computing equipmentand s hips it to distributors. For each of the next n weeks, they have a projected supplyof equipment, measured by weight, which has to be shipped via air fr eight. The weightof the equipment to be shipped in week i is wi(for i = 1, . . . , n). Each week’s supplycan be carried by one of two air freight shippers, A or B. The two companies calculatetheir shipping charges as follows:• Shipper A charges by weight, at a fixed cost per unit of weight. In other words,there is some parameter d such that it costs d · wito ship the equipment for weeki u sing Shipper A.• Shipper B will contract to ship an unlimited amount of equipment at a fixed costof F per week, independent of the weight. However, there is a catch: contractswith shipper B must be made for four weeks at a time.For a given sequence of n weeks, a schedule is a choice of shipper (A or B) for eachweeks, with the restriction that company B must be chosen for blocks of 4 contiguousweeks at a time. T he cost of the schedule is the total amount paid to company A andB according to the description above.Give a dynamic programming algorithm that takes as input the values of d and Fand the sequence of weights w1, . . . , wn, and produces a s chedule that minimizes th ecost.As an example, suppose d = 1, F = 10, n = 10, and the sequence of weights is11, 9, 9, 12, 12, 12, 12, 9, 9, 11The optimal schedule would be to choose A for three weeks, then B for a block of fourconsecutive weeks, and then A for the final three weeks. The cost of this schedulewould be11 + 9 + 9 + 4 · 10 + 9 + 9 + 11.You can make the following simplifying assumption: for every i, wi≤4F3d. Thisassumption implies, for example, that it would never be better to hir e shipper B justfor the first three weeks and pay for four weeks, and then shift over to shipper A inweek 4.In your solution, provide the same information you were asked to provide in yoursolution to the previous