You made it to your destination and it’s time to take in the sights! You’ve got

Question

You made it to your destination and it’s time to take in the sights! You’ve got a list of museums,
monuments, and marble sundry that you want to see. You decided that you don’t want to deal with the
hassle of a rental car, trusting instead to taxis and limos. Taxis charge a fixed rate per distance, while
limos will take you to your next 5 stops for a fixed cost, regardless of distance (but you must use the
limo for all 5 stops). Now you need to decide when you want to use a taxi, and when to use a limo.
Given a list, L, of the travel distances between your successive destinations, the taxi rate per mile, r,
and the cost of renting a limo, b, a schedule assigns either taxi or limo to each distance on the list,
with the restriction that limo assignments must be in contiguous blocks of 5. The cost of a schedule
is simply the number of limo rentals multiplied by b, plus the total distance travelled by taxi multiplied by r. Given L, r, and
b, give a polynomial-time algorithm that returns a schedule of minimum cost (note: for this question
you should show how to return the optimal sequence, not just its cost!)

1. Write a mathematically correct recursive property of the OPT value that you are trying to compute.
2. Explain carefully why the recursion holds. If you do this well, what you write will read as self-evident.
3. Explain carefully the data structure you will use to store the OPT value for the different subproblems and the
order in which you will fill out the entries in your data structure, per the enablement of the recursive property.
4. Where needed, state the additional information you can record which, along with a proper “backtracing”
method, will allow you to report an optimal solution, as opposed to just the value of OPT.
5. Bound the total time of your algorithm by bounding the size of the data structure and the work per entry in it.

Explanation / Answer

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.