You are driving a school bus full of rowdy students along a straight road. You would like to drop the students off quickly in order to preserve your sanity. The road has bus stops every mile, and you know how many students will get off at each stop. You can assume that your bus travels at a constant speed of 60 miles per hour, and can stop, drop-off students, and turn around instantaneously. You must drive on the road, but you can visit stops in whatever order you wish. Your job is to figure out a drop-off route to minimize the total number of minutes spent by students on the bus. So if you take 20 minutes to drop-off the first 5 students, and then another 10 minutes to drop off the next 10 students, the total number of minutes would be: 20min * 5 students + 30min 10 students = 100+ 300 = 400 student-minutes So your goal is not necessarily to end your route as soon as possible - you would much rather spend a long time on the bus with 1 student than a slightly shorter time on the bus with 100 students. Your task for this problem is to describe an efficient algorithm that returns the total student- minutes for your best possible route. You can assume you have two inputs, C[1..n], where C[i] is the number of students that want to get off at the bus-stop at mile i, and s, the starting location of your bus stop. You may use two pages for your solution to this problem, though it isn't necessary. a. Describe a recursive backtracking algorithm for computing the minimum total student- minutes for your best possible route, given C[1..n] and s as defined above. This algorithm should take the form of a recursive formula with all base cases, parameters, functions, etc clearly defined. As with all backtracking algorithms, you should start by thinking about what information you need to uniquely define a subproblem, and how to calculate the result for a subproblem in terms of what decisions can be made and simpler versions of the same subproblem. Hint: anytime you pass by a bus stop, it always makes sense to drop off students there. So, you should be able to uniquely identify a subproblem by tracking the furthest point(s) where you've dropped off students, as well as where on that frontier you are currently located. b. Describe an efficient (polynomial time, not exponential) iterative dynamic programming algorithm for this problem, based on your backtracking algorithm above. Your description should include at least: the base case(s) and your choice of data structure, how to determine the return value, pseudocode illustrating your algorithm, and analysis of its space and time complexity.